# Sidi's generalized secant method

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.

## Algorithm

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},\dots ,x_{k+1}$ one could carry out a few initializing iterations with a lower value of k.

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 $\alpha$ .

To execute the algorithm effectively, Sidi's method calculates the interpolating polynomial $p_{n,k}(x)$ in its Newton form.

## Convergence

Sidi furthermore showed that

$\lim _{n\to \infty }{\frac {x_{n+1}-\alpha }{\prod _{i=0}^{k}(x_{n-i}-\alpha )}}=L={\frac {(-1)^{k+1}}{(k+1)!}}{\frac {f^{(k+1)}(\alpha )}{f'(\alpha )}},$ $\lim \limits _{n\to \infty }{\frac {|x_{n+1}-\alpha |}{|x_{n}-\alpha |^{\psi _{k}}}}=|L|^{(\psi _{k}-1)/k}$ $s^{k+1}-s^{k}-s^{k-1}-\dots -s-1$ ## 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 $\alpha$ which is used in the nth iteration of the secant method.

This is the Newton–Raphson method. It starts off with a single approximation $x_{1}$ so we can take k = 0 in (Template:EquationNote). 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 (Template:EquationNote). 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.