Single Bounds Theorem

February 23, 2010

Discussion on the method of the Single Bounds Theorem. All of the real roots of any given real polynomial are in the interval $[-M,M]$ , and M is rather easy to compute. Narrow your possibilities and narrow your real domain.

Suppose you have some real n-degree monic polynomial P(x)

$P(x) = x^n+ a_{n-1}x^{n-1}+ a_{n-2}x^{n-2}+\cdots + a_{1}x+ a_{0}$

Notice that this is a real polynomial and thus has real coefficients a_i. Notice that this is also a monic polynomial, meaning that the lead coefficient is 1. Divide through by a non-unitary lead coefficient if you must.

Aside from being a monic polynomial with real coefficients, there are no other stipulations. The polynomial can be of any degree with any roots. The coefficients can be irrational or rational, algebraic or transcendental, it makes no difference. The theorem does not apply to any polynomial with complex coefficients and cannot help to determine complex roots.

1. Generate a set of numbers, A, comprising of the absolute values of each coefficient – with the exception of the lead coefficient (a_n=1).

$A = \{|a_0|,|a_1|,|a_2|,\ldots,|a_{n-1}|\}$

Notice that the k^th element of A is not the same as the k^th coefficient of the polynomial. The distinction is the absolute value operation.

2. Find the maximum value of A, the element of highest value, and add 1 to it.

$M_1 = 1 + \max(A)$

3. Find the maximum value, the larger element, between these two elements: 1, and the sum of the elements of A.

$M_2 = \max(1, \sum_{k=0}^{n-1} A_k)$

4. Find the minimum value between M₁ and M₂.

$M = \min(M_1,M_2)$

Once you have arrived at a value for M, you are done. All of the real roots of your original polynomial will lie in the interval $[-M,M ]$ .

Or, in other words, if x is a root then these three statements are equivalent:

$x \in [-M,M]$

$-M \le x \le M$

$|x| \le M$

This method can be arithmetically laborious but it can also be beneficial. It has the power to narrow down an infinitely large domain of possibilities, and perhaps eliminate possibilities arrived at via other techniques, and provide you with a better idea of how to proceed.

Like this:

Be the first to like this post.

Posted in method, polynomial | Tagged math, method, polynomial, roots, theorem, zeros |

One comment

[...] that they dont need to be tested. It can narrow the real domain far more restrictively than the Single Bounds Theorem. Even if the roots end up being irrational and difficult to find, at least you know whereabouts [...]
by Upper and Lower Bounds Test « Cogito's Math Tutorage March 13, 2010 at 5:04 pm

Reply

Cogito's Math Tutorage