Newton's Method

Can we make use of the above to construct a method with quadratic convergence?

To solve f(x)=0 we must rearrange ino the form x=g(x), so let us try to make this rearrangement in such a way that we have quadratic convergence. If the iteration

x_n+1=g(x_n)=x_n+h(x_n)f(x_n),

is convergent, so that $x_n\to \alpha$, say, then $h(\alpha )f(\alpha )=0$.This gives $f(\alpha )=0$, provided that $h(\alpha )\not= 0$. We should obviously want h to satisfy this condition, since otherwise we might accidentally arrive at a zero of h rather than f. We have

$$g'(\alpha )=1+f'(\alpha )h(\alpha )+f(\alpha )h'(\alpha ).$$

But $f(\alpha )=0$ if $\alpha$ is a zero of f, and for second order convergence we want $g'(\alpha )=0$. We must therefore have $1+f'(\alpha )h(\alpha )=0$, or $h(\alpha )=-\frac{1}{f'(\alpha )}$ provided that $f'(\alpha )\not= 0$, the alternative to which we shall consider shortly.

This condition only specifies the function h at a single point $\alpha$, so any h which fulfills this condition would do. However, since we do not know the value of $\alpha$ (finding it is the whole object of the exercise!), the easiest choice for h is given by $h(x)=-\frac{1}{f'(x)}$, which clearly gives the correct value at $\alpha$for any continuous function f. The resulting iterative method is the classical Newton method

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

Local convergence is assured by Theorem 5.3. A geometric interpretation is shown in Figure 9. The base of the triangle is $x_{n}-x_{n+1}= \frac{f(x_n)}{f'(x_n)}$.

  

Figure: Newton's Method

We chose g to make $g'(\alpha )=0$, but if $g''(\alpha )=0$ also, while $g'''(\alpha )\not= 0$, we would have

$$\begin{array} {lcl}x_{n+1}-\alpha & = & g(x_n)-g(\alpha )\\ ... ...3g'''(c)\\ & = & \frac{1}{6}(x_n-\alpha )^3g'''(c),\end{array}$$

where $c\in (x_n,\alpha )$. In this case

$$\frac{x_{n+1}-\alpha }{(x_n-\alpha )^3}=\frac{g'''(c)}{6}\to... ...ox{ a finite nonzero constant for }x_n\mbox{ near to }\alpha ,$$

and so the method is third order. This can be generalized to give a pth order method if

$$g'(\alpha )=g''(\alpha )=\cdots =g^{(p-1)}(\alpha )=0$$

while $g^{(p)}(\alpha )\not= 0$.

We should check that Newton's method is precisely second order. We have  

$$g'(x)=1-\frac{f'^2(x)-f(x)f''(x)}{f'(x)^2}=\frac{f(x)f''(x)}{f'(x)^2},$$ (1)

so that $g'(\alpha )=0$ as expected, and

$$g''=\frac{f'^2(ff'''+f'f'')-2ff''f'f''}{f'^4},$$

giving $g''(\alpha )=\frac{f''(\alpha )}{f'(\alpha )}$,which is finite and nonzero provided that $f''(\alpha )\not= 0, f'(\alpha )\not= 0$.

What happens if $f'(\alpha )=0$ but $f''(\alpha )\not= 0$? From (), we see that g' only exists as a limit at $x=\alpha$. We evaluate this limit with the help of Taylor's theorem as follows:

$$g'(\alpha +h)=\frac{f(\alpha +h)f''(\alpha +h)}{f'^2(\alpha ... ...a +\theta _1h)f''(\alpha +h)}{(hf''^2(\alpha +\theta _2h))^2},$$

where $0<\theta _1,\theta _2<1$. Now letting $h\to 0$ and assuming the continuity of f'', we obtain the value of the limit as $\frac{1}{2}$, so that the method is only first order with convergence factor $\frac{1}{2}$.

If we know this to be the case, we can replace the usual g(x) in Newton's method by $g(x)=x-2\frac{f(x)}{f'(x)}$. For this form of g

$$g'=1-2\frac{f'^2-ff''}{f'^2}=2\frac{ff''}{f'^2}-1,$$

and using the limit above for $\frac{ff''}{f'^2}$, we find that $g'(x)\to 0$ as $x\to \alpha$, thus restoring the second order. This is however fairly useless from the practical point of view, since we will not normally know the nature of the zero in acdvance.

For what sort of function f is it true that $f(\alpha )=f'(\alpha )=0,~f''(\alpha )\not= 0$? One possibility is when f has a repeated zero, eg, it is given by $f(x)=(x-\alpha )^2h(x)$, where h is any function which does not vanish at $x=\alpha$.