La recherche des zéros d’une fonction \( f(x) = 0 \) est un problème fondamental en analyse. Si la méthode de dichotomie (basée sur le théorème des valeurs intermédiaires) garantit la convergence par un simple encadrement, la méthode de Newton-Raphson permet d’obtenir de manière plus rapide une approximation satisfaisante des zéros de la fonction que l’on cherche à étudier.
Analyse géométrique : de la courbe à la droite
L’idée de base de Newton est l’approximation affine locale. Puisqu’il est difficile de résoudre \( f(x) = 0 \) pour une fonction non linéaire, on remplace \( f \) par sa tangente au point courant \( x_n \).
L’intérêt de la tangente est double :
1. Elle touche la courbe au voisinage de \( x_n \), ce qui signifie que son zéro devrait être proche de celui de \( f \).
2. C’est une droite, donc son intersection avec l’axe des abscisses est triviale à calculer.
L’équation de la tangente en \( (x_n, f(x_n)) \) est d’ailleurs bien connue, il s’agit de \( y = f'(x_n)(x – x_n) + f(x_n) \).
En posant \( y = 0 \), on cherche l’abscisse \( x_{n+1} \) d’intersection :
\[ 0 = f'(x_n)(x_{n+1} – x_n) + f(x_n) \Rightarrow x_{n+1} = x_n – \frac{f(x_n)}{f'(x_n)} \]
Preuve de la convergence locale et ordre 2
Dans ce qui suit, nous allons prouver qu’un tel algorithme permet effectivement d’approximer les zéros de \(f\) et avec une vitesse de convergence quadratique (rapide). Cette preuve est surtout utile si tu t’intéresses aux sujets de Parisiennes où de tels raisonnements peuvent être utiles.
Considérons une fonction \( f \) de classe \( \mathcal{C}^2 \) possédant une racine \( \ell \) telle que \( f(\ell) = 0 \) et \( f'(\ell) \neq 0 \). On définit la fonction \( g(x) = x – \frac{f(x)}{f'(x)} \).
Existence d’un intervalle de convergence
On calcule la dérivée de \( g \) :
\[ g'(x) = 1 – \frac{(f'(x))^2 – f(x)f”(x)}{(f'(x))^2} = \frac{f(x)f”(x)}{(f'(x))^2} \]
Au point fixe \( \ell \), on a \( f(\ell) = 0 \), d’où \( g'(\ell) = 0 \).
Par continuité de \( g’ \), il existe un voisinage \( I = [\ell-\alpha, \ell+\alpha] \) tel que pour tout \( x \in I \), \( |g'(x)| \leq k < 1 \). D’après le théorème du point fixe, la suite \( x_{n+1} = g(x_n) \) converge vers \( \ell \) pour tout \( x_0 \in I \).
Preuve de la convergence quadratique
Effectuons un développement de Taylor-Young de \( g \) en \( \ell \) à l’ordre 2 :
\[ g(x_n) = g(\ell) + (x_n-\ell)g'(\ell) + \frac{(x_n-\ell)^2}{2}g”(\ell) + o((x_n-\ell)^2) \]
Puisque \( g(\ell) = \ell \) et \( g'(\ell) = 0 \), il reste :
\[ x_{n+1} – \ell \approx \frac{g”(\ell)}{2} (x_n – \ell)^2 \]
En passant à la valeur absolue, on voit que l’erreur \( \epsilon_{n+1} \) est proportionnelle au carré de l’erreur \( \epsilon_n \). C’est la présence de cette puissance qui double le nombre de décimales exactes à chaque étape et permet donc une convergence rapide (dite « quadratique ») vers la valeur \(l\) que l’on cherche à approximer.
Théorème de convergence globale
En pratique, on ne connaît pas toujours un voisinage de \( \ell \). On utilise alors les conditions de Fourier pour garantir la convergence sans tâtonnement.
Théorème : Soit \( f : [a,b] \to \mathbb{R} \) de classe \( \mathcal{C}^2 \).
On suppose :
- \( f(a) \cdot f(b) < 0 \) (existence d’une racine par théorème des valeurs intermédiaires).
- \( f’ \) ne s’annule pas sur \( [a,b] \) (monotonie et unicité de la racine).
- \( f” \) ne s’annule pas sur \( [a,b] \) (convexité ou concavité constante).
Alors, en choisissant \( x_0 \in \{a,b\} \) tel que \( f(x_0) \cdot f”(x_0) > 0 \), la suite de Newton est monotone et converge vers la racine \( \ell \).
L’idée de la condition \( f(x_0) \cdot f”(x_0) > 0 \) est de s’assurer que l’on part du côté où la courbe « tourne le dos » à l’axe. Ainsi, la tangente ne peut jamais nous projeter en dehors de l’intervalle \( [a,b] \).
Implémentation et comparaison
Le script suivant permet d’observer la vitesse de convergence en calculant \( \sqrt{2} \) (racine de \( f(x) = x^2 – 2 \)).
Dans cette fonction, on prend en compte la valeur de notre\(x_0\) (le fameux \( x_0 \in \{a,b\} \) tel que \( f(x_0) \cdot f”(x_0) > 0 \)) ainsi que le nombre d’itérations, c’est à dire de calcul de \(x_{n+1}\). On calcule alors la valeur de \(x_{n+1}\) en fonction de \(x_n\) d’après la formule vue en partie I.
Pour une précision de \( 10^{-15} \), la méthode de dichotomie nécessite environ 50 itérations (puisque \( 2^{-50} \approx 10^{-15} \)). La méthode de Newton, grâce à sa convergence quadratique, atteint ce résultat en seulement 5 ou 6 itérations si \( x_0 \) est raisonnable.
Pour visualiser la vitesse de convergence, il peut être utile de vouloir afficher un graphique montrant la valeur approchée en fonction du nombre d’itérations de la méthode de Newton.
Voici une proposition de script qui permet d’afficher cela pour une approximer le zéro de la fonction \(f(x) = e^x -2\), c’est-à-dire approximer \(ln(2)\).
Explication du code
De la ligne 4 à 10, on crée un vecteur qui contient les différentes approximations progressives du zéro de notre fonction. Grâce à la méthode de Newton, on sait que ces valeurs tendent, lorsque \(n\) grandit, vers \(ln(2)\).
De la ligne 12 à 24, on créé la fonction dont le but est d’afficher le graphique où l’abscisse comprend le nombre d’itérations et l’ordonnée comprend les valeurs de \(x_n\). Je te laisse pour cela te reporter à ton cours sur la création des graphiques en Python. La création de la ligne discontinue qui affiche une ligne d’équation \(y = ln(2)\) est hors programme. De plus, le code est plus simple que l’on croit, puisque les lignes 19 à 23 sont des formalités graphiques ayant un intérêt réduit.
On obtient alors le graph suivant :
Tu observes aisément que l’approximation donnée par la méthode converge très rapidement vers la valeur de \(ln(2) \approx 0,693\). C’est là tout l’intérêt de cette méthode !
Conclusion
La méthode de Newton est donc une méthode très rapide pour approximer les zéros d’une fonction. Attention toutefois à vérifier une condition fondamentale, que \(f'(x_n)\) n’est pas nul. Cette condition remplie, on peut alors réaliser de très belles approximations dont la convergence est rapide, comme le prouve le graph ci-dessus. Il n’y a désormais plus qu’à croiser les doigts pour qu’une telle notion tombe aux concours !
Tu peux retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder ici à toutes nos autres ressources mathématiques !
