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.