Secant method

This article is about a root-finding algorithm. See all root-finding algorithms

Definition

The secant method is a root-finding algorithm that makes successive point estimates for the value of a root of a continuous function. In general, the secant method is not guaranteed to converge towards a root, but under some conditions, it does. A slight variant of this method, called the false position method, functions very similarly to the bisection method.

Summary

Item	Value
Initial condition	we are given a function, typically a continuous function, and two initial guesses $x_0$ and $x_1$ for roots of the function.
Iterative step	At stage $n$ ($n\ge 2$) we compute $x_n$ in terms of $x_{n-1},x_{n-2},f(x_{n-1}),f(x_{n-2})$.
Convergence rate	The order of convergence is the golden ratio
Computational tools needed	Function evaluation at particular points, multiplication, subtraction, and division
Termination	We may terminate based on known bounds on the size of the derivative and the function value coming in sufficient proximity to the actual value.

Initial condition

The secant method requires two initial guesses for the root, say $x_0$ and $x_1$.

Iterative step

For $n\ge 2$, we define $x_n$ as the following affine combination of the previous two guesses $x_{n-1}$ and $x_{n-2}$

$x_n=\frac{x_{n-2}f(x_{n-1})-x_{n-1}f(x_{n-2})}{f(x_{n-1})-f(x_{n-2})}$

We can therefore think of $x_n$ as an affine linear combination of $x_{n-2}$ and $x_{n-1}$ with the following respective coefficients:

$\frac{f(x_{n-1})}{f(x_{n-1})-f(x_{n-2})},\frac{-f(x_{n-2})}{f(x_{n-1})-f(x_{n-2})}$

Geometrically, this can be interpreted as follows: we make a line through the points $(x_{n-2},f(x_{n-2}))$ and $(x_{n-1},f(x_{n-1}))$ in the $(x,f(x))$-plane, and define $x_n$ as the $x$-coordinate of the intersection of this line with the $x$-axis.