Sidi's generalized secant method: Difference between revisions

Revision as of 20:32, 15 March 2013

Revision as of 23:19, 15 March 2013

Line 16:

== Algorithm ==

We call α<math>\alpha</math> the root of ''<math>f''</math>, i.e. ''<math>f''(''α''\alpha) = 0</math>. Sidi's method is an iterative method which generates a sequence <math>\{ ''x''<sub>''i''x_i \}</submath> } of estimates of α<math>\alpha</math>. Starting with ''k'' + 1 initial estimates ''x''<sub>1</submath>x_1 , ...\dots , ''x''<sub>''x_{k''+1}</submath>, the estimate ''x''<submath>''x_{k''+2}</submath> is calculated in the first iteration, the estimate ''x''<submath>''x_{k''+3}</submath> is calculated in the second iteration, etc. Each iteration takes as input the last ''k'' + 1 estimates and the value of ''<math>f''</math> for those estimates. Hence the ''n''-th iteration takes as input the estimates ''x''<sub>''n''</submath>x_n , ...\dots , ''x''<sub>''x_{n''+''k''}</submath> and the values ''<math>f''(''x''_''n''x_n) ,... \dots , ''f''(''x''<sub>''x_{n''+''k''})</submath>).

The number ''k'' must be 1 or larger: ''k'' = 1, 2, 3, .... It remains fixed during the execution of the algorithm,. althoughIn inorder someto variations ofobtain the algorithmstarting itestimates can<math>x_1 grow, from\dots e.g., x_{k = +1}</math> forone thecould firstcarry iterationout toa kfew =initializing 2iterations forwith thea secondlower iterationvalue etc,of until it reaches its fixed value''k''.

The estimate ''x''<submath>''x_{n''+''k''+1}</submath> is calculated as follows in the ''n''-th iteration. A [[polynomial ''p'']] <submath>''p_{n'', ''k''} (x)</submath> (''x'')of [[Degree of a polynomial|degree]] ''k'' is fitted to the ''k'' + 1 points (''x''<sub>''n''</submath>(x_n, ''f''(''x''_''n''x_n)), …,\dots (''x''_{''x_{n''+''k''}}, ''f''(''x''<sub>''x_{n''+''k''}))</submath>)). TheWith this polynomial, the next approximation ''x''<submath>''x_{n''+''k''+1 }</submath> of α<math>\alpha</math> is calculated as

{{NumBlk|:|<math> x_{n+k+1} = x_{n+k} - \frac{f(x_{n+k})}{p_{n,k}'(x_{n+k})} </math>|{{EquationRef|1}}}}

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

with ''p’ '' _''n'',''k''(''x''_''n''+''k'') the derivative of ''p'' _''n'',''k'' at ''x''_''n''+''k''.

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 <math>\alpha</math>.

To execute the algorithm effectively, Sidi's method calculates the interpolating polynomial <math>p_{n,k} (x)</math> in its [[Newton polynomial|Newton form]].

== 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 estimate in each iteration is calculated as

{{NumBlk|:|<math> x_{n+k+1} = x_{n+k} - \frac{f(x_{n+k})}{f'(x_{n+k})} </math>|{{EquationRef|2}}}}

This is the [[Newton's method|Newton-Raphson method]]. It starts off with a single estimate <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 calculate the derivative <math>f'(x_{n})</math> in the ''n''-th iteration.

Once the interpolating polynomial <math>p_{n,k} (x)</math> has been calculated, one can also calculate the next estimate <math>x_{n+k+1}</math> as a solution of <math>p_{n,k} (x)=0</math> instead of using {{EquationNote|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 <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 estimate <math>x_{n+k+1}</math>. Muller does this for the case ''k'' = 2 but no such prescriptions appear to exist for k > 2.

== References ==