I am asked to calculate the (theoretical) minimum number of iterations needed to find the root $\alpha$ of $x^3+2x-54$ using Newton's Method, guaranteeing an absolute error less than $10^{-8}$, and starting from an interval $I$ and $x_0$ of my election.
I have searched the root in $I=[3,4]$, with $x_0=3.5$ (which in fact is very close to the root). I tried to find the number of iterations by two ways:
1st option. Here we need to know the value of $\alpha$. As the requested analysis is theoretical, I think this is not a sin. Using Wolfram, $\alpha\approx3.60$. Searching in Wikipedia I found that $|e_{n+1}|\leq M|e_n|^2$, where $M=\sup_{x\in I}\frac{1}{2}|\frac{f''(x)}{f'(x)}|$ and $|e_k|=|x_k-\alpha|$.
In this case, $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}$$
If we want $|e_n|<10^{-8}$, then
$$(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$$
So we would need a minimum of $3$ iterations.
2nd option. Using the method shown here. $N(x)=x-\frac{f(x)}{f'(x)}\implies f(N(x))=\frac12f''(\tilde x)\frac{f(x)^2}{f'(x)^2}$
As $\max_{x\in I}|f''(x)|=24$, $\min_{x\in I}|f'(x)|=29$, then $$|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$, and as $|x-\alpha|\leq0.31|f(x)|$, and we want $|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$$
So we would need a minimum of $3$ iterations.
If my procedure is not wrong, both methods give the same number of iterations (once have been rounded). The first one is tighter, probably due to the fact that we use the value of $\alpha$. Am I right? From a theoretical point of view, is it better to use the first or the second approach?
Best Answer
The Rheinboldt-Ortega strategy for the proof of the Newton-Kantorovich theorem tells you that the convergence of the Newton method for $f(x)=0$ is majored by the convergence of the Newton method for the quadratic polynomial $$0=p(t)=\frac{L}2t^2-|f'(x_0)|t+|f(x_0)|=\frac{L}2(t-t^*)(t-t^{**}),$$ starting at $t_0=0$ towards its smaller root $t^*$. $L$ is a bound on the second derivative for a large enough neighborhood around $x_0$, $|f'(x_0)|$ gets replaced with $\|f'(x_0)^{-1}\|^{-1}$ for systems and their Jacobi matrix. This means foremost that for the iterates one gets the relation $$ |x_{k+1}-x_k|\le t_{k+1}-t_k $$
Here you get $L=24$, $f(x_0)=-4.125$, $f'(3.5)=38.75$, so that the roots are $t^{**}=3.11895341$, $t^{*}=0.11021325$. For the convergence of the $t_k$ sequence one gets the nice 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 $$ so that $$ 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}} $$ To get $|x_k-x^*|\le t^*-t_k\le 10^{-8}$ one would need approximately $$ 2^k\ge \frac{\ln(10^{-8})-\ln(t^{**}-t^*)}{\ln(θ_0)}=5.840012=2^{2.55} $$ which again gives $k=3$ as the answer.