Lehmer-Schur algorithm
Encyclopedia
In mathematics
, the Lehmer–Schur algorithm (named after Derrick Henry Lehmer
and Issai Schur
) is a root-finding algorithm
extending the one-dimensional bracketing used by the bisection method
to find the roots of a function of one complex variable inside any rectangular region of the function's holomorphicity
(i.e., analyticity
).
The rectangle in question is quadrisected into four, congruent
quarter rectangles. The argument principle
is then applied to the boundary of each quarter to find the winding number
(about the origin) for the boundary. Given that the function is analytic
within each of these quarters, a nonzero winding number
N (always an integer) identifies N zeros of the function inside the quarter in question, each zero counted as many times as its multiplicity.
Analogously with the bisection method, the algorithm is then applied recursively to any quarter whose boundary has nonzero winding number to further refine the estimates of the zeros. The recursion is repeated until the zero-containing rectangles are either small enough that their centres give sufficiently accurate zero estimates or, alternatively, that another root-finding algorithm can be applied to the estimates to further refine them.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Lehmer–Schur algorithm (named after Derrick Henry Lehmer
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer was an American mathematician who refined Édouard Lucas' work in the 1930s and devised the Lucas–Lehmer test for Mersenne primes...
and Issai Schur
Issai Schur
Issai Schur was a mathematician who worked in Germany for most of his life. He studied at Berlin...
) is a root-finding algorithm
Root-finding algorithm
A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
extending the one-dimensional bracketing used by the bisection method
Bisection method
The bisection method in mathematics is a root-finding method which repeatedly bisects an interval and then selects a subinterval in which a root must lie for further processing. It is a very simple and robust method, but it is also relatively slow...
to find the roots of a function of one complex variable inside any rectangular region of the function's holomorphicity
Holomorphic function
In mathematics, holomorphic functions are the central objects of study in complex analysis. A holomorphic function is a complex-valued function of one or more complex variables that is complex differentiable in a neighborhood of every point in its domain...
(i.e., analyticity
Analytic function
In mathematics, an analytic function is a function that is locally given by a convergent power series. There exist both real analytic functions and complex analytic functions, categories that are similar in some ways, but different in others...
).
The rectangle in question is quadrisected into four, congruent
Congruence (geometry)
In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
quarter rectangles. The argument principle
Argument principle
In complex analysis, the argument principle determines the difference between the number of zeros and poles of a meromorphic function by computing a contour integral of the function's logarithmic derivative....
is then applied to the boundary of each quarter to find the winding number
Winding number
In mathematics, the winding number of a closed curve in the plane around a given point is an integer representing the total number of times that curve travels counterclockwise around the point...
(about the origin) for the boundary. Given that the function is analytic
Analytic function
In mathematics, an analytic function is a function that is locally given by a convergent power series. There exist both real analytic functions and complex analytic functions, categories that are similar in some ways, but different in others...
within each of these quarters, a nonzero winding number
Winding number
In mathematics, the winding number of a closed curve in the plane around a given point is an integer representing the total number of times that curve travels counterclockwise around the point...
N (always an integer) identifies N zeros of the function inside the quarter in question, each zero counted as many times as its multiplicity.
Analogously with the bisection method, the algorithm is then applied recursively to any quarter whose boundary has nonzero winding number to further refine the estimates of the zeros. The recursion is repeated until the zero-containing rectangles are either small enough that their centres give sufficiently accurate zero estimates or, alternatively, that another root-finding algorithm can be applied to the estimates to further refine them.
External links
- GAP Library, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
- "On program efficiency and algebraic complexity", Jan van LeeuwenJan van LeeuwenJan van Leeuwen is a Dutch computer scientist, a professor at the Department of Information and Computing Sciences at the Utrecht University....