Polynomial interpolation works fundamentally by determining the value of an interpolating polynomial at a number of desired points. To obtain this polynomial, first we must determine its coefficients by computing divided differences.

The *interpol* operation begins by allocating
space for the divided differences as well as for the coefficients to
be determined (see Example
13-1). Note that since the entries in each row in a
divided-difference table depend only on the entries computed in the
row before it (see Figure 13.2 and
Figure 13.3), we do not have to keep
all of the table around at once. Thus, we allocate space only for the
largest row, which has * n* entries. Next, we
initialize the first row in the table with the values in

`fx`

`x`

`fx`

`fx[0]`

`coeff[0]`

The process of computing divided differences revolves around a single nested loop, which uses the
formula for divided differences discussed earlier in the chapter. In
terms of Figure 13.2 and Figure 13.3, the outer loop,
* k*, counts the number of rows for which
entries must be computed (excluding the rows for

`x`

`fx`

`i`

Start Free Trial

No credit card required