Numerical Methods in Engineering (ENGR20005)
Lecture 09 Dr. Leon Chan
lzhchan@unimelb.edu.au Department of Mechanical Engineering The University of Melbourne
Slides prepared by Prof.Andrew Ooi
L9.1: Interpolation
2
“Book” (Chap. 5)
Interpolation – Motivation
Continuous Function
f : x ↦ sin(x)
Function at discrete points
y
f(y)
1
0.5
4
1.5
7
4.5
Figure 1: Continuous Function
Figure 2: Discrete Points.
3
Polynomial Interpolation
f3(x)
f (x) f (x1)
f (x) f (x3)
f2(x) f (x1) f (x2)
f (x) f (x1)
f (x0)
Interpolation “fits” a polynomial through a set of data points.
f (x2) f (x0)
f (x0)
x0x1x x0x1x2xx0x1x2x3x
We define a polynomial of the form
fn(x) = a0 + a1x + a2x2 + ⋯ + anxn (9.1) We will require the polynomial, to pass through all data points.
•
fn(xi)=f(xi) ⇒a0+a1xi+a2x2+a3x3+…+anxn =f(xi) iii
•
•
We need to solve for coefficients ai
For nth order polynomial, there are (n+1) unknowns ai so we
f1(x)
•
need (n+1) data points. 4
a0+a1x1+a2x2+⋯+anxn =f(x1) 11
a0+a1x2+a2x2+⋯+anx2n =f(x2) a0+a1x3+a2x2+⋯+anxn =f(x3)
(n+1)equations,
(n + 1) unknowns,
a0 + a1xn+1 + a2x + ⋯ + anx
= f(xn+1) Matrix form
a0 a1 a2 a3
a⋮
1 x x2 1 1
1 x2 x2
11 x23 ⋯ x2n
f(x1) f (x2) f(x3) f(x4) ⋮
Can use any of the techniques in lectures 4 and 5 to solve.
• But you will find that this set of equation is notoriously difficult to solve.
3 3
. = .
.=. 2 n.=.
n+1 x3⋯xn
n+1
a , a , a , …, a . .=.012n
•
1 x3 x32
x3⋯x3n x43 ⋯ x4n
= 1xx2x3⋯xn n f(xn+1)•
1 x4 x42 ⋮⋮⋮⋮⋮⋮
n+1 n+1 n+1 n+1 Can we get interpolating polynomial without solving
5
set of equations?
L9.2:
Linear Newton Interpolating Polynomial
6
“Book” (Chap. 5, pg. 73)
Newton Interpolation – Linear
f (x)
f(x1) f1(x)
f (x0)
Shape of actual function f(x)
Difference between f (x) and f1(x)
f1(x)
x0 x x1 7
x
Newton Interpolation – Linear
Using similar triangles:
=
Rearrange Eq. (9.2) to give
(9.2)
f(x1) − f(x0) x1 − x0
f1(x) − f(x0) x−x0
f1(x) = f(x0) + f(x1) − f(x0) (x − x0) x1 − x0
(9.3)
8
f (x)
f(x1)
Shape of actual function f(x)
Newton Interpolation – Linear
Difference between f (x) and f1(x)
f1(x) = f (x0) + f (x1) − f (x0) (x − x0) x1 − x0
f1(x) f (x0)
f1(x)
x0x x1 9
x
f (x) f(x1)
Shape of actual function f(x)
f1(x) = f(x0) + f(x1) − f(x0) (x − x0) x1 − x0
Newton Interpolation – Linear
Difference between f (x) and f1(x)
f1(x)
f1(x) f (x0)
x0x x1 10
x
Newton Interpolation – Linear
f (x) f(x1)
Difference between f (x) and f1(x)
f1(x)
Shape of actual function f(x)
f1(x) = f(x0) + f(x1) − f(x0) (x − x0) x1 − x0
f1(x) f (x0)
x0
x
x1 x 11
f (x) f(x1)
f1(x) f (x0)
Shape of actual function f(x)
Newton Interpolation – Linear
Difference between
f (x) and f1(x)
f1(x) = f(x0) + f(x1) − f(x0) (x − x0)
f1(x)
x0 x x1
x1 − x0
x
12
Linear Interpolation Properties
f1(x) = f(x0) + f(x1) − f(x0) (x − x0) x1 − x0
A few things worth noting about the linear interpolation
• •
•
(9.3)
Equation (9.3) is called the Linear Newton interpolation formula.
In general, the smaller the interval between x0 and x1, the better the approximation at point x.
The subscript 1 for f1(x) denotes a first order interpolating polynomial.
13
Note that you can write the Linear Newton Interpolating Polynomial is just another the general linear polynomial written in a more convenient form.
f(x )−f(x ) f1(x)=f(x0)+ 1 0 (x−x0)
In the form of Newton Interpolating polynomial
x1 − x0
f1(x) = f(x0) − f(x1) − f(x0) x0 + f(x1) − f(x0) x
x1 − x0 x1 − x0 f1(x) = + x
General polynomial form
f1(x) = a0 + a1x
14
f(x0)x1 − f(x1)x0 x1 − x0
f(x1) − f(x0) x1 − x0
Exercise – Linear Interpolation
Example L09.1: Use linear interpolation to estimate the value of the function
f(x) = 1 − e−x
at x = 1.Use the interval x0 = 0 and x1 = 5.Repeat the calculation with x1 = 4,×1 = 3, x1 = 2. Illustrate on a graph how you are approaching the exact value of f(1) = 0.6321 .
15
Exercise – Linear Interpolation
Exact value of f(x = 1)
16
Exercise – Linear Interpolation
Exact value of f(x = 1)
17
Exercise – Linear Interpolation
Exact value of f(x = 1)
18
Exercise – Linear Interpolation
Exact value of f(x = 1)
19
Exercise – Linear Interpolation
Exact value of f(x = 1)
20
Use
Exercise – Linear Interpolation
f1(x) = f(x0) + f(x1) − f(x0) (x − x0) x1 − x0
f(x0 = 0) = 1 − 1 = 0
f(x1 = 5) = 1 − e−5 = 0.993269053 f(x1 = 4) = 1 − e−4 = 0.981684361 f(x1 = 3) = 1 − e−3 = 0.950212932
21
Exercise – Linear Interpolation
f1(x) = f(x0) + f(x1) − f(x0) (x − x0) x1 − x0
x1 = 5 : x1 = 4 :
Use
f1(1) = 0.993269053 ( 1 − 0 ) = 0.19966538 5−0
f1(1) = 0.981684361 ( 1 − 0 ) = 0.24542109 4−0
x1 = 3 :
f1(1) = 0.950212932 ( 1 − 0 ) = 0.31673764
3−0
22
End of Example L09.1
L9.3:
General Newton Interpolating Polynomial
24
“Book” (Chap. 5, pg. 73)
f(x1)
Newton Interpolation – Quadratic
Shape of actual function f(x)
f2(x)
f2(x) f (x0)
x0 Quadratic Polynomial
x1 x2 x
f2(x) = a0 + a1x + a2x2 25
(9.4)
Newton Interpolation – Quadratic
f2(x) = a0 + a1x + a2x2
To completely f2(x), we need to find a0, a1, and a2. We need to find 3 equations. To do that, we can require f2(x) to have the same values as the actual function at the data points, hence
• •
f2(x0) = f(x0)
⟹ a0 + a1x0 + a2x02 = f(x0) ⟹ a0+a1x1+a2x2=f(x1)
f2(x1) = f(x1) • f2(x2) = f(x2)
Note that the subscript 2 in f2(x) denotes that this is a second order interpolating polynomial.
Eq. (9.4) is just one form of the polynomial function defined in Eq. (9.1).
1
⟹ a0 + a1x2 + a2x2 = f(x2)
26
Newton Interpolation – Quadratic
f2(x) = a0 + a1x + a2x
2
Solving this equation
can involve a lot of work, especially for larger set of data points.
(9.5)
a 0 + a 1 x 0 + a 2 x 02 = f ( x 0 ) a0 + a1x1 + a2x2 = f(x1)
⟹
1
a0 + a1x2 + a2x2 = f(x2)
Consider re-writing f2(x) (Eq. (9.4)) as
f2(x) = b0 + b1(x − x0) + b2(x − x0)(x − x1)
It is possible that to show that a0, a1, a2 and b0, b1, and b2 are related a0 = b0 − b1x0 + b2x0x1
a1 = b1 − b2x0 − b2x1 a2 = b2
Hence, if we write f2(x) as in Eq. (9.5) all we need to do is to find all the b’s in Eq. (9.5).
You will see that for interpolating polynomials, it is much more convenient to write polynomial as in Eq. (9.5) 27
1x0x02a0 f(x0)
1x1x12 a1=f(x1) 1 x2 x2 a2 f(x2)
Newton Interpolation – Quadratic
f2(x) = b0 + b1(x − x0) + b2(x − x0)(x − x1) (9.5) 1. Set x = x0 in Eq. (9.5). Therefore
b0 = f(x0) (9.6)
28
Newton Interpolation – Quadratic
f2(x) = + b2(x − x0)(x − x1) (9.5)
1. Set x = x0 in Eq. (9.5). Therefore
b0 = f(x0) (9.6)
2. If we now let x = x1 in Eq (9.5) and use the result from
b0 + b1(x − x0)
step (1) above, we get
f(x1) − f(x0) x1 − x0
b1 =
29
(9.7)
Newton Interpolation – Quadratic
f2(x) = b0 + b1(x − x0) + b2(x − x0)(x − x1) (9.5) 3. Since f2(x2) = f(x2), we can use Eqs. (9.6) and (9.7)
together with Eq. (9.5) to obtain
f(x2) = f(x0) + f(x1) − f(x0) (x2 − x0) + b2(x2 − x0)(x2 − x1) x1 − x0
f(x2) − f(x1) − f(x1) − f(x0)
b2= x2−x1
x2 − x0 30
x1−x0 (9.8)
Newton Interpolation – Quadratic
Equations (9.7) and (9.8) can be simplified by introducing the following notation
f(x1) − f(x0) x1 − x0
f[x2,x1]−f[x1,x0] x2 − x0
b1 = f[x1,x0] = b2 = f[x2,x1,x0] =
(9.9)
(9.10)
The advantage of using the square brackets will be clear when we look at the general form of Newton’s interpolating polynomials in the next section.
In general, if you have n+1 data points, you will fit a polynomial of order n through all the n+1 data points.
31
i xi 0 x0 1 x1
2 x2
f(xi) f (x0)
f(x1) f (x2)
b0 =f(x0) b1 =f[x1,x0]= f(x1)−f(x0) x1 − x0
b2 =f[x2,x1,x0]= f[x2,x1]−f[x1,x0] x2 − x0
b0
f (x0)
32
i xi 0 x0 1 x1
2 x2
f (xi) b0 f (x0)
f(x1) f (x2)
f (x0)
f(x1)
b0 =f(x0) f(x1)
b2 =f[x2,x1,x0]= f[x2,x1]−f[x1,x0] x2 − x0
b1 = f[x1,x0] =
f(x1) − f(x0) x1 − x0
b1
f [x1, x0]
33
i xi f(xi) b0 b1
b2
f [x2, x1, x0]
f [x1, x0]
f [x2, x1]
0 x0 1 x1 2 x2
f (x0) f(x1) f (x2)
f (x0)
f(x1)
f (x2)
b0 = f(x0)
f(x1) f (x2)
b1 = f[x1,x0] =
f(x1) − f(x0) x1 − x0
b2 =f[x2,x1,x0]= f[x2,x1]−f[x1,x0] x2 − x0
f [x2, x1] =
f(x2) − f(x1) x2 − x1
34
Newton Interpolation – Higher-order
fn(x) = b0 + b1(x − x0) + b2(x − x0)(x − x1) + ⋯+ +bn(x − x0)(x − x1)⋯(x − xn−1)
where all the b’s are defined as
b0 = f(x0)
b1 = f [x1, x0]
b2 = f [x2, x1, x0] ⋮⋮⋮
bn = f [xn, xn−1, ⋯, x2, x1, x0] 35
Newton Interpolation – Higher-order
f(xi) − f(xj) xi − xj
is called the first divided difference,
where
f [xi, xj] =
f[xi,xj,xk] =
is called the second divided difference
f[xi,xj]−f[xj,xk] xi − xk
f [xi, xj, xk, xl] =
is called the third divided difference and
f[xi,xj,xk]−f[xj,xk,xl] xi − xl
f[xn,…,x0]= f[xn,xn−1,…,x1]−f[xn−1,xn−2,…,x0]
is called the n’th divided difference. xn − x0 36
Example L09.2: Write a MATLAB program that fits the Newton Interpolating polynomial through the data points given in the table below.
x
y
0
0
2
5
4
8
7
10
9
2
10
4
37
38
Lecture09M02.m
xpoints=[0 2 4 7 9 10] ypoints=[0 5 8 10 2 4]
b=NewtonIntCoeff(xpoints,ypoints,n);
yint=NewtonIntEval(b,xpoints,n,xint);
hold off plot(xpoints,ypoints,’ko’,’MarkerSize’,20,’MarkerFaceColor’,’r’) hold on
plot(xint,yint,’b-‘,’Linewidth’,4)
xlabel(‘x’)
ylabel(‘y’)
function b=NewtonIntCoeff(x,y,n) fd=zeros(n+1,n+1);
for i=1:n+1
fd(i,1)=y(i);
end
for j=2:n+1
for i=1:n-j+2
fd(i,j)=(fd(i+1,j-1)-fd(i,j-1))/(x(i+j-1)-x(i));
end end
b=fd(1,:);
end
b0 = f(x0)
b1 = f [x1, x0]
b2 = f [x2, x1, x0]
⋮⋮⋮
bn = f [xn, xn−1, ⋯, x2, x1, x0]
function yint=NewtonIntEval(b,xpoints,n,xint) yint=b(1)*ones(1,length(xint)); xterm=ones(1,length(xint));
for i=2:n+1
xterm=xterm.*(xint-xpoints(i-1));
yint=yint+b(i)*xterm;
end end
fn(x) = b0 + b1(x − x0) + b2(x − x0)(x − x1) + ⋯+ +bn(x − x0)(x − x1)⋯(x − xn−1)
clear all
n=length(xpoints)-1; %order of polynomial xint=0:0.1:10;
End of Example L09.2
Example L09.3: Use quadratic interpolation to estimate the value of the function
f(x) = 1 − e−x
Exercise 2
at x = 1.0. Use the intervals
a) x0 = 0,×1 = 2.0,×2 = 6.0. b) x0 = 0,×1 = 2.0,×2 = 4.0 c) x0=0,×1=2.0, x2=3.0 d) x0=0,×1=0.5×2 =2.0.
Illustrate on a graph how you are approaching the exact value of f(1) = 0.6321.
40
Use
f2(x) = b0 + b1(x − x0) + b2(x − x0)(x − x1) b0 =f(x0 =0)=0
b1 = f(x1)−f(x0) = f(x1)−b0
x1 − x0 x1 − x0 f(x2) − f(x1) − f(x1) − f(x0)
x2 − x0
41
x1 − x0
b2 = b2 =
x2 − x1 f(x2)−f(x1) −b1
x2 − x0 x2 − x1
Exact value of f(x = 1)
42
Exercise – Quadratic Interpolation
Exact value of f(x = 1)
43
Exercise – Quadratic Interpolation
Exact value of f(x = 1)
44
Exercise – Quadratic Interpolation
Exact value of f(x = 1)
45
Exercise – Quadratic Interpolation
Exact value of f(x = 1)
46
End of Example L09.3
L9.4:
Lagrange Interpolating Polynomial
48
“Book” (Chap. 5, pg. 79)
Lagrange Interpolating Polynomials
Suppose we want to interpolate between two data points, (x0, f(x0)), (x1, f(x1)) shown below
f(x1)
f (x0)
x0
x1
x
49
Lagrange Interpolating Polynomials
Suppose we want to interpolate between two data points, (x0, f(x0)), (x1, f(x1)) shown below
f(x1)
1
f (x0)
f (x0)L0(x) x
Assume that we have two functions, L0(x) and L1(x). They are defined such that
L0(x)={1 ifx=x0 0 ifx=x1
L1(x)={0 ifx=x0 1 ifx=x1
L0(x)= (x−x1), (x0 − x1)
L(x)= (x−x0) 1 (x1 − x0)
L1(x) L0(x)
x0
x1
50
Lagrange Interpolating Polynomials
Suppose we want to interpolate between two data points, (x0, f(x0)), (x1, f(x1)) shown below
f(x1) 1
f (x0)
f (x0)L0(x)
f (x1)L1(x)
Assume that we have two functions, L0(x) and L1(x). They are defined such that
L0(x)={1 ifx=x0 0 ifx=x1
L1(x)={0 ifx=x0 1 ifx=x1
L0(x)= (x−x1), (x0 − x1)
L(x)= (x−x0) 1 (x1 − x0)
L1(x)
f (x0)L0(x)
x0
x1
x
51
Lagrange Interpolating Polynomials
Suppose we want to interpolate between two data points, (x0, f(x0)), (x1, f(x1)) shown below
Assume that we have two functions, L0(x) and L1(x). They are defined such that
f(x1) 1
f (x0)
f (x1)L1(x) f1(x) = f (x0)L0(x) + f (x1)L1(x)
L0(x)={1 ifx=x0 0 ifx=x1
L1(x)={0 ifx=x0 1 ifx=x1
f (x1)L1(x)
f (x0)L0(x)
52
L0(x)= (x−x1), (x0 − x1)
f (x0)L0(x)
L(x)= (x−x0) 1 (x1 − x0)
x0
x1
x
Lagrange Interpolating Polynomials
Suppose we want to interpolate between two data points, (x0, f(x0)), (x1, f(x1)) shown below
Assume that we have two functions, L0(x) and L1(x). They are defined such that
L0(x)={1 ifx=x0 0 ifx=x1
L1(x)={0 ifx=x0 1 ifx=x1
f(x1) 1
f (x0)
f (x1)L1(x) f1(x) = f (x0)L0(x) + f (x1)L1(x)
f (x1)L1(x)
f (x0)L0(x)
53
L0(x)= (x−x1), (x0 − x1)
f (x0)L0(x)
L(x)= (x−x0) 1 (x1 − x0)
x0
x1
x
Lagrange Interpolating Polynomials
Suppose we want to interpolate between two data points, (x0, f(x0)), (x1, f(x1)) shown below
Assume that we have two functions, L0(x) and L1(x). They are defined such that
L0(x)={1 ifx=x0 0 ifx=x1
L1(x)={0 ifx=x0 1 ifx=x1
f(x1) 1
f (x0)
f (x1)L1(x) f1(x) = f (x0)L0(x) + f (x1)L1(x)
f (x1)L1(x)
f (x0)L0(x)
54
L0(x)= (x−x1), (x0 − x1)
f (x0)L0(x)
L(x)= (x−x0) 1 (x1 − x0)
x0
x1
x
Lagrange Interpolating Polynomials
Assume that we have two functions, L0(x) and L1(x). They are defined such that
{1 ifx=x0 0 ifx=x1
{0 ifx=x0 1 ifx=x1
L0(x) = L1(x) =
L(x)= (x−x1), 0 (x0 −x1)
L(x)= (x−x0) 1 (x1 −x0)
55
Lagrange Interpolating Polynomials
L(x)= (x−x1),
L(x)= (x−x0)
0
(x0 −x1)
1
(x1 −x0) L1(x)
1 L0(x)
x0
x1
Figure 8: Illustrative sketch of L0(x) and L1(x). 56
Lagrange Interpolating Polynomials
The first order Lagrange interpolating polynomial is obtained by a linear combination of L0(x) and L1(x).
f1(x) = f(x0)L0(x) + f(x1)L1(x) f1(x)=f(x0)L0(x)+f(x1)L1(x)
(9.11)
f(x1) f(x0)L0(x)
f(x0)
f(x1)L1(x)
x0
\
x1
57
Lagrange Interpolating Polynomials
Suppose we want to interpolate between three data points, (x0, f(x0)), (x1, f(x1)) and (x2, f(x2)) shown below
f(x1) f (x2)
f (x0)
x0
x1 x2 58
x
Lagrange Interpolating Polynomials
Suppose we want to interpolate between three data points, (x0, f(x0)), (x1, f(x1)) and (x2, f(x2)) shown below
Assume that we have three functions, L0(x), L1(x) and L2(x). They are defined such that
f(x1) 1
f (x2) f (x0)
x0
L1(x)
1 ifx=x0 L0(x)= 0 ifx=x1 0 ifx=x2
0 ifx=x0 L1(x)= 1 ifx=x1 0 ifx=x2
0 ifx=x0 L2(x)= 0 ifx=x1 1 ifx=x2
L0(x) = (x − x1)(x − x2) (x0 − x1)(x0 − x2)
L1(x)= (x−x2)(x−x0) (x1 − x2)(x1 − x0)
L2(x)
x1
L0(x) x2 59
f (x0)L0(x) x
L2(x) = (x − x1)(x − x0) (x2 − x1)(x2 − x0)
Lagrange Interpolating Polynomials
Suppose we want to interpolate between three data points, (x0, f(x0)), (x1, f(x1)) and (x2, f(x2)) shown below
f(x1) 1
f (x2) f (x0)
x0
L1(x)
1 ifx=x0 L0(x)= 0 ifx=x1 0 ifx=x2
0 ifx=x0 L1(x)= 1 ifx=x1 0 ifx=x2
0 ifx=x0 L2(x)= 0 ifx=x1 1 ifx=x2
Assume that we have three functions, L0(x), L1(x) and L2(x). They are defined such that
L0(x) = (x − x1)(x − x2) (x0 − x1)(x0 − x2)
L1(x)= (x−x2)(x−x0) (x1 − x2)(x1 − x0)
f (x0)L0(x)
f (x1)L1(x)
L2(x)
x1
f (x0)L0(x) x2 60
x
L2(x) = (x − x1)(x − x0) (x2 − x1)(x2 − x0)
Lagrange Interpolating Polynomials
Suppose we want to interpolate between three data points, (x0, f(x0)), (x1, f(x1)) and (x2, f(x2)) shown below
f(x1) 1
f (x2) f (x0)
x0
f (x1)L1(x)
1 ifx=x0 L0(x)= 0 ifx=x1 0 ifx=x2
0 ifx=x0 L1(x)= 1 ifx=x1 0 ifx=x2
0 ifx=x0 L2(x)= 0 ifx=x1 1 ifx=x2
f (x2)L2(x)
Assume that we have three functions, L0(x), L1(x) and L2(x). They are defined such that
L0(x) = (x − x1)(x − x2) (x0 − x1)(x0 − x2)
L1(x)= (x−x2)(x−x0) (x1 − x2)(x1 − x0)
f (x0)L0(x)
f (x1)L1(x)
L2(x)
x1 f (x0)L0(x) x2 61
x
L2(x) = (x − x1)(x − x0) (x2 − x1)(x2 − x0)
f(x1) 1
f (x2) f (x0)
f (x1)L1(x)
1 ifx=x0 L0(x)= 0 ifx=x1 0 ifx=x2
0 ifx=x0 L1(x)= 1 ifx=x1 0 ifx=x2
0 ifx=x0 L2(x)= 0 ifx=x1 1 ifx=x2
f (x2)L2(x)
Lagrange Interpolating Polynomials
Suppose we want to interpolate between three data points, (x0, f(x0)), (x1, f(x1)) and (x2, f(x2)) shown below
Assume that we have three functions, L0(x), L1(x) and L2(x). They are defined such that
xf(x )L (x) 1
0 2 2 f(x0)L0(x)
2
62
L0(x) = (x − x1)(x − x2) (x0 − x1)(x0 − x2)
f (x0)L0(x)
f (x1)L1(x)
L1(x)= (x−x2)(x−x0) (x1 − x2)(x1 − x0)
xxx
L2(x) = (x − x1)(x − x0) (x2 − x1)(x2 − x0)
Lagrange Interpolating Polynomials
Suppose we want to interpolate between three data points, (x0, f(x0)), (x1, f(x1)) and (x2, f(x2)) shown below
Assume that we have three functions, L0(x), L1(x) and L2(x). They are defined such that
f(x1) 1
f (x2) f (x0)
f (x1)L1(x)
1 ifx=x0 L0(x)= 0 ifx=x1 0 ifx=x2
0 ifx=x0 L1(x)= 1 ifx=x1 0 ifx=x2
0 ifx=x0 L2(x)= 0 ifx=x1 1 ifx=x2
L0(x) = (x − x1)(x − x2) (x0 − x1)(x0 − x2)
f (x1)L1(x)
f2(x) = f(x0)L0(x) + f(x1)L1(x) + f(x2)L2(x)
f (x0)L0(x)
f (x2)L2(x)
xxx
xf(x )L (x) 1
0 2 2 f(x0)L0(x)
2
63
L1(x)= (x−x2)(x−x0) (x1 − x2)(x1 − x0)
L2(x) = (x − x1)(x − x0) (x2 − x1)(x2 − x0)
Lagrange Interpolating Polynomials
64
Lagrange Interpolating Polynomials
Suppose we have three data points, (x0, f(x0)), (x1, f(x1)), (x2, f(x2)) and we want to fit a polynomial through it (see previous). Assume that we have three functions, L0(x), L1(x) and L2(x). They are defined such that
1 ifx=x0 L0(x)= 0 ifx=x1 0 ifx=x2
0 ifx=x0 L1(x)= 1 ifx=x1 0 ifx=x2
0 ifx=x0
L2(x)= 0 ifx=x1
1 ifx=x2 65
(9.12)
(9.13)
(9.14)
Lagrange Interpolating Polynomials
It should be easy to convince yourself that the following expressions for L0(x), L1(x) and L2(x) satisfy the conditions listed in Eqs. (9.12) – (9.14).
L0(x) =
(x−x1)(x−x2) (x0 − x1)(x0 − x2)
(x−x2)(x−x0) (x1 − x2)(x1 − x0)
(x−x1)(x−x0) (x2 − x1)(x2 − x0)
(9.15) (9.16) (9.17)
L1(x) =
L2(x) =
For illustrative purposes, Eqs. (9.15) – (9.17) are shown in the next
slide
66
Lagrange Interpolating Polynomials
1.5
1
0.5
-0.5
0
012345678
Graphical illustration of Eqs. (9.15) – (9.15) 67
Lagrange Interpolating Polynomials
The second order Lagrange interpolating polynomial is obtained by a linear combination of L0(x), L1(x) and L2(x).
f2(x) = f(x0)L0(x) + f(x1)L1(x) + f(x2)L2(x)
In general, the nth order Lagrange polynomial (i.e. the Lagrange polynomial that can be fit through n + 1 data points) can be represented concisely as
where
fn(x) = ∑n Li(x)f(xi) i=0
(9.19)
(9.18)
68
Lagrange Interpolating Polynomials
Li(x)= ∏n x−xj (9.20) j=0,j≠i xi − xj
Note that:
• The Lagrange interpolating polynomials are just a different form of the Newton interpolating polynomials.
• The main advantage is that they are slightly easier to program.
• They are slightly slower to compute than the Newton Interpolating polynomials.
69
Example L09.4: Write a MATLAB program that fits the Lagrange Interpolating polynomial through the data points given in the table below.
x
y
0
0
2
5
4
8
7
10
9
2
10
4
70
Lecture09M04.m
71
xpoints=[0 2 4 7 9 10] ypoints=[0 5 8 10 2 4]
yint=LagrangePolynomial(xpoints,ypoints,n,xint);
hold off plot(xpoints,ypoints,’ko’,’MarkerSize’,20,’MarkerFaceColor’,’r’) hold on
plot(xint,yint,’b-‘,’Linewidth’,4)
xlabel(‘x’)
ylabel(‘y’)
function yint=LagrangePolynomial(x,y,n,xint) yint=zeros(size(xint));
for i=1:n+1
Lix=1.0; for j=1:n+1
if j ~= i Lix=Lix.*(xint-x(j))/(x(i)-x(j)); end
end
yint=yint+y(i).*Lix;
end end
Li(x)= ∏n x−xj j=0,j≠i xi − xj
fn(x) = ∑n Li(x)f(xi) i=0
clear all
n=length(xpoints)-1; %order of polynomial xint=0:0.1:10;
End of Example L09.4
Example L09.5: Consider the function, f(x) = 1 − e−(x/σ)2 in the domain 0 ≤ x ≤ 5 with σ = 1. Sample this function at points x = 0.0, 0.1, 0.3, 0.5, 0.8, 1.0, 1.1, 2, 3, 5. Use the data to fit the polynomial through all the data points.
a)Does your function provide a good fit of the actual function? b)How do you think you can get a better fit to the actual function? c)What happens when you change the value of the σ to σ = 0.1?
73
Lecture09M05.m
clear all close all
hold on
sigma=1.0;
% Sample the function at the points below xpoints=[0 0.1 0.3 0.5 0.8 1.0 1.1 2 3 5] ypoints=1-exp(-(xpoints/sigma).^2)
n=length(xpoints)-1; %order of polynomial b=NewtonIntCoeff(xpoints,ypoints,n);
xint=0:0.05:5; yint=NewtonIntEval(b,xpoints,n,xint);
hold off plot(xpoints,ypoints,’ko’,’MarkerSize’,20,’MarkerFaceColor’,’r’) hold on
plot(xint,yint,’b-‘,’Linewidth’,4)
xlabel(‘x’)
ylabel(‘y’)
% Plot the actual function 0