Méthode de dichotomie

Soit $f : [a, b] \to \mathbb{R}$ une fonction continue sur $[a, b]$.

Condition de signe opposé : Si $f(a) \cdot f(b) < 0$, alors par le théorème des valeurs intermédiaires (TVI), il existe au moins un $c \in ]a, b[$ tel que $f(c) = 0$.

Algorithme de dichotomie :

1. Poser $a_0 = a$, $b_0 = b$
2. Calculer le milieu $m_n = \dfrac{a_n + b_n}{2}$
3. Si $f(a_n) \cdot f(m_n) < 0$ : la racine est dans $[a_n, m_n]$, poser $b_{n+1} = m_n$, $a_{n+1} = a_n$
4. Sinon : la racine est dans $[m_n, b_n]$, poser $a_{n+1} = m_n$, $b_{n+1} = b_n$
5. Répéter jusqu'à ce que $b_n - a_n < \varepsilon$ (tolérance voulue)

Encadrement de l'erreur : Après $n$ itérations, l'erreur est majorée par : $|x^* - m_n| \leq \frac{b - a}{2^{n+1}}$

Nombre d'itérations nécessaires pour atteindre une précision $\varepsilon$ : $n \geq \left\lceil \log_2\!\left(\frac{b-a}{\varepsilon}\right) \right\rceil - 1$

Vitesse de convergence : La dichotomie converge toujours sous les hypothèses du TVI, mais sa convergence est linéaire : l'erreur est divisée par 2 à chaque étape.

$e_{n+1} \approx \frac{1}{2} \cdot e_n$

Pour atteindre $p$ décimales correctes, il faut environ $3{,}32 \cdot p$ itérations (car $\log_2(10^p) \approx 3{,}32p$).

Méthode de Newton-Raphson : Convergence quadratique — beaucoup plus rapide.

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

L'erreur vérifie $e_{n+1} \approx C \cdot e_n^2$ : le nombre de décimales correctes double à chaque étape.

Tableau comparatif :

| Méthode | Convergence | Robustesse | Nécessite | |---|---|---|---| | Dichotomie | Linéaire ($\times 1/2$ par étape) | Très robuste | $f$ continue, signes opposés | | Newton-Raphson | Quadratique | Fragile (dépend de $x_0$) | $f$ et $f'$, bon $x_0$ | | Sécante | Super-linéaire | Intermédiaire | Deux points initiaux |

Stratégie pratique : Utiliser la dichotomie pour localiser la racine (quelques itérations), puis Newton-Raphson pour affiner rapidement.

En pratique, on utilise plusieurs critères d'arrêt possibles :

1. Critère sur l'intervalle : $|b_n - a_n| < \varepsilon$ — la longueur de l'intervalle est petite
2. Critère sur la valeur de f : $|f(m_n)| < \delta$ — le milieu est presque une racine
3. Critère mixte : les deux conditions simultanément

Le critère sur l'intervalle est le plus fiable car il garantit directement la précision sur $x^*$. Le critère sur $f$ peut être trompeur si $f$ est très plate autour de la racine (petite pente, grand déplacement en $x$).

Itération de Newton-Raphson : $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

Interprétation géométrique : À chaque étape, on remplace $f$ par sa tangente en $x_n$ et on prend le zéro de cette tangente comme nouvelle approximation.

Convergence quadratique : Près d'une racine simple $x^*$ (où $f'(x^*) \neq 0$), l'erreur $e_n = |x_n - x^*|$ satisfait : $e_{n+1} \approx \frac{|f''(x^*)|}{2|f'(x^*)|} \cdot e_n^2$

Le nombre de décimales correctes double à chaque itération. 3 itérations suffisent là où la dichotomie en demande 20.

Conditions : Newton converge si $x_0$ est suffisamment proche de $x^*$ et $f'(x_0) \neq 0$. La méthode peut diverger si $f'(x_n) \approx 0$ (tangente presque horizontale) ou si $x_0$ est mal choisi.

En pratique, on combine plusieurs critères d'arrêt :

1. Critère sur le pas : $|x_{n+1} - x_n| < \varepsilon_x$ — la suite ne bouge plus significativement.
2. Critère sur la valeur : $|f(x_n)| < \varepsilon_f$ — le point est presque une racine.
3. Nombre maximal d'itérations : éviter les boucles infinies en cas de non-convergence.
4. Critère mixte : conditions 1 ET 2 simultanément (plus robuste).

Piège du critère sur $f$ seul : si $f$ est très plate (pente faible), $|f(x_n)|$ peut être petit sans que $x_n$ soit proche de $x^*$. Le critère sur le pas est plus fiable géométriquement.

Résumé comparatif :

| Méthode | Convergence | Robustesse | Prérequis | |---|---|---|---| | Dichotomie | Linéaire ($\div 2$) | Très robuste | $f$ continue, $f(a)f(b)<0$ | | Newton | Quadratique | Fragile près de $f'=0$ | $f$ dérivable, bon $x_0$ |