Horner's Method

A method for finding roots of a polynomial equation . Now find an equation whose roots are the roots of this equation diminished by , so

(1)

The expressions for , , ... are then found as in the following example, where

(2)

Write the coefficients , , ...,  in a horizontal row, and let a new letter shown as a denominator stand for the sum immediately above it so, in the following example, . The result is the following table.

Solving for the quantities , , , , and  gives

			(3)
			(4)
			(5)
			(6)
			(7)

so the equation whose roots are the roots of , each diminished by , is

(8)

(Whittaker and Robinson 1967).

To apply the procedure, first determine the integer part of the root through whatever means are needed, then reduce the equation by this amount. This gives the second digit, by which the equation is once again reduced (after suitable multiplication by 10) to find the third digit, and so on.

To see the method applied, consider the problem of finding the smallest positive root of

(9)

This root lies between 1 and 2, so diminish the equation by 1, resulting in the left table shown above. The resulting diminished equation is

(10)

and roots which are ten times the roots of this equation satisfy the equation

(11)

The root of this equation between 1 and 10 lies between 3 and 4, so reducing the equation by 3 produces the right table shown above, giving the transformed equation

(12)

This procedure can be continued to yield the root as approximately 1.3819659.

Horner's process really boils down to the construction of a divided difference table (Whittaker and Robinson 1967).

REFERENCES:

Boyer, C. B. and Merzbacher, U. C. A History of Mathematics, 2nd ed. New York: Wiley, pp. 202-204, 256, and 307, 1991.

Horner, W. G. "A New Method of Solving Numerical Equations of All Orders by Continuous Approximation." Philos. Trans. Roy. Soc. London 109, 308-335, 1819.

Matthews, J. H. "Bibliography for Horner's Method." http://math.fullerton.edu/mathews/n2003/horner/HornerBib/Links/HornerBib_lnk_2.html.

Peña, J. M. and Sauer, T. "On the Multivariate Horner Scheme." SIAM J. Numer. Anal. 37, 1186-1197, 2000.

Peña, J. M. and Sauer, T. "On the Multivariate Horner Scheme II: Running Error Analysis." SIAM J. Numer. Anal. 65, 311-322, 2000.

Ruffini, P. "Sopra la determinazione delle radici nelle equazioni numeriche di qualunque grado." Modena, Italy, 1804.

Ruffini, P. Memorie di Mat. e di Fis. della Soc. Italiana delle Scienze. Verona, Italy, 1813.

Séroul, R. "Evaluation of Polynomials: Horner's Method." §10.6 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 216-262, 2000.

Whittaker, E. T. and Robinson, G. "The Ruffini-Horner Method." §53 in The Calculus of Observations: A Treatise on Numerical Mathematics, 4th ed. New York: Dover, pp. 100-106, 1967.