CS323 LECTURE NOTES - LECTURE 11

1 Interpolation and Approximation

1.1 Interpolation and Extrapolation

One of the main objectives of the search for mathematical models that describe the behavior of reality is to be able to predict future experimental results.

Suppose that we want to predict the population of the United States in the year 2030. Can we use data from past census to do our prediction? Suppose that we have census data stored on a table:

If we plot the data we might be able to nd a trend and make a prediction. This prediction of a value outside of the range of the given data is called extrapolation

If now we want to know the population in the year 2005, we can also use the same initial data, but now our ”guess” will be within the initial range of data. This is called interpolation.

In the case of extrapolation, if the value that we want to predict is very far from the initial range, the prediction will be bad.

1.2 Polynomial interpolation

suppose that we have a set of pairs (x,y)

.  .

.  .

.  .

where there are no duplicate values of x, i.e., xi  xj if i  j. We want to nd a degree n polynomial Pn(x) that goes exactly through each one of the points, i.e.

P(x1) = y1

P(x2) = y2

P(x3) = y3

.    .

.    .

.    .

P(xn) = yn

The rst question we can ask is: What is the degree of the poly- nomial that we are looking for? Notice that if we are given two points, the lowest degree polynomial that goes through the points is a line (degree 1 polynomial). If we are given 3 points, the poly- nomial will be a parabola (degree 2 polynomial), and so on. If we are given n + 1 point, the polynomial will have degree=n.

We can easily prove the following theorem:

Theorem

the polynomial of degree n that goes exactly through n + 1 points is unique.

Proof

We know that a given n-degree polynomial has exactly n roots. Suppose that there are two distinct n-degree polynomials Pn(x) and Qn(x) that agree on the points x1,x2, . . . ,xn+1, i.e.

Pn−1(xi) = Qn−1(xi) ∀i = 1, . . .n + 1

Let us dene the following polynomial

Rn(x) = Pn(x) − Qn(x)

This polynomial clearly satises

Rn(xi) = 0 ∀i = 1, . . . ,n + 1

but we know from the Fundamental Theorem of Algebra that the only n-degree polynomial with n + 1 roots is the 0 polyno- mial. Therefore,

Rn(x) = 0; ∀x ∈ R

which implies that

Pn(x) = Qn(x)

which completes the proof of the theorem.

1.3 Lagrange Polynomials

Suppose that we are able to nd n+1 polynomials of degree n that satisfy the condition ∀j = 1 . . .n + 1

Lj (xi) = 

To see how we can use such polynomials suppose that we want to nd a degree-2 polynomial that goes through the points:

n = 2

Suppose that we have three 2nd-degree polynomials L1, L2 and

L3

such that:

(1)

Using these polynomials we can easily write an interpolating polynomial of degree 2 that goes exactly through each one of the given 3 points:

P2(x) = L1(x)y1 + L2(x)y2 + L3(x)y3          We can verify that P2(x) goes through the 3 given points:

P2(x1) =

=

=

P2(x2) =

=

=

L1(x1)y1 + L2(x1)y2 + L3(x1)y3

(1)y1 + (0)y2 + (0)y3

y1

L1(x2)y1 + L2(x2)y2 + L3(x2)y3

(0)y1 + (1)y2 + (0)y3

y2

P2(x2) =

=

=

L1(x2)y1 + L2(x2)y2 + L3(x2)y3

(0)y1 + (0)y2 + (1)y3

y3

We now only have to nd L1, L2 and L3. Which is easy if we notice that

q(x) = (x − x2)(x − x3)

is a polynomial of degree 3 such that

q(x1) = q(x2) = q(x3) =

(x1 − x2)(x1 − x3)

0

0

Since we know that x1  x2 and x1  x3, we can dene

q(x)   (x − x2)(x − x3)

q(x1)  (x1 − x2)(x1 − x3)

In the same way we have

L2(x) =

L3(x) =

We can easily verify that these polynomials satisfy conditions (1), therefore, the 2nd-degree polynomial that goes through the given points is:

P2(x) =  y1+  y2+  y3

This polynomial is known as The Lagrange Polynomial. It can easily be generalized to a polynomial of degree n if we are given n + 1 points:

Li(x) = j(n)j

(2)

and

n+1

Pn(x) = XLi(x)yi

i=1

(3)

The number of factors that appear in each product that denes Li is n, hence the degree of each polynomial is n − 1.

Example

Find the Lagrange polynomial that goes through the points:

x y 1  6 2  4 3  8

Notice that since we have 3 points, the degree of the polynomial that we are looking for must be 2. Using the formulas for L given above, we have that

If we substitute in P2(x) we get

P2(x) =  (x2 − 5x + 6)(6) − (x2 − 4x + 3)(4) +  (x2 − 3x + 2)(8)

So we have that the interpolating polynomial that goes through the given points is: