第六章 插值 /* Interpolation */
当精确函数 y = f(x) 非常复杂或未知时，在一系列节点 x0 … xn 处测得函数值 y0 = f(x0),…
yn = f(xn)，由此构造一个简单易算的近似函数 g(x)? f(x)，满足条件 g(xi) = f(xi) (i = 0,…
n)。这里的 g(x)称为 f(x) 的 插值函数 。最常用的插值函数是 …?多项式
x0 x1 x2 x3 x4x
g(x)? f(x)
§ 1 拉格朗日多项式 /* Lagrange Polynomial */
niyxP iin,...,0,)( ==
求 n 次多项式 使得 n
nn xaxaaxP=?10)(
条件,无重合节点，即 ji xx?ji?
n = 1 已知 x0,x1 ; y0,y1,求 xaaxP
101 )(?=
使得
111001 )(,)( yxPyxP ==
可见 P1(x) 是过 ( x0,y0 ) 和 ( x1,y1 ) 两点的直线。
)()( 0
01
01
01 xxxx
yyyxP -
-
-?=
10
1
xx
xx
-
-
01
0
xx
xx
-
-= y
0 + y1
l0(x) l1(x)
== 1
0
)(
i ii
yxl
称为 拉氏基函数 /* Lagrange Basis */，
满足条件 li(xj)=?ij /* Kronecker Delta */
The mathematician S,had to move to a new place,
His wife didn't trust him very much,so when they stood
down on the street with all their things,she asked him to
watch their ten trunks,while she got a taxi,Some minutes
later she returned,Said the husband,"I thought you said
there were ten trunks,but I've only counted to nine!"
The wife said,"No,they're TEN!"
"But I have counted them,0,1,2,..."
§ 1 Lagrange Polynomial
n? 1 希望找到 li(x),i = 0,…,n 使得 li(xj)=?ij ；然后令
=
=
n
i
iin yxlxP
0
)()(,则显然有 Pn(xi) = yi 。
li(x) 每个 li 有 n 个根 x0 … xi … xn
=
-=---= n
j
j? i
jiniii xxCxxxxxxCxl
0
0 )())...()...(()(
-== j? i
ji
iii xxCxl )( 11)(
=
-
-= n
j
ij ji
j
i xx
xxxl
0
)(
)()(
=
= n
i
iin yxlxL
0
)()(
Lagrange
Polynomial
与 有关，而与 无关节点 f
§ 1 Lagrange Polynomial
定理 (唯一性 ) 满足 的 n 阶插值多项式是唯一存在的。
niyxP ii,...,0,)( ==
证明,( p.105-106 利用 Vandermonde 行列式 论证 )
反证：若不唯一，则除了 Ln(x) 外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 。
考察 则 Qn 的阶数,)()()( xLxPxQ
nnn -=
n
而 Qn 有 个不同的根n + 1 x0 … xn
注,若不将多项式次数限制为 n,则插值多项式 不唯一 。
例如 也是一个插值多项式，其中 可以是任意多项式。
=
-?= n
i
in xxxpxLxP
0
)()()()(
)(xp
§ 1 Lagrange Polynomial
插值余项 /* Remainder */
设节点
)1(?nf 在 [a,b]内存在,考察截断误差 )()()( xLxfxR
nn -=
],[ baCf n?bxxxa
n10
，且 f 满足条件,
Rolle’s Theorem,若 充分光滑，,则存在 使得 。
)(x? 0)()( 10 == xx
),( 10 xx 0)( =
推广,若 0)()()(
210 === xxx ),(),,( 211100 xxxx
使得 0)()(
10 =?= ),( 10
使得 0)( =
0)()( 0 === nxx
存在 ),( ba 使得 0)()( = n
Rn(x) 至少有 个根n+1?
=
-=
n
i
in xxxKxR
0
)()()(
任意固定 x? xi (i = 0,…,n),考察?
=
--=
n
i
ixtxKtRnt
0
)()()()(?
(x)有 n+2 个不同的根 x0… xn x ),(,0)()1( ba
xxn?=
!)1()()()1(?-? nxKR xnn?
注意这里是对 t 求导
=?-- !)1)(()()( )1()1( nxKLf xnnxn
!)1(
)()( )1(
=
n
fxK xn?
=
-?=
n
i
i
x
n
n xxn
fxR
0
)1(
)(!)1( )()(?
§ 1 Lagrange Polynomial
注,?通常不能确定?x,而是估计,?x?(a,b)
将 作为误差估计上限。
1)1( )( nn Mxf
=
-? n
i
in xxn
M
0
1 ||)!1(
当 f(x) 为任一个次数? n 的 多项式 时，,
可知,即插值多项式对于次数?n 的 多项式是 精确 的。
0)()1( xf n
0)(?xR n
Quiz:给定 xi = i +1,i = 0,1,2,3,4,5,下面哪个是 l2(x)的图像？
y
0
-
-
-1
0.5
-0.5
1 2 3 4 5 6 x
y
0
-
-
-1
0.5
-0.5
1 2 3 4 5 6 x
y
0
-
-
-1
0.5
-0.5
1 2 3 4 5 6 x
A B C
§ 1 Lagrange Polynomial
例,已知
2 33s i n,214s i n,216s i n ===
分别利用 sin x 的 1次,2次 Lagrange 插值计算 sin 50?
并估计误差。
解：
0x 1x 2x
18550 0?=
n = 1 分别利用 x0,x1 以及 x1,x2 计算
4,6 10
== xx?利用
216/4/ 6/214/6/ 4/)(1?----= xxxL
这里 )
3,6(,s i n)(,s i n)( )2(-== xxxfxxf
而
)4)(6(!2 )()(,2 3s i n21 )2(1 --= xxfxR xx
0 0 7 6 2.0)185(0 1 3 1 9.0 1 --?R?sin 50?= 0.7660444…
)185(50sin 10L 0.77614
外推 /* extrapolation */ 的实际误差?-0.01001
3,4 21 == xx
利用 sin 50 0.76008,0 0 6 6 0.0
185~0 0 5 3 8.0 1R
内插 /* interpolation */ 的实际误差?0.00596
内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。
§ 1 Lagrange Polynomial
n = 2
2
3
))((
))((
2
1
))((
))((
21))((
))(()(
4363
46
3464
36
3646
342?-- ---- ---- --=
xxxxxxxL
)185(50sin 20L 0.76543
2 3c o s21;)3)(4)(6(!3
c o s)(
2---
-=
xx xxxxR
00077.018500044.0 2R?sin 50?= 0.7660444…
2次插值的实际误差?0.00061
高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿 ……
HW,p.112-113
#5,#7
§ 1 Lagrange Polynomial
Lab 10,Lagrange Polynomial
Given a set of sample points of a
certain function f,use Lagrange polynomial to approximate function
values at some given points,
Input
There are several sets of inputs,For each set:
The 1st line contains an integer 20? n? 0 which is the degree of
Lagrange polynomial,n = -1 signals the end of file.
The 2nd line contains n+1 distinct real numbers,
The 3rd line contains n+1 real numbers,
The last line of a test case consists of an integer m > 0 and m real
numbers,
The numbers are separated by spaces and new lines.
))(,(.,,,)),(,()),(,( 1100 nn xfxxfxxfx
maa,...,1
nxxx,...,,10
)(,.,,),(),( 10 nxfxfxf
maa,...,1
§ 1 Lagrange Polynomial
Output(? represents a space)
For each ai,you are supposed to print the function value at this point in
the following format:
fprintf(outfile,"f(%6.3f)? =? %12.8e\n",a,f );
The outputs of two test cases must be seperated by a blank line.
Sample Input
7
0.5? 0.7? 0.9? 1.1? 1.3? 1.5? 1.7? 1.9
0.48? 0.64? 0.78? 0.89? 0.96? 1.00? 0.99? 0.95
5? 0.74? 1.6? 0.55? 1.2? 1.85
1
0.0? 1.0
0.0? 1.0
1? 0.5
–1
Sample Output
f(? 0.740)? =? 6.68735821e–001
f(? 1.600)? =? 1.00341309e+000
f(? 0.550)? =? 5.26938820e–001
f(? 1.200)? =? 9.29135742e–001
f(? 1.850)? =? 9.52078056e–001
f(? 0.500)? =? 5.00000000e–001
When you start writing the program,
you will find how easy it is to calculate
the Lagrange polynomial.
Oh yeah? What if I find
the current interpolation
not accurate enough?
Then you might want to take
more interpolating points into account.
Right,T en all
the Lagrange basis,li(x),
will have to be re-calculated.
Excellent point !
We will come to discuss this problem
next time.
当精确函数 y = f(x) 非常复杂或未知时，在一系列节点 x0 … xn 处测得函数值 y0 = f(x0),…
yn = f(xn)，由此构造一个简单易算的近似函数 g(x)? f(x)，满足条件 g(xi) = f(xi) (i = 0,…
n)。这里的 g(x)称为 f(x) 的 插值函数 。最常用的插值函数是 …?多项式
x0 x1 x2 x3 x4x
g(x)? f(x)
§ 1 拉格朗日多项式 /* Lagrange Polynomial */
niyxP iin,...,0,)( ==
求 n 次多项式 使得 n
nn xaxaaxP=?10)(
条件,无重合节点，即 ji xx?ji?
n = 1 已知 x0,x1 ; y0,y1,求 xaaxP
101 )(?=
使得
111001 )(,)( yxPyxP ==
可见 P1(x) 是过 ( x0,y0 ) 和 ( x1,y1 ) 两点的直线。
)()( 0
01
01
01 xxxx
yyyxP -
-
-?=
10
1
xx
xx
-
-
01
0
xx
xx
-
-= y
0 + y1
l0(x) l1(x)
== 1
0
)(
i ii
yxl
称为 拉氏基函数 /* Lagrange Basis */，
满足条件 li(xj)=?ij /* Kronecker Delta */
The mathematician S,had to move to a new place,
His wife didn't trust him very much,so when they stood
down on the street with all their things,she asked him to
watch their ten trunks,while she got a taxi,Some minutes
later she returned,Said the husband,"I thought you said
there were ten trunks,but I've only counted to nine!"
The wife said,"No,they're TEN!"
"But I have counted them,0,1,2,..."
§ 1 Lagrange Polynomial
n? 1 希望找到 li(x),i = 0,…,n 使得 li(xj)=?ij ；然后令
=
=
n
i
iin yxlxP
0
)()(,则显然有 Pn(xi) = yi 。
li(x) 每个 li 有 n 个根 x0 … xi … xn
=
-=---= n
j
j? i
jiniii xxCxxxxxxCxl
0
0 )())...()...(()(
-== j? i
ji
iii xxCxl )( 11)(
=
-
-= n
j
ij ji
j
i xx
xxxl
0
)(
)()(
=
= n
i
iin yxlxL
0
)()(
Lagrange
Polynomial
与 有关，而与 无关节点 f
§ 1 Lagrange Polynomial
定理 (唯一性 ) 满足 的 n 阶插值多项式是唯一存在的。
niyxP ii,...,0,)( ==
证明,( p.105-106 利用 Vandermonde 行列式 论证 )
反证：若不唯一，则除了 Ln(x) 外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 。
考察 则 Qn 的阶数,)()()( xLxPxQ
nnn -=
n
而 Qn 有 个不同的根n + 1 x0 … xn
注,若不将多项式次数限制为 n,则插值多项式 不唯一 。
例如 也是一个插值多项式，其中 可以是任意多项式。
=
-?= n
i
in xxxpxLxP
0
)()()()(
)(xp
§ 1 Lagrange Polynomial
插值余项 /* Remainder */
设节点
)1(?nf 在 [a,b]内存在,考察截断误差 )()()( xLxfxR
nn -=
],[ baCf n?bxxxa
n10
，且 f 满足条件,
Rolle’s Theorem,若 充分光滑，,则存在 使得 。
)(x? 0)()( 10 == xx
),( 10 xx 0)( =
推广,若 0)()()(
210 === xxx ),(),,( 211100 xxxx
使得 0)()(
10 =?= ),( 10
使得 0)( =
0)()( 0 === nxx
存在 ),( ba 使得 0)()( = n
Rn(x) 至少有 个根n+1?
=
-=
n
i
in xxxKxR
0
)()()(
任意固定 x? xi (i = 0,…,n),考察?
=
--=
n
i
ixtxKtRnt
0
)()()()(?
(x)有 n+2 个不同的根 x0… xn x ),(,0)()1( ba
xxn?=
!)1()()()1(?-? nxKR xnn?
注意这里是对 t 求导
=?-- !)1)(()()( )1()1( nxKLf xnnxn
!)1(
)()( )1(
=
n
fxK xn?
=
-?=
n
i
i
x
n
n xxn
fxR
0
)1(
)(!)1( )()(?
§ 1 Lagrange Polynomial
注,?通常不能确定?x,而是估计,?x?(a,b)
将 作为误差估计上限。
1)1( )( nn Mxf
=
-? n
i
in xxn
M
0
1 ||)!1(
当 f(x) 为任一个次数? n 的 多项式 时，,
可知,即插值多项式对于次数?n 的 多项式是 精确 的。
0)()1( xf n
0)(?xR n
Quiz:给定 xi = i +1,i = 0,1,2,3,4,5,下面哪个是 l2(x)的图像？
y
0
-
-
-1
0.5
-0.5
1 2 3 4 5 6 x
y
0
-
-
-1
0.5
-0.5
1 2 3 4 5 6 x
y
0
-
-
-1
0.5
-0.5
1 2 3 4 5 6 x
A B C
§ 1 Lagrange Polynomial
例,已知
2 33s i n,214s i n,216s i n ===
分别利用 sin x 的 1次,2次 Lagrange 插值计算 sin 50?
并估计误差。
解：
0x 1x 2x
18550 0?=
n = 1 分别利用 x0,x1 以及 x1,x2 计算
4,6 10
== xx?利用
216/4/ 6/214/6/ 4/)(1?----= xxxL
这里 )
3,6(,s i n)(,s i n)( )2(-== xxxfxxf
而
)4)(6(!2 )()(,2 3s i n21 )2(1 --= xxfxR xx
0 0 7 6 2.0)185(0 1 3 1 9.0 1 --?R?sin 50?= 0.7660444…
)185(50sin 10L 0.77614
外推 /* extrapolation */ 的实际误差?-0.01001
3,4 21 == xx
利用 sin 50 0.76008,0 0 6 6 0.0
185~0 0 5 3 8.0 1R
内插 /* interpolation */ 的实际误差?0.00596
内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。
§ 1 Lagrange Polynomial
n = 2
2
3
))((
))((
2
1
))((
))((
21))((
))(()(
4363
46
3464
36
3646
342?-- ---- ---- --=
xxxxxxxL
)185(50sin 20L 0.76543
2 3c o s21;)3)(4)(6(!3
c o s)(
2---
-=
xx xxxxR
00077.018500044.0 2R?sin 50?= 0.7660444…
2次插值的实际误差?0.00061
高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿 ……
HW,p.112-113
#5,#7
§ 1 Lagrange Polynomial
Lab 10,Lagrange Polynomial
Given a set of sample points of a
certain function f,use Lagrange polynomial to approximate function
values at some given points,
Input
There are several sets of inputs,For each set:
The 1st line contains an integer 20? n? 0 which is the degree of
Lagrange polynomial,n = -1 signals the end of file.
The 2nd line contains n+1 distinct real numbers,
The 3rd line contains n+1 real numbers,
The last line of a test case consists of an integer m > 0 and m real
numbers,
The numbers are separated by spaces and new lines.
))(,(.,,,)),(,()),(,( 1100 nn xfxxfxxfx
maa,...,1
nxxx,...,,10
)(,.,,),(),( 10 nxfxfxf
maa,...,1
§ 1 Lagrange Polynomial
Output(? represents a space)
For each ai,you are supposed to print the function value at this point in
the following format:
fprintf(outfile,"f(%6.3f)? =? %12.8e\n",a,f );
The outputs of two test cases must be seperated by a blank line.
Sample Input
7
0.5? 0.7? 0.9? 1.1? 1.3? 1.5? 1.7? 1.9
0.48? 0.64? 0.78? 0.89? 0.96? 1.00? 0.99? 0.95
5? 0.74? 1.6? 0.55? 1.2? 1.85
1
0.0? 1.0
0.0? 1.0
1? 0.5
–1
Sample Output
f(? 0.740)? =? 6.68735821e–001
f(? 1.600)? =? 1.00341309e+000
f(? 0.550)? =? 5.26938820e–001
f(? 1.200)? =? 9.29135742e–001
f(? 1.850)? =? 9.52078056e–001
f(? 0.500)? =? 5.00000000e–001
When you start writing the program,
you will find how easy it is to calculate
the Lagrange polynomial.
Oh yeah? What if I find
the current interpolation
not accurate enough?
Then you might want to take
more interpolating points into account.
Right,T en all
the Lagrange basis,li(x),
will have to be re-calculated.
Excellent point !
We will come to discuss this problem
next time.
