Mastering Algorithms With C - Kyle Loudon [148]
Figure 13.2. A divided-difference table for determining the coefficients of an interpolating polynomial of degree 3
Evaluating an Interpolating Polynomial
Once we have determined the coefficients of the interpolating polynomial pn (z), we evaluate the polynomial once for each point at which we would like to know the value of f. For example, say we know the values of f at four points: x 0 = -3.0, f (x 0) = -5.0; x 1 = -2.0, f (x 1) = -1.1; x 2 = 2.0, f (x 2) = 1.9; and x 3 = 3.0, f (x 3) = 4.8; and we would like to know the value of f at z 0 = -2.5, z 1 = 0.0, z 2 = 1.0, and z 3 = 2.5. Since we know four points along f, the interpolating polynomial will have a degree of 3. Figure 13.3 is the divided-difference table for determining the coefficients of p 3(z).
Figure 13.3. A divided-difference table producing the coefficients -5.0, 3.9, -0.63, and 0.1767
Once we have obtained the coefficients from the divided-difference table, we construct p 3(z) using the Newton formula for interpolating polynomials presented earlier. Using the coefficients from Figure 13.3, the interpolating polynomial is:
p 3(z) = -5.0+3.9(z+3.0)+(-0.63)(z+3.0)(z+2.0)+0.1767(z+3.0)(z+2.0)(z-2.0)
Next, we evaluate this polynomial once at each point z. For example, at z 0 = -2.5 we perform the following calculation:
p 3(-2.5) = -5.0+3.9(0.5)+(-0.63)(0.5)(-0.5)+0.1767(0.5)(-0.5)(-4.5) = -2.694
The value of f at z 1, z 2, and z 3 is determined in a similar manner. The results are tabulated and plotted in Figure 13.4.
Figure 13.4. Interpolating a function f (x) using the polynomial p3(z) presented in the text
Now that we have an understanding of how to interpolate a function, it is important to briefly mention the subject of error. As with any approximation method, it is important to understand that an interpolating polynomial usually has some amount of error associated with it. To minimize this error, qualitatively speaking, we must construct an interpolating polynomial using enough points along f (x), and ones properly spaced, so that the resulting polynomial gives an accurate impression of the function's character. Naturally, quantitative methods do exist for bounding the error associated with interpolation, but this book will not address them (see the related topics at the end of the chapter).
Interface for Polynomial Interpolation
Name
interpol
Synopsis
int interpol (const double *x, const double *fx, int n, double *z, double *pz,
int m);
Return Value
0 if interpolating is successful, or -1 otherwise.
Description
Determines the value of a function at specified points using polynomial interpolation. Points at which values are known are specified by the caller in x. The known values of the function at each point in x are specified in fx. Points at which values are to be determined are specified in z. The values calculated for the points passed in z are returned in pz. The number of values in x and fx is specified as n. The number of points in z (and thus returned in pz) is specified as m. It is the responsibility of the caller to manage the storage associated with x, fx, z, and pz.
Complexity
O (mn 2), where m is the number of values to determine and n is the number of points at which values are known.
Implementation and Analysis of Polynomial Interpolation
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.