Lehmer–Schur algorithm

(Redirected from Lehmer-Schur Algorithm)

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

edit

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   and its Schur Transform   by

 

where a bar denotes complex conjugation.

So, if   with  , then  , 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.

Lemma

Let   be a complex polynomial and  .

  • The roots of  , including their multiplicities, are the images under inversion in the unit circle of the non-zero roots of  .
  • If  , then  , and   share roots on the unit circle, including their multiplicities.
  • If  , then   and   have the same number of roots inside the unit circle.
  • If  , then   and   have the same number of roots inside the unit circle.
Proof

For   we have   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   , 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  .

  • All roots of   lie inside the unit circle if and only if

 ,   for  , and  .

  • All roots of   lie outside the unit circle if and only if

  for   and  .

  • If   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

edit

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. [2] .[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.

References

edit
  1. ^ Cohn, A (1922). "Uber die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise". Math. Z. 14: 110–148. doi:10.1007/BF01215894. hdl:10338.dmlcz/102550. S2CID 123129925.
  2. ^ a b Henrici, Peter (1988). Applied and computational complex analysis. Volume I: Power series- integration-conformal mapping-location of zeros (Repr. of the orig., publ. 1974 by John Wiley \& Sons Ltd., Paperback ed.). New York etc.: John Wiley. pp. xv + 682. ISBN 0-471-60841-6.
  3. ^ Marden, Morris (1949). The geometry of the zeros of a polynomial in a complex variable. Mathematical Surveys. No. 3. New York: American Mathematical Society (AMS). p. 148.
  4. ^ Schur, I (1917). "Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind". Journal für die reine und angewandte Mathematik. 1917 (147): 205–232. doi:10.1515/crll.1917.147.205. S2CID 199546483.
  5. ^ Lehmer, D.H. (1961). "A machine method for solving polynomial equations". Journal of the Association for Computing Machinery. 8 (2): 151–162. doi:10.1145/321062.321064. S2CID 17667943.
  6. ^ Stewart, G.W.III (1969). "On Lehmer's method for finding the zeros of a polynomial". Math. Comput. 23 (108): 829–835. doi:10.2307/2004970. JSTOR 2004970.
  7. ^ Loewenthal, Dan (1993). "Improvement on the Lehmer-Schur root detection method". J. Comput. Phys. 109 (2): 164–168. Bibcode:1993JCoPh.109..164L. doi:10.1006/jcph.1993.1209.