Sidi's generalized secant method is a root-finding algorithm, that is, a numerical method for solving equations of the form
The method was published by Avram Sidi.
The method can converge much faster though, with an order which approaches 2 provided that
satisfies the regularity conditions described below.
Each iteration takes as input the last k + 1 approximations and the value of
Hence the nth iteration takes as input the approximations
It remains fixed during the execution of the algorithm.
In order to obtain the starting approximations
one could carry out a few initializing iterations with a lower value of k. The approximation
is calculated as follows in the nth iteration.
of degree k is fitted to the k + 1 points
and the algorithm can continue with the (n + 1)th iteration.
Clearly, this method requires the function
to be evaluated only once per iteration; it requires no derivatives of
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
Sidi showed that if the function
is (k + 1)-times continuously differentiable in an open interval
, meaning that the following limit holds:
Sidi furthermore showed that and that the sequence converges to
is the only positive root of the polynomial We have e.g.
The order approaches 2 from below if k becomes large:
which is used in the nth iteration of the secant method.
We can expect that the larger we choose k, the better
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
It does not require an interpolating polynomial but instead one has to evaluate the derivative
[3] 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
Muller does this for the case k = 2 but no such prescriptions appear to exist for k > 2.