Lehmer–Schur algorithm

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.

References

• D. H. Lehmer, (1961), "A Machine Method for Solving Polynomial Equations", Journal of the ACM, 8, (2): 151–162, doi:10.1145/321062.321064 {{citation}}: Unknown parameter |month= ignored (help)CS1 maint: extra punctuation (link)

• Herbert S. Wilf (1978), "A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane"", Journal of the ACM, 25 (3), doi:10.1145/322077.322084

• Acton, Foreman S. (1970), "Chapter 7", Numerical Methods That Work (corrected ed.), Washington: Mathematical Association of America (published 1990), ISBN 0-88385-450-3.

• W. H. Press; B. P. Flannery; S. A. Teukolsky; W. T. Vetterling (1992), "9.5 Roots of Polynomials", [[Numerical Recipes|Numerical Recipes in C: The Art of Scientific Computing]], Cambridge University Press, p. 369, ISBN 0-521-43108-5 {{citation}}: URL–wikilink conflict (help)

External links

• GAP Library, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
• Jan van Leeuwen (January 1979): "On program efficiency and algebraic complexity" (or: how to compute the Schur transform of a complex polynomial). technical report RUU-CS-79~1. Department of Computer Science, University of Utrecht