0

For a given we denote the error $e_k = x_k - x^*$, and the convergence rate of the iterative scheme is $r$ so that

$$ \lim \frac{ ||e_{k+1} || }{ || e_k ||^r } = C $$

where $C$ is finite and positive.

Im trying to understand how to effectively use this definition. For example, take Newton;s method to find a root $f(x) = x$. The iteration is given by

$$ x_{k+1} = x_k - \frac{ f(x_k) }{f'(x_k) } $$

how can I compute the limit in this case?

Mikey Spivak
  • 871

1 Answers1

2

This is usually done using Taylor series near the root.

If $x_{k+1} = x_k - \frac{ f(x_k) }{f'(x_k) } $ and $f(x_k)$ is small and $f'(x_k)$ is not small then, since $f(x+h) \approx f(x)+hf'(x)+O(h^2f''(x)) $ for small $h$,

$\begin{array}\\ f(x_{k+1}) &=f(x_k - \dfrac{ f(x_k) }{f'(x_k) })\\ &=f(x_k) - (\dfrac{ f(x_k) }{f'(x_k) })f'(x_k)+O((\dfrac{ f(x_k) }{f'(x_k) })^2f''(x_k))\\ &=O((\dfrac{ f(x_k) }{f'(x_k) })^2f''(x_k))\\ \text{so that}\\ \dfrac{f(x_{k+1})}{f(x_k)^2} &=O(\dfrac{ f''(x_k) }{f'(x_k)^2 })\\ \end{array} $

This shows that, if both $f'$ and $f''$ are non-zero at the root, the convergence is exactly quadratic.

Note: None of this is original.

marty cohen
  • 107,799