| Version 6 |
Version 5 |
|
Horner's rule makes use of the repeated factorizations
|
Horner's rule makes use of the reapeated 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 (at some value of $x$) 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 |
one obtains |
| $$ y=(a_0 + C_2 b_2) p_0 + b_1 p_1 $$ |
$$ y=(a_0 + C_2 b_2) p_0 + b_1 p_1 $$ |
| 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 x) 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*} |
| {\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} |
