Geometrical properties of polynomial roots

In mathematics, a polynomial is a function of the form

$p(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n},\quad x\in \mathbb {C}$

where the coefficients $a_{0},\ldots ,a_{n}$ are complex numbers and $a_{n}\neq 0$. The fundamental theorem of algebra states that polynomial p has n roots. The aim of this page is to list various properties of these roots.

Continuous dependence of coefficients

The n roots of a polynomial of degree n depend continuously on the coefficients.

This result implies that the eigenvalues of a matrix depend continuously on the matrix. A proof can be found in Tyrtyshnikov(1997).

The problem of approximating the roots given the coefficients is ill-conditioned. See, for example, Wilkinson's polynomial.

Complex conjugate root theorem

Main article: Complex conjugate root theorem

The complex conjugate root theorem states that if the coefficients of a polynomial are real, then the non-real roots appear in pairs of the type a ± ib.

For example, the equation x² + 1 = 0 has roots ±i.

Radical conjugate roots

It can be proved that if a polynomial P(x) with rational coefficients has a + √b as a root, where a, b are rational and √b is irrational, then a − √b is also a root. First observe that

$\left(x-\left[a+{\sqrt {b}}\right]\right)\left(x-\left[a-{\sqrt {b}}\right]\right)=(x-a)^{2}-b.$

Denote this quadratic polynomial by D(x). Then, by the division transformation for polynomials,

$P(x)=D(x)Q(x)+cx+d=((x-a)^{2}-b)Q(x)+cx+d,\,\!$

where c, d are rational numbers (by virtue of the fact that the coefficients of P(x) and D(x) are all rational). But a + √b is a root of P(x):

$P\left(a+{\sqrt {b}}\right)=c\left(a+{\sqrt {b}}\right)+d=(ac+d)+c{\sqrt {b}}=0.$

It follows that c, d must be zero, since otherwise the final equality could be arranged to suggest the irrationality of rational values (and vice versa). Hence P(x) = D(x)Q(x), for some quotient polynomial Q(x), and D(x) is a factor of P(x).

Bounds on (complex) polynomial roots

Based on the Rouché theorem

A very general class of bounds on the magnitude of roots is implied by the Rouché theorem. If there is a positive real number R and a coefficient index k such that

$|a_{k}|\,R^{k}>|a_{0}|+\cdots +|a_{k-1}|\,R^{k-1}+|a_{k+1}|\,R^{k+1}+\cdots +|a_{n}|\,R^{n}$

then there are exactly k (counted with multiplicity) roots of absolute value less than R. For k=0,n there is always a solution to this inequality, for example

• for k=n,

$R=1+{\frac {1}{|a_{n}|}}\max\{|a_{0}|,|a_{1}|,\dots ,|a_{n-1}|\}$ or

$R=\max \left(1,\,{\frac {1}{|a_{n}|}}\left(|a_{0}|+|a_{1}|+\cdots +|a_{n-1}|\right)\right)$

are upper bounds for the size of all roots,

• for k=0,

$R={\frac {|a_{0}|}{|a_{0}|+\max\{|a_{1}|,|a_{2}|,\dots ,|a_{n}|\}}}$ or

$R={\frac {|a_{0}|}{\max(|a_{0}|,\,|a_{1}|+|a_{2}|+\cdots +|a_{n}|)}}$

are lower bounds for the size of all of the roots.

• for all other indices, the function

$h(R)=|a_{0}|\,R^{-k}+\cdots +|a_{k-1}|\,R^{-1}-|a_{k}|+|a_{k+1}|\,R+\cdots +|a_{n}|\,R^{n-k}$

is convex on the positive real numbers, thus the minimizing point is easy to determine numerically. If the minimal value is negative, one has found additional information on the location of the roots.

One can increase the separation of the roots and thus the ability to find additional separating circles from the coefficients, by applying the root squaring operation of the Dandelin-Graeffe iteration to the polynomial.

A different approach is by using the Gershgorin circle theorem applied to some companion matrix of the polynomial, as it is used in the Weierstraß–(Durand–Kerner) method. From initial estimates of the roots, that might be quite random, one gets unions of circles that contain the roots of the polynomial.

Other bounds

Useful bounds for the magnitude of all polynomial's roots include the near optimal Fujiwara bound

$2\max \left(\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{\frac {1}{2}},\dots \left|{\frac {a_{1}}{a_{n}}}\right|^{\frac {1}{n-1}},\left|{\frac {a_{0}}{2a_{n}}}\right|^{\frac {1}{n}}\right)$ (Fujiwara's bound)

which is an improvement (as the geometric mean) of

$2\max \left(\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n-1}}}\right|,\dots \left|{\frac {a_{1}}{a_{2}}}\right|,\left|{\frac {a_{0}}{2a_{1}}}\right|\right)$ (Kojima's bound)

Other bounds are

$\max \left(\left|{\frac {a_{0}}{a_{n}}}\right|,1+\left|{\frac {a_{1}}{a_{n}}}\right|,\dots 1+\left|{\frac {a_{n-1}}{a_{n}}}\right|\right)$ (Cauchy bound)

$\max \left(1,\sum _{i=0}^{n-1}\left|{\frac {a_{i}}{a_{n}}}\right|\right)$ (Hirst and Macey bound)

or

$\sum _{i=0}^{n-1}\left|{\frac {a_{i}}{a_{i+1}}}\right|$

Other bounds include one due to Lagrange. These bounds return only bounds surpassing unity, so it cannot be used for some polynomials.

Without loss of generality let the xⁿ term of a polynomial with all real roots have coefficient 1 and let the general term be a_ixⁱ. Let { a_j } be the set of negative coefficients. An upper bound for the positive real roots is given by the sum of the two largest numbers in the set { |a_j|^1/j }. This is a improvement on Fujiwara's bound which uses twice the maximum value of this set as its upper bound.

A similar bound also due to Lagrange holds for a polynomial with complex coefficients. Again let the xⁿ term of the polynomial have coefficient 1 and let the general term be a_ixⁱ. Then the upper bound for the absolute values of the roots is given by the sum of the two greatest values in the set { |a_i|^1/i }. Again this is a improvement on Fujiwara's bound which uses twice the maximum value of this set as its upper bound.

A third bound also due to Lagrange holds for a polynomial with real coefficients. Let the a_ix^n-i be the general term of the polynomial with 0 ≤ i ≤ m. Let the first d terms of the polynomial have positive coefficients and let A be the maximum of these d coefficients.

Then 1 + ( A / a₀ )^{1/( 1 + d )} is an upper bound to the positive roots of the polynomial.

Sun and Hsieh obtained an improvement on Cauchy's bound. Let the coefficient of the xⁿ term be 1 and let the general term be a_i Sun and Hsieh showed that upper bounds d₁ and d₁ could be obtained from the following equations.

d₁ = 0.5 | a_n-1 - 1 | + { ( | a_n-1 | - 1 )² - 4a }^1/2

where a = max{ |a_i| }

d₂ is the positive root of the cubic equation

Q(x) = x³ + (2 − |a_n−1|) x² + (1 − |a_n−1| − |a_n−2| ) x − a

where a = max{ |a_i| }

They also noted that d₂ ≤ d₁

Proof

Let $\zeta$ be a root of the polynomial $\scriptstyle z^{n}+a_{n-1}z^{n-1}+\cdots +a_{1}z+a_{0}$; in order to prove the inequality $\scriptstyle |\zeta |\leq R_{p}$ we can assume, of course, $\scriptstyle |\zeta |>1$. Writing the equation as $\scriptstyle -\zeta ^{n}=a_{n-1}\zeta ^{n-1}+\cdots +a_{1}\zeta +a_{0}$, and using the Hölder's inequality we find $\scriptstyle |\zeta |^{n}\leq \|a\|_{p}\|(\zeta ^{n-1},\cdots ,\zeta ,1)\|_{q}$. Now, if $p=1$, this is $\scriptstyle |\zeta |^{n}\leq \|a\|_{1}\max\{|\zeta |^{n-1},\cdots ,|\zeta |,1\}=\|a\|_{1}|\zeta |^{n-1}$, thus $\scriptstyle |\zeta |\leq \max\{1,\|a\|_{1}\}$. In the case $\scriptstyle 1<p\leq \infty$, taking into account the summation formula for a geometric progression, we have

$|\zeta |^{n}\leq \|a\|_{p}\left(|\zeta |^{q(n-1)}+\cdots +|\zeta |^{q}+1\right)^{1/q}=\|a\|_{p}\left({\frac {|\zeta |^{qn}-1}{|\zeta |^{q}-1}}\right)^{1/q}\leq \|a\|_{p}\left({\frac {|\zeta |^{qn}}{|\zeta |^{q}-1}}\right)^{1/q},$

thus $\scriptstyle |\zeta |^{nq}\leq \|a\|_{p}^{q}{\frac {|\zeta |^{qn}}{|\zeta |^{q}-1}}$ and simplifying, $\scriptstyle |\zeta |^{q}\leq 1+\|a\|_{p}^{q}$. Therefore $\scriptstyle |\zeta |\leq \|(1,\|a\|_{p})\|_{q}=R_{p}$ holds, for all $\scriptstyle 1\leq p\leq \infty .$

Bounds on positive polynomial roots

There also exist bounds on just the positive roots of polynomials; these bounds are of extreme importance and have been developed by Akritas, Strzeboński and Vigklas based on previous work by Doru Stefanescu. They are used in the computer algebra systems Mathematica, Sage, SymPy, Xcas etc and are described in P. S. Vigklas' Ph.D. Thesis and in .

Gauss–Lucas theorem

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|\leq 1}{\big |}P'(z){\big |}\leq n\max _{|z|\leq 1}{\big |}P(z){\big |}.$

Polynomials with real roots

It is possible to determine the bounds of the roots of a polynomial using Samuelson's inequality. This method is due to a paper by Laguerre.

Let $a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}$

be a polynomial with all real roots. The roots are located in the interval with endpoints

$x_{\pm }=-{\frac {a_{n-1}}{n\cdot a_{n}}}\pm {\frac {n-1}{n\cdot a_{n}}}{\sqrt {a_{n-1}^{2}-{\frac {2n}{n-1}}a_{n}a_{n-2}}}$.

Example: The polynomial

$x^{4}+5x^{3}+5x^{2}-5x-6$

has four real roots -3, -2, -1 and 1. The formula gives

$x_{\pm }=-{\frac {5}{4}}\pm {\frac {3}{4}}{\sqrt {\frac {35}{3}}}$,

its roots are contained in

I = [-3.8117 ; 1.3117].

If the polynomial f has real simple roots the Hessian H(f) evaluated on the interval [ -1, 1 ] is always ≥ 0. In symbols

H(f) = (n − 1)² f' ² − n(n − 1) f f' ≥ 0

where f' is the derivative of f with respect to x.

When n > 1 this simplifies to

f'(x) ≥ n f(x)

This relation applied to polynomials with complex roots is known as Bernstein's inequality.

Statistical repartition of the roots

The statistical properties of the roots of a random polynomial have been the subject of several studies. Let

$f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}$

be a random polynomial. If the coefficients a_i are independently and identically distributed with a mean of zero, the real roots are mostly located near ±1. The complex roots can be shown to be located on or close to the unit circle.

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

$p(x)={\frac {\sqrt {A(x)C(x)-B(x)^{2}}}{\pi A(x)}}$

where

$A(x)=\sigma \sum {x^{2i}}=\sigma {\frac {x^{2n}-1}{x-1}}$

$B(x)={\frac {1}{2}}{\frac {d}{dt}}A(x)$

$C(x)={\frac {1}{4}}{\frac {d^{2}}{dt^{2}}}A(x)+{\frac {1}{4x}}{\frac {d}{dt}}A(x)$

When the coefficients are Gaussian distributed with a non zero mean and variance of σ, a similar but more complex formula is known.

Asymptotic results

For large n, a number of asymptotic formulae are known. For a fixed x

$p(x)={\frac {1}{\pi |1-x^{2}|}}$

and

$p(\pm 1)={\frac {1}{\pi }}{\sqrt {\frac {n^{2}-1}{12}}}$

where p( x ) is the mean density of real roots. The expected number of real roots is

$N_{n}={\frac {2}{\pi }}log(n)+C+O(n^{-2})$

where C is a constant approximately equal to 0.6257358072 and O() is the order operator.

This result has been shown by Kac, Erdos and others to be insensitive to the actual distribution of coefficients. Numerical testing of this formula has confirmed these earlier results.

See also

• Descartes' rule of signs
• Sturm's theorem
• Abel–Ruffini theorem
• Viète's formulas
• Gauss–Lucas theorem
• Content (algebra)
• Rational root theorem
• Marden's Theorem
• Halley's method
• Laguerre's method
• Jenkins-Traub method
• Newton's identities

References

• E.E. Tyrtyshnikov, A Brief Introduction to Numerical Analysis, Birkhäuser Boston, 1997