Sidi's generalized secant method
This sandbox is in the article namespace. Either move this page into your userspace, or remove the {{User sandbox}} template.
Sidi's method
Sidi's method is a root-finding algorithm, i.e. a numerical method for solving equations of the form f(x) = 0. The method was published [1] by prof. Avraham Sidi. [2]
Sidi's method is a generalization of the secant method.
Algorithm
We call α the root of f, i.e. f(α) = 0. Sidi's method is an iterative method which generates a sequence { xi } of estimates of α. Starting with k+1 initial estimates x1, ... , xk+1, the estimate xk+2 is calculated in the first iteration, the estimate xk+3 is calculated in the second iteration, etc. Each iteration takes as input the last k + 1 estimates and the value of f for those estimates. Hence the n-th iteration takes as input the estimates xn, ... , xn+k and the values f(xn),..., f(xn+k).
The number k must be 1 or larger: k = 1, 2, 3, .... It remains fixed during the execution of the algorithm, although in some variations of the algorithm it can grow from e.g. k = 1 for the first iteration to k = 2 for the second iteration etc, until it reaches its fixed value.
The estimate xn+k+1 is calculated as follows in the n-th iteration. A polynomial p n, k (x) of degree k is fitted to the k + 1 points (xn, f(xn)), …, (xn+k, f(xn+k)). The next approximation xn+k+1 of α is calculated as
with p’ n,k(xn+k) the derivative of p n,k at xn+k.
References
- ^ Sidi, Avram, Applied Mathematics E-notes 8 (2008), 115-123, http://www.math.nthu.edu.tw/~amen/2008/070227-1.pdf
- ^ The home page of Avraham Sidi at the Israel Institute of Technology is at Avraham Sidi