Today I learned that Horner method not only computes the value of a polynomial
at a given point
but also gives the ratio and the remainder of
and
.
Let
. We can guess that
is a root. (See below about how to make an educated guess.) Dividing
by
gives
. (Instead of describing this division, I'll describe the next one.) Again by guessing,
is a root of
.
To divide
by
, make a table with three rows. The first row consists of the coefficients of
. The first element of the second row is 0. The third row is the sum of the first two. Therefore, the first element of the third row is 2.
Code:
2 -7 -3 18
0 4 -6 -18
2 -3 -9 0
The second and each subsequent element of the second row is
times the element of the third row immediately to the left. So, 4 = 2 * 2, -6 = 2 * (-3), and -18 = 2 * (-9). One computes the second and third row simultaneously left to right. The result indicates that the ratio is the polynomial
and the remainder is 0. Now,
is a quadratic equation.
To make an educated guess about the roots, one can use the rational root theorem. It says that if a rational number
(in the lowest terms) is a root of
, then
divides the constant term of
and
divides the leading coefficient. So, for
, all rational roots are among
. Note that the theorem says nothing about irrational roots.