Sidi's generalized secant method: Difference between revisions

Revision as of 22:34, 19 March 2013

Revision as of 22:41, 19 March 2013

Line 16:

{{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}</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.

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>.

Line 23:

== Convergence ==

Sidi showed that if the function <math>f</math> is (''k''+1)-times [[Smooth function|continuously differentiable]] in an [[open interval]] <math>I</math> containing <math>\alpha</math> (that is, <math>f \in C^{k+1} (I)</math>), and the initial estimates <math>x_1 , \dots , x_{k+1}</math> are chosen close enough to <math>\alpha</math>, then the sequence <math>\{ x_i \}</math> converges to <math>\alpha</math> (i.e.meaning the following [[Limit of a sequence|limit]] holds: <math>\lim\limits_{n \to \infty} x_n = \alpha</math>).

Sidi furthermore showed that the sequence [[Rate of convergence|converges]] to <math>\alpha</math> of order <math>\psi_k</math>, i.e.

Line 45:

== 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