Sidi's generalized secant method

Algorithm

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.

Convergence

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

and that the sequence converges to α of order ψ k , i.e.

The order of convergence ψ k is the only positive root of the polynomial

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

Related algorithms

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.