Lipid IVA 4-amino-4-deoxy-L-arabinosyltransferase

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

We call $\alpha$ the root of $f$, that is, $f(\alpha )=0$. Sidi's method is an iterative method which generates a sequence $\{x_i\}$ of approximations of $\alpha$. Starting with k + 1 initial approximations $x_1,\dots ,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,\dots ,x_{n+k}$ and the values $f(x_n),\dots ,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,\dots ,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)),\dots (x_{n+k},f(x_{n+k}))$. With this polynomial, the next approximation $x_{n+k+1}$ of $\alpha$ is calculated as

with ${p_{n^{\prime },k}}^{\prime }(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 $\alpha$.

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 $\alpha$ (that is, $f\in C^{k+1}(I)$), $\alpha$ is a simple root of $f$ (that is, $f^{\prime }(\alpha )\ne 0$) and the initial approximations $x_1,\dots ,x_{k+1}$ are chosen close enough to $\alpha$, then the sequence $\{x_i\}$ converges to $\alpha$, meaning that the following limit holds: $\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}{x}_n=\alpha$.

Sidi furthermore showed that

$\underset{n\to \mathrm{\infty }}{\lim }\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^{\prime }(\alpha )},$

and that the sequence converges to $\alpha$ of order ${\psi }_k$, i.e.

$\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}\frac{|x_{n+1}-\alpha |}{|x_n-\alpha {|}^{{\psi }_k}}=|L{|}^{({\psi }_k-1)/k}$

The order of convergence ${\psi }_k$ is the only positive root of the polynomial

$s^{k+1}-s^k-s^{k-1}-\dots -s-1$

We have e.g. ${\psi }_1=(1+\sqrt{5})/2$ ≈ 1.6180, ${\psi }_2$ ≈ 1.8393 and ${\psi }_3$ ≈ 1.9276. The order approaches 2 from below if k becomes large: $\lim {\mathrm{\backslash limits}}_{k\to \mathrm{\infty }}{\psi }_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 $\alpha$ 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=\alpha$. Also, the better ${p_{n^{\prime },k}}^{\prime }(x)$ is an approximation of $f^{\prime }(x)$ around $x=\alpha$. If we replace ${p_{n^{\prime },k}}^{\prime }$ with $f^{\prime }$ in (Template:EquationNote) 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 (Template:EquationNote). It does not require an interpolating polynomial but instead one has to evaluate the derivative $f^{\prime }$ 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.