Horner’s rule

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

	$\\displaystyle y$	$\\displaystyle=$	$\\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\\cdots+a_{n}x^{n}$
		$\\displaystyle=$	$\\displaystyle a_{0}+x(a_{1}+x(a_{2}+x(a_{3}+\\cdots+xa_{n}))\\cdots)$

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

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

p_{k}=(A_{k}+B_{k}x)p_{k-1}+C_{k}p_{k-2}

for orthogonal polynomials, one obtains

y(a)=(a_{0}+C_{2}b_{2})p_{0}(a)+b_{1}p_{1}(a)

with

	$\\displaystyle b_{n+1}$	$\\displaystyle=$	$\\displaystyle b_{n+2}=0,$
	$\\displaystyle b_{k-1}$	$\\displaystyle=$	$\\displaystyle(A_{k}+B_{k}\\cdot a)b_{k}+C_{k+1}+b_{k+1}+a_{k-1}$

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$ .

References

•
Originally from The Data Analysis Briefbook(http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)