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.
| Contents |
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
- <math>p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots + a_nx^n.<math>
for given a0,...,an. 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 n2+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 (a_{n-1} + a_n x)))<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 bn 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 b0 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 ai 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 formde:Horner-Schema