5

Suppose that $f(x)$, $f′(x)$, and $f′′(x)$ are easily computed. Derive an algorithm like Newton’s method that uses three terms in the Taylor series. The algorithm should take as input an approximation to the root and produce as output a better approximation to the root. Show that the method is cubically convergent.

So the Taylor series is $$f(x+h)=f(x)+hf'(x)+ 2\cdot \frac{h^2}{f''(x)}+ 6\cdot\frac{h^3}{f'''(x)}+\ldots$$ And I know that if we use the first two terms, Newton's method would be $x_{n+1}=x_n-\frac{f(x)}{f'(x)}$.

So using three terms, what am i supposed to do here and how do i prove cubic convergence? Thanks.

F.A.
  • 1,001
james black
  • 1,893

1 Answers1

7

As you did, write $$f(x+h)=f(x)+h f'(x)+\frac{1}{2} h^2 f''(x)+O\left(h^3\right)$$ and we look for $h$ such that $$f(x+h)=0\implies f(x)+h f'(x)+\frac{1}{2} h^2 f''(x)=0$$which is a quadratic equation in $h$ (notice the similarity with Newton method).

So, we take the smallest solution of $h$; this leads to $$h=-\frac{f'(x)}{f''(x)}\left(1-\sqrt{1-\frac{2 f(x) f''(x)}{[f'(x)]^2}} \right)$$ But we can avoid the computation of the square root since, if $f(x)$ is small, then using the approximation $$1-\sqrt{1-a}=\frac a 2+\frac{a^2}8+O(a^3)$$ $h$ becomes $$h=-\frac{f(x)}{f'(x)}\left(1+\frac{f(x)\, f''(x)}{2[f'(x)]^2} \right)$$ So the iteration scheme becomes $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\left(1+\frac{f(x_n)\, f''(x_n)}{2[f'(x_n)]^2} \right)$$ and notice that if $f''(x_n)=0$ the formula reduces to Newton's one.

Now, continue.

Claude Leibovici
  • 260,315