Lehmer–Schur algorithm: Difference between revisions

Revision as of 00:45, 16 January 2019

Latest revision as of 16:10, 7 October 2024

(24 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Root-finding algorithm}}

In [[mathematics]], the '''Lehmer–Schur algorithm''' (named after [[Derrick Henry Lehmer]] and [[Issai Schur]]) is a [[root-finding algorithm]] for [[complex polynomial]]s, extending the idea of enclosing roots like in the one-dimensional [[bisection method]] to the complex plane. It uses the Schur–CohnSchur-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.

===Lehmer-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.<ref>{{cite journal |last1=Cohn |first1=A |title=Uber die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise. |journal=Math. Z. |date=1922 |volume=14 |pages=110–148 |doi=10.1007/BF01215894 |url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN266833020_0014&DMDID=dmdlog10|hdl=10338.dmlcz/102550 |s2cid=123129925 |hdl-access=free }}</ref><ref name="Henrici">{{cite book |last1=Henrici |first1=Peter |title=Applied and computational complex analysis. Volume I: Power series- integration-conformal mapping-___location of zeros. |date=1988 |publisher=New York etc.: John Wiley |isbn=0-471-60841-6 |pages=xv + 682 |edition= Repr. of the orig., publ. 1974 by John Wiley \& Sons Ltd., Paperback}}</ref><ref>{{cite book |last1=Marden |first1=Morris |title=The geometry of the zeros of a polynomial in a complex variable. |date=1949 |publisher=Mathematical Surveys. No. 3. New York: American Mathematical Society (AMS). |page=148 }}</ref> It is based on two auxiliary polynomials, introduced by Schur.<ref>{{cite journal |last1=Schur |first1=I |title=Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind. |journal=Journal für die reine und angewandte Mathematik |date=1917 |volume=1917 |issue=147 |pages=205–232 |doi=10.1515/crll.1917.147.205 |s2cid=199546483 |url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN00216860X}}</ref>

For a complex polynmialpolynomial <math>p</math> of [[degree of a polynomial|degree]] <math>n</math> its ''reciprocal adjoint polynomial'' <math>p^{*}</math> is defined by <math>p^{*}(z) = z^{n}\overline{p(\bar{z}^{-1})} </math> and its ''SchurtransformSchur Transform'' <math>Tp</math> by

In [[mathematics]], the '''Lehmer–Schur algorithm''' (named after [[Derrick Henry Lehmer]] and [[Issai Schur]]) is a [[root-finding algorithm]] for [[complex]] [[polynomial]]s, 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 to find the distribution of the zeros of a complex polynomial with respect to the [[unit circle]] in the complex plane.

<ref>{{cite journal |last1=Cohn |first1=A |title=Uber die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise. |journal=Math.Z. |date=1922 |volume=14 |pages=110–148 |doi=10.1007/BF01215894 |url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN266833020_0014&DMDID=dmdlog10}}</ref>

<ref name="Henrici">{{cite book |last1=Henrici |first1=Peter |title=Applied and computational complex analysis. Volume I: Power series- integration-conformal mapping-___location of zeros. |date=1988 |publisher=New York etc.: John Wiley |isbn=0-471-60841-6 |pages=xv + 682 |edition= Repr. of the orig., publ. 1974 by John Wiley \& Sons Ltd., Paperback ed.}}</ref>

<ref>{{cite book |last1=Marden |first1=Morris |title=The geometry of the zeros of a polynomial in a complex variable. |date=1949 |publisher=Mathematical Surveys. No. 3. New York: American Mathematical Society (AMS). |page=148 }}</ref>

It is based on two auxiliary polynomials, introduced by Schur.<ref>{{cite journal |last1=Schur |first1=I |title=Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind. |journal=Journal für die reine und angewandte Mathematik (Crelle's Journal) |date=1917 |volume=1917 |issue=147 |pages=205–232 |doi=10.1515/crll.1917.147.205 |url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN00216860X}}</ref>

For a complex polynmial <math>p</math> of [[degree of a polynomial|degree]] <math>n</math> its ''reciprocal adjoint polynomial'' <math>p^{*}</math> is defined by <math>p^{*}(z) = z^{n}\overline{p(\bar{z}^{-1})} </math> and its ''Schurtransform'' <math>Tp</math> by

:<math>

Tp =\overline{p(0)}p-\overline{p^*(0)}p^*,

</math>

where a bar denotes [[complex conjugate|complex conjugation]].

So, if <math> p(z) = a_{n}z^{n}+\cdots+a_{1}z +a_{0} </math> with <math>a_n\neq 0</math>, then

Line 60 ⟶ 54:

Not every scaling factor is allowed, however, for the Schur-Cohn test can be applied to the polynomial <math>q</math> only if none of the following equalities occur: <math>T^{k}q(0)=0</math> for some <math>k=1,\ldots K</math> or <math>T^{K+1}q=0</math> while <math>d_K>0</math>. Now, the coefficients of the polynomials <math>T^{k}q</math> are polynomials in <math>\rho</math> and the said equalities result in polynomial equations for <math>\rho</math>, which therefore hold for only finitely many values of <math>\rho</math>. So a suitable scaling factor can always be found, even arbitrarily close to <math>1</math>.

===Lehmer's method===

Lehmers method is as follows.

<ref>{{cite journal |last1=Lehmer |first1=D.H. |title=A machine method for solving polynomial equations. |journal=J.Journal Assoc.of Comput.the Mach.Association for Computing Machinery |date=1961 |volume=8 |issue=2 |pages=151–162 |doi=10.1145/321062.321064|s2cid=17667943 |doi-access=free }}</ref>

For a given complex polynomial <math>p</math>, with the Schur-Cohn test a circular disk can be found large enough to contain all roots of <math>p</math>. 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 <math>p</math> 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 <math>p</math>.

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 allreadyalready found, is not needed and every test starts with the full-precision, original polynomial. AlsoAnd, remarkably, this polynomial has never to be evaluaredevaluated.

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.

<ref name="Henrici" />

.<ref>{{cite journal |last1=Stewart |first1=G.W.III |title=On Lehmer's method for finding the zeros of a polynomial. |journal=Math. Comput. |date=1969 |volume=23 |issue=108 |pages=829–835 |doi=10.2307/2004970|jstor=2004970 }}</ref>

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 zerosroots and thus reduce the region where zerosroots 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.

<ref>{{cite journal |last1=Loewenthal |first1=Dan |title=Improvement on the Lehmer-Schur root detection method. |journal=J. Comput. Phys. |date=1993 |volume=109 |issue=2 |pages=164–168 |doi=10.1006/jcph.1993.1209|bibcode=1993JCoPh.109..164L }}</ref>

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==

{{Empty section|date=January 2019}}

==References==

{{Reflist}}

[[Category:Root{{root-finding algorithms]]}}

{{DEFAULTSORT:Lehmer-Schur Algorithm}}

[[Category:Root-finding algorithms]]

[[Category:Polynomial factorization algorithms]]