Horner scheme
From Wikipedia, the free encyclopedia
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.
Contents[hide] |
[edit] Description of the algorithm
Given the polynomial
where are real numbers, we wish to evaluate the polynomial at a specific value of , say .
To accomplish this, we define a new sequence of constants as follows:
Then is the value of .
To see why this works, note that the polynomial can be written in the form
Thus, by iteratively substituting the bi into the expression,
[edit] Examples
Let and . Divide by using Horner's scheme. We can use a synthetic diagram to make the process faster.
2 | 4 -6 0 3 | -5 ---------------------------|------ 1 | 2 -2 -1 | 1 | | |----------------------|------- 2 -2 -1 1 | -4
The answer is
[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 ai 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 (n2+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 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
- De Boor's algorithm to evaluate splines in B-spline 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.