## Description of Polynomial Interpolation

There are many problems that can be described in terms
of a function. However, often this function is not known, and we must
infer what we can about it from only a small number of points. To do
this, we *interpolate* between the points. For
example, in Figure 13.1, the
known points along *f* (*x*) are
*x* _{0}, . . .,
*x* _{8}, shown by circular
black dots. Interpolation helps us get a good idea of the value of the
function at points *z* _{0},
*z* _{1}, and
*z* _{2}, shown by white
squares. This section presents polynomial interpolation.

Fundamental to polynomial interpolation is the construction of a
special polynomial called an *interpolating polynomial*. To
appreciate the significance of this polynomial, let’s look at some
principles of polynomials in general. First, a polynomial is a
function of the form:

*p(x) = a*
_{0}+*a*
_{1} *x*+*a*
_{2} *x*
^{2}+. . . +*a*
_{n} *x*
^{n}

where *a* _{0}, . . .,
*a _{n} * are coefficients.
Polynomials of this form are said to have degree

*n*, provided

*a*is nonzero. This is the

_{n}*power form*of a polynomial, which is especially common in mathematical discussions. However, other forms of polynomials are more convenient in certain contexts. For example, a form particularly relevant to polynomial interpolation is the

*Newton form*:

*p(x) = a*
_{0}+*a*
_{1}(*x-c*
_{1})+*a*
_{2}(*x-c*
_{1})(*x-c*
_{2})+ . . . +*a*
_{n}(*x-c*
_{1})( ...

Get *Mastering Algorithms with C* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.