Lehmer–Schur algorithm explained
In mathematics, the Lehmer–Schur algorithm (named after Derrick Henry Lehmer and Issai Schur) is a root-finding algorithm for complex polynomials, 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.
Schur-Cohn algorithm
This algorithm allows one to find the distribution of the roots of a complex polynomial with respect to the unit circle in the complex plane.[1] [2] [3] It is based on two auxiliary polynomials, introduced by Schur.[4]
For a complex polynomial
of
degree
its
reciprocal adjoint polynomial
is defined by
p*(z)=zn\overline{p(\bar{z}-1)}
and its
Schur Transform
by
Tp=\overline{p(0)}p-\overline{p*(0)}p*,
where a bar denotes
complex conjugation.
So, if
with
, then
p*(z)=\bar{a}0zn+\bar{a}1zn-1+ … +\bar{a}n
,with
leading zero-terms, if any, removed. The
coefficients of
can therefore be directly expressed in those of
and, since one or more leading coefficients cancel,
has lower degree than
. The roots of
,
, and
are related as follows.
- LemmaLet
be a complex polynomial and
.
, including their
multiplicities, are the images under inversion in the unit circle of the non-zero roots of
.
, then
, and
share roots on the unit circle, including their multiplicities.
, then
and
have the same number of roots inside the unit circle.
, then
and
have the same number of roots inside the unit circle.
- ProofFor
we have
p*(z)=zn\overline{p(z/|z|2)}
and, in particular,
for
.Also
implies
. From this and the definitions above the first two statements follow.The other two statements are a consequence of
Rouché's theorem applied on the unit circle to the functions
and
-\overline{p*(0)}p*(z)/r(z)
, where
is a polynomial that has as its roots the roots of
on the unit circle, with the same multiplicities. □
For a more accessible representation of the lemma,let
, and
denote the number of roots of
inside, on, and outside the unit circle respectively and similarly for
.Moreover let
be the difference in degree of
and
. Then the lemma implies that
if
and
if
(note the interchange of
and
).
Now consider the sequence of polynomials
, where
and
. Application of the foregoing to each pair of consecutive members of this sequence gives the following result.
- Theorem[Schur-Cohn test]Let
be a complex polynomial with
and let
be the smallest number such that
. Moreover let
for
and
for
.
lie inside the unit circle if and only if
,
for
, and
.
lie outside the unit circle if and only if
for
and
.
and if
for
(in increasing order) and
otherwise, then
has no roots on the unit circle and the number of roots of
inside the unit circle is
.
More generally, the distribution of the roots of a polynomial
with respect to an arbitrary circle in the complex plane, say one with centre
and radius
, can be found by application of the Schur-Cohn test to the 'shifted and scaled' polynomial
defined by
.
Not every scaling factor is allowed, however, for the Schur-Cohn test can be applied to the polynomial
only if none of the following equalities occur:
for some
or
while
. Now, the coefficients of the polynomials
are polynomials in
and the said equalities result in polynomial equations for
, which therefore hold for only finitely many values of
. So a suitable scaling factor can always be found, even arbitrarily close to
.
Lehmer's method
Lehmers method is as follows.[5] For a given complex polynomial
, with the Schur-Cohn test a circular disk can be found large enough to contain all roots of
. Next this disk can be covered with a set of overlapping smaller disks, one of them placed concentrically and the remaining ones evenly spread over the annulus yet to be covered. From this set, using the test again, disks containing no root of
can be removed. With each of the remaining disks this procedure of covering and removal can be repeated and so any number of times, resulting in a set of arbitrarily small disks that together contain all roots of
.
The merits of the method are that it consists of repetition of a single procedure and that all roots are found simultaneously, whether they are real or complex, single, multiple or clustered. Also deflation, i.e. removal of roots already found, is not needed and every test starts with the full-precision, original polynomial. And, remarkably, this polynomial has never to be evaluated.
However, the smaller the disks become, the more the coefficients of the corresponding 'scaled' polynomials will differ in relative magnitude. This may cause overflow or underflow of computer computations, thus limiting the radii of the disks from below and thereby the precision of the computed roots..[6] To avoid extreme scaling, or just for the sake of efficiency, one may start with testing a number of concentric disks for the number of included roots and thus reduce the region where roots occur to a number of narrow, concentric annuli. Repeating this procedure with another centre and combining the results, the said region becomes the union of intersections of such annuli.[7] Finally, when a small disk is found that contains a single root, that root may be further approximated using other methods, e.g. Newton's method.
Notes and References
- Cohn . A . Uber die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise. . Math. Z. . 1922 . 14 . 110–148 . 10.1007/BF01215894 . 10338.dmlcz/102550 . 123129925 . free .
- Book: Henrici . Peter . Applied and computational complex analysis. Volume I: Power series- integration-conformal mapping-location of zeros. . 1988 . New York etc.: John Wiley . 0-471-60841-6 . xv + 682 . Repr. of the orig., publ. 1974 by John Wiley \& Sons Ltd., Paperback.
- Book: Marden . Morris . The geometry of the zeros of a polynomial in a complex variable. . 1949 . Mathematical Surveys. No. 3. New York: American Mathematical Society (AMS). . 148 .
- Schur . I . Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind. . Journal für die reine und angewandte Mathematik . 1917 . 1917 . 147 . 205–232 . 10.1515/crll.1917.147.205 . 199546483 .
- Lehmer . D.H. . A machine method for solving polynomial equations. . Journal of the Association for Computing Machinery . 1961 . 8 . 2 . 151–162 . 10.1145/321062.321064. 17667943 . free .
- Stewart . G.W.III . On Lehmer's method for finding the zeros of a polynomial. . Math. Comput. . 1969 . 23 . 108 . 829–835 . 10.2307/2004970. 2004970 .
- Loewenthal . Dan . Improvement on the Lehmer-Schur root detection method. . J. Comput. Phys. . 1993 . 109 . 2 . 164–168 . 10.1006/jcph.1993.1209. 1993JCoPh.109..164L .