horner scheme

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.

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.

Basic idea

Assume we want to evaluate the polynomial in the monomial form

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

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

p(x) = y

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 instable compared to the additions. The Horner algorithm rearranges the polynomial into the recursive form

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

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

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

we rearrange it into

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

Then starting from the innermost parentheses and working outwards we define

\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} If we put the b_n in the polynomial we see that

\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} so b₀ is the 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).

Horner Scheme

History

Basic idea

Horner algorithm

Application

See also