Suppose you have an nth degree polynomial with complex coefficients
p(z) = anzn + an-1zn-1 + … + a0
and you want to find some circle that is guaranteed to contain all the zeros of p.
Cauchy found such a circle in 1829. The zeros of p lie inside the circle |z| ≤ r where r is the unique positive root of
f(z) = |an|zn − |an-1|zn-1 − … − |a0|
This value of r is known as the Cauchy radius of the polynomial p.
This may not seem like much of an improvement: you started with wanting to find the roots of an nth degree polynomial and you end with finding the roots of an nth degree polynomial. But Cauchy’s theorem reduces the problem of finding all roots of a complex polynomial to finding one root of a real polynomial. Furthermore, the positive root we’re after is guaranteed to be unique.
If a0 = 0 then p(z) has a factor of z and so we can reduce the problem to bounding the zeros of p(z)/z. Otherwise, f(0) < 0. Eventually f(z) must be positive because the zn term will overtake the rest of the terms for large enough z. So we only need to find some value of z where f(z) > 0 and then we could use the bisection method to find r.
Since our goal is to bound the zeros of p, we don’t need to find r exactly: an upper bound on r will do, though the smaller the upper bound the better. The bisection method gives us a sequence of upper bounds, so we could work in rational arithmetic and have rigorously provable upper bounds.
As for how to find a real value of z where f is positive, we could try z = 2k for successive value of k until we find one that works.
For example, let’s bound the roots of
p(z) = 12z5 + 2z2 + 23i = 0.
Cauchy’s theorem says we need to find the unique positive root of
f(z) = 12z5 − 2z2 − 23.
Now f(0) = −23 and f(2) = 353. So we know right away that the roots of p have absolute value less than 2.
Next we evaluate f(1), which turns out to be −13, and so the Cauchy radius is larger than 1. This doesn’t necessarily mean that p has a root with absolute value greater than 1, only that the Cauchy radius is greater than 1. An upper bound on the Cauchy radius is an upper bound on the absolute values of the roots of p; a lower bound on the Cauchy radius is not necessarily a lower bound on the largest root.
Carrying out two steps of the bisection method by hand was easy, but let’s automate the process of carrying it out further.
>>> from scipy.optimize import bisect >>> bisect(lambda x: 12*x**5 - 2*x*x - 23, 1, 2) 1.1646451258329762
So Python tells us r = 1.1646451258329762.
Here’s a plot of the roots and the Cauchy radius.
In this example the roots of p are located very near a circle with the Cauchy radius. The roots range in absolute value between 1.1145600699993699 and 1.1634197192917954. The roots nearly lie in a circle because the quadratic term in our polynomial is small and so we are approximately finding the fifth roots of −23i.
Let’s do another example with randomly generated coefficients to get a better idea of how Cauchy’s theorem works in general. The coefficients of our polynomial, from 0th to 5th, are
0.126892 + 0.689356i, -0.142366 + 0.260969, – 0.918873 + 0.489906i, 0.0599824 – 0.679312i, – 0.222055 + 0.273651, + 0.154408 + 0.733325i
The roots have absolute value between 0.7844606228243709 and 1.2336256274024142, and the Cauchy radius is 1.5088421845957782. Here’s a plot.
Related posts
The post Bounding complex roots by a positive root first appeared on John D. Cook.