Sidi's generalized secant method is a
root-finding algorithm
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
, that is, a
numerical method
In numerical analysis, a numerical method is a mathematical tool designed to solve numerical problems. The implementation of a numerical method with an appropriate convergence check in a programming language is called a numerical algorithm.
Mathem ...
for solving
equations
In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in F ...
of the form
. The method was published
by
Avram Sidi.
[
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
]
The method is a generalization of the
secant method
In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function ''f''. The secant method can be thought of as a finite-difference approximation of ...
. Like the secant method, it is an
iterative method
In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived fr ...
which requires one evaluation of
in each iteration and no
derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. F ...
s of
. The method can converge much faster though, with an
order which approaches 2 provided that
satisfies the regularity conditions described below.
Algorithm
We call
the root of
, that is,
. Sidi's method is an iterative method which generates a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of approximations of
. Starting with ''k'' + 1 initial approximations
, the approximation
is calculated in the first iteration, the approximation
is calculated in the second iteration, etc. Each iteration takes as input the last ''k'' + 1 approximations and the value of
at those approximations. Hence the ''n''th iteration takes as input the approximations
and the values
.
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
one could carry out a few initializing iterations with a lower value of ''k''.
The approximation
is calculated as follows in the ''n''th iteration. A
polynomial of interpolation of
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
''k'' is fitted to the ''k'' + 1 points
. With this polynomial, the next approximation
of
is calculated as
with
the derivative of
at
. Having calculated
one calculates
and the algorithm can continue with the (''n'' + 1)th iteration. Clearly, this method requires the function
to be evaluated only once per iteration; it requires no derivatives of
.
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
.
To execute the algorithm effectively, Sidi's method calculates the interpolating polynomial
in its
Newton form.
Convergence
Sidi showed that if the function
is (''k'' + 1)-times
continuously differentiable
In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non-vertical tangent line at each interior point in its ...
in an
open interval
In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Other ...
containing
(that is,
),
is a simple root of
(that is,
) and the initial approximations
are chosen close enough to
, then the sequence
converges to
, meaning that the following
limit
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2019 ...
holds:
.
Sidi furthermore showed that
:
and that the sequence
converges to
of order
, i.e.
:
The order of convergence
is the
only positive root of the polynomial
:
We have e.g.
≈ 1.6180,
≈ 1.8393 and
≈ 1.9276. The order approaches 2 from below if ''k'' becomes large:
[
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
]
Related algorithms
Sidi's method reduces to the secant method if we take ''k'' = 1. In this case the polynomial
is the linear approximation of
around
which is used in the ''n''th iteration of the secant method.
We can expect that the larger we choose ''k'', the better
is an approximation of
around
. Also, the better
is an approximation of
around
. If we replace
with
in () we obtain that the next approximation in each iteration is calculated as
This is the
Newton–Raphson method
In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valu ...
. It starts off with a single approximation
so we can take ''k'' = 0 in (). It does not require an interpolating polynomial but instead one has to evaluate the derivative
in each iteration. Depending on the nature of
this may not be possible or practical.
Once the interpolating polynomial
has been calculated, one can also calculate the next approximation
as a solution of
instead of using (). For ''k'' = 1 these two methods are identical: it is the secant method. For ''k'' = 2 this method is known as
Muller's method
Muller's method is a root-finding algorithm, a numerical method for solving equations of the form ''f''(''x'') = 0. It was first presented by David E. Muller in 1956.
Muller's method is based on the secant method, which constructs at every iterat ...
.
For ''k'' = 3 this approach involves finding the roots of a
cubic function
In mathematics, a cubic function is a function of the form f(x)=ax^3+bx^2+cx+d
where the coefficients , , , and are complex numbers, and the variable takes real values, and a\neq 0. In other words, it is both a polynomial function of degree ...
, which is unattractively complicated. This problem becomes worse for even larger values of ''k''. An additional complication is that the equation
will in general have
multiple solutions and a prescription has to be given which of these solutions is the next approximation
. Muller does this for the case ''k'' = 2 but no such prescriptions appear to exist for ''k'' > 2.
References
Root-finding algorithms