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.

Interpolation with nine points to find the value of a function at other points
Figure 13.1. Interpolation with nine points to find the value of a function at other points

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, . . ., an are coefficients. Polynomials of this form are said to have degree n, provided an is nonzero. This is the 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.