Sidi's generalized secant method: Difference between revisions

Revision as of 21:30, 14 August 2013

Revision as of 15:50, 26 April 2014

Line 10:

== Algorithm ==

We call <math>\alpha</math> the root of <math>f</math>, that is, <math>f(\alpha)=0</math>. Sidi's method is an [[iterative method]] which generates a [[sequence]] <math>\{ x_i \}</math> of approximations of <math>\alpha</math>. Starting with ''k'' + 1 initial approximations <math>x_1 , \dots , x_{k+1}</math>, the approximation <math>x_{k+2}</math> is calculated in the first iteration, the approximation <math>x_{k+3}</math> is calculated in the second iteration, etc. Each iteration takes as input the last ''k'' + 1 approximations and the value of <math>f</math> at those approximations. Hence the ''n''th iteration takes as input the approximations <math>x_n , \dots , x_{n+k}</math> and the values <math>f(x_n) , \dots , f(x_{n+k})</math>.

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

Line 48:

== Related algorithms ==

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

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

Line 56:

This is the [[Newton's method|Newton–Raphson method]]. It starts off with a single approximation <math>x_1</math> so we can take ''k'' = 0 in ({{EquationNote|2}}). It does not require an interpolating polynomial but instead one has to evaluate the derivative <math>f'</math> in each iteration. Depending on the nature of <math>f</math> this may not be possible or practical.

Once the interpolating polynomial <math>p_{n,k} (x)</math> has been calculated, one can also calculate the next approximation <math>x_{n+k+1}</math> as a solution of <math>p_{n,k} (x)=0</math> instead of using ({{EquationNote|1}}). For ''k''&nbsp;=&nbsp;1 these two methods are identical: it is the [[secant method]]. For ''k''&nbsp;=&nbsp;2 this method is known as [[Muller's method]].<ref name="muller"/> For ''k''&nbsp;=&nbsp;3 this approach involves finding the roots of a [[cubic function]], which is unattractively complicated. This problem becomes worse for even larger values of&nbsp;''k''. An additional complication is that the equation <math>p_{n,k} (x)=0</math> will in general have [[Properties of polynomial roots|multiple solutions]] and a prescription has to be given which of these solutions is the next approximation <math>x_{n+k+1}</math>. Muller does this for the case ''k''&nbsp;=&nbsp;2 but no such prescriptions appear to exist&nbsp;for ''k''&nbsp;>&nbsp;2.

== References ==