Sidi's generalized secant method: Difference between revisions

Revision as of 15:15, 27 March 2013

Revision as of 21:30, 14 August 2013

Line 4:

</ref><ref>

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

</ref>

The method is a generalization of the [[secant method]]. Like the secant method, it is an [[iterative method]] which requires one evaluation of <math>f</math> in each iteration and no [[Derivative|derivativesderivative]]s of <math>f</math>. The method can converge much faster though, with an [[Rate of convergence|order]] which approaches 2 provided that <math>f</math> satisfies the regularity conditions described below.

== Algorithm ==

Line 20:

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. Clearly, this method requires the function <math>f</math> to be evaluated only once per iteration; it requires no derivatives of <math>f</math>.

The iterative cycle is stopped if an appropriate stop-criterion is met. Typically the criterion is that the last calculated approximation 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]].

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

<references/>

[[Category:Root-finding algorithms]]

<!-- This will add a notice to the bottom of the page and won't blank it! The new template which says that your draft is waiting for a review will appear at the bottom; simply ignore the old (grey) drafted templates and the old (red) decline templates. A bot will update your article submission. Until then, please don't change anything in this text box and press "Save page". -->

[[Category:Root-finding algorithms]]