Nombre d'itérations pour trouver la racine de $x^3+2x-54$ en utilisant la méthode de Newton

Nov 23 2020

On me demande de calculer le nombre minimum (théorique) d'itérations nécessaires pour trouver la racine $\alpha$ de $x^3+2x-54$ en utilisant la méthode de Newton, garantissant une erreur absolue inférieure à $10^{-8}$, et à partir d'un intervalle $I$ et $x_0$ de mon élection.

J'ai fouillé la racine dans $I=[3,4]$, avec $x_0=3.5$(qui en fait est très proche de la racine). J'ai essayé de trouver le nombre d'itérations de deux manières:

1ère option. Ici, nous devons connaître la valeur de$\alpha$. Comme l'analyse demandée est théorique, je pense que ce n'est pas un péché. En utilisant Wolfram,$\alpha\approx3.60$. En cherchant sur Wikipedia, j'ai trouvé que$|e_{n+1}|\leq M|e_n|^2$, où $M=\sup_{x\in I}\frac{1}{2}|\frac{f''(x)}{f'(x)}|$ et $|e_k|=|x_k-\alpha|$.

Dans ce cas, $M=\frac{1}{2}|\frac{6\cdot3}{3\cdot3^2+2}|=0.310$

$$|e_n|\leq M^{\sum_{i=0}^{n-1}2^i}|e_o|^{2^n}=0.31^{2^n-1}|3.5-\alpha|^{2^n}\approx0.31^{2^n-1}\cdot0.1^{2^n}$$

Si nous voulons $|e_n|<10^{-8}$, puis $$(0.31\cdot0.1)^{2^n}<10^{-8}\cdot0.31\to2^n>\frac{\log(10^{-8}\cdot0.31)}{\log(0.031)}\to n>\frac{\log(\frac{\log(10^{-8}\cdot0.31)}{\log(0.031)})}{\log(2)}\approx2.5$$

Nous aurions donc besoin d'un minimum de $3$ itérations.

2ème option. En utilisant la méthode illustrée ici .$N(x)=x-\frac{f(x)}{f'(x)}\implies f(N(x))=\frac12f''(\tilde x)\frac{f(x)^2}{f'(x)^2}$

Comme $\max_{x\in I}|f''(x)|=24$, $\min_{x\in I}|f'(x)|=29$, puis $$|f(N(x))|\leq\frac{12}{29^2}|f(x)|^2\to|f(x_n)|\leq(\frac{12}{29^2})^{\sum_{i=0}^{n-1}2^i}|f(x_0)|^{2^n}$$

$|f(x_0)|=|f(3.5)|\approx3.70$, et comme $|x-\alpha|\leq0.31|f(x)|$, et nous voulons $|x_n-\alpha|<10^{-8}$:

$$0.31(\frac{12}{29^2})^{2^n-1}\cdot3.7^{2^n}<10^{-8}\to(\frac{12\cdot3.7}{29^2})^{2^n}<\frac{10^{-8}\cdot12}{0.31\cdot29^2}\to0.0528^{2^n}<0.046\cdot10^{-8}\to$$ $$\to n>\frac{\log(\frac{\log(0.046\cdot10^{-8})}{\log(0.0528)})}{\log(2)}\approx2.87$$

Nous aurions donc besoin d'un minimum de $3$ itérations.

Si ma procédure n'est pas erronée, les deux méthodes donnent le même nombre d'itérations (une fois arrondies). Le premier est plus serré, probablement en raison du fait que nous utilisons la valeur de$\alpha$. Ai-je raison? D'un point de vue théorique, vaut-il mieux utiliser la première ou la deuxième approche?

Réponses

1 LutzLehmann Nov 25 2020 at 20:58

La stratégie de Rheinboldt-Ortega pour la preuve du théorème de Newton-Kantorovich vous indique que la convergence de la méthode de Newton pour $f(x)=0$ est majorée par la convergence de la méthode de Newton pour le polynôme quadratique $$0=p(t)=\frac{L}2t^2-|f'(x_0)|t+|f(x_0)|=\frac{L}2(t-t^*)(t-t^{**}),$$ à partir de $t_0=0$ vers sa petite racine $t^*$. $L$ est une borne sur la deuxième dérivée pour un voisinage assez grand autour de $x_0$, $|f'(x_0)|$ est remplacé par $\|f'(x_0)^{-1}\|^{-1}$pour les systèmes et leur matrice Jacobi. Cela signifie avant tout que pour les itérations on obtient la relation$$ |x_{k+1}-x_k|\le t_{k+1}-t_k $$

Ici vous obtenez $L=24$, $f(x_0)=-4.125$, $f'(3.5)=38.75$, pour que les racines soient $t^{**}=3.11895341$, $t^{*}=0.11021325$. Pour la convergence des$t_k$ séquence on obtient la belle relation $$ \theta_{k+1}=\frac{t_{k+1}-t^*}{t_{k+1}-t^{**}} =\frac{p'(t_k)(t_k-t^*)-p(t_k)}{p'(t_k)(t_k-t^{**})-p(t_k)} =\frac{t_k-t^*}{t_k-t^{**}}\frac{2t_k-(t^*+t^{**})-(t_k-t^{**})}{2t_k-(t^*+t^{**})-(t_k-t^{*})}=\theta_k^2 $$ pour que $$ t_k=\frac{t^*-θ_0^{2^k}t^{**}}{1-θ_0^{2^k}},~~θ_0=\frac{t^*}{t^{**}}, ~~t^*-t_k=\frac{θ_0^{2^k}(t^{**}-t^*)}{1-θ_0^{2^k}} $$ Obtenir $|x_k-x^*|\le t^*-t_k\le 10^{-8}$ il faudrait environ $$ 2^k\ge \frac{\ln(10^{-8})-\ln(t^{**}-t^*)}{\ln(θ_0)}=5.840012=2^{2.55} $$ qui donne à nouveau $k=3$ comme réponse.