Description
1,the question you need to do is Lab-7, the detail is on the pdf.2,please do it on your own, the topic_3_slides I provide to you is the lecture, and problem 10 is similar to the task you need to do.3,finish task that he asked for, don’t need to do the bonus.4, after you finish the code, please follow the check list to check if the code is correct.5,you must code for the adaptive integration yourself rather than relying on built-in Matlab commands that calculate integrals.
Unformatted Attachment Preview
CHEE 3602 – Topic 3:
Interpolating polynomials
Stanislav Sokolenko
Fall 2023
Motivation
Interpolating polynomials
Motivation
Why interpolate?
Many important mathematical operations are only defined for functions (equations)
e.g. the concept of derivative/integral only makes sense for functions — what is “the rate of change” of a set of data points?
Collected empirical data must be converted into functional form so
that it can be processed/analyzed
e.g. calculating the rate of reaction given a set of concentrations
requires fitting a function to the concentration data
3/118
Interpolating polynomials
Motivation
Numerical methods
Interpolation is the process of fitting individual data points to
a function — enabling analysis that would not be possible using discrete points.
Many common numerical methods are derived using interpolation, even if there is no apparent interpolation taking place.
4/118
Interpolating polynomials
Motivation
Numerical methods
This topic is divided into two specific tasks:
Building interpolating polynomials
Applying interpolating polynomials to develop methods for differentiation/integration
We will start by going through a practical example of interpolation and
justifying the use of polynomials for interpolation.
5/118
Interpolating polynomials
Motivation
6/118
Defining interpolation
Interpolation refers to the approximation of a function
using a series of tabulated values.
( )
Interpolating polynomials
Motivation
Reading tables
In effect, interpolation is used to estimate values between table rows.
T (°C)
P
*
(Hg)
90
525.76
92
566.99
94
610.91
96
657.62
98
707.27
100
760.00
Given the table above, what is the vapour pressure of water at 96.5 °C?
7/118
Interpolating polynomials
Motivation
8/118
Reading tables
Given that there is no entry for 96.5 °C, there are a couple of options
T (°C)
P
*
(Hg)
90
525.76
92
566.99
94
610.91
96
657.62
98
707.27
100
760.00
The simplest is to assume that
96.5 ≈ 96
Therefore,
P
(96.5) ≈ 657.62
*
…
Interpolating polynomials
Motivation
Reading tables
This is a very rough approximation. How can it be improved?
T (°C)
P
*
(Hg)
90
525.76
92
566.99
94
610.91
96
657.62
98
707.27
100
760.00
96.5 is between 96 and 98
(96.5 − 96)/(98 − 96) = 0.25
So the pressure should be higher
P
(96.5) ≈ 657.62 + (707.27 − 657.62)(0.25)
*
= 670.03
9/118
Interpolating polynomials
Motivation
Mathematically
Both approximations can be expressed as interpolation:
1.
The 657.62 estimate used a 0 order polynomial
2.
The 670.03 estimate used a 1st order polynomial
The 1st order polynomial captures more information around
the surrounding table entries than the 0 order.
the only option?
But is this is
10/118
Interpolating polynomials
Motivation
11/118
Interpolating functions
The goal of interpolation is to define a function that can fill in the
gaps between data table entries (or data points)
If the function that generated the original data is unknown, it makes
sense to choose something convenient
A good interpolating function should be easy to
generate (formulate)
evaluate
differentiate
integrate
Interpolating polynomials
Motivation
Polynomials
Polynomials satisfy every single one of the requirements!
12/118
Interpolating polynomials
Motivation
Polynomials
An nth-order polynomial is defined as
( ) = 0 + 1 + 2 2 + … +
An nth-order polynomial
requires
( ) has + 1 coefficients and therefore
+ 1 points to estimate.
13/118
Interpolating polynomials
Motivation
Back to the table
Consider estimating vapour pressure at 96.5 one more time,
T (°C)
P
*
(Hg)
90
525.76
92
566.99
94
610.91
96
657.62
98
707.27
100
760.00
Three values can be used to fit a quadratic.
14/118
Exumple
Tefx
)
x *> ( x X 3 )
L
R 凶)
—
(x *) ( x ×7) fr
–
–
* *^) <
L
-
x
-
,
⽕器
*
-
f
—
× )
3
-
t
,
还
wn,
+
xx
0
0 )
)xc . y ( Lx
t ⼀
-
"
.
3
)1
-
c
)
9 ((1 0)
t
-
JM L JC . }
)
-
132 01 399 68
^+
284 ,
:
-
.
=
13 66 x
.
^
-
.
+
44 18x + 110 62
.
.
-
c
世≈
qi
0
57 91 399 .68
.
+
t
)
ω
L
) (
0 .
0
.
39 )
391 . 96 ) ×+ 110 . 62
-
Interpolating polynomials
Motivation
Formal justification
A nice feature of using polynomials is that they can be used to
approximate a subset of any continuous function.
More formally, the Weierstrass approximation theorem states
( ) is a continuous function in the closed interval
≤ ≤ , then for every > 0, there exists a polynomial
( ), where the value of depends on the value of such that
for all x in the closed interval ≤ ≤ , | ( ) − ( )| < .”
that: “If
15/118
Interpolating polynomials
Motivation
Polynomial uniqueness
It is only possible to define one polynomial of order
through
fined.
that passes
+ 1 points, regardless of how the polynomial is de-
This means that while some methods for polynomial
construction may be more convenient than others, the final
output is often identical.
16/118
Interpolating polynomials
Motivation
Chemical engineering example
Temperature
Recall the T-xy diagram:
Vapour fraction
Liquid fraction
Fraction benzene
Although there is an algorithm for getting
straightforward way of getting
= ( , )
, = ( ), there is no
17/118
Interpolating polynomials
Motivation
Interpolation
One practical option is to generate a set of
, points using
, and then interpolate to find the reverse
relation: = ( , ).
different values of
18/118
Interpolating polynomials
Motivation
Interpolation
Temperature
Linear interpolation can get good results with a large number of points:
Fraction benzene
19/118
Interpolating polynomials
Motivation
Interpolation
Temperature
But increasing interpolation order can yield dramatic improvements:
Fraction benzene
20/118
Interpolating polynomials
Motivation
Nomenclature
These slides reserve the term interpolation for fitting methods where the line of fit must pass through every single point.
In contrast to regression, where the line of fit does not have to
pass through every single data point.
21/118
Interpolating polynomials
Motivation
22/118
Noise
...
Note, passing through every single point is not always appropriate
Good interpolation
Bad interpolation
Never interpolate noisy data!
Good regression
Interpolating polynomials
Motivation
Topic outline
1.
Interpolating polynomials
2.
Differentiation/integration
23/118
Interpolating polynomials
Motivation
24/118
Learning outcomes
By the end of this topic, you should be able to:
1.
Apply Lagrange, divided difference, and Newton polynomial methods to generate interpolating functions
2.
Estimate interpolation error
3.
Understand the derivation of spline interpolation
4.
Derive and apply finite difference and Newton-Cotes methods to
differentiate or integrate data
5.
Understand and apply adaptive integration methods
Interpolating polynomials
Interpolating polynomials
Interpolating polynomials
26/118
Lagrange
Lagrange polynomial
The Lagrange interpolating polynomial is the most intuitive of all the
interpolating polynomials.
Given three points
2 ( ) =
( 1 , 1 ), ( 2 , 2 ), ( 3 , 3 ):
( − 2 )( − 3 )
( − 1 )( − 3 )
( − 1 )( − 2 )
1 +
2 +
( 1 − 2 )( 1 − 3 )
( 2 − 1 )( 2 − 3 )
( 3 − 1 )( 3 − 2 ) 3
...
It looks complicated, but this equation is straightforward to derive
Interpolating polynomials
Interpolating polynomials
27/118
Lagrange
The derivation
First,
2 ( ) must pass through all of the values, so it makes sense
that they would be in the final equation:
2 ( ) =
1 +
So what can be multiplied by
when
= 1 ?
2 +
3
2 to make sure that the 2 term disappears
Interpolating polynomials
Interpolating polynomials
28/118
Lagrange
The derivation
At
= 1 , ( − 1 ) = 0, so the 2 and 3 terms disappear:
2 ( ) =
But what about the
1 +
( − 1 )
1 and 3 terms for 2 ?
2 +
( − 1 )
3
Interpolating polynomials
Interpolating polynomials
29/118
Lagrange
The derivation
Continuing:
2 ( ) =
( − 2 )
1 +
( − 1 )
2 +
( − 1 )( − 2 )
3
Interpolating polynomials
Interpolating polynomials
30/118
Lagrange
The derivation
And the numerators are done:
2 ( ) =
Plug in
( − 2 )( − 3 )
1 +
( − 1 )( − 3 )
2 +
( − 1 )( − 2 )
= 1 , what should the denominator be to get 1 ?
3
Interpolating polynomials
Interpolating polynomials
Lagrange
The derivation
Divide by
( 1 − 2 )( 1 − 3 ) to make sure 2 ( 1 ) = 1 :
2 ( ) =
( − 2 )( − 3 )
( − 1 )( − 3 )
( − 1 )( − 2 )
1 +
2 +
3
( 1 − 2 )( 1 − 3 )
And follow the same approach for the other terms
...
31/118
Interpolating polynomials
Interpolating polynomials
Lagrange
The derivation
Overall result is therefore:
2 ( ) =
( − 2 )( − 3 )
( − 1 )( − 3 )
( − 1 )( − 2 )
1 +
2 +
( 1 − 2 )( 1 − 3 )
( 2 − 1 )( 2 − 3 )
( 3 − 1 )( 3 − 2 ) 3
As illustrated before
...
32/118
Interpolating polynomials
Interpolating polynomials
Lagrange
General form
The overall equation can be concisely expressed as:
− ⎞
⎛
⎟
( ) = ∑ ⎜∏
−
=1 ⎝ ≠
⎠
+1
33/118
Interpolating polynomials
Interpolating polynomials
34/118
Lagrange
Polynomial evaluation
Once a polynomial is constructed using a set of points, the denominator
and the
values do not change:
2 ( ) = ( − 2 )( − 3 ) 1 + ( − 1 )( − 3 ) 2 + ( − 1 )( − 2 ) 3
So it is more efficient to calculate the constant values of
for a set of points and then store them for later use.
...
But adding an extra point requires a lot of extra math
1 , 2 , 3 once
Interpolating polynomials
Interpolating polynomials
Lagrange
Example
Problem 1
Interpolate the following T-xy temperature data as a function
of fraction benzene using a Lagrange polynomial:
i
Temperature (°C)
Fraction benzene
1
80.10
1.00
2
95.36
0.39
3
110.62
0.00
35/118
Exumple
Tefx
)
x *> ( x X 3 )
L
R 凶)
—
(x *) ( x ×7) fr
–
–
* *^) <
L
-
x
-
,
⽕器
*
-
f
—
× )
3
-
t
,
还
wn,
+
xx
0
0 )
)xc . y ( Lx
t ⼀
-
"
.
3
)1
-
c
)
9 ((1 0)
t
-
JM L JC . }
)
-
132 01 399 68
^+
284 ,
:
-
.
=
13 66 x
.
^
-
.
+
44 18x + 110 62
.
.
-
c
世≈
qi
0
57 91 399 .68
.
+
t
)
ω
L
) (
0 .
0
.
39 )
391 . 96 ) ×+ 110 . 62
-
Interpolating polynomials
Interpolating polynomials
Divided difference
Divided difference polynomial
The ideal method for polynomial construction should enable
flexible calculation of different order polynomials using the
same set of points. One way to do this is with divided difference polynomials.
So, what is this divided difference?
36/118
Interpolating polynomials
Interpolating polynomials
Divided difference
Divided difference
A divided difference of order 1,
the two points
[ 1 , 2 ], is effectively the slope between
( 1 , 1 ), ( 2 , 2 ):
[ 1 , 2 ] =
And a divided difference of order 2,
two slopes between three points:
[ 1 , 2 , 3 ] =
2 − 1
2 − 1
[ 1 , 2 , 3 ], is like a “slope” of the
[ 2 , 3 ] − [ 1 , 2 ]
=
3 − 1
3 − 2
2 − 1
−
3 − 2
2 − 1
3 − 1
37/118
Interpolating polynomials
Interpolating polynomials
38/118
Divided difference
Divided difference polynomial
t ] 上
fi
,
:
a*
F,
涎
tniIr
A polynomial of order
can then be built using:
鸒
!
( ) = [ ] + ( − )[ , +1 ] + ( − )( − +1 )[ , +1 , +2 ] + ...
Given three points
would be:
( 1 , 1 ), ( 2 , 2 ), ( 3 , 3 ), a second order polynomial
2 ( ) = [ 1 ] + ( − 1 )[ 1 , 2 ] + ( − 1 )( − 2 )[ 1 , 2 , 3 ]
Interpolating polynomials
Interpolating polynomials
Divided difference
Divided difference polynomial
2 ( ) = [ 1 ] + ( − 1 )[ 1 , 2 ] + ( − 1 )( − 2 )[ 1 , 2 , 3 ]
This may not look very convenient, but recall that:
[ 1 , 2 , 3 ] =
[ 2 , 3 ] − [ 1 , 2 ]
3 − 1
So polynomial order can be increased with one new term.
39/118
Interpolating polynomials
Interpolating polynomials
Divided difference
Table of differences
The divided difference polynomial can be built up using a table
of pre-computed divided differences, with the total number of
terms selected based on the required precision.
This is a major improvement over the Lagrange polynomial,
which must be almost entirely rebuilt if it is necessary to change
the number of points used in the interpolation.
40/118
Interpolating polynomials
Interpolating polynomials
Divided difference
Shorthand notation
Since the square bracket notation
[ 1 , 2 , 3 , ...] can quickly grow very
long, it is common to use a shorthand notation:
[ 1 ] = 1(0) = 1
[ 1 , 2 ] = 1(1) =
2(0) − 1(0)
2 − 1
=
2 − 1
2 − 1
3
2
(1)
(1)
− 2− 1
−
−
2
1
1
[ 1 , 2 , 3 ] = 1(2) = 2
= 3 2
3 − 1
3 − 1
−
−
41/118
Interpolating polynomials
Interpolating polynomials
Divided difference
General form
So the overall equation can be concisely expressed as:
⎜∏( − )⎞
⎟ 1( )
( ) = ∑ ⎛
=0 ⎝ =1
⎠
42/118
Interpolating polynomials
Interpolating polynomials
Divided difference
Verification
Problem 2
Take the definition of a divided difference polynomial:
( ) = [ 1 ] + ( − 1 )[ 1 , 2 ] + ( − 1 )( − 2 )[ 1 , 2 , 3 ] + ...
and show that for
= 2 , ( 2 ) = 2 .
43/118
Interpolating polynomials
Interpolating polynomials
Divided difference
Example
Problem 3
Interpolate the following T-xy temperature data as a function
of fraction benzene using a divided difference polynomial:
i
Temperature (°C)
Fraction benzene
1
80.10
1.00
2
95.36
0.39
3
110.62
0.00
44/118
"
fi extid
Px) :
)
:
t
f,"
)
, )
t
,
8. 1
:
,
( - xp ( xx
by alaulaticndiviliddiffereue
start
f
x
×2
-
95 36
,
:
87 (c
-
.
- 25 . 0 z
x,
0.
39
-
1
ti fi " fie
)
i
or
≈
10. 10
1
0
2
0
}
f
.
14 (
!
1
,
y95 .36 - 34 - 13
…
)
011 .62
t
②]
I
!
.3
-25
"
-
。
f
…
.
…
"
,
⼀
,
×
3
-
×,
t 25
39 13
-
.
:
o
=
if
we
(
-
02
,
1
4 11
,
Ist
wave
P a)
a
2
.
⼀
"
80
,
10 +
order
xL) L
-
ashimtc
,
25 c 2 )
.
udorder
Prx)
:
87 , 0 t
L) (
-
2 i )+ L
)( x- . n)
0
3
al 4 . 1)
l
Ervor
atuate :
)1 x
14 .
)
1
0 (
PRx ⼀⼼
11
)
coupave
Expoud to
appractins
.
4 . llx
e ito 39 .
tLi
8ol
on
'xel
14
0
=
14 11x -44
'
.
Tese of
i 3)
.
.
.
3Y
,
6)x 4 (
10 62
.
RCC 39)
.
:
95 36
.
,
2
Interpolating polynomials
Interpolating polynomials
Newton
Newton polynomial
Recall that one of the trade-offs considered when comparing
numerical methods is robustness/generality vs. speed. A simplifying assumption can often be used to generate a simplified
and potentially better version of an existing algorithm.
One such simplification that is often made with interpolation
is to choose equidistant points, making it possible to get rid of
( +1 − ) terms in the divided difference formulation and
replace them with a constant step size of ℎ.
all
45/118
Interpolating polynomials
Interpolating polynomials
Newton
Finite differences
Since there is no need to keep track of all the
Δ(0) 1 = 1
terms, remove them:
Δ(1) 1 = Δ(0) 2 − Δ(0) 1 = 2 − 1
Δ(2) 1 = Δ(1) 2 − Δ(1) 1 = ( 3 − 2 ) − ( 2 − 1 )
= 3 − 2 2 + 1
46/118
Interpolating polynomials
Interpolating polynomials
47/118
Newton
Newton polynomial
( − ) terms are replaced by the number of “steps” is from
the first point 1 , where each step ℎ = 2 − 1 :
All the
=
− 1
ℎ
Allowing the Newton polynomial to be defined as:
( ) = Δ(0) 1 + Δ(1) 1 +
( − 1) (2)
( − 1)( − 2) (3)
Δ 1 +
Δ 1 + ...
2!
3!
Which is a considerable simplification over the divided difference approach that can be used when the data is on an equally spaced grid.
Interpolating polynomials
Interpolating polynomials
Newton
The kernel of many applications
The Newton polynomial (finite difference) formulation forms
the basis of topic 4.
Start getting used to it now!
48/118
Interpolating polynomials
Interpolating polynomials
Newton
Verification
Problem 4
Substitute
= ( − 1 )/ℎ into the divided difference equation:
2 ( ) = 1(0) + ( − 1 ) 1(1) + ( − 1 )( − 2 ) 1(2)
and show that it is equivalent to the Newton polynomial when
2 − 1 = 3 − 2 = ℎ .
49/118
Interpolating polynomials
Interpolating polynomials
Newton
Example
Problem 5
Using the vapour pressure example data from the beginning
of this topic, generate a 2nd order Newton polynomial from
1 = 94 to calculate ∗ (96.5).
50/118
Interpolating polynomials
Interpolating polynomials
Newton
Different differences
Newton polynomials were introduced with forward differences:
Δ = +1 −
But backward differences are not much different:
∇ = − −1
( ) = ∇(0) + ∇(1) +
=
−
ℎ
( + 1) (2)
( + 1)( + 2) (3)
∇ +
∇ + ...
2!
3!
51/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
Global vs. local fit
points requires a polynomial of order − 1. However, working with high order polynomials ( > 20) can lead
Fitting a
to large round-off errors under some circumstances.
Instead of using a single high order polynomial to perform a
global fit, one solution is to combine many low order polynomial to perform a local fit.
52/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
Basic setup
Consider a small set of points to be fit:
( 2 , 2 )
( 1 , 1 )
( 3 , 3 )
( 4 , 4 )
53/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
1st order
Unique 1st order splines can be generated by forcing each spline to
touch neighbouring points.
( 2 , 2 )
( 1 , 1 )
( 3 , 3 )
( 4 , 4 )
54/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
1st order
points can be fit by − 1 polynomials, so:
Parameters:
2 parameters per
− 1 polynomial = 2( − 1)
Available information:
Each of the
− 1 polynomials touches 2 points
2( − 1) − 2( − 1) = 0
(sufficient to calculate all parameters)
55/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
2nd order
However, these conditions are not sufficient for 2nd order splines.
( 2 , 2 )
( 1 , 1 )
( 3 , 3 )
( 4 , 4 )
Data points alone do not specify a unique set of polynomials.
56/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
2nd order
points can be fit by − 1 polynomials, so:
Parameters:
3 parameters per
− 1 polynomial = 3( − 1)
Available information:
Each of the
− 1 polynomials touches 2 points
3( − 1) − 2( − 1) = − 1
(not enough to calculate parameters)
57/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
2nd order
Intuitively, it should be clear that this is a bad fit:
( 2 , 2 )
( 3 , 3 )
( 1 , 1 )
But how can a good fit be described mathematically?
( 4 , 4 )
58/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
2nd order
In general, a “good” fit is smooth
( 2 , 2 )
( 3 , 3 )
( 1 , 1 )
And smoothness is defined by continuous derivatives
( 4 , 4 )
…
59/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
2nd order
points can be fit by − 1 polynomials, so:
Parameters:
3 parameters per
− 1 polynomial = 3( − 1)
Available information:
Each of the
− 1 polynomials touches 2 points
Neighbouring polynomials have same 1st derivatives
at
− 2 points
3( − 1) − 2( − 1) − ( − 2) = 1
(still not enough to calculate parameters)
60/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
2nd order
points can be fit by − 1 polynomials, so:
Parameters:
3 parameters per
− 1 polynomial = 3( − 1)
Available information:
Each of the
− 1 polynomials touches 2 points
Neighbouring polynomials have same 1st derivatives
at
− 2 points
Force 1st or 2nd derivative to zero at 1 point
3( − 1) − 2( − 1) − ( − 2) − 1 = 0
(sufficient to calculate all parameters)
61/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
Higher orders
Increasing polynomial orders require more conditions
Typically, continuity conditions are extended to all higher orders
− 2 points and have the
same 1st, 2nd, 3rd, etc., derivatives at − 2 points
neighbouring polynomials connect at
Extra conditions are provided by setting the derivatives of edge
polynomials to zero
62/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
In practice
Cubic polynomials are usually smooth enough for most applications.
Spline definition may not be applicable for special cases like
discontinuities. It may be necessary to implement custom spline
equation with special definitions or make use of advanced packages.
63/118
Interpolating polynomials
Interpolating polynomials
Spline interpolation
Some math
Problem 6
Derive a set of equations that can be used to calculate spline
parameters for a quadratic spline across
points.
64/118
Example 6
.
sit
1
1
≈
i
∅
↓
xo
six]
ien
tie
is
tfinfisfi ,
di
:
need
we
Xi+ 1
Con
–
X0
≈
e
fod
eo
‘
bilx xi” t
bi ci
,
a,
( x xu)
C,
–
–
lne
fuall
iegnae ,
li
liunty candition
on
the
left
silxi)
xis
fl aitbi xix tcicxi
a
i
,
=
②
si (
)
fi):
ai
fi)
:
FEce
③
xit
Ist
–
,
=fi)
tbi ( xie
–
fls ebihiecihi
derivaeve
Si ‘(xlt 1
]
=Sit
xi
)
)
xi tCi ( xier
eo
1 ( Xit )
be
–
‘
equal
to
heighbauring
playoamials
,
bf t
2ci
hie
xity
lxour -xo
)
,
t
2 cieitxun –
( bit
靠 Jhi
fiur fitbihi t
=
fien fi
2
:
bo tbie
hi
↑
T
known
bitbit
,
unbow
2
=
)
州
hi
f)
2
bitr
bitlt
:
hitll 了
⼀
1
1
1
co
Δ
(
10
0
…
… …
–
last
our
”
s n-
[
| ]
…
…
…
carditichiwillsetund dorvaeve
uelaie
pilynnut
1 ( xn
)
2
: car
=
0
fuituy tbue hurs tCut
hnl ,
s bas
器
:
t
π
recap
!
ifwe
Cr
have
we
.
n
–
polynennele
l
.
I
l
I
[
?
=
pones
a
[
a =
b
hoave
ai
fiso
=
,
bi
is
fom
salved
asyslem
of
lnen
,
equalin
.
壑
i 鬭
囖
1
1
0
1
0
0
⼊
7
O
G
O
(
0
0
–
!
00
0
…
O
…
…
…
Cr
Eul ia
–
assumed
as
side
A
from biel bofer iilonmz
solue
2s
–
.
do
How
.
,
we
this
me
,
c
Λ
0
⇌
⼀
「
O
Ψ
⼄
f(
n
.
6
) ?
fiud si
xi = U
we
me
8
,
whochpoly namial
V= 2
cican 6
)
a
thi luo
su – ar
6
–
)
t
–
Interpolating polynomials
Interpolating polynomials
Method comparison
Algorithm selection
Algorithm selection depends on a large number of different factors, the
following is just a suggestion:
If you are dealing with more than 20 points: splines
If your data is on an evenly spaced grid: Newton polynomial
Otherwise: divided difference polynomial
The Lagrange interpolating polynomial was introduced because it is
easy to understand.
Its only advantage over the divided difference
method is that it is easier to program.
65/118
Interpolating polynomials
Interpolating polynomials
Method comparison
Caution
All interpolating techniques define a function that passes through
every single observed data point. You should not do this if your
data is noisy!
66/118
Interpolating polynomials
Interpolating polynomials
Method comparison
Further reading
Chapter 4 in the book covers everything in these slides and
more. Sections 4.1-4.2 serve as a good introduction to interpolation, sections 4.4-4.6 cover the three major global interpolation methods, and section 4.9 describes cubic splines.
67/118
Derivatives and integrals
Interpolating polynomials
Derivatives and integrals
Background
Derivatives and integrals
Beyond the direct application of interpolating polynomials to
“read between the table rows”, interpolating polynomials are
also used to develop methods for techniques such as differentiation and integration.
69/118
Interpolating polynomials
Derivatives and integrals
Background
Mathematical interpretation
Derivatives and integrals are often conceptualized geometrically
a derivative is the slope of the tangent line at a given point
an integral is the area under a section of a curve
This conceptualization can be used to determine how to calculate a
derivative or integral
but it does not explain why either is useful
70/118
Interpolating polynomials
Derivatives and integrals
Background
Physical interpretation
A derivative corresponds to a rate of change, while an integral
is an accumulation (typically over space or time).
These values may be useful on their own or as a means of calculating others.
71/118
Interpolating polynomials
Derivatives and integrals
72/118
Background
Rate of change
The flow rate (
) out of the pipe
is directly related to the rate of
change of fluid height in the ves-
H
Q
sel (
):
=
vessel
d
d
Interpolating polynomials
Derivatives and integrals
Background
Rate of change
Note that the above expression is not theoretical (we do not
necessarily know the rate of change in fluid height in advance).
However, fluid height is considerably easier to measure than
flow rate.
73/118
Interpolating polynomials
Derivatives and integrals
74/118
Background
Accumulation
Q
The overall fluid height in the ves-
) is directly related to the
flow rate ( ) out of the pipe over
sel (
time:
H
( ) = ∣ = +
0
1
vessel
∫ ( )dt
0
Interpolating polynomials
Derivatives and integrals
Background
Accumulation
If we know the flow rate of fluid going into the pipe, we can
predict the height of the fluid in the vessel in advance.
75/118
Interpolating polynomials
Derivatives and integrals
Background
Another example
Derivatives and integrals are also used for monitoring reactions
Differentiation to calculate reaction rates from concentration data
=
d
d
Integration to calculate concentration from reaction rate
( ) = 0 + ∫ dt
0
76/118
Interpolating polynomials
Derivatives and integrals
77/118
Background
Numerical vs. analytical
It is possible to solve simple derivatives and integrals analytically
typically using pattern recognition (to identify useful variable
substitutions or techniques like integration by parts)
Numerical methods are often simpler and allow the solution of
problems that cannot be solved analytically
Numerical methods can also be used to work with data (a series of
points) where the true function is unknown
Interpolating polynomials
Derivatives and integrals
Background
Simplifying equations
The general differentiation/integration technique is always the
same — interpolate input data into a function and find the derivative/integral of the function as normal.
However, this process can be derived into a simple algebraic
equation for common problems.
78/118
Interpolating polynomials
Derivatives and integrals
79/118
Differentiating points
Differentiation
If the input data points are evenly spaced, a derivative equation can be
calculated by fitting a Newton polynomial to points around
( , )
( , ).
Interpolating polynomials
Derivatives and integrals
Differentiating points
1st order
Recall the 1st order Newton polynomial:
1 ( ) = + Δ(1)
=
Where
−
ℎ
ℎ is the step size between , +1 .
Calculating
d 1 ( )
requires using the chain rule:
d
d 1 ( ) d 1 ( ) d
=
d
d d
80/118
Interpolating polynomials
Derivatives and integrals
Differentiating points
1st order
The two terms:
d 1 ( )
d
= ( + Δ(1) )
d
d
= Δ(1) = +1 −
d
1
=
d ℎ
Together:
d 1 ( )
+1 −
=
d
ℎ
81/118
Interpolating polynomials
Derivatives and integrals
Differentiating points
Visually
Comparing the estimate and true value:
( , )
The estimate is good if the function is smooth and the step size is small.
82/118
Interpolating polynomials
Derivatives and integrals
Differentiating points
Higher orders
( +1 − )/ℎ is a first-order finite difference. The same process
can be used to define higher order finite difference equations.
83/118
Interpolating polynomials
Derivatives and integrals
Differentiating points
Higher orders
Problem 7
Derive a finite difference equation for the derivative at a point
using a 2nd order Newton Polynomial equation.
84/118
Interpolating polynomials
Derivatives and integrals
85/118
Integrating points
Integration
If the input data points are evenly spaced, an integral equation can be
calculated by fitting a Newton polynomial to points around
( , )
( , ).
Interpolating polynomials
Derivatives and integrals
Integrating points
1st order
Recall the same 1st order Newton polynomial:
1 ( ) = + Δ(1)
=
Where
−
ℎ
ℎ is the step size between , +1 .
Use the chain rule to go from
to :
+1
= ∫ 1 ( )d
86/118
Interpolating polynomials
Derivatives and integrals
Integrating points
1st order
First, convert
to
d
1
=
d ℎ
d = ℎ d
And do not forget about the limits of integration:
1
= ∫ 1 ( )ℎ d
0
With a 1st order estimate, use only two points
, +1 , or = 0, 1.
87/118
Interpolating polynomials
Derivatives and integrals
Integrating points
1st order
1
= ∫ 1 ( )ℎ d
0
1
= ℎ ∫ + Δ(1) d
0
∣
2 (1)
= ℎ ( + Δ ) ∣∣
2
∣
1
= ℎ ( + Δ(1) )
2
= ℎ ( +
=
+1 −
)
2
ℎ( + +1 )
2
1
=0
88/118
Interpolating polynomials
Derivatives and integrals
Integrating points
Visually
Comparing the estimate and true value:
( , )
The estimate is good if the function is smooth and the step size is small.
89/118
Interpolating polynomials
Derivatives and integrals
Integrating points
Global estimate
A single integral is typically calculated over all the points:
90/118
Interpolating polynomials
Derivatives and integrals
Integrating points
Global estimate
To integrate over
points, sum over all − 1 sub-intervals:
−1
= ∑
=1
But the formula allows some simplification:
ℎ( + +1 )
2
=1
−1
=∑
−1
ℎ
= ( 1 + ∑ 2 + )
2
=2
91/118
Interpolating polynomials
Derivatives and integrals
Integrating points
Higher orders
ℎ( +1 + )/2 is a first-order Newton-Cotes equation (other-
wise known as the trapezoid rule). The same process can be
used to define higher order Newton-Cotes equations (such as
the Simpson’s rule or Simpson’s 3/8 rule).
92/118
Interpolating polynomials
Derivatives and integrals
93/118
Integrating points
Higher orders
Problem 8
Derive a Newton-Cotes equation for a global integral over
points using a 2nd order Newton Polynomial equation.
Interpolating polynomials
Derivatives and integrals
Integrating points
Example
Problem 9
Given the following set of data, use a 2nd order Newton polynomial to estimate the derivative at
integral between
= 0, 1
= 0.5 and the global
x
0.00
0.25
0.50
0.75
1.00
y
1.00
1.28
1.65
2.12
2.72
Compare the estimates to the true values given that
= .
94/118
Interpolating polynomials
Derivatives and integrals
95/118
Integrating functions
Integrating functions
When trying to find a derivative or integral from a set of points, the
underlying function is unknown
However, we may also be interested in finding the integral of a
known function
more common for integrals as derivatives are relatively easy to
find analytically
Recall the problem from topic 1 that could not be solved analytically:
∫ − d
2
Interpolating polynomials
Derivatives and integrals
Integrating functions
Integrating functions
Numerically integrating functions is similar to points.
Suggest a method to find the previously mentioned integral:
∫ − d
2
96/118
Interpolating polynomials
Derivatives and integrals
97/118
Integrating functions
Beyond points
If the function is known, it is easy to calculate function values at a
series of points and directly apply the Newton-Cotes equations
step size or order can be varied to estimate accuracy
However, knowing the function enables a better estimate than possible with a fixed set of points
Gauss-Legendre
quadrature
can
be
used
to
optimize
which
points to choose (outside the scope of the course)
Richardson extrapolation can be used to generate a more accurate estimate from two estimates with different step sizes
Interpolating polynomials
Derivatives and integrals
Integrating functions
Beyond points
By leveraging how truncation error works, so-called “adaptive” methods are able to get better estimates with less work.
98/118
Interpolating polynomials
Derivatives and integrals
Integrating functions
Taylor series and truncation
The Taylor series offers a convenient introduction to truncation error.
Recall the Taylor series formulation:
( ) = ( 0 ) + ′ ( 0 )( − 0 ) +
1
″ ( 0 )( − 0 )2 + …
2!
Where the ellipses can be represented by a remainder term:
( ) = ( 0 ) + ′ ( 0 )( − 0 ) +
1
″ ( 0 )( − 0 )2 + 3
2!
99/118
Interpolating polynomials
Derivatives and integrals
100/118
Integrating functions
Taylor series and truncation
It can be shown that the remainder can be defined as:
( ) = ( 0 ) + ′ ( 0 )( − 0 ) +
where
1
1
″ ( 0 )( − 0 )2 +
‴ ( )( − 0 )3
2!
3!
is some val
