Lehmer–Schur algorithm: Difference between revisions

Revision as of 09:16, 15 August 2023

Latest revision as of 16:10, 7 October 2024

(7 intermediate revisions by 6 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-Cohn test to test increasingly smaller disks for the presence or absence of roots.

Line 23 ⟶ 24:

;Proof

Along the unit circleFor <math>|z| =\neq 10</math> we have <math>1/\overline{z} = z</math> and <math>|z^n| = 1</math> which, substituted into the formula <math>p^{*}(z) = z^{n} \overline{p(\bar{z}/|z|^{-1}2)} </math> yieldsand, thein identityparticular,

<math>|p^*(z)| = |p(z)|</math> for <math>|z|=1</math>.

Also <math>\delta \neq 0</math> implies <math>|p(0)| \neq |p^*(0)|</math>. From this and the definitions above the first two statements follow.

Line 56 ⟶ 57:

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

Line 64 ⟶ 65:

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

Line 71 ⟶ 72:

{{Reflist}}

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

{{DEFAULTSORT:Lehmer-Schur Algorithm}}

[[Category:Root-finding algorithms]]

[[Category:Polynomial factorization algorithms]]