CS323 LECTURE NOTES - LECTURE 11
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
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:
year |
population |
1950 1960 . . . 2010 |
. . . |
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
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:
x1 = 1 x2 = 2 x3 = 3 |
y1 = 6 y2 = 4 y3 = 8 |
n = 2
Suppose that we have three 2nd-degree polynomials L1, L2 and
L3
such that:
L1(x1) = 1 L1(x2) = 0 L1(x3) = 0 |
L2(x1) = 0 L2(x2) = 1 L2(x3) = 0 |
L3(x1) = 0 L3(x2) = 0 L3(x3) = 1 |
(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
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) =
(x − x1)(x − x3) |
(x2 − x1)(x2 − x3) (x − x1)(x − x2) |
(x3 − x1)(x3 − x2) |
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
L1(x) = L2(x) = L3(x) = |
= (x2 − 5x + 6) |
= − (x2 − 4x + 3) |
|
= (x2 − 3x + 2) |
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:
P2(x) = 3x2 − 11x + 14
2022-03-29