Lehmer–Schur algorithm: Difference between revisions

Revision as of 09:16, 15 August 2023

Revision as of 23:53, 4 September 2023

Line 56:

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