Liczba iteracji do znalezienia katalogu głównego $x^3+2x-54$ przy użyciu metody Newtona
Jestem proszony o obliczenie (teoretycznej) minimalnej liczby iteracji potrzebnych do znalezienia źródła $\alpha$ z $x^3+2x-54$ stosując metodę Newtona, gwarantując bezwzględny błąd mniejszy niż $10^{-8}$i zaczynając od interwału $I$ i $x_0$ mojego wyboru.
Przeszukałem korzeń $I=[3,4]$, z $x_0=3.5$(który w rzeczywistości jest bardzo blisko korzenia). Próbowałem znaleźć liczbę iteracji na dwa sposoby:
1 opcja. Tutaj musimy poznać wartość$\alpha$. Ponieważ wymagana analiza jest teoretyczna, myślę, że nie jest to grzech. Używając Wolfram,$\alpha\approx3.60$. Szukając w Wikipedii , znalazłem to$|e_{n+1}|\leq M|e_n|^2$, gdzie $M=\sup_{x\in I}\frac{1}{2}|\frac{f''(x)}{f'(x)}|$ i $|e_k|=|x_k-\alpha|$.
W tym przypadku, $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}$$
Jeśli chcemy $|e_n|<10^{-8}$, następnie $$(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$$
Więc potrzebowalibyśmy minimum $3$ iteracje.
2. opcja. Używając metody pokazanej tutaj .$N(x)=x-\frac{f(x)}{f'(x)}\implies f(N(x))=\frac12f''(\tilde x)\frac{f(x)^2}{f'(x)^2}$
Tak jak $\max_{x\in I}|f''(x)|=24$, $\min_{x\in I}|f'(x)|=29$, następnie $$|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$, i jako $|x-\alpha|\leq0.31|f(x)|$i chcemy $|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$$
Więc potrzebowalibyśmy minimum $3$ iteracje.
Jeśli moja procedura nie jest zła, obie metody dają taką samą liczbę iteracji (raz zostały zaokrąglone). Pierwsza jest ciaśniejsza, prawdopodobnie ze względu na to, że używamy wartości$\alpha$. Czy mam rację? Z teoretycznego punktu widzenia lepiej zastosować pierwsze czy drugie podejście?
Odpowiedzi
Strategia Rheinboldta-Ortegi do dowodu twierdzenia Newtona-Kantorowicza mówi, że zbieżność metody Newtona dla $f(x)=0$ specjalizuje się w zbieżności metody Newtona dla wielomianu kwadratowego $$0=p(t)=\frac{L}2t^2-|f'(x_0)|t+|f(x_0)|=\frac{L}2(t-t^*)(t-t^{**}),$$ zaczynać od $t_0=0$ w kierunku mniejszego korzenia $t^*$. $L$ jest ograniczeniem drugiej pochodnej dla wystarczająco dużego sąsiedztwa $x_0$, $|f'(x_0)|$ zostanie zastąpiony $\|f'(x_0)^{-1}\|^{-1}$dla systemów i ich macierzy Jacobiego. Oznacza to przede wszystkim, że dla iteracji otrzymujemy relację$$ |x_{k+1}-x_k|\le t_{k+1}-t_k $$
Tutaj masz $L=24$, $f(x_0)=-4.125$, $f'(3.5)=38.75$, tak że korzenie są $t^{**}=3.11895341$, $t^{*}=0.11021325$. Aby uzyskać konwergencję$t_k$ sekwencja pierwsza otrzymuje niezłą relację $$ \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 $$ po to aby $$ 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}} $$ Dostać $|x_k-x^*|\le t^*-t_k\le 10^{-8}$ potrzeba około $$ 2^k\ge \frac{\ln(10^{-8})-\ln(t^{**}-t^*)}{\ln(θ_0)}=5.840012=2^{2.55} $$ co znowu daje $k=3$ jako odpowiedź.