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
of the terms of the th degree polynomial in in order to reduce the computation of the polynomial (at some value ) to multiplications and additions.
The rule can be generalized to a finite series
of orthogonal polynomials
. Using the recurrence relation
for orthogonal polynomials, one obtains
with
for the evaluation of at some particular . This is a simpler calculation than the straightforward approach, since and are known, and are easy to compute (possibly themselves by Horner's rule), and and are given by a backwardsrecurrence which is linear in .
References
