Sidi's generalized secant method: Difference between revisions

Revision as of 21:39, 26 March 2013

Latest revision as of 18:34, 22 March 2025

(10 intermediate revisions by 9 users not shown)

Line 1:

'''Sidi's generalized secant 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 [[Avram Sidi]].<ref>

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

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

We call <math>\alpha</math> the root of <math>f</math>, that is, <math>f(\alpha)=0</math>. Sidi's method is an [[iterative method]] which generates a [[sequence]] <math>\{ x_i \}</math> of approximations of <math>\alpha</math>. Starting with ''k'' + 1 initial approximations <math>x_1 , \dots , x_{k+1}</math>, the approximation <math>x_{k+2}</math> is calculated in the first iteration, the approximation <math>x_{k+3}</math> is calculated in the second iteration, etc. Each iteration takes as input the last ''k'' + 1 approximations and the value of <math>f</math> at those approximations. Hence the ''n''th iteration takes as input the approximations <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 approximations <math>x_1 , \dots , x_{k+1}</math> one could carry out a few initializing iterations with a lower value of ''k''.

Line 18 ⟶ 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. Clearly, this method requires the function <math>f</math> to be evaluated only once per iteration; it requires [[Derivative-free optimization|no derivatives]] of <math>f</math>.

The iterative cycle is stopped if an appropriate stop-stopping 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 46 ⟶ 44:

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

</ref>

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

Line 57 ⟶ 54:

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{{root-finding algorithms]]}}

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