Sidi's generalized secant method: Difference between revisions

Revision as of 22:47, 19 March 2013

Revision as of 13:47, 23 March 2013

Line 1:

'''Sidi's method''' is a [[root-finding algorithm]], that is, a [[numerical method]] for solving [[equations]] of the form <math>f(x)=0</math> . The method was published

by Avraham Sidi.<ref>

Sidi, Avram, "Generalization Of The Secant Method For Nonlinear Equations", Applied Mathematics E-notes '''8''' (2008), 115-123115–123, http://www.math.nthu.edu.tw/~amen/2008/070227-1.pdf

</ref><ref>

The home page of Avraham Sidi at the Israel Institute of Technology is at [http://www.cs.technion.ac.il/people/asidi/ Avraham Sidi]

Line 17 ⟶ 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'' &nbsp;+ &nbsp;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 24 ⟶ 23:

== Convergence ==

Sidi showed that if the function <math>f</math> is (''k''&nbsp;+&nbsp;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> (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 36 ⟶ 35:

We have e.g. <math>\psi_1 = (1+\sqrt{5})/2</math> ≈ 1.6180, <math>\psi_2</math> ≈ 1.8393 and <math>\psi_3</math> ≈ 1.9276. The order approaches 2 from below if ''k'' becomes large: <math> \lim\limits_{k \to \infty} \psi_k = 2</math>

<ref name="muller">

Muller, David E., "A Method for Solving Algebraic Equations Using an Automatic Computer," Mathematical Tables and Other Aids to Computation '''10''' (1956), 208-215208–215

</ref>

Sidi's method has also been discussed

<ref>

Soleymani F. and Hosseinabadi V., "New Third- and Sixth-Order Derivative-Free Techniques for Nonlinear Equations", Journal of Mathematics Research '''3''' (2011), 107-112107–112

</ref>

in the context of an "efficiency index". This index weighs the convergence order of a method against the number of function evaluations per iterative step, the number being 1 in Sidi's case.

Line 52 ⟶ 51:

{{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-RaphsonNewton–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 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 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]] <ref name="muller"/>. 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 <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.