Analyse de la convergence de la méthode de Newton
1. Cas de non-convergence
Il est important de noter que la méthode de Newton ne converge pas toujours. Un exemple de divergence est illustré dans la figure ci-dessous (non incluse ici). On y considère la fonction :
\[ f(x) = \arctan(x) \]
On montre ce qui se passe si l'on part d’un point particulier \( x_0 = 1.3917 \), qui est un point fixe pour deux itérations de la méthode de Newton. Dans ce cas, au lieu de converger, les itérations peuvent osciller ou diverger.
2. Analyse de l'erreur
Soit \( r \) une racine simple de \( f(x) \), c’est-à-dire telle que \( f(r) = 0 \) et \( f'(r) \neq 0 \). On note l’erreur à la \( n \)-ième itération par :
\[ e_n = x_n - r \]
Si la méthode de Newton converge, alors elle converge quadratiquement, c’est-à-dire que :
\[ e_{n+1} \approx C e_n^2 \]
Pour voir cela, on réécrit :
\[ e_{n+1} = x_{n+1} - r = x_n - \frac{f(x_n)}{f'(x_n)} - r = e_n - \frac{f(x_n)}{f'(x_n)} \]
En développant \( f \) autour de \( r \) (en considérant \( x_n = r + e_n \)), on a :
\[ f(x_n) = f(r + e_n) = f(r) + e_n f'(r) + \frac{1}{2} e_n^2 f''(\xi_n) \quad \text{avec } \xi_n \in [r, x_n] \]
Or \( f(r) = 0 \), donc :
\[ f(x_n) = e_n f'(r) + \frac{1}{2} e_n^2 f''(\xi_n) \]
De même :
\[ f'(x_n) = f'(r) + e_n f''(\eta_n) \quad \text{avec } \eta_n \in [r, x_n] \]
On en déduit :
\[ e_{n+1} = e_n - \frac{f(x_n)}{f'(x_n)} \approx e_n - \frac{e_n f'(r) + \frac{1}{2} e_n^2 f''(\xi_n)}{f'(r)} \]
En négligeant les termes d’ordre supérieur dans le dénominateur, on obtient :
\[ e_{n+1} \approx \frac{1}{2} \cdot \frac{f''(\xi_n)}{f'(r)} \cdot e_n^2 \]
Autrement dit :
\[ e_{n+1} \approx C e_n^2 \quad \text{avec } C = \frac{1}{2} \cdot \frac{f''(r)}{f'(r)} \]
Cela confirme que la méthode de Newton possède une convergence quadratique lorsque \( f \) est suffisamment régulière (au moins \( C^2 \)) et \( f'(r) \neq 0 \).
3. Théorème de convergence locale
On peut formuler un théorème assurant la convergence sous certaines hypothèses :
Théorème
Soit \( f \in C^2([a, b]) \), telle que :
- 1) \( f(a)f(b) < 0 \) (changement de signe sur \([a, b]\))
- 2) \( f'(x) \neq 0 \) pour tout \( x \in [a, b] \) (fonction strictement monotone)
- 3) \( f''(x) \) ne change pas de signe sur \([a, b]\) (fonction convexe ou concave)
Alors :
- a) \( f \) admet une unique racine \( r \in [a, b] \).
- b) Pour tout \( x_0 \in [a, b] \) tel que \( f(x_0)f''(x_0) > 0 \), la méthode de Newton converge vers \( r \).
- c) La convergence est quadratique, avec :
\[ \lim_{n \to \infty} \frac{e_{n+1}}{e_n^2} = \frac{1}{2} \cdot \frac{f''(r)}{f'(r)} \]
Ce théorème garantit donc la convergence rapide de la méthode, pourvu que les conditions soient remplies et que le point de départ soit bien choisi.