Lehmer–Schur algorithm: Difference between revisions

Revision as of 06:29, 18 January 2019

Revision as of 12:42, 24 January 2019

Line 6:

===Schur-Cohn algorithm===

This [[algorithm]] allows to find the distribution of the zerosroots 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}}</ref>

Line 71:

<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 |pages=829–835 |doi=10.2307/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}}</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]].