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.

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)}

.

The roots of

p

∗

{\displaystyle p^{*}}

, including their multiplicities, are the images under inversion in the unit circle of the non-zero roots of

p

{\displaystyle p}

.