In mathematics, a univariate polynomial of degree with real or complex coefficients has complex roots, if counted with their multiplicities. They form a multiset of points in the complex plane. This article concerns the geometry of these points, that is the information about their localization in the complex plane that can be deduced from the degree and the coefficients of the polynomial.
Some of these geometrical properties are related to a single polynomial, such as upper bounds on the absolute values of the roots, which define a disk containing all roots, or lower bounds on the distance between two roots. Such bounds are widely used for root-finding algorithms for polynomials, either for tuning them, or for computing their computational complexity.
Some other properties are probabilistic, such as the expected number of real roots of a random polynomial of degree with real coefficients, which is less than
1+ | 2\pi |
ln |
(n)
In this article, a polynomial that is considered is always denoted
p(x)=a0+a1x+ … +anxn,
a0,...,an
an ≠ 0
The roots of a polynomial of degree depend continuously on the coefficients. For simple roots, this results immediately from the implicit function theorem. This is true also for multiple roots, but some care is needed for the proof.
A small change of coefficients may induce a dramatic change of the roots, including the change of a real root into a complex root with a rather large imaginary part (see Wilkinson's polynomial). A consequence is that, for classical numeric root-finding algorithms, the problem of approximating the roots given the coefficients can be ill-conditioned for many inputs.
The complex conjugate root theorem states that if the coefficientsof a polynomial are real, then the non-real roots appear in pairs of the form .
It follows that the roots of a polynomial with real coefficients are mirror-symmetric with respect to the real axis.
This can be extended to algebraic conjugation: the roots of a polynomial with rational coefficients are conjugate (that is, invariant) under the action of the Galois group of the polynomial. However, this symmetry can rarely be interpreted geometrically.
Upper bounds on the absolute values of polynomial roots are widely used for root-finding algorithms, either for limiting the regions where roots should be searched, or for the computation of the computational complexity of these algorithms.
Many such bounds have been given, and the sharper one depends generally on the specific sequence of coefficient that are considered. Most bounds are greater or equal to one, and are thus not sharp for a polynomial which have only roots of absolute values lower than one. However, such polynomials are very rare, as shown below.
Any upper bound on the absolute values of roots provides a corresponding lower bound. In fact, if
an\ne0,
a0+a1x+ … +anxn,
an+an-1x+ … +a0xn,
Lagrange and Cauchy were the first to provide upper bounds on all complex roots.[1] Lagrange's bound is[2]
n-1 | ||
max\left\{1,\sum | \left| | |
i=0 |
ai | |
an |
\right|\right\},
1+max\left\{\left|
an-1 | |
an |
\right|,\left|
an-2 | |
an |
\right|,\ldots,\left|
a0 | |
an |
\right|\right\}
Lagrange's bound is sharper (smaller) than Cauchy's bound only when 1 is larger than the sum of all
\left| | ai |
an |
\right|
Both bounds result from the Gershgorin circle theorem applied to the companion matrix of the polynomial and its transpose. They can also be proved by elementary methods.
If is a root of the polynomial, and one has
n| | |
|a | |
n||z |
=
n-1 | |
\left|\sum | |
i=0 |
i\right| \le | |
a | |
iz |
n-1 | |
\sum | |
i=0 |
i| \le | |
|a | |
iz |
n-1 | |
\sum | |
i=0 |
n-1 | |
|a | |
i||z| |
.
Dividing by
n-1 | |
|a | |
n||z| |
,
|z|\le
n-1 | |
\sum | |
i=0 |
|ai| | |
|an| |
,
Similarly, for Cauchy's bound, one has, if,
n| | |
|a | |
n||z |
=
n-1 | |
\left|\sum | |
i=0 |
i\right| \le | |
a | |
iz |
n-1 | |
\sum | |
i=0 |
i| \le | |
|a | |
iz |
max|ai|\sum
n-1 | |
i=0 |
|z|i =
|z|n-1 | |
|z|-1 |
max|ai| \le
|z|n | |
|z|-1 |
max|ai|.
|an|(|z|-1)\lemax|ai|.
These bounds are not invariant by scaling. That is, the roots of the polynomial are the quotient by of the root of, and the bounds given for the roots of are not the quotient by of the bounds of . Thus, one may get sharper bounds by minimizing over possible scalings. This gives
min | |
s\inR+ |
\left(max\left\{
n-1 | ||
s,\sum | \left| | |
i=0 |
ai | |
an |
\right|si-n+1\right\}\right),
min | |
s\inR+ |
\left(s+max0\le\left(\left|
ai | |
an |
\right|si-n+1\right)\right),
Another bound, originally given by Lagrange, but attributed to Zassenhaus by Donald Knuth, is
2max\left\{\left|
an-1 | |
an |
\right|,\left|
an-2 | |
an |
\right|1/2,\ldots,\left|
a0 | |
an |
\right|1/n\right\}.
Let be the largest
\left| | ai |
an |
| ||||
\right| |
|ai| | |
|an| |
\leAn-i
0\lei<n.
n-1 | |
-a | |
i=0 |
aizi,
an,
n-1 | |
\begin{align} |z| | |
i=0 |
An-i
| ||||
|z| |
. \end{align}
|z|n\leA
|z|n | |
|z|-A |
,
|z|>A.
Lagrange improved this latter bound into the sum of the two largest values (possibly equal) in the sequence
\left[\left|
an-1 | |
an |
\right|,\left|
an-2 | |
an |
\right|1/2,\ldots,\left|
a0 | |
an |
\right|1/n\right].
Lagrange also provided the bound
\sumi\left|
ai | |
ai+1 |
\right|,
ai
Hölder's inequality allows the extension of Lagrange's and Cauchy's bounds to every -norm. The -norm of a sequence
s=(a0,\ldots,an)
\|s\|h=
n | |
\left(\sum | |
i=0 |
h\right) | |
|a | |
i| |
1/h,
\|s\|infty=
n} | |
style{max | |
i=0 |
|ai|.
If
1h+ | |||
|
1{|a | |
n|}\left\|(|a |
n|,\left\|(|an-1|,\ldots,|a0|\right)\|h\right)\|k.
For and, one gets respectively Cauchy's and Lagrange's bounds.
For, one has the bound
1{|a | |
n|}\sqrt{|a |
2+|a | |
n-1 |
|2+ …
2 | |
+|a | |
0| |
}.
Let be a root of the polynomial
n+a | |
p(x)=a | |
n-1 |
xn-1+ … +a1x+a0.
Setting
A=\left( | |an-1| |
|an| |
,\ldots,
|a1| | , | |
|an| |
|a0| | |
|an| |
\right),
z\le\left\|(1,\left\|A\right\|h\right)\|k.
If
|z|\le1,
|z|>1
Writing the equation as
| ||||
-z |
zn-1+ … +
a1 | z+ | |
an |
a0 | |
an |
,
|z|n\leq\|A\|h ⋅ \left\|(zn-1,\ldots,z,1)\right\|k.
If, this is
n\leq\|A\| | |
|z| | |
1max |
\left\{|z|n-1,\ldots,|z|,1\right\}
n-1 | |
=\|A\| | |
1|z| |
.
|z|\leqmax\{1,\|A\|1\}.
In the case, the summation formula for a geometric progression, gives
|z|n\leq\|A\|h\left(|z|k(n-1)+ … +|z|k
| ||||
+1\right) |
=\|A\|h\left(
|z|kn-1 | |
|z|k-1 |
| ||||
\right) |
\leq\|A\|h\left(
|z|kn | |
|z|k-1 |
| ||||
\right) |
.
|z|kn\leq
k | |
\left(\|A\| | |
h\right) |
|z|kn | |
|z|k-1 |
,
|z|k\leq
k. | |
1+\left(\|A\| | |
h\right) |
Thus, in all cases
|z|\leq\left\|\left(1,\|A\|h\right)\right\|k,
Many other upper bounds for the magnitudes of all roots have been given.[4]
Fujiwara's bound[5]
2max\left\{\left|
an-1 | |
an |
\right|,\left|
an-2 | |
an |
| ||||
\right| |
,\ldots,\left|
a1 | |
an |
| ||||
\right| |
,\left|
a0 | |
2an |
| ||||
\right| |
Kojima's bound is[6]
2max\left\{\left|
an-1 | \right|,\left| | |
an |
an-2 | |
an-1 |
\right|,\ldots,\left|
a0 | |
2a1 |
\right|\right\},
ai
Sun and Hsieh obtained another improvement on Cauchy's bound.[7] Assume the polynomial is monic with general term . Sun and Hsieh showed that upper bounds and could be obtained from the following equations.
d1=\tfrac{1}{2}\left((|an-1|-1)+\sqrt{(|an-1|-1)2+4a}\right), a=max\{|ai|\}.
is the positive root of the cubic equation
Q(x)=x3+(2-|an-1|)x2+(1-|an-1|-|an-2|)x-a, a=max\{|ai|\}
They also noted that .
The previous bounds are upper bounds for each root separately. Landau's inequality provides an upper bound for the absolute values of the product of the roots that have an absolute value greater than one. This inequality, discovered in 1905 by Edmund Landau,[8] has been forgotten and rediscovered at least three times during the 20th century.[9] [10] [11]
This bound of the product of roots is not much greater than the best preceding bounds of each root separately.[12] Let
z1,\ldots,zn
M(p)=|an|\prod
n | |
j=1 |
max(1,|zj|)
M(p)\le
n | |
\sqrt{\sum | |
k=0 |
2}. | |
|a | |
k| |
Surprisingly, this bound of the product of the absolute values larger than 1 of the roots is not much larger than the best bounds of one root that have been given above for a single root. This bound is even exactly equal to one of the bounds that are obtained using Hölder's inequality.
This bound is also useful to bound the coefficients of a divisor of a polynomial with integer coefficients:[13] if
q=
m | |
\sum | |
k=0 |
bkxk
|bm|\le|an|,
|bi| | |
|bm| |
\le\binommi
M(p) | |
|an| |
,
\binommi
|bi|\le\binommiM(p)\le\binommi
n | |
\sqrt{\sum | |
k=0 |
2}, | |
|a | |
k| |
m | |
\sum | |
i=0 |
|bi|\le2mM(p)\le2m
n | |
\sqrt{\sum | |
k=0 |
2}. | |
|a | |
k| |
Rouché's theorem allows defining discs centered at zero and containing a given number of roots. More precisely, if there is a positive real number and an integer such that
|ak|Rk>|a0|+ … +|ak-1|Rk-1+|ak+1|Rk+1+ … +|an|Rn,
|z|=R,
\begin{align} |a0&+ … +ak-1zk-1+ak+1zk+1+ … +anzn|\\ &\le|a0|+ … +|ak-1|Rk-1+|ak+1|Rk+1+ … +|an|Rn\\ &\le|ak|Rk\le|akzk|. \end{align}
p(z)
zk
The above result may be applied if the polynomial
hk(x)=|a0|+ … +|ak-1|xk-1
k+|a | |
-|a | |
k+1 |
|xk+1+ … +|an|xn.
In the remaining of the section, suppose that . If it is not the case, zero is a root, and the localization of the other roots may be studied by dividing the polynomial by a power of the indeterminate, getting a polynomial with a nonzero constant term.
For and, Descartes' rule of signs shows that the polynomial has exactly one positive real root. If
R0
Rn
R0\le|z|\leR1.
h0
hn,
For, Descartes' rule of signs implies that
hk(x)
Rk,1<Rk,2
|z|\leRk,1
|z|\geRk,2
Instead of explicitly computing
Rk,1
Rk,2,
Rk
hk(Rk)<0
Rk,1<Rk<Rk,2
Rk
Rh
Rk
Rh<|z|<Rk.
For computing
Rk,
h(x) | |
xk |
Rk
h(x) | |
xk |
h(x) | |
xk |
One can increase the number of existing
Rk
R0<R1<...<Rn
(Rk-1,Rk),
The Gershgorin circle theorem applies the companion matrix of the polynomial on a basis related to Lagrange interpolation to define discs centered at the interpolation points, each containing a root of the polynomial; see for details.
If the interpolation points are close to the roots of the roots of the polynomial, the radii of the discs are small, and this is a key ingredient of Durand–Kerner method for computing polynomial roots.
For polynomials with real coefficients, it is often useful to bound only the real roots. It suffices to bound the positive roots, as the negative roots of are the positive roots of .
Clearly, every bound of all roots applies also for real roots. But in some contexts, tighter bounds of real roots are useful. For example, the efficiency of the method of continued fractions for real-root isolation strongly depends on tightness of a bound of positive roots. This has led to establishing new bounds that are tighter than the general bounds of all roots. These bounds are generally expressed not only in terms of the absolute values of the coefficients, but also in terms of their signs.
Other bounds apply only to polynomials whose all roots are reals (see below).
To give a bound of the positive roots, one can assume
an>0
Every upper bound of the positive roots of
n | |
q(x)=a | |
nx |
+
n-1 | |
\sum | |
i=0 |
i | |
min(0,a | |
i)x |
n | |
p(x)=\sum | |
i=0 |
i | |
a | |
ix |
Applied to Cauchy's bound, this gives the upper bound
n-1 | |
1+{stylemax | |
i=0 |
Similarly, another upper bound of the positive roots is
2{max | |
aian<0 |
Other bounds have been recently developed, mainly for the method of continued fractions for real-root isolation.[14] [15]
If all roots of a polynomial are real, Laguerre proved the following lower and upper bounds of the roots, by using what is now called Samuelson's inequality.[16]
Let
n | |
\sum | |
k=0 |
akxk
- | an-1 |
nan |
\pm
n-1 | |
nan |
2 | |
\sqrt{a | |
n-1 |
-
2n | |
n-1 |
anan-2
For example, the roots of the polynomial
x4+5x3+5x2-5x-6=(x+3)(x+2)(x+1)(x-1)
-3.8118<- | 5 |
4 |
-
3 | \sqrt{ | |
4 |
35 | |
3 |
The root separation of a polynomial is the minimal distance between two roots, that is the minimum of the absolute values of the difference of two roots:
\operatorname{sep}(p)=min\{|\alpha-\beta| ; \alpha ≠ \betaandp(\alpha)=p(\beta)=0\}
The root separation is a fundamental parameter of the computational complexity of root-finding algorithms for polynomials. In fact, the root separation determines the precision of number representation that is needed for being certain of distinguishing distinct roots. Also, for real-root isolation, it allows bounding the number of interval divisions that are needed for isolating all roots.
For polynomials with real or complex coefficients, it is not possible to express a lower bound of the root separation in terms of the degree and the absolute values of the coefficients only, because a small change on a single coefficient transforms a polynomial with multiple roots into a square-free polynomial with a small root separation, and essentially the same absolute values of the coefficient. However, involving the discriminant of the polynomial allows a lower bound.
For square-free polynomials with integer coefficients, the discriminant is an integer, and has thus an absolute value that is not smaller than . This allows lower bounds for root separation that are independent from the discriminant.
Mignotte's separation bound is[17] [18]
\operatorname{sep}(p)>
\sqrt{3|\Delta(p)| | |
\Delta(p)
style\|p\|2=\sqrt{a
2}. | |
n |
For a square free polynomial with integer coefficients, this implies
\operatorname{sep}(p)>
\sqrt3 | ||||||||||||
|
>
1{2 | ||||
|
See main article: Gauss–Lucas theorem. The Gauss–Lucas theorem states that the convex hull of the roots of a polynomial contains the roots of the derivative of the polynomial.
A sometimes useful corollary is that, if all roots of a polynomial have positive real part, then so do the roots of all derivatives of the polynomial.
A related result is Bernstein's inequality. It states that for a polynomial P of degree n with derivative P′ we have
max|z||P'(z)|\lenmax|z||P(z)|.
If the coefficients of a random polynomial are independently and identically distributed with a mean of zero, most complex roots are on the unit circle or close to it. In particular, the real roots are mostly located near, and, moreover, their expected number is, for a large degree, less than the natural logarithm of the degree.
If the coefficients are Gaussian distributed with a mean of zero and variance of σ then the mean density of real roots is given by the Kac formula[19] [20]
m(x)=
\sqrt{A(x)C(x)-B(x)2 | |
where
\begin{align} A(x)&=\sigma
n-1 | |
\sum | |
i=0 |
x2i=\sigma
x2n-1 | |
x2-1 |
,\\ B(x)&=
1 | |
2 |
d | |
dx |
A(x),\\ C(x)&=
1 | |
4 |
d2 | |
dx2 |
A(x)+
1 | |
4x |
d | |
dx |
A(x). \end{align}
When the coefficients are Gaussian distributed with a non-zero mean and variance of σ, a similar but more complex formula is known.
For large, the mean density of real roots near is asymptotically
m(x)=
1 | |
\pi|1-x2| |
x2-1\ne0,
m(\pm1)=
1 | |
\pi |
\sqrt{
n2-1 | |
12 |
It follows that the expected number of real roots is, using big notation
Nn=
2 | |
\pi |
lnn+C+
2 | |
\pin |
+O(n)
In other words, the expected number of real roots of a random polynomial of high degree is lower than the natural logarithm of the degree.
Kac, Erdős and others have shown that these results are insensitive to the distribution of the coefficients, if they are independent and have the same distribution with mean zero. However, if the variance of the th coefficient is equal to
\binomni,
\sqrtn.
A polynomial
p
p(x)=a
m1 | |
(x-z | |
1) |
…
mk | |
(x-z | |
k) |
with distinct roots
z1,\ldots,zk
m1,\ldots,mk
zj
mj=1
mj\ge2
In 1972, William Kahan proved that there is an inherent stability of multiple roots.[22] Kahan discovered that polynomials with a particular set of multiplicities form what he called a pejorative manifold and proved that a multiple root is Lipschitz continuous if the perturbation maintains its multiplicity.
This geometric property of multiple roots is crucial in numerical computation of multiple roots.