
Sidi’s Generalized Secant Method For Finding Roots of Equations
by admin in Math, Statistics, and Optimization , MATLAB Family , Roots of Equation on June 14, 2019Sidi’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 f 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
- 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
- Traub, J.F., “Iterative Methods for the Solution of Equations”, Prentice Hall, Englewood Cliffs, N.J. (1964)
- Muller, David E., “A Method for Solving Algebraic Equations Using an Automatic Computer”, Mathematical Tables and Other Aids to Computation 10 (1956), 208–215
Share Now!