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 {xi, 0 ≤ in} and corresponding data values {yi, 0 ≤ in}, find the polynomial pn(x) of degree less than or equal to n, such that

equation

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

equation

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 yi = f(xi), for each i), so we will present most ...

Get An Introduction to Numerical Methods and Analysis, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.