Numerical Analysis (Newton's Method)

Introduction

Newton's method is a technique for finding the root of a scalar-valued function f(x) of a single variable x. It has rapid convergence properties but requires that model information providing the derivative exists.

Background

Useful background for this topic includes:

• 3. Iteration
• 7. Taylor series

References

• Bradie, Section 2.4, Newton's Method, p.95.
• Mathews, Section 2.4, Newton-Raphson and Secant Methods, p.70.
• Weisstein, http://mathworld.wolfram.com/NewtonsMethod.html.

Theory

Assumptions

Newton's method is based on the assumption that functions with continuous derivatives look like straight lines when you zoom in closely enough to the functions. This is demonstrated here.

We will assume that f(x) is a scalar-valued function of a single variable x and that f(x) has a continuous derivative f⁽¹⁾(x) which we can compute.

Derivation

Suppose we have an approximation x_a to a root r of f(x), that is, f(r) = 0. Figure 1 shows a function with a root and an approximation to that root.

Figure 1. A function f(x), a root r, and an approximation to that root x_a.

Because f(x) has a continuous derivative, it follows that at any point on the curve of f(x), if we examine it closely enough, that it will look like a straight line. If this is the case, why not approximate the function at (x_a, f(x_a)) by a straight line which is tangent T_xa to the curve at that point? This is shown in Figure 2.

Figure 2. The line tangent to the point (x_a, f(x_a)).

The formula for this line may be deduced quite easily: the linear polynomial f⁽¹⁾(x_a) ⋅ (x - x_a) is zero at x_a and has a slope of f⁽¹⁾(x_a), and therefore, if we add f(x_a), it will be tangent to the given point on the curve, that is, the linear polynomial

is the tangent line. Because the tangent line is a good approximation to the function, it follows that the root of the tangent line should be a better approximation to the root than x_a, and solving for the root of the tangent is straight-forward:

HOWTO

Problem

Given a function of one variable, f(x), find a value r (called a root) such that f(r) = 0.

Assumptions

We will assume that the function f(x) is continuous and has a continuous derivative.

Tools

We will use sampling, the derivative, and iteration. Information about the derivative is derived from the model. We use Taylor series for error analysis.

Initial Requirements

We have an initial approximation x₀ of the root.

Iteration Process

Given the approximation x_n, the next approximation x_{n + 1} is defined to be

Halting Conditions

There are three conditions which may cause the iteration process to halt:

1. We halt if both of the following conditions are met:
   • The step between successive iterates is sufficiently small, |x_n + 1 - x_n| < ε_step, and
   • The function evaluated at the point x_{n + 1} is sufficiently small, |f(x_n + 1)| < ε_abs.
2. If the derivative f⁽¹⁾(x_n) = 0, the iteration process fails (division-by-zero) and we halt.
3. If we have iterated some maximum number of times, say N, and have not met Condition 1, we halt and indicate that a solution was not found.

If we halt due to Condition 1, we state that x_{n + 1} is our approximation to the root.

If we halt due to either Condition 2 or 3, we may either choose a different initial approximation x₀, or state that a solution may not exist.

Error Analysis

Given that we are using Newton's method to approximate a root of the function f(x).

Suppose we have an approximation of the root x_n which has an error of (r - x_n). What is the error of the next approximationx_{n + 1} found after one iteration of Newton's method?

Suppose r is the actual root of f(x). Then from the Taylor series, we have that:

where ξ ∈ [r, x_n]. Note, however, that f(r) = 0, so if we set the left-hand side to zero and divide both sides by f⁽¹⁾(x_n), we get:

We can bring the first two terms to the left-hand side and multiple each side by -1. For the next step, I will group two of the terms on the terms on the left-hand side:

Note that the object in the parentheses on the left-hand side is, by definition, x_{n + 1} (after all, x_{n + 1} = x_n - f(x_n)/f⁽¹⁾(x_n) ), and thus we have:

But the left hand side is the error of x_{n + 1}, and therefore we see that error is reduced by a scalar multiple of the square of the previous error.

To demonstrate this, let us find the root of f(x) = e^x - 2 starting with x₀ = 1. We note that the 1st and 2nd derivatives of f(x) are equal, so we will approximate ½ f⁽²⁾(ξ)/f⁽¹⁾(x_n) by ½. Table 1 shows the Newton iterates, their absolute errors, and the approximation of the error based on the square previous error.

Table 1. Newton iterates in finding a root of f(x) = e^x - 2.

n	xn	errn = ln(2) - xn	½ errn - 12
0	1.0	-3.069 ⋅ 10-1	N/A
1	0.735758882342885	-4.261 ⋅ 10-2	-4.708 ⋅ 10-2
2	0.694042299918915	-8.951 ⋅ 10-4	-9.079 ⋅ 10-4
3	0.693147581059771	-4.005 ⋅ 10-7	-4.006 ⋅ 10-7
4	0.693147180560025	-8.016 ⋅ 10-14	-8.020 ⋅ 10-14

Note that the error at the nth step is very closely approximated by the error of the (n - 1)th step. Now, in reality, we do not know what the actual error is (otherwise, we wouldn't be using Newton's method, would we?) but this reassures us that, under reasonable conditions, Newton's method will converge very quickly.

Failure of Newton's Method

The above formula suggests that there are three situations where Newton's method may not converge quickly:

1. Our approximation is far away from the actual root,
2. The 2nd derivative is very large, or
3. The derivative at x_n is close to zero.

Examples

Example 1

As an example of Newton's method, suppose we wish to find a root of the function f(x) = cos(x) + 2 sin(x) + x². A closed form solution for x does not exist so we must use a numerical technique. We will use x₀ = 0 as our initial approximation. We will let the two values ε_step = 0.001 and ε_abs = 0.001 and we will halt after a maximum of N = 100 iterations.

From calculus, we know that the derivative of the given function is f⁽¹⁾(x) = -sin(x) + 2 cos(x) + 2x.

We will use four decimal digit arithmetic to find a solution and the resulting iteration is shown in Table 1.

Table 1. Newton's method applied to f(x) = cos(x) + 2 sin(x) + x².

n	xn	xn + 1	|f(xn + 1)|	|xn + 1 - xn|
0	0.0	-0.5000	0.1688	0.5000
1	-0.5000	-0.6368	0.0205	0.1368
2	-0.6368	-0.6589	0.0008000	0.02210
3	-0.6589	-0.6598	0.0006	0.0009

Thus, with the last step, both halting conditions are met, and therefore, after four iterations, our approximation to the root is -0.6598 .

Questions

Question 1

Find a root of the function f(x) = e^-x cos(x) starting with x₀ = 1.3 . The terminating conditions are given by ε_abs = 1e-5 and ε_step = 1e-5.

Answer: 1.57079632679490 after five iterations.

Question 2

Perform three steps of Newton's method for the function f(x) = x² - 2 starting with x₀ = 1. Use a calculator for the third step.

Answer: 3/2, 17/12, 577/408 ≈ 1.414215686274510

Applications to Engineering

Consider the circuit, consisting of a voltage source, a resistor, and a diode, shown in Figure 1.

Suppose we wish to find the current running through this circuit. To do so, we can use Kirchhoff's voltage law (KVL) which says that the sum of the voltages around a loop is zero. For this, we need the model of diode which states that the relationship between the current and the voltage across a diode is given by the equation

Solving this equation for the voltage v and using values I_S = 8.3e-10 A, V_T = 0.7 V, and n = 2, we get from KVL that

This equation cannot be solved exactly for the current with any of the tools available in an undergraduate program (it requires the use of the Lambert W function). Therefore we must resort to using numerical methods:

Defining the left hand side of the equation to be v(i), we have to solve v(i) = 0 for i, and we will continue iterating until ε_step< 1e-10 and ε_abs < 1e-5.Table 1. Newton's method applied to v(i).

n	in	in + 1	|v(in + 1)|	|in + 1 - in|
0	0.0	2.964283918e-10	0.0724	2.96e-10
1	2.964283918e-10	3.547336588e-10	1.81e-3	5.83e-11
2	3.547336588-10	3.562680160-10	1.17e-5	1.53e-12
3	3.562680160e-10	3.562690102e-10	2.63e-9	9.94e-16

Therefore, the current is approximately 3.562690102e-10 A.

Matlab

Finding a root of f(x) = cos(x):

eps_step = 1e-5;
eps_abs = 1e-5;
N = 100;
x = 0.2;

for i=1:N
    xn = x - cos(x)/( -sin(x) );

    if abs( x - xn ) < eps_step && abs( cos( xn ) ) < eps_abs
       break;
    elseif i == N
       error( 'Newton\'s method did not converge' );
    end

    x = xn;
end

xn
        

What happens if you start with smaller values of x? Why?

Maple

The following commands in Maple:

with( Student[Calculus1] ):
NewtonsMethod( cos(x), x = 0.5, output = plot, iterations = 5 );

produces the plot in Figure 1: 

For more help on Newton's method or on the Student[Calculus1] package, enter:

?NewtonsMethod

?Student , Calculus1