188
7 Solving Nonlinear Algebraic Equations
7.3 The Secant Method
When finding the derivative f (x) in Newton’s method is problematic, or when
function evaluations take too long; we may adjust the method slightly. Instead of
using tangent lines to the graph we may use secants. 4 The approach is referred to as
the secant method, and the idea is illustrated graphically in Fig. 7.2 for our example
problem x 2 − 9 = 0.
The idea of the secant method is to think as in Newton’s method, but instead of
using f (x n ), we approximate this derivative by a finite difference or the secant,
i.e., the slope of the straight line that goes through the points (x n , f (x n )) and
(x n−1 , f (x n−1 )) on the graph, given by the two most recent approximations x n and
x n−1 . This slope reads
f (x n ) − f (x n−1 )
x n − x n−1
.
(7.2)
Inserting this expression for f (x n ) in Newton’s method simply gives us the secant
method:
x n+1 = x n −
f (x n )
f (x n )−f (x n−1 )
x n −x n−1
,
or
x n+1 = x n − f (x n )
x n − x n−1
f (x n ) − f (x n−1 )
.
(7.3)
Comparing (7.3) to the graph in Fig. 7.2, we see how two chosen starting points
(x 0 = 1000, x 1 = 700, and corresponding function values) are used to compute
x 2 . Once we have x 2 , we similarly use x 1 and x 2 to compute x 3 . As with Newton’s
method, the procedure is repeated until f (x n ) is below some chosen limit value,
or some limit on the number of iterations has been reached. We use an iteration
counter here too, based on the same thinking as in the implementation of Newton’s
method.
We can store the approximations x n in an array, but as in Newton’s method,
we notice that the computation of x n+1 only needs knowledge of x n and x n−1 , not
“older” approximations. Therefore, we can make use of only three variables: x for
x n+1 , x1 for x n , and x0 for x n−1 . Note that x0 and x1 must be given (guessed) for
the algorithm to start.
A program secant_method.py that solves our example problem may be written
as:
import sys
def secant(f, x0, x1, eps):
f_x0 = f(x0)
f_x1 = f(x1)
4 https://en.wikipedia.org/wiki/Secant_line.
7 Solving Nonlinear Algebraic Equations
7.3 The Secant Method
When finding the derivative f (x) in Newton’s method is problematic, or when
function evaluations take too long; we may adjust the method slightly. Instead of
using tangent lines to the graph we may use secants. 4 The approach is referred to as
the secant method, and the idea is illustrated graphically in Fig. 7.2 for our example
problem x 2 − 9 = 0.
The idea of the secant method is to think as in Newton’s method, but instead of
using f (x n ), we approximate this derivative by a finite difference or the secant,
i.e., the slope of the straight line that goes through the points (x n , f (x n )) and
(x n−1 , f (x n−1 )) on the graph, given by the two most recent approximations x n and
x n−1 . This slope reads
f (x n ) − f (x n−1 )
x n − x n−1
.
(7.2)
Inserting this expression for f (x n ) in Newton’s method simply gives us the secant
method:
x n+1 = x n −
f (x n )
f (x n )−f (x n−1 )
x n −x n−1
,
or
x n+1 = x n − f (x n )
x n − x n−1
f (x n ) − f (x n−1 )
.
(7.3)
Comparing (7.3) to the graph in Fig. 7.2, we see how two chosen starting points
(x 0 = 1000, x 1 = 700, and corresponding function values) are used to compute
x 2 . Once we have x 2 , we similarly use x 1 and x 2 to compute x 3 . As with Newton’s
method, the procedure is repeated until f (x n ) is below some chosen limit value,
or some limit on the number of iterations has been reached. We use an iteration
counter here too, based on the same thinking as in the implementation of Newton’s
method.
We can store the approximations x n in an array, but as in Newton’s method,
we notice that the computation of x n+1 only needs knowledge of x n and x n−1 , not
“older” approximations. Therefore, we can make use of only three variables: x for
x n+1 , x1 for x n , and x0 for x n−1 . Note that x0 and x1 must be given (guessed) for
the algorithm to start.
A program secant_method.py that solves our example problem may be written
as:
import sys
def secant(f, x0, x1, eps):
f_x0 = f(x0)
f_x1 = f(x1)
4 https://en.wikipedia.org/wiki/Secant_line.