Newton's Method

Learning Project Summary

Project Code: Newton's Method
School: Computer Science
Department: Scientific Computing

Content Summary

This learning project offers learning activities to Newton's Method. In this course, students will learn how to solve problems of the type $f(x) = 0\,$ using the Newton’s Method, also called the Newton-Raphson iteration.

Derivation of the Newton's Method

In Newton’s method, we must first assume that the function is differentiable, i.e. that function $f\,$ has a definite slope at each point. Hence at any point $(x_0, f(x_0))\,$ , we can calculate the tangent $f'\!(x_0)\,$ , which is a fairly good approximation to the curve at that point. Alternatively, we can see that linear function

$l(x) = f'\!(x_0)(x - x_0) + f(x_0)$

is quite close to function $f\,$ near point $x_0\,$ , and at $x_0\,$ , the functions $l\,$ and $f\,$ give the same value. Hence, we take it that the solution to the problem $l(x) = 0\,$ will give a fairly good approximation to the problem $f(x) = 0\,$ .

The zero of $l(x)\,$ can be easily found:

  $l(x) = 0\,$ 
  $f'\!(x_0)(x - x_0) + f(x_0) = 0$ 
  $x = x_0 - \left(\frac{f(x_0)}{f'\!(x_0)}\right)$

This can be done repeatedly to produce points with the following equation:

  $x_{n+1} = x_n - \left(\frac{f(x_n)}{f'\!(x_n)}\right)$

An alternative way of viewing Newton’s method is as follows: we let $x_0\,$ be our approximation to the problem $f(x) = 0\,$ , then we try to solve for the correction h such that

  $f(x_0 + h) = 0\,$

If $f\,$ is well-behaved function, we can then write the Taylor series at $x_0\,$ as

  $f(x_0) + hf'\!(x_0) + \frac{h^2}{2}f''\!(x_0) + ... = 0$

By dropping all but the first two terms of the series, we can achieve an approximation of h through the equation

  $f(x_0) + hf'\!(x_0) = 0$

Solving for h, we then achieve our next approximation to the root of $f\,$ with the equation

  $\begin{matrix}x_1 & = &x_0 + h \\ \ & = & x_0 - \left(\frac{f(x_0)}{f'\!(x_0)}\right) \end{matrix}$

Repeating this process results in the recursive definition of Newton’s Method

  $x_{n+1} = x_n - \left(\frac{f(x_n)}{f'\!(x_n)}\right)$

The success of Newton’s method depends on whether the following equation holds: $\lim_{n\rightarrow \infty} x_n = r\,$ where r is the root of $f\,$ .

Code

The following is an example of a function that can be written using MATLAB to perform Newton's Method on any given mathematical function $f\,$ .

function x = Newton(f, fp, x, nmax, e)
 
% f is an inline function which we apply Newton's method on
% fp is an inline function that is the derivative of function f
% x is the initial guess of the root
% nmax is the total number of iterations done
% e is the error used to control convergence
 
fprintf('x(0) = %10g \n', x)
for n = 1:nmax
    d = f(x)/fp(x);
    x = x - d;
    fprintf('x(%i) = %10g \n', n, x)
    if abs(d) < e
        fprintf('Converged! \n')
        return
    end
end

Example

We try to locate the root of the equation $f(x) = x^3 - 2x^2 + x - 3\,$ with initial starting point $x_0\,$ = 3. Note also that the derivative of the above function is $f'\!(x) = 3x^2 - 4x + 1$

Then we do the following:

declare our function f
f = inline('x^3 - 2*x^2 + x - 3');
 
% declare the derivative of function f
fp = inline('3*x^2 - 4*x + 1');
 
% declare total number of iterations to be undertaken
nmax = 10;
 
% declare value of initial starting point
x = 3.0;
 
% declare amount of error allowed
e = 1.0e-15;
 
% carry out iteration using function above
x = Newton(f,fp,x,nmax,e)
 
% results are as follows:
x(0) =          3 
x(1) =     2.4375 
x(2) =    2.21303 
x(3) =    2.17555 
x(4) =    2.17456 
x(5) =    2.17456 
x(6) =    2.17456 
x(7) =    2.17456 
Converged! 
 
x =
 
2.174559410292980

Problems and Restrictions of Newton's Method

Firstly, and most obviously, Newton's Method can only be applied with functions that are differentiable. This can be seen straight from the formula, where f’(x) is a necessary part of the iterative function.

Secondly, the starting point must be chosen carefully, and it is best chosen with an approximate idea of the graph of the function in mind. If chosen wrongly, one of the following three situations could happen:

Runaway: In which Newton’s Method leads away from the root instead of towards the root; the solution diverges rather than converges.
Flat Spot: In which the derivative of the graph at the starting point is 0, and thus the next iterative point occurs at infinity and cannot be used.
Cycle: In which the solutions cycle between two points, and never converges to the root.

Convergence

Newton's method is said to converge quadratically to the root r, if r is a simple root, i.e. $f'\!(r) \ne \; 0$ . This means that the errors obey the inequality $|r - x_{n+1}| \le \; c|r - x_n|^2$ .

Using the Taylor Series, we see that there exists some point $\xi\,$ between $x_{n}\,$ and $r\,$ such that

  $f(r) = f(x_n) + (r-x_n)f'\!(x_n) + \frac{1}{2} (r-x_n)^2f''\!(\xi\,) = 0$

Dividing the last equation throughout by $f'\!(x_n)$ , we get

  $\frac{f(x_n)}{f'\!(x_n)} + r - x_n + (r - x_n)^2 \frac{f''\!(\xi\,)}{2f'\!(x_n)} = 0$

Substituting the equation used in Newton's Method, we get

  $r - x_{n+1} + (r - x_n)^2 \frac{f''\!(\xi\,)}{2f'\!(x_n)} = 0$

Thus

  $|r - x_{n+1}| = \frac{f''\!(\xi\,)}{2f'\!(x_n)} |r - x_n|^2$

Exercises

Locate the root of $f(x) = \cos(2x) + \sin(3x)\,$ nearest $\pi\,$ using Newton's method.
Two of the four zeros of $f(x)=x^4 + 3x^3 - 5x^2 + 1\,$ are positive. Find them by Newton's method, correct to two significant figures.

References

[1] Cheney, Ward and Kincaid, David. Numerical Mathematics and Computing. 6th Edition. United States: Thomson Brooks/Cole, 2008.

Active Participants

Active participants in this Learning Group

Esther

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