Lehmer–Schur algorithm

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. 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. This algorithm allows 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({ar {z}}^{-1})}}} and its Schurtransform T p {displaystyle Tp} by 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} eq 0} , then p ∗ ( z ) = a ¯ 0 z n + a ¯ 1 z n − 1 + ⋯ + a ¯ n {displaystyle p^{*}(z)={ar {a}}_{0}z^{n}+{ar {a}}_{1}z^{n-1}+cdots +{ar {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. Let p {displaystyle p} be a complex polynomial and δ = ( T p ) ( 0 ) {displaystyle delta =(Tp)(0)} . For z ≠ 0 {displaystyle z eq 0} we have p ∗ ( z ) = z n p ( z / | z | 2 ) ¯ {displaystyle p^{*}(z)=z^{n}{overline {p(z/|z|^{2})}}} and, in particular, | p ∗ ( z ) | = | p ( z ) | {displaystyle |p^{*}(z)|=|p(z)|} for | z | = 1 {displaystyle |z|=1} .Also δ ≠ 0 {displaystyle delta eq 0} implies | p ( 0 ) | ≠ | p ∗ ( 0 ) | {displaystyle |p(0)| eq |p^{*}(0)|} . From this and the definitions above the first two statements follow.The other two statements are a consequence of Rouché's theorem applied on the unit circle to the functions p ( 0 ) ¯ p ( z ) / r ( z ) {displaystyle {overline {p(0)}}p(z)/r(z)} and − p ∗ ( 0 ) ¯ p ∗ ( z ) / r ( z ) {displaystyle -{overline {p^{*}(0)}}p^{*}(z)/r(z)} , where r {displaystyle r} is a polynomial that has as its roots the roots of p {displaystyle p} on the unit circle, with the same multiplicities. □ For a more accessible representation of the lemma,let n p − , n p 0 {displaystyle n_{p}^{-},n_{p}^{0}} , and n p + {displaystyle n_{p}^{+}} denote the number of roots of p {displaystyle p} inside, on, and outside the unit circle respectively and similarly for T p {displaystyle Tp} .Moreover let d {displaystyle d} be the difference in degree of p {displaystyle p} and T p {displaystyle Tp} . Then the lemma implies that ( n p − , n p 0 , n p + ) = ( n T p − , n T p 0 , n T p + + d ) {displaystyle (n_{p}^{-},;n_{p}^{0},;n_{p}^{+})=(n_{Tp}^{-},;n_{Tp}^{0},;n_{Tp}^{+}+d)} if δ > 0 {displaystyle delta >0} and ( n p − , n p 0 , n p + ) = ( n T p + + d , n T p 0 , n T p − ) {displaystyle (n_{p}^{-},;n_{p}^{0},;n_{p}^{+})=(n_{Tp}^{+}+d,;n_{Tp}^{0},;n_{Tp}^{-})} if δ < 0 {displaystyle delta <0} (note the interchange of + {displaystyle ^{+}} and − {displaystyle ^{-}} ). Now consider the sequence of polynomials T k p {displaystyle T^{k}p} ( k = 0 , 1 , … ) {displaystyle (k=0,1,ldots )} , where T 0 p = p {displaystyle T^{0}p=p} and T k + 1 p = T ( T k p ) {displaystyle T^{k+1}p=T(T^{k}p)} . Application of the foregoing to each pair of consecutive members of this sequence gives the following result. Let p {displaystyle p} be a complex polynomial with T p ≠ 0 {displaystyle Tp eq 0} and let K {displaystyle K} be the smallest number such that T K + 1 p = 0 {displaystyle T^{K+1}p=0} . Moreover let δ k = ( T k p ) ( 0 ) {displaystyle delta _{k}=(T^{k}p)(0)} for k = 1 , … , K {displaystyle k=1,ldots ,K} and d k = deg ⁡ T k p {displaystyle d_{k}=deg T^{k}p} for k = 0 , … , K {displaystyle k=0,ldots ,K} .