Introduction
Theory
HOWTO
Error Analysis
Examples
Questions
Applications in Engineering
Matlab
Maple
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:
References
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^{(1)}(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^{(1)}(x_{a}) ⋅ (x - x_{a})
is zero at x_{a} and has a slope of f^{(1)}(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_{0} 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:
- 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}.
- If the derivative f^{(1)}(x_{n}) = 0, the
iteration process fails (division-by-zero) and we halt.
- 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_{0}, 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 approximation x_{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^{(1)}(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^{(1)}(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_{0} = 1. We note that the 1st and 2nd
derivatives of f(x) are equal, so we will approximate
½ f^{(2)}(ξ)/f^{(1)}(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 |
x_{n} |
err_{n} = ln(2) - x_{n} |
½ err_{n - 1}^{2} |
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:
- Our approximation is far away from the actual root,
- The 2nd derivative is very large, or
- 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^{2}. A
closed form solution for x does not exist so we must use a numerical
technique. We will use x_{0} = 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^{(1)}(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^{2}.
n |
x_{n} |
x_{n + 1} |
|f(x_{n + 1})| |
|x_{n + 1} - x_{n}| |
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_{0} = 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} - 2 starting with x_{0} = 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.
Figure 1. A resistor-diode circuit.
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 |
i_{n} |
i_{n + 1} |
|v(i_{n + 1})| |
|i_{n + 1} - i_{n}| |
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 (click to enlarge).
Figure 1. Newton's method applied to f(x) = cos(x).
For more help on Newton's method or on the Student[Calculus1] package, enter:
?NewtonsMethod
?Student,Calculus1