Sidi's generalized secant method

This sandbox is in the article namespace. Either move this page into your userspace, or remove the {{User sandbox}} template.

Sidi's method

Sidi's method is a root-finding algorithm, i.e. a numerical method for solving equations of the form ${\displaystyle f(x)=0}$  . The method was published ^[1] by prof. Avraham Sidi. ^[2]

Sidi's method is a generalization of the secant method.

Algorithm

We call ${\displaystyle \alpha }$  the root of ${\displaystyle f}$ , i.e. ${\displaystyle f(\alpha )=0}$ . Sidi's method is an iterative method which generates a sequence ${\displaystyle \{x_{i}\}}$  of estimates of ${\displaystyle \alpha }$ . Starting with k + 1 initial estimates ${\displaystyle x_{1},\dots ,x_{k+1}}$ , the estimate ${\displaystyle x_{k+2}}$  is calculated in the first iteration, the estimate ${\displaystyle x_{k+3}}$  is calculated in the second iteration, etc. Each iteration takes as input the last k + 1 estimates and the value of ${\displaystyle f}$  for those estimates. Hence the n-th iteration takes as input the estimates ${\displaystyle x_{n},\dots ,x_{n+k}}$  and the values ${\displaystyle 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 estimates ${\displaystyle x_{1},\dots ,x_{k+1}}$  one could carry out a few initializing iterations with a lower value of k.

The estimate ${\displaystyle x_{n+k+1}}$  is calculated as follows in the n-th iteration. A polynomial ${\displaystyle p_{n,k}(x)}$  of degree k is fitted to the k + 1 points ${\displaystyle (x_{n},f(x_{n})),\dots (x_{n+k},f(x_{n+k}))}$ . With this polynomial, the next approximation ${\displaystyle x_{n+k+1}}$  of ${\displaystyle \alpha }$  is calculated as

${\displaystyle x_{n+k+1}=x_{n+k}-{\frac {f(x_{n+k})}{p_{n,k}'(x_{n+k})}}}$

1

with ${\displaystyle p_{n,k}'(x_{n+k})}$  the derivative of ${\displaystyle p_{n,k}(x_{n+k})}$  at ${\displaystyle x_{n+k}}$ . Having calculated ${\displaystyle x_{n+k+1}}$  one calculates ${\displaystyle f(x_{n+k+1})}$  and the algorithm can continue with the (n + 1)-th iteration.

The iterative cycle is stopped if an appropriate stop-criterion is met. Typically the criterion is that the last calculated estimate is close enough to the sought-after root ${\displaystyle \alpha }$ .

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

Related algorithms

Sidi's method reduces to the secant method if we take k = 1. In this case the polynomial ${\displaystyle p_{n,1}(x)}$  is the linear approximation of ${\displaystyle f}$  around ${\displaystyle \alpha }$  which is used in the n-th iteration of the secant method.

We can expect that the larger we choose k, the better ${\displaystyle p_{n,k}(x)}$  is an approximation of ${\displaystyle f(x)}$  around ${\displaystyle x=\alpha }$ . Also, the better ${\displaystyle p_{n,k}'(x)}$  is an approximation of ${\displaystyle f'(x)}$  around ${\displaystyle x=\alpha }$ . If we replace ${\displaystyle p_{n,k}'}$  with ${\displaystyle f'}$  in (1) we obtain that the next estimate in each iteration is calculated as

${\displaystyle x_{n+k+1}=x_{n+k}-{\frac {f(x_{n+k})}{f'(x_{n+k})}}}$

2

This is the Newton-Raphson method. It starts off with a single estimate ${\displaystyle x_{1}}$  so we can take k = 0 in 2. It does not require an interpolating polynomial but instead one has to calculate the derivative ${\displaystyle f'(x_{n})}$  in the n-th iteration.

Once the interpolating polynomial ${\displaystyle p_{n,k}(x)}$  has been calculated, one can also calculate the next estimate ${\displaystyle x_{n+k+1}}$  as a solution of ${\displaystyle 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 cubic function, which is unattractively complicated. This problem aggravates for even larger values of k. An additional complication is that the equation ${\displaystyle 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 estimate ${\displaystyle x_{n+k+1}}$ . Muller does this for the case k = 2 but no such prescriptions appear to exist for k > 2.

References

1. Sidi, Avram, Applied Mathematics E-notes 8 (2008), 115-123, http://www.math.nthu.edu.tw/~amen/2008/070227-1.pdf
2. The home page of Avraham Sidi at the Israel Institute of Technology is at Avraham Sidi