An Introduction to Numerical Methods and Analysis, 2nd Edition

CHAPTER 4

INTERPOLATION AND APPROXIMATION

One of the oldest problems in mathematics—and, at the same time, one of the most applied—is the problem of constructing an approximation to a given function f from among simpler functions, typically (but not always) polynomials. A slight variation of this problem is that of constructing a smooth function from a discrete set of data points.

In this chapter we will study both of these problems and develop several methods for solving them. We start with a more general treatment of an idea we first saw in Chapter 2.

4.1 LAGRANGE INTERPOLATION

The basic interpolation problem can be posed in one of two ways:

1. Given a set of nodes {x_i, 0 ≤ i ≤ n} and corresponding data values {y_i, 0 ≤ i ≤ n}, find the polynomial p_n(x) of degree less than or equal to n, such that

2. Given a set of nodes {x_i, 0 ≤ i ≤ n} and a continuous function f(x), find the polynomial p_n(x) of degree less than or equal to n, such that

Note that in the first case we are trying to fit a polynomial to the data, and in the second we are trying to approximate a given function with the interpolating polynomial.

While the two cases are in fact different, we can always consider the first one to be a special case of the second (by taking y_i = f(x_i), for each i), so we will present most ...