Root-Finding Techniques for Polynomials

# Root-Finding Techniques for Polynomials

We will now look at a few techniques to find roots of polynomials. The first theorem will tell us that if we have a rational root (in lowest terms) to a polynomial with integer coefficients, then the numerator/denominator of this rational root is restricted to be certain values.

 Theorem 1 (The Rational Root Theorem): If $r = \frac{p}{q} \in \mathbb{Q}$ is a rational root (in lowest terms) of the polynomial $f(x) = a_0 + a_1x + ... + a_nx^n$ with integer coefficients $a_0, a_1, ..., a_n \in \mathbb{Z}$ and $a_0 \neq 0$ then $p$ divides $a_0$ and $q$ divides $a_n$.

Note that if a rational number $r = \frac{p}{q}$ is in "lowest terms", then the greatest common divisor of $p$ and $q$ is $1$, sometimes symbolically written as $\mathrm{gcd} (p, q) = 1$ or simply $(p, q) = 1$.

• Proof: Let $r = \frac{p}{q}$ be a rational root (in lowest terms) of $f(x) = a_0 + a_1x + ... + a_nx^n$ where $a_0 \neq 0$. Then $f(r) = f \left ( \frac{p}{q} \right ) = 0$ and so:
(1)
\begin{align} \quad f \left ( \frac{p}{q} \right ) = 0 = a_0 + a_1 \left ( \frac{p}{q} \right ) + ... + a_n \left ( \frac{p}{q} \right )^n \end{align}
• If we multiply both sides of this equation by $q^n$ we get that:
(2)
\begin{align} \quad 0 = a_0q^n + a_1 pq^{n-1} + ... + a_np^n \\ \quad a_0 q^n = -a_1 pq^{n-1} - ... - a_np^n \\ \quad a_0 q^n = p(-a_1q^{n-1} - ... - a_np^{n-1}) \end{align}
• Therefore $p$ divides $a_0$ since $\mathrm{gcd} (p, q) = 1$. Furthermore, note that:
(3)
\begin{align} \quad 0 = a_0q^n + a_1 pq^{n-1} + ... + a_np^n \\ \quad a_np^n = -a_0q^n - a_1 pq^{n-1} - ... - a_{n-1}p^{n-1}q \\ \quad a_np^n = q(-a_0q^{n-1} - a_1pq^{n-2} - ... - a_{n-1}p^{n-1}) \end{align}
• Therefore $q$ divides $a_np^n$, and hence $q$ divides $a_n$ since $\mathrm{gcd} (p, q) = 1$. $\blacksquare$
 Theorem 2 (Descarte's Rule of Signs): If $p(x)$ is a polynomial with real coefficients written in descending powers of $x$, that is $p(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0$ then: a) The number of positive real roots of $p(x)$ is equal to the number of sign changes in $p(x)$ or the number of sign changes in $p(x)$ minus an even positive integer. b) The number of negative real roots of $p(x)$ is equal to the number of sign changes in $p(-x)$ or the number of sign changes in $p(-x)$ minus an even positive integer.

We will not prove Descarte's Rule of signs here.

 Theorem 3 (Bound's Theorem): Let $p(x) = a_0 + a_1x + ... + a_nx^n$ be a polynomial with complex coefficients, and let $\lambda$ be a root of $p$. Then $\mid \lambda \mid < \frac{\mathrm{max} \{ \mid a_0 \mid, \mid a_1 \mid, ..., \mid a_{n-1} \mid \}}{\mid a_n \mid} + 1$.
• Proof: Theorem 3 above is trivially true for $\mid \lambda \mid ≤ 1$. Suppose that $\mid \lambda \mid > 1$. Let $M = \mathrm{max} \{ \mid a_0 \mid, \mid a_1 \mid , ..., \mid a_{n-1} \mid \}$. Now since $\lambda$ is a root of $p$, we have that:
(4)
\begin{align} \quad 0 = a_0 + a_1 \lambda + ... + a_n \lambda^n \\ \quad a_n \lambda^n = -a_0 - a_1 \lambda - ... - a_{n-1}\lambda^{n-1} \\ \quad \mid a_n \lambda^n \mid = \mid -a_0 - a_1 \lambda - ... - a_{n-1}\lambda^{n-1} \mid \\ \quad \mid a_n \mid \mid \lambda \mid^n ≤ \mid a_0 \mid + \mid a_1 \mid \mid \lambda \mid + ... + \mid a_{n-1} \mid \mid \lambda \mid^{n-1} \\ \quad \mid a_n \mid \mid \lambda \mid^n ≤ M + M \mid \lambda \mid + ... + M \mid \lambda \mid^{n-1} \\ \quad \mid a_n \mid \mid \lambda \mid^n ≤ M \left ( 1 + \mid \lambda \mid + ... + \mid \lambda \mid^{n-1} \right ) \end{align}
• The sum $1 + \mid \lambda \mid + ... + \mid \lambda \mid^{n-1}$ can be replaced as a geometric series $1 + \mid \lambda \mid + ... + \mid \lambda \mid^{n-1} = \frac{1 - \mid \lambda \mid^n}{1 - \mid \lambda \mid}$, and so:
(5)
\begin{align} \quad \mid a_n \mid \mid \lambda \mid^n ≤ M \left ( \frac{1 - \mid \lambda \mid^n}{1 - \mid \lambda \mid} \right ) \\ \quad \mid a_n \mid \mid \lambda \mid^n ≤ M \left ( \frac{\mid \lambda \mid^n}{\mid \lambda \mid - 1} - \frac{1}{\mid \lambda \mid - 1} \right ) \\ \quad \mid a_n \mid \mid \lambda \mid^n < M \left ( \frac{\mid \lambda \mid^n}{\mid \lambda \mid - 1} \right ) \end{align}
• If we divide both sides of the equation above by $\mid \lambda \mid^n$ and since $\mid \lambda \mid > 1$ we have that:
(6)
\begin{align} \quad \mid a_n \mid < \frac{M}{\mid \lambda \mid - 1} \Leftrightarrow \mid \lambda \mid - 1 < \frac{M}{\mid a_n \mid} \Leftrightarrow \mid \lambda \mid < \frac{M}{\mid a_n \mid} + 1 = \frac{\mathrm{max} \{ \mid a_0 \mid, \mid a_1 \mid, ..., \mid a_{n-1} \mid \}}{\mid a_n \mid} + 1 \quad \blacksquare \end{align}