TOPICS
Search

Horner's Method

A method for finding roots of a polynomial equation f(x)=0. Now find an equation whose roots are the roots of this equation diminished by r, so

0=f(x+r)=f(r)+xf^'(r)+1/2x^2f^('')(r)+1/3x^3f^(''')(r)+....
(1)

The expressions for f(r), f^'(r), ... are then found as in the following example, where

f(x)=Ax^5+Bx^4+Cx^3+Dx^2+Ex+F.
(2)

Write the coefficients A, B, ..., F 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, P=Ar+B. The result is the following table.

ABCDEF
(Ar)/P(Pr)/Q(Qr)/R(Rr)/S(Sr)/omega
(Ar)/T(Tr)/U(Ur)/R(Vr)/chi
(Ar)/W(Wr)/X(Xr)/psi
(Ar)/Y(Yr)/phi
(Ar)/theta

Solving for the quantities theta, phi, psi, chi, and omega gives

theta=5Ar+B=1/(4!)f^((iv))(r)
(3)
phi=10Ar^2+4Br+C=1/(3!)f^(''')(r)
(4)
psi=10Ar^3+6Br^2+3Cr+D=1/(2!)f^('')(r)
(5)
chi=5Ar^4+4Br^3+3Cr^2+2Dr+E=f^'(r)
(6)
omega=Ar^5+Br^4+Cr^3+Dr^2+Er+F=f(r),
(7)

so the equation whose roots are the roots of f(x)=0, each diminished by r, is

0=Ax^5+thetax^4+phix^3+psix^2+chix+omega
(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.

HornersMethod

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

x^3-4x^2+5=0.
(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

x^3-x^2-5x+2=0,
(10)

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

x^3-10x^2-500x+2000=0.
(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

x^3-x^2-533+437=0.
(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).

See also

Divided Difference, Newton's Method

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Horner's Method

Cite this as:

Weisstein, Eric W. "Horner's Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HornersMethod.html

Subject classifications