In mathematics, the Lehmer–Schur algorithm (named after Derrick Henry Lehmer and Issai Schur) is a root-finding algorithm extending the idea of enclosing roots like in the one-dimensional bisection method to the complex plane. It uses the Schur–Cohn test to test increasingly smaller disks for the presence or absence of roots. Alternative methods like Wilf's algorithm apply different tests to differently shaped areas but keep the idea of descent by subdivision.
Contents
The Lehmer method
The Schur–Cohn test described below allows one to determine if a polynomial has no roots in the unit disk and in some cases to determine the exact number of roots. The method proposed by Lehmer test for the presence of roots of a polynomial
Starting with c=0 and ρ=1, the radius in increased or decreased by factors of 2 until the annulus
If after some recursions a small disk is found that contains only one root, this root is further approximated using Newton's method and then the polynomial is deflated by splitting off the corresponding linear factor. After that, the whole procedure is restarted.
Schur transformation of polynomials
Consider, as before, a polynomial with complex coefficients
Denote the reverse conjugate polynomial as
Since the highest degree coefficients cancel,
This result is a consequence of Rouché's theorem.
Schur–Cohn test
Apply the Schur transform repeatedly,
The first follows from the root number preserving property of the Schur transform. For the second,
Wilf's global bisection algorithm
The aim of this algorithm is 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. For each quarter, the image of the boundary is a curve in the complex plane. The argument principle is then applied to this path to find the winding number about the origin. 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 by Rouché's theorem, 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.