Sequence of iteration in Newton Raphson method.

Question

To find positive square root of $a>0$ by solving equation $x^2-a$ by Newton-Raphson mathod, if $x_n$ denotes $n$th iterate with $x_0>0, x_0\neq\sqrt{a}$, then the sequence $(x_n) $ is

$1.$ strictly increasing.

$2.$ strictly decreasing.

$3.$ constant.

$4.$ not convergent.

According to me if I start from right of square root of $a$ we get decreasing sequence and if started from left then increasing sequence. How can be some option correct ? For me it seems all options as incorrect. Please comment. Thank you.

Answer 1

This is not intended to be a complete answer, but more of a guide to how to approach this and similar problems.

The first thing to do is some experimentation. For this I would recommend 'geogebra', which is a program for experimenting with graphs and plane geometry. You pick a value of a, and plot your function. Then pick a value of $x_0$. From here you need to construct the Newton - Raphson method one iteration at a time, which should be quite instructive as to how it works. Plot point at $(x_0,0)$, then a vertical line through this point, then a tangent where it intersects the graph, where this tangent intersects the axis is $x_1$. Do this a few more times so you can see what the method is doing until it disappears and each step is too small.

At this point you should be able to vary the values of $a$ and $x_0$, and see what the method does for various cases. I suggest you do this yourself and reach your own conclusions before reading on. Firstly, for $x_0 >\sqrt{a}$ the sequence is decreasing. This is because of the curvature of the function. Secondly, for $0<x_0<\sqrt{a}$ we have $x_1>\sqrt{a} $, which then proceeds as previously. Hopefully with the visual representation it should be obvious that these are true, but it may also be instructive to try to prove these statements.

Answer 2

Concerning questions $(1)$ and $(2)$, it depends if you start higher or lower than to root of the equation.

Darboux theorem states that if $f(x_0)\times f''(x_0) >0$ the path to solution will be monotonic without any overshoot of the solution. If not, there will be an overshoot.

For illustration, let us take $a=100$.

Starting with $x_0=5$, the iterates will be $$\{5.00000,\color{red}{12.5000},10.2500,10.0030,10.0000\}$$ Starting with $x_0=15$, the iterates will be $$\{15.0000,10.8333,10.0321,10.0001,10.0000\}$$

Answer 3

The iteration is given by $$x_{n + 1} = g(x_n)$$ where $$g(x) = \frac{x}{2} + \frac{a}{2x}.$$ Compute $$g'(x) = \frac{1}{2}\left(1 - \frac{a}{x^2}\right).$$ Let $c = \sqrt{a}$ and remember that $g(c) = c$ by construction of Newton's method. Then by Taylor's theorem, \begin{align} x_{n + 1} - c &= g(x_n) - g(c) \\ &= g'(\xi(c, x_n))(x_n - c) \end{align} where $\xi(c, x_n)$ is between $c$ and $x_n$. If $x_0 > c$, then the sequence clearly decreases and converges to $c$. If $0 < x_0 < c$, then $x_1 > c$ so the sequence decreases from here and converges to $c$.