Méthode de Newton

analysis

On démontre ici la méthode de Newton qui permet de trouver numériquement une approximation précise d’un zéro d’une fonction réelle d’une variable réelle.

[ROU]
p. 152

Théorème 1 (Méthode de Newton). Soit $f : [c, d] \to R$ une fonction de classe $C^{2}$ strictement croissante sur $[c, d]$ . On considère la fonction $φ : [c, d] x \to \mapsto R x - \frac{f ( x )}{f ^{'} ( x )}$ (qui est bien définie car $f^{'} > 0$ ). Alors :

$\exists! a \in [c, d]$ tel que $f (a) = 0$ .
$\exists α > 0$ tel que $I = [a - α, a + α]$ est stable par $φ$ .
La suite $(x_{n})$ des itérés (définie par récurrence par $x_{n + 1} = φ (x_{n})$ pour tout $n \geq 0$ ) converge quadratiquement vers $a$ pour tout $x_{0} \in I$ .

Démonstration. Soit $x \in [c, d]$ . Comme $f (a) = 0$ , on peut écrire : $φ (x) - a = x - a - \frac{f ( x ) - f ( a )}{f ^{'} ( x )} = \frac{f ( a ) - f ( x ) - ( a - x ) f ^{'} ( x )}{f ^{'} ( x )}$ Or, la formule de Taylor-Lagrange à l’ordre $2$ donne l’existence d’un $z \in] a, x [$ tel que $⟺ f (a) = f (x) + f^{'} (x) (a - x) + \frac{1}{2} f^{''} (z) (a - x)^{2} f (a) - f (x) - f^{'} (x) (a - x) = \frac{1}{2} f^{''} (z) (a - x)^{2}$ D’où : $φ (x) - a = \frac{f ^{''} ( z )}{2 f ^{'} ( x )} (x - a)^{2} (*)$ Soit $C = \frac{m a x _{x \in [c, d]} ∣ f ^{''} ( x ) ∣}{2 m i n _{x \in [c, d]} ∣ f ^{'} ( x ) ∣}$ . Par $(*)$ , on a : $\forall x \in [c, d], ∣ φ (x) - a ∣ \leq C ∣ x - a ∣^{2}$ Soit maintenant $α > 0$ suffisamment petit pour que $C α < 1$ et que $I = [a - α, a + α] \subseteq [c, d]$ . Alors : $x \in I ⟹ ∣ φ (x) - a ∣ \leq C α^{2} < α$ (la première inégalité se voit en faisant un dessin, et la seconde vient du fait que $C α < 1$ ). D’où $φ (I) \subseteq I$ . Et si $x_{0} \in I$ , on a donc $\forall n \in N$ , $x_{n} \in I$ et $∣ x_{n + 1} - a ∣ = ∣ φ (x_{n}) - a ∣ \leq C ∣ x_{n} - a ∣^{2}$ D’où $C ∣ x_{n} - a ∣ \leq (C ∣ x_{0} - a ∣)^{2^{n}} \leq (C α)^{2^{n}}$ où $C α < 1$ . On a donc bien convergence quadratique de la suite $(x_{n})$ vers le réel $a$ . ◻

[DEM]
p. 100

Remarque 2. On suppose que l’on connaisse une approximation grossière du point que l’on nomme $x_{0}$ .

$tikzpicture-1$

L’idée de la méthode est de remplacer la courbe représentative de $f$ par sa tangente au point $x_{0}$ : $y = f^{'} (x_{0}) (x - x_{0}) + f (x_{0})$ L’abscisse $x_{1}$ du point d’intersection de cette tangente avec l’axe des abscisses est donnée par $x_{1} = x_{0} - \frac{f ( x _{0} )}{f ^{'} ( x _{0} )}$ d’où le fait d’itérer la fonction $φ : x \mapsto x - \frac{f ( x )}{f ^{'} ( x )}$ .

[ROU]
p. 152

Corollaire 3. En reprenant les hypothèses et notations du théorème précédent, et en supposant de plus $f$ strictement convexe sur $[c, d]$ , le résultat du théorème est vrai sur $I = [a, d]$ . De plus :

$(x_{n})$ est strictement décroissante (ou constante).
$x_{n + 1} - a \sim \frac{f ^{''} ( a )}{2 f ^{'} ( a )} (x_{n} - a)^{2}$ pour $x_{0} > a$ .

Démonstration. La dérivée $f^{'}$ est strictement croissante (car $f$ est strictement convexe) sur $] c, d [$ . Ainsi, soit $x \in [a, d]$ . Si $x = a$ , on a $φ (x) = x$ , et la suite $(x_{n})$ est alors constante. Supposons maintenant $x > a$ . On a : $φ (x) = x - \frac{f ( x ) > 0}{> 0 f ^{'} ( x )} < x$ Et par $(*)$ (de la démonstration précédente), $\exists z \in] a, x [$ : $φ (x) - a = \frac{f ^{''} ( z )}{2 f ^{'} ( z )} (x - a)^{2} > 0 ⟺ φ (x) < a$ Ainsi, $I = [a, d]$ est stable par $φ$ et pour $x_{0} \in] a, d]$ , on a $x_{n} \in] a, d]$ pour tout $n \in N$ et la suite $(x_{n})$ est strictement décroissante. La suite $(x_{n})$ admet donc une limite $ℓ$ vérifiant $φ (ℓ) = ℓ ⟺ f (ℓ) = 0$ ie. $ℓ = a$ par unicité. Comme dans le théorème précédent, la convergence est quadratique : $0 \leq x_{n + 1} - a \leq C (x_{n} - a)^{2}$ Enfin, si $x_{0} \in] a, d]$ , on a comme dans $(*)$ : $\forall n \in N, x_{n} > a et \frac{x _{n + 1} - a}{( x _{n} - a ) ^{2}} = \frac{f ^{''} ( z _{n} )}{2 f ^{'} ( x _{n} )}$ où $z_{n} \in] a, x_{n} [$ (d’après la démarche effectuée pour obtenir $(*)$ ). On fait tendre $n$ vers l’infini et la fraction de droite tend vers $\frac{f ^{''} ( a )}{2 f ^{'} ( a )}$ ; d’où le résultat. ◻

Remarque 4. L’ajout de l’hypothèse de convexité à la méthode de Newton, nous permet de nous affranchir de l’intervalle $I$ tout en gardant la même vitesse de convergence.