Sidi's generalized secant method: Difference between revisions

Revision as of 20:26, 15 March 2013

Latest revision as of 18:34, 22 March 2025

(32 intermediate revisions by 11 users not shown)

Line 1:

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

{{User sandbox}}

by [[Avram Sidi]].<ref>

<!-- EDIT BELOW THIS LINE -->

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

== Sidi's method ==

Sidi's method is a [[root-finding algorithm]], i.e. a numerical method for solving equations of the form ''f''(''x'') = 0. 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>

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]

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

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''<sub>''i''x_i \}</submath> } of estimatesapproximations of α<math>\alpha</math>. Starting with ''k'' + 1 initial estimatesapproximations ''x''<sub>1</submath>x_1 , ...\dots , ''x''<sub>''x_{k''+1}</submath>, the estimateapproximation ''x''<submath>''x_{k''+2}</submath> is calculated in the first iteration, the estimateapproximation ''x''<submath>''x_{k''+3}</submath> is calculated in the second iteration, etc. Each iteration takes as input the last ''k'' + 1 estimatesapproximations and the value of ''<math>f''</math> forat those estimatesapproximations. Hence the ''n''-th iteration takes as input the estimatesapproximations ''x''<sub>''n''</submath>x_n , ...\dots , ''x''<sub>''x_{n''+''k''}</submath> and the values ''<math>f''(''x''_''n''x_n) ,... \dots , ''f''(''x''<sub>''x_{n''+''k''})</submath>).

The number ''k'' must be 1 or larger: ''k'' = 1, 2, 3, .... It remains fixed during the execution of the algorithm,. althoughIn inorder someto variations ofobtain the algorithmstarting itapproximations can<math>x_1 grow, from\dots e.g., x_{k = +1}</math> forone thecould firstcarry iterationout toa kfew =initializing 2iterations forwith thea secondlower iterationvalue etc,of until it reaches its fixed value''k''.

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

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

with ''p’ '' _''n'',''k''(''x''_''n''+''k'') the derivative of ''p'' _''n'',''k'' at ''x''_''n''+''k''.

The iterative cycle is stopped if an appropriate 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]].

== 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>), <math>\alpha</math> is a simple root of <math>f</math> (that is, <math>f'(\alpha) \neq 0</math>) and the initial approximations <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 that the following [[Limit of a sequence|limit]] holds: <math>\lim\limits_{n \to \infty} x_n = \alpha</math>.

Sidi furthermore showed that

:<math> \lim_{n\to\infty} \frac{x_{n +1}-\alpha}{\prod^k_{i=0}(x_{n-i}-\alpha)} = L = \frac{(-1)^{k+1}} {(k+1)!}\frac{f^{(k+1)}(\alpha)}{f'(\alpha)}, </math>

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

:<math> \lim\limits_{n \to \infty} \frac{|x_{n+1}-\alpha|}{|x_n-\alpha|^{\psi_k}} = |L|^{(\psi_k-1)/k} </math>

The order of convergence <math>\psi_k</math> is the [[Descartes's rule of signs|only positive root]] of the polynomial

:<math> s^{k+1} - s^k - s^{k-1} - \dots - s - 1 </math>

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

Traub, J.F., "Iterative Methods for the Solution of Equations", Prentice Hall, Englewood Cliffs, N.J. (1964)

</ref>

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

{{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–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/>

{{root-finding algorithms}}

[[Category:Root-finding algorithms]]