La méthode de la bissection est simple, mais ne garantit pas une réduction monotone de l’erreur d’une itération à l’autre. Pour obtenir des méthodes plus performantes, il est nécessaire de prendre davantage en compte les valeurs de la fonction $f$, voire de considérer leur évolution par l’intermédiaire de la dérivée $f^{\prime }$ (si $f$ est différentiable) ou par une approximation de cette dernière.

Développements limités et formule de Taylor

Il peut être utile de savoir approximer une fonction telle que $\sin$ ou $\cos$ par des polynômes. C’est ce qui a été fait en Analyse I au semestre d’automne en remplaçant par exemple $\sin (x)$ par sa fonction infiniment petite équivalente (IPE) $x$ au voisinage de $x=0$ : $\sin (x)\sim x$ au voisinage de $x=0$. Durant le semestre de printemps, en Analyse II, vous allez poursuivre cette approche et obtenir le résultat important suivant (voir polycopié d’Analyse II, en page 66 et suivantes) : Dans le développement ci-dessus, chaque terme fait intervenir la dérivée, à un certain ordre $k$, évaluée en $a$, de la fonction $f$ :

$$f^{(k)}(a)\equiv \frac{d^k}{d{x}^k}f(a).$$

La somme

$$\sum _{k=0}^n\frac{f^{(k)}(a)}{k!}(x-a{)}^k$$

est appelée polynôme de Taylor de la fonction $f$ à l’ordre $n$ autour de $a$. On retrouve l’IPE de $f$ en ne prenant que les premiers termes non nuls et non constants de cette somme.

Développement au premier ordre

Les méthodes de la sécante, de la corde et de Newton que nous allons discuter ci-dessous exploitent le développement limité au premier ordre de la fonction $f$. Ecrivons le polynôme de Taylor au premier ordre au voisinage d’un point $x_k$ (qui peut être la $k$ème approximation de la racine cherchée) :

$$y(x)=f(x_k)+\frac{f^{\prime }(x_k)}{1!}(x-x_k).$$

Cette fonction $y$ est la tangente à la fonction $f$ au point $x_k$. En considérant cette fonction $y$ comme une approximation de $f$, il est naturel de chercher la racine de $y$ et de la voir comme une approximation de la racine de $f$. En appelant $x_{k+1}$ cette racine de $y$, il vient

$$\begin{array}{rl}y(x_{k+1})=& f(x_k)+f^{\prime }(x_k)(x_{k+1}-x_k)\\ =& 0.\end{array}$$

Cette approche suggère la méthode itérative suivante : $\forall k\ge 0$, étant donné $x_k$, déterminer $x_{k+1}$ en résolvant l’équation

$$f(x_k)+q_k(x_{k+1}-x_k)=0\iff x_{k+1}=x_k-\frac{f(x_k)}{q_k},$$

où $q_k$ est la dérivée $f^{\prime }(x_k)$ de $f$ évaluée en $x_k$ ou une approximation de cette dernière. On est donc amené à chercher l’intersection $x_{k+1}$ entre l’axe des $x$ et la droite de pente $q_k$ passant par le point $(x_k,f(x_k))$ :

$$q_k=\text{"pente"}=\frac{\text{"deˊnivellation"}}{\text{"distance horizontale"}}=\frac{f(x_k)}{x_k-x_{k+1}}.$$

Dans ce qui suit, nous allons considérer trois choix particuliers pour la pente $q_k$.

Méthode de la sécante

Dans la méthode de la sécante, on se donne deux valeurs initiales $x_{-1}$ et $x_0$ qui peuvent, par exemple, être les bornes $a$ et $b$ de l’intervalle $[a,b]$ dans lequel on cherche une racine de $f$. On pose alors

$$q_k=\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}},\forall k\ge 0.$$

On a ainsi

$$x_{k+1}=x_k-\underset{=q_k^{-1}}{\underbrace{\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}}}f(x_k),\forall k\ge 0.$$

Premières étapes de la méthode de la sécante :

Les éléments de la suite $\{x_k\}$ produite par la méthode de la sécante peuvent sortir de l’intervalle $[a,b]$ et même diverger. Toutefois, on peut montrer le résultat de convergence local suivant :

Méthode de la corde

Dans la méthode de la corde, on se donne une valeur initiale $x_0$ et on utilise la même pente pendant tout le processus itératif en posant

$$q_k=\frac{f(b)-f(a)}{b-a}\equiv q,\forall k\ge 0.$$

On a ainsi

$$x_{k+1}=x_k-\underset{=q_k^{-1}\equiv q^{-1}}{\underbrace{\frac{b-a}{f(b)-f(a)}}}f(x_k),\forall k\ge 0.$$

Premières étapes de la méthode de la corde :

On peut montrer que la suite $\{x_k\}$ converge avec un ordre de convergence $p=1$.

Méthode de Newton

La méthode de Newton nécessite que $f\in {\mathcal{C}}^1(J)$. La fonction $f$ doit donc être une fois continûment dérivable dans $J$, $J$ étant un voisinage “suffisamment grand” contenant $\alpha$. De plus, on suppose que $f^{\prime }(\alpha )\ne 0$ (pour que la convergence soit optimale). Ces hypothèses étant vérifiées, on choisit une “bonne” première approximation $x_0$ de $\alpha$ et on pose

$$q_k=f^{\prime }(x_k),\forall k\ge 0.$$

On a ainsi

$$x_{k+1}=x_k-\underset{=q_k^{-1}}{\underbrace{\frac{1}{f^{\prime }(x_k)}}}f(x_k)=x_k-\frac{f(x_k)}{f^{\prime }(x_k)},\forall k\ge 0.$$

Premières étapes de la méthode de Newton :

Géométriquement, $x_{k+1}$ est l’abscisse du point d’intersection avec l’axe des abscisses de la tangente au graphe de $f$ passant par le point $(x_k,f(x_k))$. La méthode de Newton est d’ailleurs également appelée méthode des tangentes (ou encore méthode de Newton-Raphson).

On montrera plus bas que la suite $\{x_k\}$ converge avec un ordre de convergence $p=2$. Remarquons que l’ordre de convergence de la méthode de Newton est $p=1$ si $f^{\prime }(\alpha )=0$.