Encyclopedia > Horner scheme

  Article Content

Horner scheme

The Horner scheme is an algorithm for the efficient evaluation of polynomial functions, and for dividing polynomials by linear polynomials.

Given a number x and a polynomial p(T) = a0 + a1T + ... + anT n, the Horner scheme computes the number

p(x) = a0 + a1x + a2x2 + ... + an xn
as well as a polynomial q(T) = b0 + b1T + ... + bn-1T n-1 such that
p(T) = (T - x) · q(T) + p(x).
The algorithm works as follows:

  1. set i := n - 1
  2. set bi := an
  3. if i < 0, stop; the result p(x) is in b-1.
  4. set i := i - 1
  5. set bi := bi+1 * x + ai+1
  6. Go to step 3.

This is the method of choice for evaluating polynomials; it is faster and more numerically stable than the "normal" method, which involves computing the powers of x and multiplying them with the coefficients. The Horner scheme is often used to convert between different positional number systems (in which case x is the base of the number system, and the ai are the digits) and can also be used if x is a matrix, in which case the gain is even larger.

There is another way to describe the Horner scheme. Given the ai coefficients and the number x, first rewrite p with x factored out:

p(x) = a0 + a1x + a2x2 + ... + an-1 xn-1 + an xn
= a0 + x(a1 + x(a2 + ... + x(an-1 + x(an)) ... ))
then evaluate this expression in the obvious way, starting from the innermost parentheses and working out. The value of the expression in the innermost parentheses is bn-1. The value of the expression in the second-to-innermost parentheses is bn-2, and so on until until the value of the contents of the outermost parentheses is b0.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Jamesport, New York

... residing in the town. The population density is 133.3/km² (345.1/mi²). There are 959 housing units at an average density of 83.8/k ...

This page was created in 24.7 ms