A polynomial of degree n may be written in three different forms
0 = f(x)
= a0 x^n + a1 x^(n-1) + a2 x^(n-2) + … + an
= a0 (x – x0) (x – x1) (x – x2) … (x – x(n-1)),
where the leading coefficient a0 is not zero.
By saying that the polynomial is real, we mean that each of the coefficients ai is real. By saying that each of the roots is real, we mean that each of the roots xi is real. For convenience, we consider the xi to be in decreasing order.
Rules of engagement: We play this game with the stipulation that neither the coefficients {ai} nor the roots {xi} are visible. The exception is that the values of a1 and an may be computed numerically. (Let us remind you that, according to the Theory of Equations, the coefficient a1 is minus the sum or the roots of the polynomial, while the coefficient an is either plus or minus the product of the roots, depending upon the parity of n being zero (even) or one (odd), respectively.) However, we are given the degree n of the polynomial. Moreover, once the value of a particular root is ascertained, various operations involving that root become permissible.
[Historical note: While for both logical and pedagogical reasons, this exposition of the squaring algorithm as applied to a polynomial should precede its application to symmetric matrices, actually I wrote it only now (October 2005) -- by abstraction from its application to a symmetric matrix -- in response to a request for a tutorial.]
Definition: The pair of roots xi and xj is said to be degenerate iff (= if and only if) xi = xj. It is said to be cross-sign degenerate iff (= if and only if) xi = - xj. In each case, the degeneracy of a root is the cardinality of set of roots equal to it. The combined degeneracy is the sum of these two degeneracies. A polynomial is said to be degenerate iff (= if and only if) it possesses at least one root with a combined degeneracy greater that one.
Definition: The polynomial is said to be positive iff (= if and only if) the smallest root x(n-1) >= 0.
Definition: The polynomial is said to be positive-definite iff (= if and only if) the smallest root x(n-1) > 0.
Definition: The polynomials f(x) and f’(x) are said to be equivalent iff (= if and only if) the set of their roots is the same.
Definition: f(x + t) is the translation of the polynomial f(x) by the constant t.
The computation of a translation is demonstrated as part of the Horner’s method for finding the roots of a polynomial.
Theorem: The polynomial resulting from the translation by t has each corresponding root diminished by t.
Proof is obvious.
Theorem: The translation f(x – t) is the inverse of the translation f(x + t).
Proof is obvious.
Definition: The polynomial is said to be monic iff (= if and only if) the coefficient of the highest-degree term a0 is one.
Theorem: A monic polynomial, each of whose roots is real, is real.
Proof is obvious.
Converse is false, however.
Proof: The polynomial 0 = x^2 + 1 has the two roots {i, -i}, each of which is complex.
Theorem: The polynomial 0 = f’(x) = f(x) / a0 is a monic polynomial equivalent to the original polynomial.
Proof is obvious.
Henceforth, we will display the monic polynomial as the representative of its equivalence class.
Since the aforementioned operation is disallowed by the rules of engagement, we have to include the "monic" in the overall hypothesis at the top of this page.
Definition: f(g x) is the gauge transformation of the polynomial f(x) by the scale-factor g, which may not be zero. This transformation is also known as the scale transformation.
Theorem: The polynomial resulting from the gauge transformation by g has each corresponding root divided by g.
Proof is obvious.
Theorem: The gauge transformation by 1/g is the inverse of that by g.
Proof is obvious.
Theorem: Division. The polynomial f’(x) = f(1/x) has each corresponding root the reciprocal of that of the original function.
Proof is obvious.
Theorem: The division is idempotent; i.e., it is its own inverse.
Proof is obvious.
Lemma: The polynomial f(x) f(-x) is of degree 2n and has only even-order terms.
Proof is obvious.
Theorem: Squaring. The each of the roots of the polynomial f’(x^2) = f(x) f(-x) is the square of the corresponding root of the original polynomial f(x).
Proof is obvious.
Corollary: After s such squarings, the typical root xi becomes p = xi^2^s.
Proof is obvious.
Corollary: The solution for s is s = ln(ln(p) / ln(xi)) / ln(2).
Proof is obvious.
Lemma: Consider a non-degenerate polynomial with x0 = 1. To a precision p (take, e.g., p = 10^(-12)), the largest value that x1 can have is x1 = 1 – p. After at most s = ln(-ln(p) / p) ln(2) squarings, to a precision of p, we will obtain the polynomial x^n – x^(n-1) = 0.
Proof is obvious.
Lemma: This resulting polynomial is invariant under an additional squaring.
Proof is obvious.
Theorem: we have found the largest root to be one.
Proof follows from the observation that a translation of one yields the polynomial x^n = 0.
Corollary: If we had not been given that the largest root is one; we would perform a gauge transformation of -a1, prior to each squaring. The result of the squarings would converge to the aforementioned resulting polynomial. The value of the original root would be the product of the discounted gauge transformations. This discounting of each gauge transformation g consists of taking the power g^2^(-s), where s is the running value of the squaring.
Proof is obvious.
Lemma: Had the original given polynomial the largest in magnitude root with a combined degeneracy of d; the resulting polynomial would have become (x – 1)^d x^(n-d) = x^n – d x^(n-1) + …. = 0.
Proof is obvious.
Lemma: This resulting polynomial is invariant under an additional squaring.
Proof is obvious.
Theorem: we have found the largest root to be one.
Proof follows from the observation that a translation of one yields the polynomial x^n = 0.
Corollary: If we had not been given that the largest root is one; we would perform a gauge transformation of -a1/d, prior to each squaring. The result of the squarings would converge to the aforementioned resulting polynomial. The value of the original root would be the product of the discounted gauge transformations. This discounting of each gauge transformation g consists of taking the power g^2^(-s), where s is the running value of the squaring.
Proof is obvious.
If we were not given the value of d; how would we know what value to use? Clairvoyance! The combined degeneracy has to be a small natural number. We ascertain it as follows:
Lemma: Consider a monic degenerate polynomial with a single non-zero root x0 = 1 of degeneracy d. That is, the polynomial is 0 = f(x) = (x – 1)^d x^(n – d) = x^n – d x^(n – 1) …. Since we do not know the value of d, we perform our gauge transformation by d. The polynomial becomes 0 = f(x) = (x – 1/d)^d x^(n – d). Then, we perform a squaring of its roots, to obtain the polynomial 0 = f(x) = (x – 1/d^2)^d x^(n – d) = x^n – 1/d x^(n – 1) ….Thus, the value of the degeneracy is minus the reciprocal of the coefficient of x^(n – 1).
Proof is obvious.
Theorem: Now, that the lemma has given us the value of d, we may employ the previous corollary, to obtain the convergent polynomial.
Proof is obvious.
Precaution: Do not set p too small and do not exceed the corresponding s. Otherwise, the accumulated errors may cause a false resolution of a degeneracy.
Strategy: If better precision is desired; translate the original polynomial by the approximate root, then employ the division theorem and a gauge transformation to obtain more precise value of the root.
What is the sign of the root? If f(x) is zero; x is a positive root. If f(-x) is zero; x is a negative root. If both are zero; we have a cross-sign degeneracy. If only one of them is zero; the degeneracy is of that root. However if both of them are zero and the cross-sign degeneracy is greater that two; we do know neither which of the two roots is degenerate nor its degeneracy.
Lemma: A translation by minus the value of the root yields a polynomial with a factor of x^d, where d is the degeneracy of the root.
Proof is obvious.
Theorem: Deflation. Divide the resulting polynomial by x^d, to obtain a new polynomial of degree n – d. If we know the root x but not its degeneracy d; use d = 1. Then, perform the inverse translation.
Proof is obvious.
Algorithm: Squaring. Repeat the process, until no more roots remain. The difference between the degree of the original polynomial and how many roots have been found is the degeneracy of the zero root.
At any time, a judicious translation or division may be employed to alter the sequence of discovery of the roots.
Killing a root: The rules of engagement allow that once the value of a non-degenerate root is known, any constant may be added to it. The addition of the additive inverse is said to kill the root. This operation may be performed as either an alternative to, or preceding the, deflation.
Definition: The kernel polynomial k(x) of a given polynomial is comprised of all of its degenerate -- same sign and cross-sign -- roots and all of its zero roots.
Theorem: Any translation breaks a cross-sign degeneracy.
Proof is obvious.
As stated at the outset, by the rules of engagement, the coefficients of the polynomial are cryptic. However, we may ascertain their values as follows:
Take a set of n+1 convenient distinct real numbers {ui}.
Numerically compute the corresponding values of the polynomial {f(ui)}. In a typical application, this is a time consuming operation.
Employ a polynomial interpolation formula to find the values of the coefficients {ai} of the polynomial.
If desired; differentiate this polynomial analytically. The rules of engagement would preclude doing so directly from the original polynomial.
Employ some algorithm to find the roots {xi} of this polynomial. For instance, either Horner's method or Newton's method may be used. Again, in a typical application, it would be very time consuming to attempt to employ the Newton's method upon the original polynomial. The rules of engagement would preclude employing the Horner's method upon the original polynomial.
Then, employ the division theorem, upon the original polynomial, to refine the values of these roots.
Here you have solved the given polynomial.
Copyright © 2005 by R. I. ‘Scibor-Marchocki. Last modified on Sunday 30-th October 2005.