| Version current |
Version 6 |
| Horner's rule is a technique to reduce the work required for the computation of a polynomial at a particular value. Its simplest form makes use of the repeated factorizations |
Horner's rule makes use of the repeated factorizations |
|
|
| \begin{eqnarray*} |
\begin{eqnarray*} |
| y & = & a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n \\ |
y & = & a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n \\ |
| & = & a_0 + x(a_1 + x(a_2 + x(a_3 + \cdots +xa_n)) \cdots ) |
& = & a_0 + x(a_1 + x(a_2 + x(a_3 + \cdots +xa_n)) \cdots ) |
| \end{eqnarray*} |
\end{eqnarray*} |
|
of the terms of the $n$th degree polynomial in $x$ in order to reduce the computation of the polynomial (at some value of $x$) to $n$ multiplications and $n$ additions. |
| of the terms of the $n$th degree polynomial in $x$ in order to reduce the computation of the polynomial $y(a)$ (at some value $x = a$) to $n$ multiplications and $n$ additions. |
|
|
|
| The rule can be generalized to a finite series |
The rule can be generalized to a finite series |
|
|
| $$ y = a_0 p_0 + a_1 p_1 + \cdots + a_n p_n $$ |
$$ y = a_0 p_0 + a_1 p_1 + \cdots + a_n p_n $$ |
|
|
| of orthogonal polynomials $p_k = p_k(x)$. Using the recurrence relation |
of orthogonal polynomials $p_k = p_k(x)$. Using the recurrence relation |
|
|
| $$ p_k = (A_k + B_k x) p_{k-1} + C_k p_{k-2} $$ |
$$ p_k = (A_k + B_k x) p_{k-1} + C_k p_{k-2} $$ |
|
one obtains |
| for orthogonal polynomials, one obtains |
$$ y=(a_0 + C_2 b_2) p_0 + b_1 p_1 $$ |
|
|
| $$ y(a) = (a_0 + C_2 b_2) p_0(a) + b_1 p_1(a) $$ |
|
|
|
| with |
with |
|
|
| \begin{eqnarray*} |
\begin{eqnarray*} |
| b_{n+1} & = & b_{n+2} = 0 , \\ |
b_{n+1} & = & b_{n+2} = 0 , \\ |
|
b_{k-1} & = & (A_k + B_k\cdot a) b_k + C_{k+1} + b_{k+1} + a_{k-1}
|
b_{k-1} & = & (A_k + B_k x) b_k + C_{k+1} + b_{k+1} + a_{k-1}
|
| \end{eqnarray*} |
\end{eqnarray*} |
|
|
| for the evaluation of $y$ at some particular $a$. This is a simpler calculation than the straightforward approach, since $a_0$ and $C_2$ are known, $p_0(a)$ and $p_1(a)$ are easy to compute (possibly themselves by Horner's rule), and $b_1$ and $b_2$ are given by a backwards-recurrence which is linear in $n$. |
|
|
|
| {\bf References} |
{\bf References} |
|
|
| \begin{itemize} |
\begin{itemize} |
| \item Originally from The Data Analysis Briefbook |
\item Originally from The Data Analysis Briefbook |
| (\PMlinkexternal{http://rkb.home.cern.ch/rkb/titleA.html}{http://rkb.home.cern.ch/rkb/titleA.html}) |
(\PMlinkexternal{http://rkb.home.cern.ch/rkb/titleA.html}{http://rkb.home.cern.ch/rkb/titleA.html}) |
| \end{itemize} |
\end{itemize} |
