Anzahl der Iterationen, um die Wurzel von zu finden $x^3+2x-54$ unter Verwendung der Newtonschen Methode
Ich werde gebeten, die (theoretische) Mindestanzahl von Iterationen zu berechnen, die zum Auffinden der Wurzel erforderlich sind $\alpha$ von $x^3+2x-54$ unter Verwendung der Newtonschen Methode, die einen absoluten Fehler von weniger als garantiert $10^{-8}$und ausgehend von einem Intervall $I$ und $x_0$ meiner Wahl.
Ich habe die Wurzel in gesucht $I=[3,4]$mit $x_0=3.5$(was in der Tat sehr nahe an der Wurzel ist). Ich habe versucht, die Anzahl der Iterationen auf zwei Arten zu ermitteln:
1. Option. Hier müssen wir den Wert von kennen$\alpha$. Da die angeforderte Analyse theoretisch ist, denke ich, dass dies keine Sünde ist. Mit Wolfram,$\alpha\approx3.60$. Bei der Suche in Wikipedia habe ich das gefunden$|e_{n+1}|\leq M|e_n|^2$, wo $M=\sup_{x\in I}\frac{1}{2}|\frac{f''(x)}{f'(x)}|$ und $|e_k|=|x_k-\alpha|$.
In diesem Fall, $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}$$
Wenn wir wollen $|e_n|<10^{-8}$, dann $$(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$$
Wir würden also ein Minimum von brauchen $3$ Iterationen.
2. Option. Mit der hier gezeigten Methode .$N(x)=x-\frac{f(x)}{f'(x)}\implies f(N(x))=\frac12f''(\tilde x)\frac{f(x)^2}{f'(x)^2}$
Wie $\max_{x\in I}|f''(x)|=24$, $\min_{x\in I}|f'(x)|=29$, dann $$|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$, und wie $|x-\alpha|\leq0.31|f(x)|$und wir wollen $|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$$
Wir würden also ein Minimum von brauchen $3$ Iterationen.
Wenn meine Prozedur nicht falsch ist, geben beide Methoden die gleiche Anzahl von Iterationen (einmal gerundet). Der erste ist enger, wahrscheinlich aufgrund der Tatsache, dass wir den Wert von verwenden$\alpha$. Habe ich recht? Ist es aus theoretischer Sicht besser, den ersten oder den zweiten Ansatz zu verwenden?
Antworten
Die Rheinboldt-Ortega-Strategie zum Beweis des Newton-Kantorovich-Theorems sagt Ihnen, dass die Konvergenz der Newton-Methode für $f(x)=0$ wird durch die Konvergenz der Newton-Methode für das quadratische Polynom bestimmt $$0=p(t)=\frac{L}2t^2-|f'(x_0)|t+|f(x_0)|=\frac{L}2(t-t^*)(t-t^{**}),$$ beginnt um $t_0=0$ in Richtung seiner kleineren Wurzel $t^*$. $L$ ist eine Grenze für die zweite Ableitung für eine ausreichend große Nachbarschaft $x_0$, $|f'(x_0)|$ wird ersetzt durch $\|f'(x_0)^{-1}\|^{-1}$für Systeme und ihre Jacobi-Matrix. Dies bedeutet in erster Linie, dass man für die Iterationen die Beziehung erhält$$ |x_{k+1}-x_k|\le t_{k+1}-t_k $$
Hier bekommen Sie $L=24$, $f(x_0)=-4.125$, $f'(3.5)=38.75$, so dass die Wurzeln sind $t^{**}=3.11895341$, $t^{*}=0.11021325$. Für die Konvergenz der$t_k$ Sequenz bekommt man die schöne Beziehung $$ \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 $$ damit $$ 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}} $$ Bekommen $|x_k-x^*|\le t^*-t_k\le 10^{-8}$ man würde ungefähr brauchen $$ 2^k\ge \frac{\ln(10^{-8})-\ln(t^{**}-t^*)}{\ln(θ_0)}=5.840012=2^{2.55} $$ was wieder gibt $k=3$ als Antwort.