Given the $ f(x)=x^3+x-1 $, I have shown so far that $ f$ has a unique root $r\in(0,1)$ and that for the sequence $(x_{n}), n>=0$ produced by Newton's method we have $$\lim_{n\to\infty} x_{n}=r$$ for every $x_{0}\in\mathbb{R}$. How do I prove that $$\lim_{n\to\infty} \frac{x_{n+1}-r}{(x_{n}-r)^2}=\frac{3r}{3r^2+1}$$ ?
Asked
Active
Viewed 1,123 times
2 Answers
3
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^3+x_n -1}{3x_n^2+1} = \frac{2x_n^3+1}{3x_n^2+1}$$
hence
$$x_{n+1}-r =\frac{2x_n^3+1}{3x_n^2+1} - r = \frac{2x_n^3 - 3x_n^2r+1-r}{3x_n^2+1} = \frac{2x_n^3 - 3x_n^2r+r^3}{3x_n^2+1} = \frac{(x_n-r)^2(2x_n+r)}{3x_n^2+1}$$
Therefore
$$\frac{x_{n+1}-r}{(x_n-r)^2} = \frac{2x_n+r}{3x_n^2+1} \to \frac{3r}{3r^2+1}$$
as $n \to \infty$.
Catalin Zara
- 6,187
-
I didn't substitute $1-r$ with $r^3$, that's why I couldn't prove it, thanks – asdf Apr 25 '16 at 15:57
2
What you have written is $\frac{1}{2} \frac{f''(r)}{f'(r)}$. This is actually the usual error estimate for Newton's method for a simple root and twice continuously differentiable $f$, when $x_n$ is known to be converging to $r$. It is not at all specific to your problem.
To prove it, let $g(x)=x-\frac{f(x)}{f'(x)}$ and then notice that you have $\frac{g(x_n)-r}{(x_n-r)^2}$. Now Taylor expand the numerator about $x_n=r$ to get your result.
Ian
- 101,645