In mathematics, the Lehmer–Schur algorithm (named after Derrick Henry Lehmer and Issai Schur) is a root-finding algorithm for complex polynomials, 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.
Schur-Cohn algorithm This algorithm allows one to find the distribution of the roots of a complex polynomial with respect to the unit circle in the complex plane. It is based on two auxiliary polynomials, introduced by Schur. For a complex polynomial p {\displaystyle p} of degree n {\displaystyle n} its reciprocal adjoint polynomial p ∗ {\displaystyle p^{*}} is defined by p ∗ ( z ) = z n p ( z ¯ − 1 ) ¯ {\displaystyle p^{*}(z)=z^{n}{\overline {p({\bar {z}}^{-1})}}} and its Schur Transform T p {\displaystyle Tp} by
T p = p ( 0 ) ¯ p − p ∗ ( 0 ) ¯ p ∗ , {\displaystyle Tp={\overline {p(0)}}p-{\overline {p^{*}(0)}}p^{*},}
where a bar denotes complex conjugation. So, if p ( z ) = a n z n + ⋯ + a 1 z + a 0 {\displaystyle p(z)=a_{n}z^{n}+\cdots +a_{1}z+a_{0}} with a n ≠ 0 {\displaystyle a_{n}\neq 0} , then
p ∗ ( z ) = a ¯ 0 z n + a ¯ 1 z n − 1 + ⋯ + a ¯ n {\displaystyle p^{*}(z)={\bar {a}}_{0}z^{n}+{\bar {a}}_{1}z^{n-1}+\cdots +{\bar {a}}_{n}} , with leading zero-terms, if any, removed. The coefficients of T p {\displaystyle Tp} can therefore be directly expressed in those of p {\displaystyle p} and, since one or more leading coefficients cancel, T p {\displaystyle Tp} has lower degree than p {\displaystyle p} . The roots of p {\displaystyle p} , p ∗ {\displaystyle p^{*}} , and T p {\displaystyle Tp} are related as follows.
Lemma Let p {\displaystyle p} be a complex polynomial and δ = ( T p ) ( 0 ) {\displaystyle \delta =(Tp)(0)} .
… excerpt ends here. Continue reading the full article.
