Sidi's generalized secant method: Difference between revisions

Revision as of 11:31, 17 March 2013

Revision as of 13:25, 19 March 2013

Line 1:

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

<!-- EDIT BELOW THIS LINE -->

by prof. Avraham Sidi.<ref>

== Sidi's method ==

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

<ref>

Sidi, Avram, Applied Mathematics E-notes '''8''' (2008), 115-123, http://www.math.nthu.edu.tw/~amen/2008/070227-1.pdf

</ref><ref>

by prof. Avraham Sidi.

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

Sidi's</ref> methodIt is a generalization of the [[secant method]].

</ref>

Sidi's method is a generalization of the [[secant method]].

== Algorithm ==

We call <math>\alpha</math> the root of <math>f</math>, i.e.that is, <math>f(\alpha)=0</math>. Sidi's method is an [[iterative method]] which generates a [[sequence]] <math>\{ x_i \}</math> of estimates of <math>\alpha</math>. Starting with ''k'' + 1 initial estimates <math>x_1 , \dots , x_{k+1}</math>, the estimate <math>x_{k+2}</math> is calculated in the first iteration, the estimate <math>x_{k+3}</math> 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 <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 estimates <math>x_1 , \dots , x_{k+1}</math> one could carry out a few initializing iterations with a lower value of ''k''.

The estimate <math>x_{n+k+1}</math> is calculated as follows in the ''n''-th iteration. A [[polynomial]] <math>p_{n,k} (x)</math> of [[Degree of a polynomial|degree]] ''k'' is fitted to the ''k'' + 1 points <math>(x_n, f(x_n)), \dots (x_{n+k}, f(x_{n+k}))</math>. With this polynomial, the next approximation <math>x_{n+k+1}</math> 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}}}}

Line 30 ⟶ 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> (i.e.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. 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 51 ⟶ 44:

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 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]]. For ''k'' = 3 this approach involves finding the roots of a [[cubic function]], which is unattractively complicated. This problem aggravatesbecomes 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.

== References ==

<references/>

[[:Category:Root-finding algorithms]]

== Request review at [[WP:AFC]] ==

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