Lehmer–Schur algorithm: Difference between revisions

Revision as of 19:36, 11 February 2019

Revision as of 11:46, 26 February 2019

Line 9:

<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 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 ''Schurtransform'' <math>Tp</math> by

:<math>

Line 64:

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 already found, is not needed and every test starts with the full-precision, original polynomial. And, 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.