Sidi’s Generalized Secant Method For Finding Roots of Equations

by admin in , , on June 14, 2019

Sidi’s generalized secant method is a root-finding algorithm, that is, a numerical method for solving equations of the form f(x) = 0 . The method was published by Avram Sidi.[1] The method is a generalization of the secant method. Like the secant method, it is an iterative method which requires one evaluation of f in each iteration and no derivatives of f. The method can converge much faster though, with an order which approaches 2 provided that f satisfies the regularity conditions described below.

Notes On This Method:

– Changing the K value might give you the second or third root …
– if you got a werdo answer for a specifice K, just repeat the calculation untile if fixes itself (this because we are using a random initial conditions equal to K value – means K = 3 –> we have 3 random initial conditons and as this number increase its hard to make this method converge), but for K = 2 you 100% will get a true answer.
– K starts from 2 and unlimited from the upper side.

Example On Using This Code

Input

f =@(x) x.^4 - 8.*x +1;        % Equation we interest to solve
N = 1e6;                       % Max. Number of iterations
err = eps;                     % Tollerance value

Output

RootX = 0.12503 , FX = 0 , Error = 2.7756e-17

Contents

  • Algorithm
  • Convergence
  • Related algorithms
  • References

Algorithm

We call alpha the root of f, that is, f(alpha) = 0. Sidi’s method is an iterative method which generates a sequence {x_(i)} of approximations of alpha. Starting with k + 1 initial approximations x_(1),… ,x_(k+1), the approximation x_(k+2) is calculated in the first iteration, the approximation x_(k+3) is calculated in the second iteration, etc. Each iteration takes as input the last k + 1 approximations and the value of f at those approximations. Hence the nth iteration takes as input the approximations x_(n),… ,x_(n+k) and the values f(x_(n)),… ,f(x_(n+k)).

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 x_(1),… ,x_(k+1) one could carry out a few initializing iterations with a lower value of k.

The approximation x_(n+k+1) is calculated as follows in the nth iteration. A polynomial of interpolation p_(n,k)(x) of degree k is fitted to the k + 1 points

With this polynomial, the next approximation x_(n+k+1)  of alpha is calculated as

(1)

with p’_{n,k}(x_(n+k)) the derivative of p_(n,k) at x_(n+k). Having calculated x_(n+k+1) one calculates f(x_(n+k+1))) and the algorithm can continue with the (n + 1)th iteration. Clearly, this method requires the function f to be evaluated only once per iteration; it requires no derivatives of f .

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 alpha. To execute the algorithm effectively, Sidi’s method calculates the interpolating polynomial p_(n,k)(x) in its Newton form.

Convergence

Sidi showed that if the function f is (k + 1)-times continuously differentiable in an open interval I containing alpha (that is, f in C^(k+1)(I)), alpha  is a simple root of f  (that is, f ‘(alpha) = 0) and the initial approximations x_(1),… ,x_(k+1) are chosen close enough to alpha, then the sequence x_(i) converges to alpha , meaning that the following limit holds:

.

Sidi furthermore showed that

and that the sequence converges to alpha of order psi_(k), i.e.

The order of convergence psi_(k) is the only positive root of the polynomial

We have e.g. psi_(i) = (1 + Sqrt(5)) / 2 ≈ 1.6180, psi _(2) ≈ 1.8393 and psi _(3) ≈ 1.9276. The order approaches 2 from below if k becomes large:

Related Algorithms

Sidi’s method reduces to the secant method if we take k = 1. In this case the polynomial p_(n,1)(x) is the linear approximation of around alpha which is used in the nth iteration of the secant method. We can expect that the larger we choose k, the better p_(n,k)(x) is an approximation of f(x) around x = alpha. Also, the better p’_(n,k)(x) is an approximation of f'(x) around x = alpha. If we replace p’_(n,k)(x) with  f’ in (1) we obtain that the next approximation in each iteration is calculated as

(2)

This is the Newton–Raphson method. It starts off with a single approximation x_(1) so we can take k = 0 in (2). It does not require an interpolating polynomial but instead one has to evaluate the derivative f’ in each iteration. Depending on the nature of f this may not be possible or practical.

Once the interpolating polynomial p_(n,k)(x) has been calculated, one can also calculate the next approximation x_(n+k+1) as a solution of p_(n,k)(x) = 0 instead of using (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.[3] 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 p_(n,k)(x) = 0 will in general have multiple solutions and a prescription has to be given which of these solutions is the next approximation x_(n+k+1). Muller does this for the case k = 2 but no such prescriptions appear to exist for k > 2.

References

  1. 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
  2. Traub, J.F., “Iterative Methods for the Solution of Equations”, Prentice Hall, Englewood Cliffs, N.J. (1964)
  3. Muller, David E., “A Method for Solving Algebraic Equations Using an Automatic Computer”, Mathematical Tables and Other Aids to Computation 10 (1956), 208–215

0 Sale

Share Now!

Release Information

  • Price
    :

    $14.99

  • Released
    :

    June 14, 2019

  • Last Updated
    :

    June 14, 2019

Share Your Valuable Opinions