ROOT FINDING TECHNIQUES: Newton's Method
Consider a function f ( x ) which has the following graph:
Suppose that we want to locate the root r which lies near the point x0. The main idea in Newton’s method is to approximate the curve with a straight line for x between the values of x0 and r. The straight line is assumed to be tangent to the curve at the point ( x0, f(x0) ).
Graphically we can represent this with the picture below, where the tangent line and the new root estimate x1 are shown in red.
We can see that x1 is closer to the root r than x0. If we were to repeat the process we can very easily see that x2 would be even closer to the root etc. as it is shown below:
Analytically how can we obtain x1 if we know x0 ? Let’s try to write the equation of the red straight line. Its slope m is given by the value of the derivative of the function at x = x0 , i.e.
and consequently its equation is:
The point x = x1 corresponds to the point of the straight line where y = 0. Consequently we obtain:
If we solve this equation for x1 we obtain the iteration formula:
As an example
of the method consider the following table which illustrates the steps
needed to find the positive root of
x2 – 2 = 0
We start with the initial guess x = 2 and we note that
| xOld | f(xOld) |
f’(xOld) |
xNew |
remarks |
| 2 | 2 | 4 |
2 – 2/4 = 1.5 |
|
| 1.5 | 0.25 | 3 | 1.5
– 0.25 / 3 =
1.4167 |
Note
how quickly the method zooms to the solution |
| 1.4167 | 0.0070 | 2.8334 | 1.4167
– 0.007/2.8334 =
1.4142 |
At this point we reach the “exact” value considering 4 decimal digits. Hence we STOP |
Note that the actual root of the equation is the square root of two, which is 1.414213562. If we round this value to 4 decimal places we have 1.4142. What is the error between this “exact” value and our approximation of the first and second line of the table?
There are two error estimates we may calculate:
Absolute error:
|
1.5 – 1.4142 | = 0.0858 for the first line and
| 1.4167 – 1.4142 | = 0.0025 for the second line.
Relative error:
|
( 1.5 – 1.4142 ) / 1.4142 | = 0.0607 for the first line ( or 6.07
per cent ) and
| ( 1.4167 – 1.4142 ) / 1.4142 | = 0.0018 for the second line (
or 0.18 per cent)
PROS & CONS of the method:
1) When the method works, works very fast. Usually if we start close enough to the root the method performs well
2) If we have the wrong starting value the method diverges ( produces increasingly nonsensical results)
3) We must be able to produce an analytic expression for the derivative of the function. In certain applications this may not be possible.
4) At each step of the iteration we have to perform 2 function evaluations ( the function and the derivative). Again in certain applications this may slow down the method.
5) There is a problem with double roots, but it can be fixed.
Newton’s method can be programmed very efficiently using a functions.
