Sidi's generalized secant method is a root-finding algorithm, that is, a numerical method for solving equations of the form f ( x ) = 0 . The method was published by Avram Sidi.
The method is a generalization of the secant method. Like the secant method, it is an iterative method which requires one evaluation of f in each iteration and no derivatives of f . The method can converge much faster though, with an order which approaches 2 provided that f satisfies the regularity conditions described below.
We call α the root of f , that is, f ( α ) = 0 . Sidi's method is an iterative method which generates a sequence { x i } of approximations of α . Starting with k + 1 initial approximations x 1 , … , x k + 1 , the approximation x k + 2 is calculated in the first iteration, the approximation x k + 3 is calculated in the second iteration, etc. Each iteration takes as input the last k + 1 approximations and the value of f at those approximations. Hence the nth iteration takes as input the approximations x n , … , x n + k and the values f ( x n ) , … , f ( x n + k ) .
The number k must be 1 or larger: k = 1, 2, 3, .... It remains fixed during the execution of the algorithm. In order to obtain the starting approximations x 1 , … , x k + 1 one could carry out a few initializing iterations with a lower value of k.
The approximation x n + k + 1 is calculated as follows in the nth iteration. A polynomial of interpolation p n , k ( x ) of degree k is fitted to the k + 1 points ( x n , f ( x n ) ) , … ( x n + k , f ( x n + k ) ) . With this polynomial, the next approximation x n + k + 1 of α is calculated as
with p n , k ′ ( x n + k ) the derivative of p n , k at x n + k . Having calculated x n + k + 1 one calculates f ( x n + k + 1 ) and the algorithm can continue with the (n + 1)th iteration. Clearly, this method requires the function f to be evaluated only once per iteration; it requires no derivatives of f .
The iterative cycle is stopped if an appropriate stop-criterion is met. Typically the criterion is that the last calculated approximation is close enough to the sought-after root α .
To execute the algorithm effectively, Sidi's method calculates the interpolating polynomial p n , k ( x ) in its Newton form.
Sidi showed that if the function f is (k + 1)-times continuously differentiable in an open interval I containing α (that is, f ∈ C k + 1 ( I ) ), α is a simple root of f (that is, f ′ ( α ) ≠ 0 ) and the initial approximations x 1 , … , x k + 1 are chosen close enough to α , then the sequence { x i } converges to α , meaning that the following limit holds: lim n → ∞ x n = α .
Sidi furthermore showed that
lim n → ∞ x n + 1 − α ∏ i = 0 k ( x n − i − α ) = L = ( − 1 ) k + 1 ( k + 1 ) ! f ( k + 1 ) ( α ) f ′ ( α ) , and that the sequence converges to α of order ψ k , i.e.
lim n → ∞ | x n + 1 − α | | x n − α | ψ k = | L | ( ψ k − 1 ) / k The order of convergence ψ k is the only positive root of the polynomial
s k + 1 − s k − s k − 1 − ⋯ − s − 1 We have e.g. ψ 1 = ( 1 + 5 ) / 2 ≈ 1.6180, ψ 2 ≈ 1.8393 and ψ 3 ≈ 1.9276. The order approaches 2 from below if k becomes large: lim k → ∞ ψ k = 2
Sidi's method reduces to the secant method if we take k = 1. In this case the polynomial p n , 1 ( x ) is the linear approximation of f around α which is used in the nth iteration of the secant method.
We can expect that the larger we choose k, the better p n , k ( x ) is an approximation of f ( x ) around x = α . Also, the better p n , k ′ ( x ) is an approximation of f ′ ( x ) around x = α . If we replace p n , k ′ with f ′ in (1) we obtain that the next approximation in each iteration is calculated as
This is the Newton–Raphson method. It starts off with a single approximation x 1 so we can take k = 0 in (2). It does not require an interpolating polynomial but instead one has to evaluate the derivative f ′ in each iteration. Depending on the nature of f this may not be possible or practical.
Once the interpolating polynomial p n , k ( x ) has been calculated, one can also calculate the next approximation x n + k + 1 as a solution of p n , k ( x ) = 0 instead of using (1). For k = 1 these two methods are identical: it is the secant method. For k = 2 this method is known as Muller's method. For k = 3 this approach involves finding the roots of a cubic function, which is unattractively complicated. This problem becomes worse for even larger values of k. An additional complication is that the equation p n , k ( x ) = 0 will in general have multiple solutions and a prescription has to be given which of these solutions is the next approximation x n + k + 1 . Muller does this for the case k = 2 but no such prescriptions appear to exist for k > 2.
