Editing Horner's method (section)

== Polynomial root finding ==
Using the long division algorithm in combination with [[Newton's method]], it is possible to approximate the real roots of a polynomial. The algorithm works as follows. Given a polynomial <math>p_n(x)</math> of degree <math>n</math> with zeros <math> z_n < z_{n-1} < \cdots < z_1,</math> make some initial guess <math> x_0 </math> such that <math> z_1 < x_0 </math>. Now iterate the following two steps:

# Using [[Newton's method]], find the largest zero <math>z_1</math> of <math>p_n(x)</math> using the guess <math>x_0</math>.
# Using Horner's method, divide out <math>(x-z_1)</math> to obtain <math>p_{n-1}</math>. Return to step 1 but use the polynomial <math>p_{n-1}</math> and the initial guess <math>z_1</math>.

These two steps are repeated until all real zeros are found for the polynomial. If the approximated zeros are not precise enough, the obtained values can be used as initial guesses for Newton's method but using the full polynomial rather than the reduced polynomials.<ref>{{harvnb|Kress|1991|p=112}}.</ref>

=== Example ===

[[File:HornerandNewton.gif|thumb|right|400px|Polynomial root finding using Horner's method]]

Consider the polynomial
<math display="block">p_6(x) = (x+8)(x+5)(x+3)(x-2)(x-3)(x-7)</math>
which can be expanded to
<math display="block">p_6(x) = x^6 + 4x^5 - 72x^4 -214x^3 + 1127x^2 + 1602x -5040.</math>

From the above we know that the largest root of this polynomial is 7 so we are able to make an initial guess of 8. Using Newton's method the first zero of 7 is found as shown in black in the figure to the right. Next <math>p(x)</math> is divided by <math>(x-7)</math> to obtain
<math display="block">p_5(x) = x^5 + 11x^4 + 5x^3 - 179x^2 - 126x + 720</math>
which is drawn in red in the figure to the right. Newton's method is used to find the largest zero of this polynomial with an initial guess of 7. The largest zero of this polynomial which corresponds to the second largest zero of the original polynomial is found at 3 and is circled in red. The degree 5 polynomial is now divided by <math>(x-3)</math> to obtain
<math display="block">p_4(x) = x^4 + 14x^3 + 47x^2 - 38x - 240</math>
which is shown in yellow. The zero for this polynomial is found at 2 again using Newton's method and is circled in yellow. Horner's method is now used to obtain
<math display="block">p_3(x) = x^3 + 16x^2 + 79x + 120</math>
which is shown in green and found to have a zero at&nbsp;&minus;3. This polynomial is further reduced to
<math display="block">p_2(x) = x^2 + 13x + 40</math>
which is shown in blue and yields a zero of&nbsp;&minus;5. The final root of the original polynomial may be found by either using the final zero as an initial guess for Newton's method, or by reducing <math>p_2(x)</math> and solving the [[linear equation]]. As can be seen, the expected roots of &minus;8, &minus;5, &minus;3, 2, 3, and 7 were found.