Mastering Algorithms With C - Kyle Loudon [147]
Function tables
Tables containing values of computationally expensive functions or models of complicated physical phenomena. Often it is too costly to compute and store values of a function with the granularity required at some later time. Thus, we store a limited number of points and interpolate between them.
Scientific computing
An area in which solving equations is one of the most fundamental problems routinely performed.
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.
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)(x-c 2). . . (x-c n)
where a 0, . . ., an are coefficients and c 1, . . ., cn are centers. Notice how when c 1, . . ., cn are all 0, the Newton form of a polynomial reduces to the power form above.
Constructing an Interpolating Polynomial
Now that we understand a bit about polynomials, let's look at how to construct the polynomial that interpolates a function f (x). To interpolate f (x), a polynomial pn (z) of degree ≤ n is constructed using n + 1 points, x 0, . . ., xn , known along f (x). The points x 0, . . ., xn are called interpolation points. Using pn (z), we approximate the value of f (x) at x=z. Interpolation requires that point z be on the interval [x 0, xn ]. pn (z) is constructed using the formula:
where x 0, . . ., xn are the points along f (x) for which values are known, and f [ x 0], . . ., f [x 0, . . ., xn ] are divided differences, which are derived from x 0, . . ., xn and the values of f (x) at these points. This is called the Newton formula for interpolating polynomials. Notice its similarities with the Newton form of polynomials in general. Divided differences are computed using the formula:
Notice that this formula shows that for divided differences when i < j we must have computed other divided differences beforehand. For example, to compute f [x 0, x 1, x 2, x 3], values are required for f [x 1, x 2, x 3] and f [x 0, x 1, x 2] in the numerator. Fortunately, we can use a divided-difference table to help compute divided differences in a systematic manner (see Figure 13.2).
A divided-difference table consists of several rows. The top row stores x 0, . . ., xn . The second row stores values for f [x 0], . . ., f [xn ]. To compute each divided difference in the remainder of the table, we draw a diagonal from each divided difference back to f [xi ] and f [xj ] (shown as dotted lines for f [x 1, x 2, x 3] in Figure 13.2). To get xi and xj in the denominator, we then proceed straight up from f [xi ] and f [xj ]. The two divided differences in the numerator are those immediately above the one being computed. When the table is complete, the coefficients for the interpolating polynomial are the divided differences at the far left of each row, beginning with the second row (shown in light