Content deleted Content added
No edit summary |
m task, replaced: Math.Z. → Math. Z. |
||
Line 1:
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.
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.
This [[algorithm]] allows 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}}</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>
Line 60:
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>.
Lehmers method is as follows.
| |||