The Newton's method

Newton's Method

Numerical analysis > The Newton's method

Newton's method generates a sequence $\displaystyle x_k$ to find the root $\displaystyle \alpha$ of a function $\displaystyle f$ starting from an initial guess $\displaystyle x_0$ . This initial guess $x_0$ should be close enough to the root $\alpha$ for the convergence to be guaranteed. We construct the tangent of $\displaystyle f$ at $\displaystyle x_0$ and we find an approximation of $\alpha$ by computing the root of the tangent. Repeating this iterative process we obtain the sequence $\displaystyle x_k$ .

Derivation of Newton's Method

Approximating $\displaystyle f(x)$ with a second order Taylor expansion around $\displaystyle x_k$ ,

f(x)=f(x_k)+f'(x_k)(x-x_k)+\frac{f''(\eta_k)}{2}(x-x_k)^2,

with $\displaystyle \eta_k$ between $\displaystyle x$ and $\displaystyle x_k$ . Imposing $x=\alpha$ and recalling that $f(\alpha)=0$ , with a little rearranging we obtain

\alpha=x_k-\frac{f(x_k)}{f'(x_k)}-\frac{(\alpha-x_k)^2}{2}\frac{f''(\eta_k)}{f'(x_k)}.

Neglecting the last term, we find an approximation of $\displaystyle \alpha$ which we shall call $\displaystyle x_{k+1}$ . We now have an iteration which can be used to find successively more precise approximations of $\displaystyle \alpha$ :

Newton's method :

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

Convergence Analysis

It's clear from the derivation that the error of Newton's method is given by

Newton's method error formula:

\alpha-x_{k+1}=-\frac{f''(\eta_k)}{2f'(x_k)}(\alpha-x_k)^2.

From this we note that if the method converges, then the order of convergence is 2. On the other hand, the convergence of Newton's method depends on the initial guess $\displaystyle x_0$ .

The following theorem holds

Theorem

Assume that $f(x),\,f'(x),$ and $\displaystyle f''(x)$ are continuous in neighborhood of the root $\displaystyle \alpha$ and that $\displaystyle f'(\alpha)\neq 0$ . Then, taken $\displaystyle x_0$ close enough to $\displaystyle \alpha$ , the sequence $\displaystyle x_k$ , with $k\geq 0$ , defined by the Newton's method converges to $\alpha$ . Moreover the order of convergence is $\displaystyle p=2$ , as

\lim_{k\to\infty}\frac{\alpha-x_{k+1}}{(\alpha-x_k)^2}=-\frac{f''(\alpha)}{2f'(\alpha)}.

Advantages and Disadvantages of Newton's Method

Advantages of using Newton's method to approximate a root rest primarily in its rate of convergence. When the method converges, it does so quadratically. Also, the method is very simple to apply and has great local convergence.

The disadvantages of using this method are numerous. First of all, it is not guaranteed that Newton's method will converge if we select an $\displaystyle x_0$ that is too far from the exact root. Likewise, if our tangent line becomes parallel or almost parallel to the x-axis, we are not guaranteed convergence with the use of this method. Also, because we have two functions to evaluate with each iteration ( $f(x_k)$ and $f'(x_k)$ , this method is computationally expensive. Another disadvantage is that we must have a functional representation of the derivative of our function, which is not always possible if we working only from given data.

This article is issued from Wikiversity - version of the Tuesday, March 31, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.