Secant method
Encyclopedia
In numerical analysis
, the secant method is a root-finding algorithm
that uses a succession of roots of secant line
s to better approximate a root of a function
f. The secant method can be thought of as a finite difference
approximation of Newton's method
. However, the method was developed independently of Newton's method, and predated the latter by over 3000 years.
As can be seen from the recurrence relation, the secant method requires two initial values, x0 and x1, which should ideally be chosen to lie close to the root.
and 
, we construct a line through the points 
and 
, as demonstrated in the picture on the right. In point-slope form, this line has the equation
We find the root of this line – the value of
such that 
– by solving the following equation for 
:
The solution is
We then use this new value of
as 
and repeat the process using 
and 
instead of 
and 
. We continue this process, solving for 
, 
, etc., until we reach a sufficiently high level of precision (a sufficiently small difference between 
and 
).
of the secant method converge to a root of 
, if the initial values 
and 
are sufficiently close to the root. The order of convergence is α, where
is the golden ratio
. In particular, the convergence is superlinear, but not quite quadratic.
This result only holds under some technical conditions, namely that
be twice continuously differentiable and the root in question be simple (i.e., with multiplicity 1).
If the initial values are not close enough to the root, then there is no guarantee that the secant method converges. There is no general definition of "close enough", but the criterion has to do with how "wiggly" the function is on the interval
. For example, if 
is differentiable on that interval and there is a point where 
on the interval, then the algorithm may not converge.
does, and hence it does not always converge. The false position method
(or regula falsi) uses the same formula as the secant method. However, it does not apply the formula on
and 
, like the secant method, but on 
and on the last iterate 
such that 
and 
have a different sign. This means that the false position method
always converges.
The recurrence formula of the secant method can be derived from the formula for Newton's method
by using the finite difference
approximation
.
If we compare Newton's method with the secant method, we see that Newton's method converges faster (order 2 against α ≈ 1.6). However, Newton's method requires the evaluation of both
and its derivative 
at every step, while the secant method only requires the evaluation of 
. Therefore, the secant method may occasionally be faster in practice. For instance, if we assume that evaluating 
takes as much time as evaluating its derivative and we neglect all other costs, we can do two steps of the secant method (decreasing the logarithm of the error by a factor α² ≈ 2.6) for the same cost as one step of Newton's method (decreasing the logarithm of the error by a factor 2), so the secant method is faster. If however we consider parallel processing for the evaluation of the derivative, Newton's method proves its worth, being faster in time, though still spending more steps.
is a generalization of the secant method to more than one dimension.
The following graph shows the function f in red and the last secant line in bold blue. In the graph, the x-intercept of the secant line seems to be a good approximation of the root of f.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, the secant method is a root-finding algorithm
Root-finding algorithm
A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
that uses a succession of roots of secant line
Secant line
A secant line of a curve is a line that intersects two points on the curve. The word secant comes from the Latin secare, to cut.It can be used to approximate the tangent to a curve, at some point P...
s to better approximate a root of a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
f. The secant method can be thought of as a finite difference
Finite difference
A finite difference is a mathematical expression of the form f − f. If a finite difference is divided by b − a, one gets a difference quotient...
approximation of Newton's method
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
. However, the method was developed independently of Newton's method, and predated the latter by over 3000 years.
The method
The secant method is defined by the recurrence relationRecurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
As can be seen from the recurrence relation, the secant method requires two initial values, x0 and x1, which should ideally be chosen to lie close to the root.
Derivation of the method
Starting with initial values and , we construct a line through the points and , as demonstrated in the picture on the right. In point-slope form, this line has the equationWe find the root of this line – the value of
such that – by solving the following equation for :The solution is
We then use this new value of
as and repeat the process using and instead of and . We continue this process, solving for , , etc., until we reach a sufficiently high level of precision (a sufficiently small difference between and ).Convergence
The iterates of the secant method converge to a root of , if the initial values and are sufficiently close to the root. The order of convergence is α, whereis the golden ratio
Golden ratio
In mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...
. In particular, the convergence is superlinear, but not quite quadratic.
This result only holds under some technical conditions, namely that
be twice continuously differentiable and the root in question be simple (i.e., with multiplicity 1).If the initial values are not close enough to the root, then there is no guarantee that the secant method converges. There is no general definition of "close enough", but the criterion has to do with how "wiggly" the function is on the interval
. For example, if is differentiable on that interval and there is a point where on the interval, then the algorithm may not converge.Comparison with other root-finding methods
The secant method does not require that the root remain bracketed like the bisection methodBisection method
The bisection method in mathematics is a root-finding method which repeatedly bisects an interval and then selects a subinterval in which a root must lie for further processing. It is a very simple and robust method, but it is also relatively slow...
does, and hence it does not always converge. The false position method
False position method
The false position method or regula falsi method is a term for problem-solving methods in algebra and calculus. In simple terms, these methods begin by attempting to evaluate a problem using test values for the variables, and then adjust the values accordingly.-Algebra:In algebra, the false...
(or regula falsi) uses the same formula as the secant method. However, it does not apply the formula on
and , like the secant method, but on and on the last iterate such that and have a different sign. This means that the false position methodFalse position method
The false position method or regula falsi method is a term for problem-solving methods in algebra and calculus. In simple terms, these methods begin by attempting to evaluate a problem using test values for the variables, and then adjust the values accordingly.-Algebra:In algebra, the false...
always converges.
The recurrence formula of the secant method can be derived from the formula for Newton's method
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
by using the finite difference
Finite difference
A finite difference is a mathematical expression of the form f − f. If a finite difference is divided by b − a, one gets a difference quotient...
approximation
.If we compare Newton's method with the secant method, we see that Newton's method converges faster (order 2 against α ≈ 1.6). However, Newton's method requires the evaluation of both
and its derivative at every step, while the secant method only requires the evaluation of . Therefore, the secant method may occasionally be faster in practice. For instance, if we assume that evaluating takes as much time as evaluating its derivative and we neglect all other costs, we can do two steps of the secant method (decreasing the logarithm of the error by a factor α² ≈ 2.6) for the same cost as one step of Newton's method (decreasing the logarithm of the error by a factor 2), so the secant method is faster. If however we consider parallel processing for the evaluation of the derivative, Newton's method proves its worth, being faster in time, though still spending more steps.Generalizations
Broyden's methodBroyden's method
In numerical analysis, Broyden's method is a quasi-Newton method for the numerical solution of nonlinear equations in k variables. It was originally described by C. G. Broyden in 1965....
is a generalization of the secant method to more than one dimension.
The following graph shows the function f in red and the last secant line in bold blue. In the graph, the x-intercept of the secant line seems to be a good approximation of the root of f.
External links
- Java code By Behzad Torkian
- Animations for the secant method
- Secant Method Notes, PPT, Mathcad, Maple, Mathematica, Matlab at Holistic Numerical Methods Institute
- Module for Secant Method by John H. Mathews