Lehmer–Schur algorithm: Difference between revisions

Revision as of 14:17, 22 December 2013

Revision as of 20:13, 3 January 2014

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-CohnSchur–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-CohnSchur–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-CohnSchur–Cohn test to the shifted and scaled polynomial <math>p(c+\rho z)</math>.

Starting with ''c''=0 and &rho;=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).

Line 30:

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

===Schur-CohnSchur–Cohn Testtest===

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''&nbsp;=&nbsp;1,&nbsp;2,&nbsp;...,&nbsp;''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.