Horner scheme

From Free net 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 1 History 2 Basic idea 3 Horner algorithm 4 Application 5 See also 6 References

History

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

It has been shown that the Horner scheme is optimal, that is, any algorithm that evaluates 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, and Victor Pan proved that the number of multiplications is minimal in 1966.

Basic idea

Assume we want to evaluate the polynomial in the monomial form

<math>p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots + a_nx^n.</math>

for given a₀,...,a_n. That is we want to know

<math>p(x) = y</math>

for a given x. When using the monomial form of the polynomial we need n additions and (n²+n)/2 multiplications for the calculation of p(x). Our aim is to decrease the number of multiplications because they are slow and numerically unstable compared to the additions. The Horner algorithm rearranges the polynomial into the recursive form

<math>p(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x)\cdots))</math>

and then evaluates the polynomial recursively using only n additions and n multiplications. Additionally it is numerically more stable because we eliminated some multiplications. Alternatively it could be computed with n fused multiply-adds.

Horner algorithm

Given the polynomial

<math>p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n.</math>

we rearrange it into

<math>p(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x)))</math>

Then starting from the innermost parentheses and working outwards we define

<math>

\begin{matrix}

   b_n & := & a_{n}             \\

b_{n-1} & := & a_{n-1} + b_{n} x \\

       & \vdots &              \\
 b_{0} & := & a_{0} + b_{1} x 

\end{matrix} </math>

If we put the b_n in the polynomial we see that

<math>

\begin{matrix} p(x) & = & a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + b_n x))) \\ p(x) & = & a_0 + x(a_1 + x(a_2 + \cdots x(b_{n-1}))) \\

    & \vdots &              \\

p(x) & = & a_0 + x(b_1) \\ p(x) & = & b_0 \\ \end{matrix} </math>

so b₀ is the value of the polynomial p at x.

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 are the digits) and can also be used if x is a matrix, in which case the gain is even larger.

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

See also

• 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.
• Clenshaw algorithm to evaluate polynomials in Chebyshev form
• De Casteljau's algorithm to evaluate polynomials in Bézier form

References

• 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 0262032937. Problem 2-3 (pg.39) and page 823 of section 30.1: Representation of polynomials.de:Horner-Schema

fr:Méthode de Hörner nl:Hornerschema pl:Schemat Hornera pt:Esquema de Horner sv:Horners algoritm