Let p(x) be the n-th degree polynomial
a0 x^n + a1 x^(n - 1) + a2 x^(n - 2) + a3 x^(n - 3) + ... + ai x^(n - i) + ... + an
where a0 is not zero. Also, the i are subscripts of the a; but, because of typographical limitations, we write then in-line.
The polynomial is said to be monic iff (= if and only if) a0 is one.
Since, by definition; a0 is not zero, the polynomial equation p(x) = 0 may be divided by a0 to yield the corresponding monic polynomial equation. Obviousely, the roots are invariant under this transformation. In the monic polynomial equation, the coefficients are (- 1)^i times the symmetric functions of the roots. Specifically,.a1 is minus the sum or the roots and an is (- 1)^n times the product of the roots. Our prelimenary goal is to make a1 zero and an (- 1)^n.
DesCarte's rule of signs states the obvious relation between the amount of sign changes of the coefficients ai of a polynomial and that there are as many (or an even amount less) of strictly positive roots of the polynomial equation. By replacing x by minus x, one may obtain the corresponding estimate of how many strictly negative roots there are. Of course, the amount of missing terms, at the right end of the polynomial, tells eactly how many zero roots there are.
First, we consider the easier transformation. However, because of the interaction between these two transformations, we would apply the translation transformation first. The guage transformation also is know as a scale-change. For some fixed non-zero b, let y = b x. Then x = y / b. Substitution yields
y^n + a1 b y^(n - 1) + a2 b^2 y^(n - 2) + a3 b^3 y^(n - 3) + ... + ai b^i y^(n - i) + ... an b^n = 0
If we take b = an^(-1 / n); then, the constant term will become one.
The algorithm for synthetic division of the polynomial with coefficients a by x - r is the new polynomial with coefficients:
b0 = a0, b1 = a1 + r b0, b2 = a2 + r b1, b3 = a3 + r b2, ..., bi = ai + r b(i -1), ..., bn = an + r b(n - 1)
Obviousely, bn is the remainder and b0 x^(n -1) + ... + b(n - 1) (a polynomial of one less degree) is the quotient of a0 x^n + ... + an divided by x - r. Iff (= if and only if) the remainder is zero, we have found a root r of the original polynomial. Then, the resulting quotient is said to be a reduced polynomial (of degree (n - 1)).
Perform n successive synthetic divisions of these intermediate quotients. Then, we obtain a constant as the last quotient. These quotients, written in reverse order, are the coefficients of a new n-th degree polynomial. Its roots have been diminished by r; that is, the each new root is r less than the corresponding old root. We say that the (original) polynomial function has been translated by r.
If we take r = - a1 / n in a monic polynomial; then, the new polynomial (of necessity, monic) will have its (n - 1) degree term missing; that is, with a zero coefficient.
As our standard polynomial equation, we will take
x^n + a2 x^(n - 2) + a3 x^(n - 3) + ... + ai x^(n - i) + ... + (- 1)^n = 0
We had performed the division by a0, translation by - a1 / n, and guage transformation by (- an)^(- 1 / n) to arrive here. In it, three of the coefficients have standard values: a0 = 1, a1 = 0, and an = (-1)^n. Since, in a monic polynomial equation, the arithmetic mean of the roots is minus a1; the arithmetic mean of the roots in our standard polynomial equation is zero. Since, in a monic polynomial equation, the geometric mean of the roots is (- an)^(1 / n); the geometric mean of the roots in our standard polynomial equation is one.
In practive, it only may be possible to confine the an to be in the closed interval ((- 1 / 2) ^ n, (- 2) ^ n], where the end-points need to be interchanged iff (= if and only if) n is odd.
Having their arithmetic mean zero, places the roots near the origin. Having their geometric mean one (or as near to one as practical), prevents the roots from being either too small or too large in magnitude. As a consequence, henceforth, we may perform the operations upon the polynomial in integer (rather than real (= floating point)) arithmetic. Integer arithmetic is faster than floating-point arithmetic. Much faster, if multi-precision is desired.
Horner's method, for finding a root of a polynomial equation, is an iterative sequence of translations to place the root at the origin. Then, the sum of these translations is the root of the original equation.
Then, we would employ synthetic division to reduce the equation by this root. Re-standardize the equation, and look for the next root. Sometimes, we skip the re-standardization step. Doing so is a mater of judgment.
While Horner's method is well-suited to hand-calculation, it becomes very tedious as the degree of the polynomial equation increases or if we are in the complex (rather than real) field.
Copywrite (c) 1997 R. I. 'Sciibor-Marchocki last modified on Tuesday 20-th May 1997.