Horner scheme

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged with Ruffini's rule. (Discuss)

In the mathematical subfield of numerical analysis, the Horner scheme or Horner algorithm, named after William George Horner, is an algorithm for the efficient evaluation of polynomials in monomial form.

1 Description of the algorithm
2 Application
3 Efficiency
4 History
5 See also
6 References

[edit] Description of the algorithm

Given the polynomial

$p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,$

where $a_0, \ldots, a_n$ are real numbers, we wish to evaluate the polynomial at a specific value of $x\,\!$ , say $x_0\,\!$ .

To accomplish this, we define a new sequence of constants as follows:


$b_n\,\!$	$:=\,\!$	$a_n\,\!$
$b_{n-1}\,\!$	$:=\,\!$	$a_{n-1} + b_n x_0\,\!$
	$\vdots$
$b_0\,\!$	$:=\,\!$	$a_0 + b_1 x_0\,\!$

Then $b_0\,\!$ is the value of $p(x_0)\,\!$ .

To see why this works, note that the polynomial can be written in the form

$p(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x) \cdots ))$

Thus, by iteratively substituting the $b i$ into the expression,


$p(x)\,\!$	$=\,\!$	$a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + b_n x) \dots ))$
	$=\,\!$	$a_0 + x(a_1 + x(a_2 + \cdots x(b_{n-1}) \dots ))$
	$\vdots$
	$=\,\!$	$a_0 + x(b_1)\,\!$
	$=\,\!$	$b_0\,\!$

[edit] Application

The Horner scheme is often used to convert between different positional numeral systems — in which case x is the base of the number system, and the a_i coefficients are the digits of the base-x representation of a given number — and can also be used if x is a matrix, in which case the gain in computational efficiency is even greater.

The Horner scheme can also be viewed as a fast algorithm for dividing a polynomial by a linear polynomial (see Ruffini's rule).

[edit] Efficiency

Evaluation using the monomial form of a degree-n polynomial requires at most n additions and (n²+n)/2 multiplications, if powers are calculated by repeated multiplication. Horner's scheme requires only n additions and n multiplications. (Minimizing the number of multiplications is desirable because they are time consuming and numerically unstable compared to addition.) Alternatively, Horner's scheme can be computed with n fused multiply-adds.

It has been shown that the Horner scheme is optimal, in that any algorithm to evaluate an arbitrary polynomial must use at least as many steps. That the number of additions required is minimal was shown by Alexander Ostrowski in 1954, that the number of multiplications is minimal by Victor Pan 1966. When x is a matrix, the Horner scheme is not optimal.

This assumes that the polynomial is evaluated in monomial form and no preconditioning of the representation is allowed, which makes sense if the polynomial is evaluated only once. However, if preconditioning is allowed and the polynomial is to be evaluated many times, then faster algorithms are possible. They involve a transformation of the representation of the polynomial. In general, a degree-n polynomial can be evaluated using only $\left\lfloor \frac{n}{2} \right \rfloor +2$ multiplications and n additions [see D.E. Knuth: The Art of Computer Programming, Vol.2]

[edit] History

Even though the algorithm is named after William George Horner, who described it in 1819, the method was already known to Isaac Newton in 1669, and even earlier to the Chinese mathematician Ch'in Chiu-Shao in the 13th century.

[edit] See also

Clenshaw algorithm to evaluate polynomials in Chebyshev form
De Casteljau's algorithm to evaluate polynomials in Bézier form

[edit] References

William George Horner. A new method of solving numerical equations of all orders, by continuous approximation. In Philosophical Transactions of the Royal Society of London, pp. 308-335, July 1819.
Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Pages 486–488 in section 4.6.4.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-3 (pg.39) and page 823 of section 30.1: Representation of polynomials.