Just Stuff

Just another WordPress.com weblog

Cauchy’s Bound for the Roots of a Polynomial

with 4 comments

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.]

Advertisements

Written by CaptainBlack

March 8, 2009 at 11:52

Posted in Maths and Stuff

Tagged with , ,

4 Responses

Subscribe to comments with RSS.

  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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: