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_0 + 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 [1] and P. Ruffini [1].

References

[1]	W.G. Horner, Philos. Transact. Roy. Soc. London Ser. A , 1 (1819) pp. 308–335
[2]	P. Ruffini, Mem. Coronata Soc. Ital. Sci. , 9 (1802) pp. 44–526

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

[a1]	F.B. Hildebrand, "Introduction to numerical analysis" , McGraw-Hill (1974)
[a2]	F. Cajori, "A history of mathematics" , Chelsea, reprint (1980)