Dans de nombreux théorèmes d’analyse on trouve des résultats tels que “il existe un réel \(x\) tel que \(f(x) = 0\) ” où \(f\) est une fonction donnée.
On pourra penser au Théorème des Valeurs Intermédiaires (si \(f\) est continue), au Théorème de Rolle (ici ce sera plutôt “ \(f(x) = 0\) ” ) ou encore au théorème du point fixe (on résout ici \(g(x) = x\) ce qui équivaut à \(f(x) = g(x)−x = 0)\).
On dit que \(x\) est un zéro ou une racine de \(f\) et la question naturelle est alors “que vaut ce \(x\)?”.

Résolution approchée de $f(x) = 0$ — Résumé

I. Introduction

On cherche une valeur approchée d'un zéro $\xi$ de $f$ (i.e. $f(\xi)=0$) lorsqu'on
ne peut pas le calculer explicitement. $f$ est supposée continue sur un intervalle $I$.

II. Ordre de convergence

Soit $(x_n)_n \to \xi$ et $e_n = |x_n - \xi|$. La convergence est d'ordre $p$
s'il existe $0 < c_- \leq c_+$ tels qu'à partir d'un certain rang :
$$c_- e_n^p \leq e_{n+1} \leq c_+ e_n^p.$$
On parle de convergence linéaire si $p=1$, quadratique si $p=2$.
Une condition suffisante : $\lim\limits_{n\to\infty} \dfrac{e_{n+1}}{e_n^p} = c \neq 0$.

À chaque étape, le nombre de décimales exactes est multiplié par $p$ (si $p>1$).

III. Méthode de la dichotomie

On part d'un intervalle $[a,b]$ tel que $f(a)f(b) < 0$ (changement de signe).
À chaque étape on coupe en deux : $c = \tfrac{a+b}{2}$, puis on remplace $[a,b]$
par $[c,b]$ ou $[a,c]$ selon le signe de $f(c)$.

Les suites $(a_n)$ et $(b_n)$ sont adjacentes et convergent vers $\xi$, et $b_n - a_n
= \tfrac{b-a}{2^n}$.

Erreur : $|x_n - \xi| \leq \dfrac{b-a}{2^n}$.

Pour atteindre la précision $\epsilon$ il faut $n \geq \log_2\!\left(\dfrac{b-a}{\epsilon}\right)$
étapes. La convergence est linéaire (ordre 1).

IV. Fonctions convexes

$f: I \to \mathbb{R}$ est convexe si :
$$\forall x,y \in I,\; \forall \lambda \in [0,1],$$
$$f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y).$$
Caractérisations : $f$ convexe $\Leftrightarrow$ $f'$ croissante $\Leftrightarrow$ $f'' \geq 0$
(si $f$ est deux fois dérivable).

Inégalité des 3 pentes : $f$ convexe $\Leftrightarrow$ pour tous $x < y < z$ dans $I$ :

$\frac{f(y)-f(x)}{y-x} \leq \frac{f(z)-f(x)}{z-x} \leq \frac{f(z)-f(y)}{z-y}.$

Tangente sous le graphe : si $f$ est convexe dérivable, alors pour tout $x_0 \in I$ :
$$f(x) \geq f(x_0) + f'(x_0)(x-x_0),\, \forall x \in I.$$

V. Méthode de la sécante (fausse position)

On remplace $f$ par la fonction affine $L$ interpolant $f$ en $a$ et $b$ :
$$L(x) = f(a) + \frac{f(b)-f(a)}{b-a}(x-a),$$
$$\bar{\xi} = \frac{af(b)-bf(a)}{f(b)-f(a)}.$$
Estimation de l'erreur (avec $m = \min|f'|$, $M = \max|f''|$) :
$$|\bar{\xi} - \xi| \leq \frac{M}{2m}|\bar{\xi}-a||\bar{\xi}-b|.$$
Méthode itérative (sous hypothèses $f'>0$, $f''>0$) :
$$x_0 = a, \qquad x_{n+1} = \frac{x_n f(b) - b f(x_n)}{f(b)-f(x_n)}.$$
La suite $(x_n)$ est croissante, majorée par $\xi$, et converge vers $\xi$.
La convergence est linéaire (ordre 1) :
$$\frac{x_{n+1}-\xi}{x_n - \xi} \to c $$
$$c= \frac{f(b)-f'(\xi)(b-\xi)}{f(b)} \in\, ]0,1[.$$
Test d'arrêt : on s'arrête dès que $\dfrac{M}{2m}|x_{n+1}-x_n||x_{n+1}-b| < \epsilon$.

VI. Méthode de Newton

On utilise la tangente à $C_f$ au point courant plutôt que la corde.
La tangente en $(c, f(c))$ coupe l'axe des abscisses en :
$$x = c - \frac{f(c)}{f'(c)}.$$
Algorithme (sous hypothèses $f'>0$, $f''>0$, $f(a)f(b)$ négatif) :
$$x_0 = b, \qquad x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.$$
La suite $(x_n)$ est décroissante, minorée par $\xi$, et converge vers $\xi$.
La convergence est quadratique (ordre 2) :
$$x_{n+1} - \xi = \frac{f''(\zeta_n)}{2f'(x_n)}(x_n-\xi)^2,$$
$$\lim_{n\to+\infty}\frac{x_{n+1}-\xi}{(x_n-\xi)^2} = \frac{f''(\xi)}{2f'(\xi)} \neq 0.$$
À chaque étape le nombre de décimales exactes est doublé.

Interprétation point fixe : Newton correspond au choix $\varphi(x) = x - \dfrac{f(x)}{f'(x)}$,
qui vérifie $\varphi'(\xi) = 0$ (point fixe super-attractif), d'où la convergence quadratique.

Exemple (algorithme de Babylone) : pour $f(x) = x^2 - a$, Newton donne
$x_{n+1} = \tfrac{1}{2}\!\left(x_n + \tfrac{a}{x_n}\right)$, qui converge quadratiquement vers $\sqrt{a}$.

VII. Tableau comparatif

$$\begin{array}{|lccc|}
\hline
\text{Méthode} & \text{Hypothèses} & \text{Ordre} & \text{Formule}\\
\hline
\text{Dichotomie} & f \text{ continue} & 1 &
x_{n+1} = \tfrac{a_n+b_n}{2}\\
\hline
\text{Sécante} & f \in C^2,\; f'>0,\; f''>0 & 1 &
x_{n+1} = \tfrac{x_n f(b)-b f(x_n)}{f(b)-f(x_n)}\\
\hline
\text{Newton} & f \in C^2,\; f'>0,\; f''>0 & 2 &
x_{n+1} = x_n - \tfrac{f(x_n)}{f'(x_n)}\\
\hline
\end{array}$$

---

Pour plus de détails, consulter le PDF ci-joint.

---