Convergence of Newton Iteration

297 Views Asked by At

For $a>0$, I want to compute $\frac{1}{a}$ using Newton's iteration by finding a zero of $f(x)=a-\frac{1}{x}$. Newton's iteration formula reads $$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}=2x_k-ax_k^2$$

By the Banach Fixed Point Theorem, I can conclude that this Netwon iteration converges for starting values in the interval $I=\left(\frac{1}{2a}, \frac{3}{2a}\right)$.

Now I would like to show that we also have convergence for starting values in $\left(0,\frac{1}{a}\right]$.

To this end, it would be enough to show that at some point of the iteration, we land in the interval $I$, right? Is that the right approach? How can we show that?

2

There are 2 best solutions below

2
On BEST ANSWER

$a$ is an unessential parameter. Indeed $$x_{k+1}=2x_k-ax_k^2$$ is equivalent to $$ax_{k+1}=2ax_k-a^2x_k^2$$ i.e. by setting $t=ax$, $$t_{k+1}=2t_k-t_k^2.$$


Then notice that the function $f(t)=2t-t^2$ maps $[0,2]$ to $[0,1]$, and values outside this range to negative.

As

$$0<t<1\implies t<f(t)<1$$ and $$f(0)=0,f(1)=1$$ and $$t<0\implies f(t)<t,$$ we have convergence to $x=\frac1a$ for $x_0$ in $(0,\frac2a)$, convergence to $x=0$ for $x_0=0\lor x_0=\frac2a$ and divergence elsewhere.


Extra:

The convergence speed can be assessed from

$$1-t_{k+1}=1-2t_k+t_k^2=(1-t_k)^2.$$

Then by induction,

$$1-t_n=(1-t_0)^{2^n}.$$

Again, this converges when $|1-t_0|\le1$, and does it quadratically.


The iterates, converging to a square function

enter image description here

0
On

The Banach fixed point theorem isn't always the best for proving convergence. Your function is convex for $x>0$ and concave for $x<0$. You might be able to use this. Try doing this exercise (Spivak's calculus book) for a better idea of what I am suggesting.