In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Lehmer–Schur algorithm (named after
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer (February 23, 1905 – May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s and ...
and
Issai Schur
Issai Schur (10 January 1875 – 10 January 1941) was a Russian mathematician who worked in Germany for most of his life. He studied at the University of Berlin. He obtained his doctorate in 1901, became lecturer in 1903 and, after a stay at the ...
) is a
root-finding algorithm
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
for
complex polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...
s, extending the idea of enclosing roots like in the one-dimensional
bisection method
In mathematics, the bisection method is a root-finding method that applies to any continuous function for which one knows two values with opposite signs. The method consists of repeatedly bisecting the interval defined by these values and the ...
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
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
allows one to find the distribution of the roots of a complex polynomial with respect to the
unit circle
In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucl ...
in the complex plane.
It is based on two auxiliary polynomials, introduced by Schur.
For a complex polynomial
of
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
its ''reciprocal adjoint polynomial''
is defined by
and its ''Schur Transform''
by
:
where a bar denotes
complex conjugation
In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, (if a and b are real, then) the complex conjugate of a + bi is equal to a - ...
.
So, if
with
, then
,
with
leading zero-terms, if any, removed. The
coefficients
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves var ...
of
can therefore be directly expressed in those of
and, since one or more leading coefficients cancel,
has lower degree than
. The roots of
,
, and
are related as follows.
;Lemma
Let
be a complex polynomial and
.
*The roots of
, including their
multiplicities
In mathematics, the multiplicity of a member of a multiset is the number of times it appears in the multiset. For example, the number of times a given polynomial has a root at a given point is the multiplicity of that root.
The notion of multip ...
, are the images under
inversion
Inversion or inversions may refer to:
Arts
* , a French gay magazine (1924/1925)
* ''Inversion'' (artwork), a 2005 temporary sculpture in Houston, Texas
* Inversion (music), a term with various meanings in music theory and musical set theory
* ...
in the unit circle of the non-zero roots of
.
* If
, then
, and
share roots on the unit circle, including their multiplicities.
* If
, then
and
have the same number of roots inside the unit circle.
* If
, then
and
have the same number of roots inside the unit circle.
;Proof
Along the unit circle
we have
and
which, substituted into the formula
yields the identity
for
.
Also
implies
. From this and the definitions above the first two statements follow.
The other two statements are a consequence of
Rouché's theorem
Rouché's theorem, named after Eugène Rouché, states that for any two complex-valued functions and holomorphic inside some region K with closed contour \partial K, if on \partial K, then and have the same number of zeros inside K, where ...
applied on the unit circle to the functions
and
, where
is a polynomial that has as its roots the roots of
on the unit circle, with the same multiplicities. □
For a more accessible representation of the lemma,
let
, and
denote the number of roots of
inside, on, and outside the unit circle respectively and similarly for
.
Moreover let
be the difference in degree of
and
. Then the lemma implies that
if
and
if
(note the interchange of
and
).
Now consider the sequence of polynomials
, where
and
.
Application of the foregoing to each pair of consecutive members of this sequence gives the following result.
;Theorem
chur-Cohn testLet
be a complex polynomial with
and let
be the smallest number such that
. Moreover let
for
and
for
.
* All roots of
lie inside the unit circle if and only if
,
for
, and
.
* All roots of
lie outside the unit circle if and only if
for
and
.
* If
and if
for
(in increasing order) and
otherwise, then
has no roots on the unit circle and the number of roots of
inside the unit circle is
:
.
More generally, the distribution of the roots of a polynomial
with respect to an arbitrary circle in the complex plane, say one with centre
and radius
, can be found by application of the Schur-Cohn test to the 'shifted and scaled' polynomial
defined by
.
Not every scaling factor is allowed, however, for the Schur-Cohn test can be applied to the polynomial
only if none of the following equalities occur:
for some
or
while
. Now, the coefficients of the polynomials
are polynomials in
and the said equalities result in polynomial equations for
, which therefore hold for only finitely many values of
. So a suitable scaling factor can always be found, even arbitrarily close to
.
Lehmer's method
Lehmers method is as follows.
For a given complex polynomial
, with the Schur-Cohn test a circular disk can be found large enough to contain all roots of
. Next this disk can be covered with a set of overlapping smaller disks, one of them placed concentrically and the remaining ones evenly spread over the annulus yet to be covered. From this set, using the test again, disks containing no root of
can be removed. With each of the remaining disks this procedure of covering and removal can be repeated and so any number of times, resulting in a set of arbitrarily small disks that together contain all roots of
.
The merits of the method are that it consists of repetition of a single procedure and that all roots are found simultaneously, whether they are real or complex, single, multiple or clustered. Also deflation, i.e. removal of roots already found, is not needed and every test starts with the full-precision, original polynomial. And, remarkably, this polynomial has never to be evaluated.
However, the smaller the disks become, the more the coefficients of the corresponding 'scaled' polynomials will differ in relative magnitude. This may cause overflow or underflow of computer computations, thus limiting the radii of the disks from below and thereby the precision of the computed roots.
.
To avoid extreme scaling, or just for the sake of efficiency, one may start with testing a number of concentric disks for the number of included roots and thus reduce the region where roots occur to a number of narrow , concentric annuli. Repeating this procedure with another centre and combining the results, the said region becomes the union of intersections of such annuli.
Finally, when a small disk is found that contains a single root, that root may be further approximated using other methods, e.g.
Newton's method
In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valu ...
.
References
{{DEFAULTSORT:Lehmer-Schur Algorithm
Root-finding algorithms