# Just Stuff

Just another WordPress.com weblog

## Cauchy’s Bound for the Roots of a Polynomial

#### Preamble

This post serves a number of purposes, the first to demonstrate the use of LaTeX in WordPress, the second to provide a convenient location for the proof of this result which while elementary seems difficult to find clearly stated and proven on-line.

#### Background

When searching for the roots of a polynomial it is advantageous to have some idea of the part of the real line or complex plane in which they lie. Once the roots are localised in this manner numerical techniques can be employed to find them.

There are a number of ways of localizing roots, particularly real roots, from the rational roots theorem that provides a list a candidates for the rational roots of a polynomial, through Descartes’ rule of signs which provides bounds on the number of positive and negative roots, through various bounds on the roots, of which the Cauchy bound is an example, through to Sturm sequences. All of these methods have their uses, but here I want to give the Cauchy bound.

#### Cauchy’s Bound on the Roots of a Polynomial

Let:

$P(x)=x^n + a_{n-1}x^{n-1}+ ... + a_1 x+a_0$

be a monic polynomial of degree $n$, then if $x$ is a root of $P(x)$, that is a solution of $P(x)=0$:

$|x| \le 1+\max_{i=0,..,n-1} |a_i|$

Proof

We will start by assuming that $x$ is a solution of $P(x)=0$ that has absolute value greater than $1$, since if it were otherwise the bound would hold trivially.  Now  rewrite $P(x)=0$ as:

$x^n=-a_0-a_1x- .. -a_{n-1}x^{n-1}$

Now if we write $h=\max_{i=0,..,n-1} |a_i|$ then since:

$|x^n| \le |a_0|+|a_1||x|+ ... + |a_{n-1}||x^{n-1}|$

as $|x|>1$ and for real  $n$ we have $|x^n|=|x|^n$ we get:

$|x|^n \le h [1+|x|+ .. +|x|^{n-1}]$

hence the expression inside the square brackets is a finite geometric series so:

$|x|^n \le h \frac{|x|^n-1}{|x|-1}$

Therefore as $|x|>1$:

$|x|-1 \le h \frac{|x|^n-1}{|x^n|} = h \left( 1-\frac{1}{|x|^n} \right)$.

Then:

$|x|-1 \le h$.

and so $|x| \le 1+h$, which proves what was to be proven.

#### Example

Consider $P(x)=x^2+3x+14$, the Cauchy bound for its the roots is $15$, and the roots are (approximately) $x=-1.5\pm 3.428 i$, and $|x|\approx 3.741 \le 15$ as expected.

[Conclusions on LaTeX on wordpress: the results look OK, but the system is temperamental, at least twice now having stripped out the back slashes from the LaTeX, also on occasion it fails to parse LaTeX code that it parsed earlier.]

Written by CaptainBlack

March 8, 2009 at 11:52

Posted in Maths and Stuff

Tagged with , ,

### 4 Responses

1. There has been some interest in similar bounds on the roots of polynomials in the recent Mathematical Gazette which arrived yesterday (18th March 2009, Note 93.02, Volume 93 Issue 526, Pages 87-88) where the bound:

$|x| \le \max (1+ |a_{n-1}|, |a_{n-2}|,\ ..\ , |a_0|)$

is obtained by Alan Cohen, but this uses the bound on the largest eigen value of the companion matrix of the polynomial of Gerschgorin. For proof of this we are refered to the classic; Golub and Van Loan’s “Matrix Computations”.

This bound is slightly better, but the proof is not as accessible as that of the Cauchy bound.

I submitted a note based on this Cauchy Bound post to The Mathematics Gazette some time ago as a comment on Alan Cohen’s note and it should be published in the next edition. Interestingly enough the typography of the proof copy is not as nice as that in this post. (CB 19-Jan-2010)

CB

CaptainBlack

March 19, 2009 at 07:59

2. shouldn’t the Cauchy bound on the example be 4 instead of 15? (max_{I=0 to n-1} not max_{I=0 to n}

bruin

September 2, 2016 at 04:45

• No, It would not matter as $|a_0|=14$

CaptainBlack

September 2, 2016 at 15:47