diff --git a/1.1 Dichotomie.ipynb b/1.1 Dichotomie.ipynb index 6a31074..bb560f5 100644 --- a/1.1 Dichotomie.ipynb +++ b/1.1 Dichotomie.ipynb @@ -1,239 +1,272 @@ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Equations non-linéaires\n", "\n", "**Objectif :** trouver les zéros (ou racines) d'une fonction $f:[a,b] \\rightarrow \\mathbf R$ : \n", "$$\\alpha \\in [a,b] \\,:\\, f(\\alpha) = 0$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# importing libraries used in this book\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ - "# defining the fonction that we want to interpolate\n", + "# defining the fonction\n", "def f(x):\n", " return x*np.sin(x*2.*np.pi) + 0.5*x - 0.25\n", "\n", "[a,b] = [-2,2]\n", "\n", "# points used to plot the graph \n", "z = np.linspace(a, b, 100)\n", "\n", "plt.plot(z, f(z),'-')\n", "\n", "# labels, title, legend\n", "plt.xlabel('x'); plt.ylabel('$f(x)$'); #plt.title('data')\n", "plt.legend(['$f(t)$'])\n", "plt.grid(True)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Méthode de dichotomie ou bissection\n", "\n", "Si $f$ est continue et elle change de signe dans $[a,b]$, alors il existe au moins un $\\alpha$ tel que $f(\\alpha) = 0$.\n", "\n", "On peut alors définir l'algorithme suivant :\n", "\n", "$a^{(0)}=a$, $b^{(0)}=b$. Pour $k=0,1,...$\n", "\n", "1. $x^{(k)}=\\frac{a^{(k)}+b^{(k)}}{2}$\n", "2. si $f(x^{(k)})=0$, alors $x^{(k)}$ est le zéro cherché.\n", "\n", " Autrement:\n", "\n", - " 1. soit $f(x^{(k)})f(a^{(k)})= b) :\n", " print(' b must be greater than a (b > a)')\n", " return 0,0,0\n", " \n", " # what we consider as \"zero\"\n", " eps = 1e-12\n", " \n", " # evaluate f at the endpoints\n", " fa = fun(a)\n", " fb = fun(b)\n", "\n", " if abs(fa) < eps : # a is the solution\n", " zero = a\n", " esterr = fa\n", " k = 0\n", " return zero, esterr, k\n", " \n", " if abs(fb) < eps : # b is the solution\n", " zero = b\n", " esterr = fb\n", " k = 0\n", " return zero, esterr, k\n", "\n", " if fa*fb > 0 :\n", " print(' The sign of FUN at the extrema of the interval must be different')\n", " return 0,0,0\n", "\n", "\n", "\n", " # We want the final error to be smaller than tol, \n", " # i.e. k > log( (b-a)/tol ) / log(2)\n", "\n", " nmax = int(np.ceil(np.log( (b-a)/tol ) / np.log(2)))\n", "\n", " \n", " # but nmax shall be smaller the the nmaximum iterations asked by the user\n", " if ( maxIterations < nmax ) :\n", " nmax = int(round(maxIterations))\n", " print('Warning: nmax is smaller than the minimum number of iterations necessary to reach the tolerance wished');\n", "\n", " # vector of intermadiate approximations etc\n", " x = np.zeros(nmax)\n", "\n", " # initial error is the length of the interval.\n", " esterr = (b - a)\n", "\n", " # do not need to store all the a^k and b^k, so I call them with a new variable name:\n", " ak = a\n", " bk = b\n", " # the values of f at those points are fa and fk\n", "\n", " for k in range(nmax) :\n", "\n", " # approximate solution is midpoint of current interval\n", " x[k] = (ak + bk) / 2\n", " fx = fun(x[k]);\n", " # error estimator is the half of the previous error\n", " esterr = esterr / 2\n", "\n", " # (Complete the code below)\n", "\n", "\n", "\n", " zero = x[k];\n", "\n", " if esterr > tol :\n", " print('Warning: bisection stopped without converging to the desired tolerance because the maximum number of iterations was reached');\n", "\n", " return zero, esterr, k, x \n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "[a,b] = [-.5,1]\n", "tol = 1e-10\n", "maxIter = 4\n", "zero, esterr, k, x = bisection(a,b,f,tol,maxIter)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ - "from NonLinearEquationsLib import plotBisectionIterations\n", + "def plotBisectionIterations (a,b,f,x,N=200) :\n", + " # plot the graphical interpretation of the Bisection method\n", + " import matplotlib.pyplot as plt\n", + "\n", + " def putSign(y,f,text) :\n", + " if (f(y) < 0) :\n", + " plt.annotate(text, (y, 0.02*deltaAxis) )\n", + " else :\n", + " plt.annotate(text, (y, -0.05*deltaAxis) )\n", + " \n", + " \n", + " z = np.linspace(a,b,N)\n", + " plt.plot(z,f(z), 'b-')\n", + " \n", + " plt.plot([a,a], [0,f(a)], 'g:')\n", + " plt.plot([b,b], [0,f(b)], 'g:')\n", "\n", - "plt.rcParams.update({'font.size': 16})\n", - "plt.figure(figsize=(8, 5))\n", + " # For putting a sign at the initial point\n", + " deltaAxis = plt.gca().axes.get_ylim()[1] - plt.gca().axes.get_ylim()[0]\n", "\n", - "plotBisectionIterations(a,b,f,x)\n", + " putSign(a,f,\"a\")\n", + " putSign(b,f,\"b\")\n", + " \n", + " for k in range(x.size) :\n", + " plt.plot([x[k],x[k]], [0, f(x[k])], 'g:')\n", + " putSign(x[k],f,\"$x_\"+str(k)+\"$\")\n", "\n", - "# plt.savefig('Bisection-iterations.png', dpi=600)\n", + " # Plot the x,y-axis \n", + " plt.plot([a,b], [0,0], 'k-',linewidth=0.1)\n", + " plt.plot([0,0], [np.min(f(z)),np.max(f(z))], 'k-',linewidth=0.1)\n", "\n", - "print(f'The estimated root is {zero:2.12f}, the estimated error {esterr:1.3e} and the residual is {f(zero):1.3e}, after {k} iterations')" + " plt.ylabel('$f$'); plt.xlabel('$x$');\n", + "\n", + " return" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], - "source": [] + "source": [ + "plt.rcParams.update({'font.size': 16})\n", + "plt.figure(figsize=(8, 5))\n", + "\n", + "plotBisectionIterations(a,b,f,x)\n", + "\n", + "# plt.savefig('Bisection-iterations.png', dpi=600)\n", + "\n", + "print(f'The estimated root is {zero:2.12f}, the estimated error {esterr:1.3e} and the residual is {f(zero):1.3e}, after {k} iterations')" + ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.7" } }, "nbformat": 4, "nbformat_minor": 4 }