en>Rich Farmbrough: remove Erik9bot category,outdated, tag and general fixes, removed Stub tag using Project:AWB

2009-12-18T06:33:16Z

remove Erik9bot category,outdated, tag and general fixes, removed Stub tag using Project:AWB

New page

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.

==The Lehmer method==
The Schur–Cohn test described below allows to determine if a polynomial has no roots in the unit disk and in some cases to determine the exact number of roots. The method proposed by Lehmer test for the presence of roots of a polynomial <math>p(z)</math> on a collection of disks <math>D(c,\rho)</math> in the complex plane by applying the Schur–Cohn test to the shifted and scaled polynomial <math>p(c+\rho z).</math>

Starting with ''c''=0 and ρ=1, the radius in increased or decreased by factors of 2 until the annulus <math>\rho\le|z|\le2\rho</math> is found to contain roots. Then the method is recursively applied to the 8 disks with center <math>c_k=\frac53\rho e^{i\frac{k\pi}4}</math>, <math>k=0,1,\dots,7</math> and initial radius <math>\rho</math> (originally <math>\frac56\rho</math>, which is slightly too small to cover the full annulus).

If after some recursions a small disk is found that contains only one root, this root is further approximated using [[Newton's method]] and then the polynomial is deflated by splitting off the corresponding linear factor. After that, the whole procedure is restarted.

===Schur transformation of polynomials===
Consider, as before, a polynomial with complex coefficients
:<math>
p(z)=a_n z^n+\dots+a_1 z+a_0.
</math>
Denote the reverse conjugate polynomial as <math>p^*(z)=z^n\bar p(z^{-1})=z^n\overline p(\bar z^{-1})</math>.
Then the Schur transform <math>Tp</math> of <math>p</math> is the polynomial
:<math>
(Tp)(z)=\bar a_0p(z)-a_n p^*(z).
</math>
Since the highest degree coefficients cancel, <math>\deg Tp<\deg p</math>, and the constant coefficient of <math>Tp</math> is
<math>\delta_1=(Tp)(0)=|a_0|^2-|a_n|^2.</math>

;Lemma
:If <math>\delta_1>0</math>, then <math>p</math> and <math>Tp</math> have the same number of roots inside the unit disk and on the unit circle.

:If <math>\delta_1<0</math>, then <math>p</math> has the same number of roots inside the unit disk as <math>Tp</math> (and <math>p^*</math>) has outside, and both have the same number of roots on the unit circle.

This result is a consequence of [[Rouché's theorem]].

===Schur–Cohn test===

Apply the Schur transform repeatedly, <math>T^{k+1}p=T(T^kp)</math>, let ''K'' be the first index with <math>T^{K+1}p=0</math>. Denote <math>d_k=\deg T^kp</math>, <math>d_{k+1}<d_k</math> and <math>\delta_k=(T^kp)(0)</math>.

;Theorem
:If <math>\delta_k>0</math> for all ''k'' = 1, 2, ..., ''K'', then <math>p</math> has no roots inside the unit disk.

:If <math>\delta_{\bar k}<0</math> exactly once, <math>\delta_k>0</math> for <math>k\ne \bar k</math>, then ''p'' has <math>d_{\bar k}</math> roots inside the unit disk.

The first follows from the root number preserving
property of the Schur transform. For the second, <math>T^{\bar k}p, \dots, T^Kp</math> have no roots inside the unit disk or on the unit circle. <math>T^{\bar k}p</math> has <math>d_{\bar k}=\deg T^{\bar k}p</math> roots outside the unit disk, so that <math>T^{\bar k-1}p</math> and thus also <math>T^{\bar k-2}p,\dots,Tp,p</math> have the same number of roots inside the unit disk.

==Variations on the subdivision idea==

===Wilf's global bisection algorithm===

The aim of this algorithm is to find the roots of a function of one complex variable inside any rectangular region of the function's [[Holomorphic function|holomorphicity]] (''i.e.'', [[Analytic function|analyticity]]).

The rectangle in question is quadrisected into four, [[Congruence (geometry)|congruent]] quarter rectangles. For each quarter, the image of the boundary is a curve in the complex plane. The [[argument principle]] is then applied to this path to find the [[winding number]] about the origin. Given that the function is [[Analytic function|analytic]] within each of these quarters, a nonzero [[winding number]] ''N'' (always an integer) identifies ''N'' zeros of the function inside the quarter in question by [[Rouché's theorem]], each zero counted as many times as its [[Multiplicity (mathematics)|multiplicity]].

Analogously with the bisection method, the algorithm is then applied recursively to any quarter whose boundary has nonzero winding number to further refine the estimates of the zeros. The recursion is repeated until the zero-containing rectangles are either small enough that their centres give sufficiently accurate zero estimates or, alternatively, that another root-finding algorithm can be applied to the estimates to further refine them.

==References==
{{Cite check|date=June 2011}}
* {{citation
|author= D. H. Lehmer,
|title=A Machine Method for Solving Polynomial Equations
|journal=Journal of the ACM
|volume=8,
|number=2
|date=April 1961
|pages=151–162
|doi=10.1145/321062.321064
}}

* {{citation
|author=Herbert S. Wilf
|title=A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane"
|journal=Journal of the ACM
|year=1978
|volume=25
|number=3
|doi=10.1145/322077.322084
}}

* {{citation
|author=Acton, Foreman S.
|title=Numerical Methods That Work
|year=1970
|publication-date=1990
|edition=corrected
|place=Washington
|publisher=[[Mathematical Association of America]]
|chapter=Chapter 7
|isbn=0-88385-450-3}}.

* {{citation
|author1=W. H. Press
|author2=B. P. Flannery
|author3=S. A. Teukolsky
|author4=W. T. Vetterling
|title=[[Numerical Recipes|Numerical Recipes in C: The Art of Scientific Computing]]
|publisher=Cambridge University Press
|year=1992
|chapter=9.5 Roots of Polynomials
|page=369
|ISBN=0-521-43108-5
|url=http://www.nrbook.com/a/bookcpdf.html
}}

==External links==
* [https://svn.ece.lsu.edu/svn/dmk/trunk/benchmarks/simtools/scpu2k/gap/polystff.g GAP Library, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany]
* [[Jan van Leeuwen]] (January 1979): [http://www.cs.uu.nl/research/techreps/repo/CS-1979/1979-01.pdf "On program efficiency and algebraic complexity"] (or: how to compute the Schur transform of a complex polynomial). technical report RUU-CS-79~1. Department of Computer Science, University of Utrecht

{{DEFAULTSORT:Lehmer-Schur Algorithm}}
[[Category:Root-finding algorithms]]

Tidal tensor - Revision history

en>Rich Farmbrough: remove Erik9bot category,outdated, tag and general fixes, removed Stub tag using Project:AWB