View source for Horner scheme

A method for obtaining the incomplete fraction and the remainder in the division of a polynomial
\begin{equation}\label{eq:1}
f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0
\end{equation}
by a binomial $x-a$, where all the coefficients $a,a_0,\ldots,a_n$ lie in a certain field, e.g. in the field of complex numbers. Any polynomial $f(x)$ can be uniquely represented in the form
$$
f(x) = g(x)(x-a) + r
$$
where $g(x) = b_{n-1}x^{n-1} + b_{n-2}x^{n-2} + \cdots + b_0$ is the incomplete fraction, while $r$ is the remainder which, according to the [[Bezout theorem]], equals $f(a)$. The coefficients of $g(x)$ and $r$ are calculated by the recurrence formulas
\begin{equation}\label{eq:2}
\left.{
\begin{array}{c}
b_{n-1} = a_n,\ \ b_{n-2} = a_{n-1} + a b_{n-1},\ \ldots\,,\ b_0 = a_1 + a b_1 \ ; \\
r = a_0 + a b_0 
\end{array}
}\right\rbrace\ \ .
\end{equation}

The following table
$$
\begin{array}{|c|c|c|c|c|c|}
\hline \\
a_n & a_{n-1} & \ldots & a_1 & a_0 \\
\hline \\
a & b_{n-1} & b_{n-2} & \ldots & b_0 \\
\hline
\end{array}
$$
whose upper line is given, while the lower line is filled in accordance with the formulas \eqref{eq:2}), is used in the computations. In fact, this method is identical with the method of Ch'in Chiu-Shao employed in medieval China. At the beginning of the 19th century it was rediscovered, almost simultaneously, by W.G. Horner [[#References|[1]]] and P. Ruffini [[#References|[1]]].

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  W.G. Horner,   ''Philos. Transact. Roy. Soc. London Ser. A'' , '''1'''  (1819)  pp. 308–335</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  P. Ruffini,   ''Mem. Coronata Soc. Ital. Sci.'' , '''9'''  (1802)  pp. 44–526</TD></TR>
</table>



====Comments====
Horner's scheme is used for the efficient evaluation of polynomials. The straightforward evaluation of $f(x)$ for a given value $x=a$ by computing the powers $a^2,a^3,\ldots,a^n$ and forming the linear combination according to \eqref{eq:1} would require $2n-1$ multiplications. However, by writing $f(x)$ in the  "nested"  form
$$
f(x) = x(\cdots(x(xa_n + a_{n-1}) + a_{n-2}) \cdots)+a_0\,,
$$
only $n$ (sequential) multiplications are involved. It is easily verified that using this nested representation the work consists of the computation steps given by \eqref{eq:2}. Since $r=f(a)$, the evaluation of $f(a)$ requires $n$ instead of $2n-1$ multiplications.

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  F.B. Hildebrand,   "Introduction to numerical analysis" , McGraw-Hill  (1974)</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  F. Cajori,   "A history of mathematics" , Chelsea, reprint  (1980)</TD></TR>
</table>

{{TEX|done}}