Proof of an inequality using Newton's Method

Question

Question: Show that the function $f(x):= x^3 -2x -5$ has a zero $r$ in the interval $I:= [2,2.2]$. If $x_1 :=2$ and if we define the sequence $(x_n)$ using Newton's procedure, show that $|x_{n+1} -r| \le (0.7)|x_n -r|^2$. Show that x_4 is accurate to within six decimal places.

I was able to the do the first and last part of this question. My difficulty lies in showing that $|x_{n+1} -r| \le (0.7)|x_n -r|^2$.

By Newton's Method, I determined that $x_{n+1} := x_n- \frac{x^3_n -2x_n -5}{2x^2_n -2} = \frac {x^3_n +5}{2x^2_n -2 }$. Then I suppose I would have to show that $|\frac {x^3_n +5}{2x^2_n -2 }-r| \le (0.7)|x_n-r|^2$. So I think at this point I would have to use induction. The problem is finding a way that is not so tedious. I thought maybe I could take advantage of the fact that by Newton's Method, $x_n \to r$ but this does not really help matters. Any help would be very much appreciated.

Answer 1

First note that you have made a slip in the recursion, it should be $$x_{n+1}=\frac{2x_n^3+5}{3x_n^2-2}\ .$$ This gives $$|x_{n+1}-r|=\Bigl|\,\frac{2x_n^3+5}{3x_n^2-2}-r\,\Bigr| =\Bigl|\,\frac{2x_n^3-3rx_n^2+2r+5}{3x_n^2-2}\,\Bigr|\ .$$ Now the numerator can be factorised as $$(x_n-r)^2(2x_n+r)\ ,$$ where we have used the fact that $r$ is a root of the cubic and so $r^3=2r+5$. Therefore $$|x_{n+1}-r|=|x_n-r|^2\Bigl|\,\frac{2x_n+r}{3x_n^2-2}\,\Bigr|\ .$$ But it is not hard to see that we will always have $$2\le x_n\le 2.2\quad\hbox{and}\quad 2\le r\le 2.2\ ;$$ hence $$|2x_n+r|\le6.6\quad\hbox{and}\quad |3x_n^2-2|\ge10\ ,$$ which gives the required estimate.

Answer 2

$f(x)$ is convex and increasing on the interval $I=[2,2.2]$, hence given that $$ x_0=2,\quad x_{n+1} = x_n-\frac{f(x_n)}{f'(x_n)}$$ we have that $\{x_n\}_{n\in\mathbb{N}^*}$ is a decreasing sequence that converges towards the only root $\xi$ of $f$ in $I$. Since in a neighbourhood of $\xi$ we have: $$ f(x) = (x-\xi)f'(\xi)+\frac{1}{2}(x-\xi)^2 f''(\xi) + (x-\xi)^3, $$ $$ f'(x) = f'(\xi) + (x-\xi)f''(\xi)+3(x-\xi)^2, $$ it happens that: $$ f(x)-(x-\xi)f'(x) = -\frac{1}{2}(x-\xi)^2 f''(\xi)-2(x-\xi)^3, $$ so: $$x_{n+1}-\xi = -\frac{1}{f'(x_n)}\left(f(x_n)-(x_n-\xi)f'(x_n)\right)=\frac{(x_n-\xi)^2}{f'(x_n)}\left(\frac{1}{2}f''(\xi)+2(x_n-\xi)\right)\tag{1}$$ Since over $I$ we have $f'(x)\geq f'(2)=10, f''(x)\leq f''(2.2)=13.2,|x-\xi|\leq 0.2$, the claim follows.