thumb|300px|The first two iterations of the secant method. The red curve shows the function f, and the blue lines are the secants. For this particular case, the secant method will not converge to the visible root.
In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines 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, so it is considered a quasi-Newton method. Historically, it is as an evolution of the method of false position, which predates Newton's method by over 3000 years.
The method
The secant method is an iterative numerical method for finding a zero of a function . Given two initial values and , the method proceeds according to the recurrence relation
:<math>
x_n
= x_{n-1} - f(x_{n-1}) \frac{x_{n-1} - x_{n-2{f(x_{n-1}) - f(x_{n-2})}
= \frac{x_{n-2} f(x_{n-1}) - x_{n-1} f(x_{n-2})}{f(x_{n-1}) - f(x_{n-2})}.
</math>
This is a nonlinear second-order recurrence that is well-defined given and the two initial values and . Ideally, the initial values should be chosen close to the desired zero.
Derivation of the method
Starting with initial values and , we construct a line through the points and , as shown in the picture above. In point–point form, the equation of this line is
:<math>y = \frac{f(x_1) - f(x_0)}{x_1 - x_0}(x - x_1) + f(x_1).</math>
The root of this linear function, that is the value of such that is
:<math>x = x_1 - f(x_1) \frac{x_1 - x_0}{f(x_1) - f(x_0)}.</math>
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 ):
:<math>
\begin{align}
x_2 & = x_1 - f(x_1) \frac{x_1 - x_0}{f(x_1) - f(x_0)}, \\[6pt]
x_3 & = x_2 - f(x_2) \frac{x_2 - x_1}{f(x_2) - f(x_1)}, \\[6pt]
& \,\,\,\vdots \\[6pt]
x_n & = x_{n-1} - f(x_{n-1}) \frac{x_{n-1} - x_{n-2{f(x_{n-1}) - f(x_{n-2})}.
\end{align}
</math>
Convergence
The iterates <math>x_n</math> of the secant method converge to a root of <math>f</math> if the initial values <math>x_0</math> and <math>x_1</math> are sufficiently close to the root and <math>f</math> is well-behaved. When <math>f</math> is twice continuously differentiable and the root in question is a simple root, i.e., it has multiplicity 1, the order of convergence is the golden ratio <math>\varphi = (1+\sqrt{5})/2 \approx 1.618.</math> This convergence is superlinear but subquadratic.
If the initial values are not close enough to the root or <math>f</math> is not well-behaved, then there is no guarantee that the secant method converges at all. There is no general definition of "close enough", but the criterion for convergence has to do with how "wiggly" the function is on the interval between the initial values. For example, if <math>f</math> is differentiable on that interval and there is a point where <math>f' = 0</math> on the interval, then the algorithm may not converge.
Comparison with other root-finding methods
The secant method does not require or guarantee that the root remains bracketed by sequential iterates, like the bisection method does, and hence it does not always converge. The false position method (or ) uses the same formula as the secant method. However, it does not apply the formula on <math>x_{n-1}</math> and <math>x_{n-2}</math>, like the secant method, but on <math>x_{n-1}</math> and on the last iterate <math>x_k</math> such that <math>f(x_k)</math> and <math>f(x_{n-1})</math> have a different sign. This means that the false position method always converges; however, only with a linear order of convergence. Bracketing with a super-linear order of convergence as the secant method can be attained with improvements to the false position method (see Regula falsi § Improvements in regula falsi) such as the ITP method or the Illinois method.
The recurrence formula of the secant method can be derived from the formula for Newton's method
:<math>x_n = x_{n-1} - \frac{f(x_{n-1})}{f'(x_{n-1})}</math>
by using the finite-difference approximation, for a small <math>\epsilon =x_{n-1} - x_{n-2} </math>:
<math>f'(x_{n-1}) = \lim_{\epsilon \rightarrow 0} \frac {f(x_{n-1})-f(x_{n-1} - \epsilon)}{\epsilon } \approx \frac{f(x_{n-1}) - f(x_{n-2})}{x_{n-1} - x_{n-2</math>
The secant method can be interpreted as a method in which the derivative is replaced by an approximation and is thus a quasi-Newton method.
If we compare Newton's method with the secant method, we see that Newton's method converges faster (order 2 against order the golden ratio φ ≈ 1.6).
Notes
See also
- False position method
References
External links
- Secant Method Notes, PPT, Mathcad, Maple, Mathematica, Matlab at Holistic Numerical Methods Institute