Newton's Method

From Wiki

Newton's Method is a fast way of finding roots of equations by iteration.

1 Basics
2 Deriving Newton's Method
3 The Initial Guess
4 Computing Square Roots with Newton's Method

[edit] Basics

In general, the following algorithm can be used to find the roots of an equation having the special form $x = f(x)\,$ . Solutions of this equation are also sometimes called fixed points.

1. Make an initial guess $x_0\,$ and use the above equation to iterate to get further guesses $x_1 = f(x_0), x_2 = f(x_1), ...\,$ .
2. Show that this sequence of iterates $x_n\,$ converges to a limit, i.e. show that $\lim_{n \to \infty} f(x_n) = \eta$ .
3. Show that $\eta = f(\eta)\,$ , i.e. show that the limit is a root of the equation.

This algorithm only works in certain cases. In particular, $f(x)\,$ and $f'(x)\,$ must be continuous in the interval $x \in [a, b]$ and $|f'(x)| \leq \lambda < 1$ . Furthermore, the iterates $x_n\,$ defined recursively by $x_{x+1} = f(x_n)\,$ must all lie in the interval $[a, b]\,$ . If we now choose $x_0\,$ to be in the interval it can be shown that the iterates will always converge to $\eta\,$ .

[edit] Deriving Newton's Method

The above root-finding algorithm can also be used to solve equations of the form $g(x) = 0\,$ .

A solution $\eta\,$ of $g(x) = 0\,$ is also a solution of $x = f(x) = x - g(x)\,$ . Conversely, if $\eta\,$ is a solution of $x = f(x)\,$ then it is also a solution of $g(x) = x - f(x) = 0\,$ .

$\eta\,$ is even a solution of $x = f(x) = x - \frac{g(x)}{h(x)}$ where $h(x)\,$ is a continuous function that is not zero close to $\eta\,$ . Let us now look at the iterates $x_{n+1} = x_n - \frac{g(x_n)}{h(x_n)}$ and let us try to choose a function $h(x)\,$ so that these iterates converge as fast as possible.

We now compute $f'(x) = \frac{d}{dx} \lbrack x - \frac{g(x)}{h(x)} \rbrack = 1 - \frac{g'(x) h(x) - h'(x) g(x)}{h^2(x)} = 1 - \frac{g'(x)}{h(x)} + \frac{h'(x) g(x)}{h^2(x)}$ .

Now, because of $g(\eta) = 0\,$ we have $f'(\eta) = 1 - \frac{g'(\eta)}{h(\eta)}$ . If we now set $h(x) = g'(x)\,$ we have $f'(\eta) = 0\,$ . This turns out to be an optimal choice with rapid convergence and allows us to use the above iteration algorithm because $|f'(x)| \leq \lambda < 1$ for all $x\,$ sufficiently close to $\eta\,$ , which immediately follows from the continuity of $f'(x)\,$ .

We finally arrive at Newton's Method, an iteration scheme to rapidly solve the equation $g(x) = 0\,$ :

$x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)}$

[edit] The Initial Guess

The initial guess $x_0\,$ needs to be chosen sufficiently close to $\eta\,$ , so that $|f'(x_0)| \leq \lambda < 1\,$ . We can verify this by using the $f'(x)\,$ computed above with $h(x) := g'(x)\,$ :