The Newton's method

Template:Merge to Template:S Template:Center topTemplate:Font
Template:Center bottom
Template:Navigation bar

Newton's method generates a sequence $x_k$ to find the root $\alpha$ of a function $f$ starting from an initial guess $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 $f$ at $x_0$ and we find an approximation of $\alpha$ by computing the root of the tangent. Repeating this iterative process we obtain the sequence $x_k$.

Derivation of Newton's Method

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

$f(x)=f(x_k)+f^{\prime }(x_k)(x-x_k)+\frac{f^{″}({\eta }_k)}{2}(x-x_k{)}^2,$

with ${\eta }_k$ between $x$ and $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^{\prime }(x_k)}-\frac{(\alpha -x_k{)}^2}{2}\frac{f^{″}({\eta }_k)}{f^{\prime }(x_k)}.$

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

Newton's method :

$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(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^{\prime }(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 $x_0$.

The following theorem holds

Theorem

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

$\underset{k\to \mathrm{\infty }}{\lim }\frac{\alpha -x_{k+1}}{(\alpha -x_k{)}^2}=-\frac{f^{″}(\alpha )}{2f^{\prime }(\alpha )}.$

Advantages and Disadvantages of the Newton-Raphson 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 $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^{\prime }(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.