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) = a_nxⁿ + a_n-1x^n-1 + ... + a₀

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

Then

abs(c) ≤ 1 + {abs(a_n-1 + ... + abs(a₀)}/abs(a_n)

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 a_ncⁿ + a_n-1c^n-1 + ... + a₀ = 0, and we have:

a_ncⁿ = -a_n-1c^n-1 + .... + -a₀

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

abs(a_n)*abs(c)ⁿ ≤ abs(a_n-1)*abs(c)^n-1 + ... + abs(a₀)

(4) Let H = max{abs(a_n-1), ..., abs(a₀) }

(5) So,

abs(a_n)*abs(c)ⁿ ≤ H(abs(c)^n-1 + ... + 1)

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

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

and therefore:

abs(a_n)*abs(c)ⁿ ≤ H[abs(c)ⁿ]/[abs(c) - 1]

(7) So, we can state:

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

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

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

and finally,

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

QED