Tuesday, February 03, 2009

Cauchy's Bound for Real Roots

Augustin-Louis Cauchy came up with a useful bound for real roots in a polynomial equation. This works well with Sturm's Theorem.

Theorem: Cauchy's Bound for Real Roots

Let f(x) = anxn + an-1xn-1 + ... + a0

Let c be a root of f(x) such that f(c)=0

Then

abs(c) ≤ 1 + {abs(an-1 + ... + abs(a0)}/abs(an)

Proof:

(1) Assume that abs(c) is greater than 1. [The alternative is true since 1 + abs(x) ≥ 1]

(2) Since c is a root, then ancn + an-1cn-1 + ... + a0 = 0, and we have:

ancn = -an-1cn-1 + .... + -a0

(3) Using a basic inequality (see Lemma 2, here), we have:

abs(an)*abs(c)n ≤ abs(an-1)*abs(c)n-1 + ... + abs(a0)

(4) Let H = max{abs(an-1), ..., abs(a0) }

(5) So,

abs(an)*abs(c)n ≤ H(abs(c)n-1 + ... + 1)

(6) Since (abs(c)-1)*(abs(c)n-1 + ... + 1) = abs(c)n - 1 and since abs(c) is greater than 1, it follows that:

H(abs(c)n-1 + ... + 1) = H[abs(c)n - 1]/[abs(c) - 1]

and therefore:

abs(an)*abs(c)n ≤ H[abs(c)n]/[abs(c) - 1]

(7) So, we can state:

abs(an) ≤ H/[abs(c) - 1]

(8) Since abs(an) and abs(c)-1 are positive, we can also state:

abs(c) - 1 ≤ H/abs(an)

and finally,

abs(c) ≤ 1 + H/abs(an)

QED

3 comments:

fuaada said...

Hi Larry, it seems very useful to me....could you please leave a reference regarding to this Theorem, so that i can review it....cheers!
Fuaada

Larry Freeman said...

Hi Fuaada,

I'm sorry, I don't remember my reference on this.

My content on Sturm is from:
100 Great Problems of Elementary Mathematics

fuaada said...

Okay...that's fine...:)