数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
第 1章 插 值
实际中,f(x)多样，复杂，通常只能观测到一些离散数据；
或者 f(x)过于复杂而难以运算。这时我们要用近似函数 g(x)来
逼近 f(x)。
自然地，希望 g(x)通过所有的离散点
? 概念
x0 x1 x2 x3 x4x
g(x) ? f(x)
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
定义,为定义在区间 上的函数,为区间上 n+1个互不
相同的点,为给定的某一函数类。求 上的函数 满足
)(xf ? ?ba,? ? 0ni ix ?
? ? )(xg
nixfxg ii,,0,)()( ???
问题
? 是否存在唯一
? 如何构造
? 误差估计
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
? ? ??
????
???
,,
)()()()(
)()()(
0
00
00
n
inniii
nn
aa
xaxaxfxg
xaxaxg
?
?
?
??
??
有解 系数行列式不为 0
设 则
1,与基函数无关
2,与原函数 f(x)无关
3,基函数个数与点个数相同
特点：
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
存在唯一定理
定理 1.1, 为 n＋ 1个节点，
n+1维空间，则插值函数存在唯一，当且仅当
? ? 0ni ix ? },,{ 10 ns p a n ??? ???
0
)()(
)()(
0
000
?
nnn
n
xx
xx
??
??
?
???
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
},,,1{)( 2 nn xxxs p a nx ?????对应于
则
0
1
1
0
0
??? ?
??? nij
ji
n
n
n
xx
x
x
?
???
?
Vandermonde行列式
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
多项式插值的 Lagrange型
?如何找？
在基函数上下功夫，取基函数为 nn
ii xl ??? 0)}({
要求
?
?
?
?
???
ji
jixl
ijji,1
,0)( ? 则
)()()(
0
i
n
i
i xfxlxg ?
?
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?线性插值
01
0
1
10
1
0 )(,)( xx
xxxl
xx
xxxl
?
??
?
??
)()()()()( 11001 xlxfxlxfxL ??
求
nii xl 0)}({ ?
，易知：
)())(()()( 110 niiii xxxxxxxxaxl ????? ?? ??
)())(()(
1
110 niiiiii
i xxxxxxxxa ?????
?? ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?二次插值
))((
))((
)(
))((
))((
)(
))((
))((
)(
1202
10
2
2101
20
1
2010
21
0
xxxx
xxxx
xl
xxxx
xxxx
xl
xxxx
xxxx
xl
??
??
?
??
??
?
??
??
?
2 0 0 1 1 2 2( ) ( ) ( ) ( ) ( ) ( ) ( )L x f x l x f x l x f x l x? ? ?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)3,3(),1,2(),0,0(),2,1( ?
例：
)31)(21)(01(
)3)(2)(0()(
0 ??????
???? xxxxl
)23)(03)(13(
)2)(0)(1()(
3 ???
???? xxxxl
)32)(02)(12(
)3)(0)(1()(
2 ???
???? xxxxl
)30)(20)(10(
)3)(2)(1()(
1 ???
???? xxxxl
)(3)(1)(0)(2)( 3210 xlxlxlxlxg ????
例,已知
2 33s i n,214s i n,216s i n ??? ???
分别利用 sin x 的 1次,2次 Lagrange 插值计算 sin 50?
并估计误差。
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
§ 1 Lagrange Polynomial
解：
0x 1x 2x
185500 ??
n = 1 分别利用 x0,x1 以及 x1,x2 计算
4,6 10
?? ?? xx?利用
216/4/ 6/214/6/ 4/)(1 ???????? ?? ??? ? xxxL
这里 )
3,6(,s in)(,s in)( )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 10 ?? ?L 0.77614
外推 /* extrapolation */ 的实际误差 ??0.01001
3,4 21 ?? ?? xx
?利用 sin 50?? 0.76008,00660.0
185~00538.0 1 ???????? ?R
内插 /* interpolation */ 的实际误差 ?0.00596
内插通常优于外推。选择
要计算的 x 所在的区间的
端点，插值效果较好。
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
n = 2
2
3
))((
))((
2
1
))((
))((
21))((
))(()(
4363
46
3464
36
3646
342 ??? ?????? ?????? ???
????
??
????
??
????
?? xxxxxxxL
)185(50sin 20 ?? ?L 0.76543
2 3c o s21;)3)(4)(6(!3
c o s)(
2 ?????
??
xx xxxxR ????
?
00 0 77.018500 0 44.0 2 ???????? ?R ?sin 50?= 0.7660444…
2次插值的实际误差 ?0.00061
高次插值通常优于
低次插值
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
误差 )()()( xLxfxR
nn ??解：
)())(()(
,0,0)(
,0,)()(
0 nn
in
ini
xxxxxkxR
nixR
nixLxf
????
???
??
?
?
??
求
)( ?xk
0)( a n d,0,0)(
)())(()()()(
)(,
0
???
?????
??
anix
xtxtaktLtft
aka
i
nn
??
?
?
?设
易知
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)(t?? 有 n+2个零点
)!1(
)(
)(
)!1)(()()(
0)(,
)1(
)1()1(
)1(
?
?
???
???
?
??
?
n
f
ak
nakf
n
nn
n
?
???
???
)()(
)!1(
)()(
0
)1(
n
n
n xxxxn
fxR ??
?
??
?
??
由 a的任意性
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
事后误差估计
给定 ? ? 1
0
?
?
n
iix
任取 n+1个构造 )(xL
n
)(
~
1,,1
)(,,0
xLni
xLni
n
n
???
??
?
?
如：
另取
则
)()(
)!1(
)(
)(
~
)(
)()(
)!1(
)(
)()(
11
2
)1(
0
1
)1(
?
?
?
??
?
??
??
?
??
n
n
n
n
n
n
xxxx
n
f
xLxf
xxxx
n
f
xLxf
?
?
?
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
近似
)()( 2)1(1)1( ?? ?? ? nn ff
则
? ?)(
~
)()()(
)(
~
)()(
)(
~
)(
)()(
10
0
01
0
10
1
1
0
xLxL
xx
xx
xLxf
xL
xx
xx
xL
xx
xx
xf
xx
xx
xLxf
xLxf
nn
n
n
n
n
n
n
n
nn
n
?
?
?
???
?
?
?
?
?
??
?
?
?
?
?
?
??
?
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?Lagrange 插值的缺点
无承袭性。增加一个节点，所有的基函数都要重新计算
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
Newton型多项式插值
},,{ 110 ?nxxx ? },,{ 10 nxxx ?
且
nixfxNxN iinin ?,1,)()()( 1 ??? ?
)()()( 011 nnn xxxxaxq ???? ?? ?
同样
)()()( 10 ????? nnn xxxxaxq ?
)()()( 1 xqxNxN nnn ?? ?
承袭性, )()()(
11 xqxNxN nnn ?? ??
1?? nP
为实数
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)()()()( 10010 ????????? nnn xxxxaxxaaxN ??
而且有：
?
?
?
?
?
?
?
????????
???????
????
??
?
)()()()()(
)())(()()(
)()()(
)()(
10010
21202202102
101101
000
nnnnnnnn
n
n
n
xfxxxxaxxaaxN
xfxxxxaxxaaxN
xfxxaaxN
xfaxN
??
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
这样：
)( 00 xfa ?
01
01
1
)()(
xx
xfxfa
?
??
???
?
???
? ?
?
?
?
? 1
02
02
12
2
)()(1 a
xx
xfxf
xx
a
???
?
???
?
?
??
?
?
?
???
? ?
?
?
?
? 2
01
1
03
03
23
3
1)()(1 a
xx
a
xx
xfxf
xx
a
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
0
101
0
01
01
10
],,[],,[
],,[
)()(
],[
xx
xxfxxf
xxf
xx
xfxf
xxf
k
kk
k
?
?
?
?
?
?
?
??
? 称为 k阶差商
称为 1阶差商
定义,差商
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)( 00 xfa ?
],[)()( 10
01
01
1 xxfxx
xfxfa ?
?
??
? ? ],,[],[],[
1
)()(1
0120102
12
1
02
02
12
2
xxxfxxfxxf
xx
a
xx
xfxf
xx
a
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
由归纳：
],,[ 0 nn xxfa ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
此处用到差商的一个性质, （用归纳法易证）
对称性：
],,[],,[ 00 kiik xxfxxf ?? ?
定义关键：找不同的元素相减作分母
的任意排列是 kii k,,0,,0 ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
Newton插值构造
)(,00 xfx
)(,11 xfx
)(,22 xfx
?
)(,nn xfx
],[ 10 xxf
],[ 12 xxf
],[ 1 nn xxf ?
],,[ 012 xxxf
],,[ 21 ?? nnn xxxf
? ?
],,[ 0xxf n ?
1、先构造差商表
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?例子
2点 Newton型插值
)()()()()( 0
01
01
01 xxxx
xfxfxfxN ?
?
???
2、利用差商表的最外一行，构造插值多项式
)()](,,[)](,[)()( 1000100 ???????? nnn xxxxxxfxxxxfxfxN ???
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
? 一些性质
?
? ?? ????
??
?
?
n
i niiiiii
i
n
n
nn
xxxxxxxx
xf
xxf
x
xLxN
0 110
0
)())(()(
)(
],,[
)()(
??
?
的系数一样
性质 2
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
误差
0
0 1 0 0
1
00
{ } N e w t on ( )
{ } { } ( ) ( ) [,,,] ( ) ( )
( ) ( )
( ) ( ) [,,,] ( ) ( )
n
i i n
n
i i n n n n
n
n n n
x N x
x a N t N t f x x a t x t x
N a f a
f a N a f x x a a x a x
?
??
?
? ? ? ?
?
? ? ? ? ?
另 一 方 面
设 插 值 为
则 有 为
显 然
)!1(
)(],,,[ 1
0 ???
?
n
faxxf n
n
?? 性质 3
1
0
() ( ) ( ) ( ) ( )
( 1 ) !
n
n n n
fN x R x x x x x
n
??? ? ?
?同 样 的 误 差 为
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
差商性质总结
?
? ?? ????
?
n
i niiiiii
i
n xxxxxxxx
xf
xxf
0 110
0 )())(()(
)(
],,[
??
?
],,[],,[ 00 niin xxfxxf ?? ?
)!(
)(],,[
0 n
fxxf n
n
???
??
?
?
???
nk
nkaxxfxPxf n
k
n
,0
,],,[),()(
0 ?推论：若
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
1.4 Hermite插值
有时候，构造插值函数除了函数值的条件以外，还需要一定的
连续性条件，如一阶导数值等，这种插值称为 Hermite插值。
插值称为
条件的插值和定义：满足
H e r m i t e
}),,,1),(,{(,)}(,{ 00 niiikiniii kkxfxxfx ?? ? ?
n
iii
n
iii
i
xfxxfx
k
00 )}(',{,)}(,{
1
??
?
和
满足一阶导条件为例，即每个点上还要以所有 称为二重密切 Hermite插值
§ 3 Hermite Interpolation
例,设 x0 ? x1 ? x2,已知 f(x0),f(x1),f(x2) 和 f ’(x1),求多项式 P(x)
满足 P(xi) = f (xi),i = 0,1,2,且 P’(x1) = f ’(x1),并估计误差。
模仿 Lagrange 多项式的思想，设解,首先,P的阶数 = 3
? ?? 2 13 )()()()()(
?0i ii
xhx1f ’xhxfxP ?
h0(x) 有根 x1,x2,且 h0’(x1) = 0 ? x1 是重根。 )()()( 2
2
100 xxxxCxh ???
又, h0(x0) = 1 ? C0
)()(
)()()(
20
2
10
2
2
10
xxxx
xxxxxh
??
???
h2(x)
h1(x) 有根 x0,x2 ? ))()(()( 201 xxxxBAxxh ????
由余下条件 h1(x1) = 1 和 h1’(x1) = 0 可解。
与 h0(x) 完全类似。
(x)?h1 有根 x0,x1,x2 ? ?h
1 ))()(()( 2101 xxxxxxCx ?????
h1又, ’(x1) = 1 ? C1 可解。
其中 hi(xj) = ?ij,hi’(x1) = 0,(xi) = 0,’(x1) = 1?h1 ?h1
),())()(()()()( 221033 xxxxxxxKxPxfxR ?????? !4 )()( )4(fxK ??
与 Lagrange 分析
完全类似
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)()}({,)}({
)(')()()()(
12
00
00
12
xPxgxh
xfxgxfxhxH
nn
ii
n
ii
n
i
ii
n
i
iin
?
??
??
?
?
?? ??
问题变为求函数
设，
?
?
?
?
?
?
?
?
?
?
ijji
ji
ji
ijji
xg
xg
xh
xh
?
?
)('
0)(
,0)('
)(
同样：
仿照 Lagrange插值的做法，首先确定多项式插值空间的维数，
注意到，我们的条件共有 2(n+1)个条件，所以，最高次数为 2n+1
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
1000'
0100'
0010
0001
0
0
00
??
???????
??
??
???????
??
??
n
n
nn
x
x
x
x
gghh
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?整个构造步骤如下：
1、确定多项式的最高项次数，就是函数空间的维数
2、假设一组基函数，列出插值多项式
3、列出基函数满足的公式（画表），求基函数
称为
构造基函数方法
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
误差分析
类似 Lagrange插值的分析方法
0
0
00
0
0
11
0
11
0
11
0
( 1 )
0
0
( ) ( ) ( )
{,,} ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( 1 ) !
()
( ) (
( 1 ) !
n
n
nn
n
n
kk
n
kk
n
k k n k k n
n
k k n
n
R x f x H x
x x R x
R x k x x x x x
t f t H t k x t x t x
f k x k k n
f
R x x x
k k n
?
? ? ?
?
??
??
? ? ? ? ? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ?
易知,为 若干重根
记
0
11
) ( )
n
kk
n
xx
??
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
二重密切 Hermite插值误差
( 2 2 )
22
0
()( ) ( ) ( )
( 2 2) !
n
n
fR x x x x x
n
??? ? ?
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
例,在 [?5,5]上考察 的 Ln(x)。取
21
1)(
xxf ?? ),.,,,0(105 niinx i ????
-5 -4 -3 -2 -1 0 1 2 3 4 5-0.5
0
0.5
1
1.5
2
2.5
n 越大，
端点附近抖动
越大，称为
Runge 现象
Ln(x) ? f (x)?
是否次数越高越好呢？
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
分段低阶插值
? Runge现象
例：
]1,1[ 251 1)( 2 ???? xxxf
等距节点构造 10次 Lagrange插值多项式
)(10 xL
x
)(
)(
10 xL
xf
-0.90
0.04706
1.57872
-0.70
0.07547
-0.22620
-0.50
0.13793
0.25376
-0.30
0.30769
0.23535
1901年,Runge
等距高次插值，
数值稳定性差，
本身是病态的。
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?分段线性插值
每个小区间上，作线性插值
],[),()()( 11
11
1
??
??
? ?
?
??
?
??
iii
ii
i
i
ii
i
i xxxxfxx
xxxf
xx
xxxs
? ],[,)()( 1??? iiin xxxxSxp
(1) ],[)( baCxp
n ?
(2) )(xp
n
在每个小区间上为一个不高于 1次的多项式
分段 低次 插值
特性
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?误差
],[ 1?? ii xxx
2
12
1
)2(
22
M
))((
!2
)(
)()(
?
?
?
?
?
? ?
?
????
?
?
ii
iin
xx
xxxx
f
xpxf
?
)(822M)()( 2
2
12 abhMxxnxpxf ii
n ????
??
?
? ????? ?
可以看出 ???? nxfxp
n ),()(
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
收敛，可惜只一阶精度，不够光滑。
类似，可以作二重密切 Hermite插值
关键：
分段、低阶插值
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
三次样条插值
分段低阶插值，收敛性好，但光滑性不够理想。在工业设计中，
对曲线光滑性要求高，如：流线型
设想这样一曲线：插值，次数不高于 3次，整个曲线 2阶连续导
数，称为三次样条函数插值。
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
每个小区间不高于 3次，
],[,)( 123 ?????? iiiiiii xxxdxcxbxaxS 1,,0 ?? ni ?
有 4n个未知数，我们的已知条件如下：
( 0) ( 0)
'( 0) '( 0)
''( 0) ''( 0)
( ) ( )
ii
ii
ii
ii
S x S x
S x S x
S x S x
S x f x
? ? ?
? ? ?
? ? ?
?
1,,1 ?? ni ?
ni,,0 ??
1,,1 ?? ni ?
1,,1 ?? ni ?
共 3n-3+n+1=4n-2个条件
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?m关系式
需要附加 2个条件，通常在 边界 处给出
设
],[,
)(',)('
)()(),()(
,)('
1
11
11
?
??
?? ?
?
?
?
??
??
?
ii
iiiiii
iiiiii
iii
xxx
mxSmxS
xfxSxfxS
mxS 则
所以，是 3次二重 Hermite插值，记
iii xxh ?? ? 1
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
2
13
2
113
2
12
2
112
1
( ) [ 2( ) ] ( ) ( )
1
[ 2( ) ] ( ) ( )
1
( ) ( )
1
( ) ( )
i i i i i
i
i i i i
i
i i i
i
i i i
i
S x h x x x x f x
h
h x x x x f x
h
x x x x m
h
x x x x m
h
?
??
?
??
? ? ? ?
? ? ? ?
? ? ?
? ? ?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
13
13
12
12
6
'' ( ) [ 2( ) ] ( )
6
[ 2( ) ] ( )
1
[ 6( ) 2 ]
1
[ 6( ) 2 ]
i i i i
i
i i i
i
i i i
i
i i i
i
S x h x x f x
h
h x x f x
h
x x h m
h
x x h m
h
?
?
?
?
? ? ?
? ? ?
? ? ?
? ? ?
由
)('')('' 1 iiii xSxS ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
1
11
11
2iii i i
i i i i
hhm m m
h h h h
?
??
??
??
??
1 1 1
1 1 1
( ) ( ) ( ) ( )3 i i i i i i
i i i i i i
h f x f x h f x f x
h h h h h h
? ? ?
? ? ?
?? ??
????
????
i? ici?
1,,1 ?? ni ?
112 ( [,] [,] )i i i i i if x x f x x??????
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
0
1 1 1 1
2 2 2 2
1 1 1 1
2
2
2
n n n n
n
m
mc
mc
mc
m
??
??
??
? ? ? ?
??
??
? ? ? ?
??
? ? ? ?
??
? ? ? ?
???
? ? ? ?
??
? ? ? ?
??
? ? ? ?
??
??
??
两个边界条件
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
有
iiiiii cmmm ??? ?? 11 2 ?? 1,,1 ?? ni ?
加上边值条件
(1) 固支边界条件
nn mxSmxS ?? )(',)(' 00
(2)
nn MxSMxS ?? )('',)('' 00
n
n
nnnn
M
h
xxfmm
M
h
xxfmm
2
],[32
2
],[32
11
0
1
1010
???
???
??
(3) 周期边界条件
)(')('),('')('' 00 nn xSxSxSxS ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?M关系式
设
],[,
)('',)(''
)()(),()(
,)(''
1
11
11
?
??
??
?
?
?
?
??
??
?
ii
iiiiii
iiiiii
iii
xxx
MxSMxS
xfxSxfxS
MxS 则
记
iii xxh ?? ? 1
1
1''( )
ii
ii
x x x xS x M M
hh
?
?
????
?
三弯距法,3次多项式导 2次后，为线性函数
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
积分 2次
33
1
11
( ) ( )( ) ( ) ( )
66
ii
i i i i i
ii
x x x xS x M M c x x d x x
hh
?
??
??? ? ? ? ? ?
由
)(')(' 1 iiii xSxS ??
有
iiiiii dmmM ??? ?? 11 2 ?? 1,,1 ?? ni ?
11
11
11
( ) ( ) ( ) ( )6 6 [,,]i i i i
i i i
i i i i
f x f x f x f x f x x x
h h h h
??
??
??
?? ??
????
? ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
计算过程如下
)(,
)(,
)(,
)(,
)(,
11
22
11
00
nn
nn
xfx
xfx
xfx
xfx
xfx
??
?
n
n
h
h
h
h
1
2
1
?
?
1
2
1n
?
?
?
?
1
2
1n
?
?
?
?
01
12
23
1
[,]
[,]
[,]
[,]
nn
f x x
f x x
f x x
f x x
?
1
2
1
?n
c
c
c
?
1
2
1n
d
d
d
?
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
第 1章 插 值
实际中,f(x)多样，复杂，通常只能观测到一些离散数据；
或者 f(x)过于复杂而难以运算。这时我们要用近似函数 g(x)来
逼近 f(x)。
自然地，希望 g(x)通过所有的离散点
? 概念
x0 x1 x2 x3 x4x
g(x) ? f(x)
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
定义,为定义在区间 上的函数,为区间上 n+1个互不
相同的点,为给定的某一函数类。求 上的函数 满足
)(xf ? ?ba,? ? 0ni ix ?
? ? )(xg
nixfxg ii,,0,)()( ???
问题
? 是否存在唯一
? 如何构造
? 误差估计
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
? ? ??
????
???
,,
)()()()(
)()()(
0
00
00
n
inniii
nn
aa
xaxaxfxg
xaxaxg
?
?
?
??
??
有解 系数行列式不为 0
设 则
1,与基函数无关
2,与原函数 f(x)无关
3,基函数个数与点个数相同
特点：
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
存在唯一定理
定理 1.1, 为 n＋ 1个节点，
n+1维空间，则插值函数存在唯一，当且仅当
? ? 0ni ix ? },,{ 10 ns p a n ??? ???
0
)()(
)()(
0
000
?
nnn
n
xx
xx
??
??
?
???
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
},,,1{)( 2 nn xxxs p a nx ?????对应于
则
0
1
1
0
0
??? ?
??? nij
ji
n
n
n
xx
x
x
?
???
?
Vandermonde行列式
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
多项式插值的 Lagrange型
?如何找？
在基函数上下功夫，取基函数为 nn
ii xl ??? 0)}({
要求
?
?
?
?
???
ji
jixl
ijji,1
,0)( ? 则
)()()(
0
i
n
i
i xfxlxg ?
?
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?线性插值
01
0
1
10
1
0 )(,)( xx
xxxl
xx
xxxl
?
??
?
??
)()()()()( 11001 xlxfxlxfxL ??
求
nii xl 0)}({ ?
，易知：
)())(()()( 110 niiii xxxxxxxxaxl ????? ?? ??
)())(()(
1
110 niiiiii
i xxxxxxxxa ?????
?? ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?二次插值
))((
))((
)(
))((
))((
)(
))((
))((
)(
1202
10
2
2101
20
1
2010
21
0
xxxx
xxxx
xl
xxxx
xxxx
xl
xxxx
xxxx
xl
??
??
?
??
??
?
??
??
?
2 0 0 1 1 2 2( ) ( ) ( ) ( ) ( ) ( ) ( )L x f x l x f x l x f x l x? ? ?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)3,3(),1,2(),0,0(),2,1( ?
例：
)31)(21)(01(
)3)(2)(0()(
0 ??????
???? xxxxl
)23)(03)(13(
)2)(0)(1()(
3 ???
???? xxxxl
)32)(02)(12(
)3)(0)(1()(
2 ???
???? xxxxl
)30)(20)(10(
)3)(2)(1()(
1 ???
???? xxxxl
)(3)(1)(0)(2)( 3210 xlxlxlxlxg ????
例,已知
2 33s i n,214s i n,216s i n ??? ???
分别利用 sin x 的 1次,2次 Lagrange 插值计算 sin 50?
并估计误差。
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
§ 1 Lagrange Polynomial
解：
0x 1x 2x
185500 ??
n = 1 分别利用 x0,x1 以及 x1,x2 计算
4,6 10
?? ?? xx?利用
216/4/ 6/214/6/ 4/)(1 ???????? ?? ??? ? xxxL
这里 )
3,6(,s in)(,s in)( )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 10 ?? ?L 0.77614
外推 /* extrapolation */ 的实际误差 ??0.01001
3,4 21 ?? ?? xx
?利用 sin 50?? 0.76008,00660.0
185~00538.0 1 ???????? ?R
内插 /* interpolation */ 的实际误差 ?0.00596
内插通常优于外推。选择
要计算的 x 所在的区间的
端点，插值效果较好。
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
n = 2
2
3
))((
))((
2
1
))((
))((
21))((
))(()(
4363
46
3464
36
3646
342 ??? ?????? ?????? ???
????
??
????
??
????
?? xxxxxxxL
)185(50sin 20 ?? ?L 0.76543
2 3c o s21;)3)(4)(6(!3
c o s)(
2 ?????
??
xx xxxxR ????
?
00 0 77.018500 0 44.0 2 ???????? ?R ?sin 50?= 0.7660444…
2次插值的实际误差 ?0.00061
高次插值通常优于
低次插值
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
误差 )()()( xLxfxR
nn ??解：
)())(()(
,0,0)(
,0,)()(
0 nn
in
ini
xxxxxkxR
nixR
nixLxf
????
???
??
?
?
??
求
)( ?xk
0)( a n d,0,0)(
)())(()()()(
)(,
0
???
?????
??
anix
xtxtaktLtft
aka
i
nn
??
?
?
?设
易知
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)(t?? 有 n+2个零点
)!1(
)(
)(
)!1)(()()(
0)(,
)1(
)1()1(
)1(
?
?
???
???
?
??
?
n
f
ak
nakf
n
nn
n
?
???
???
)()(
)!1(
)()(
0
)1(
n
n
n xxxxn
fxR ??
?
??
?
??
由 a的任意性
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
事后误差估计
给定 ? ? 1
0
?
?
n
iix
任取 n+1个构造 )(xL
n
)(
~
1,,1
)(,,0
xLni
xLni
n
n
???
??
?
?
如：
另取
则
)()(
)!1(
)(
)(
~
)(
)()(
)!1(
)(
)()(
11
2
)1(
0
1
)1(
?
?
?
??
?
??
??
?
??
n
n
n
n
n
n
xxxx
n
f
xLxf
xxxx
n
f
xLxf
?
?
?
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
近似
)()( 2)1(1)1( ?? ?? ? nn ff
则
? ?)(
~
)()()(
)(
~
)()(
)(
~
)(
)()(
10
0
01
0
10
1
1
0
xLxL
xx
xx
xLxf
xL
xx
xx
xL
xx
xx
xf
xx
xx
xLxf
xLxf
nn
n
n
n
n
n
n
n
nn
n
?
?
?
???
?
?
?
?
?
??
?
?
?
?
?
?
??
?
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?Lagrange 插值的缺点
无承袭性。增加一个节点，所有的基函数都要重新计算
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
Newton型多项式插值
},,{ 110 ?nxxx ? },,{ 10 nxxx ?
且
nixfxNxN iinin ?,1,)()()( 1 ??? ?
)()()( 011 nnn xxxxaxq ???? ?? ?
同样
)()()( 10 ????? nnn xxxxaxq ?
)()()( 1 xqxNxN nnn ?? ?
承袭性, )()()(
11 xqxNxN nnn ?? ??
1?? nP
为实数
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)()()()( 10010 ????????? nnn xxxxaxxaaxN ??
而且有：
?
?
?
?
?
?
?
????????
???????
????
??
?
)()()()()(
)())(()()(
)()()(
)()(
10010
21202202102
101101
000
nnnnnnnn
n
n
n
xfxxxxaxxaaxN
xfxxxxaxxaaxN
xfxxaaxN
xfaxN
??
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
这样：
)( 00 xfa ?
01
01
1
)()(
xx
xfxfa
?
??
???
?
???
? ?
?
?
?
? 1
02
02
12
2
)()(1 a
xx
xfxf
xx
a
???
?
???
?
?
??
?
?
?
???
? ?
?
?
?
? 2
01
1
03
03
23
3
1)()(1 a
xx
a
xx
xfxf
xx
a
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
0
101
0
01
01
10
],,[],,[
],,[
)()(
],[
xx
xxfxxf
xxf
xx
xfxf
xxf
k
kk
k
?
?
?
?
?
?
?
??
? 称为 k阶差商
称为 1阶差商
定义,差商
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)( 00 xfa ?
],[)()( 10
01
01
1 xxfxx
xfxfa ?
?
??
? ? ],,[],[],[
1
)()(1
0120102
12
1
02
02
12
2
xxxfxxfxxf
xx
a
xx
xfxf
xx
a
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
由归纳：
],,[ 0 nn xxfa ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
此处用到差商的一个性质, （用归纳法易证）
对称性：
],,[],,[ 00 kiik xxfxxf ?? ?
定义关键：找不同的元素相减作分母
的任意排列是 kii k,,0,,0 ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
Newton插值构造
)(,00 xfx
)(,11 xfx
)(,22 xfx
?
)(,nn xfx
],[ 10 xxf
],[ 12 xxf
],[ 1 nn xxf ?
],,[ 012 xxxf
],,[ 21 ?? nnn xxxf
? ?
],,[ 0xxf n ?
1、先构造差商表
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?例子
2点 Newton型插值
)()()()()( 0
01
01
01 xxxx
xfxfxfxN ?
?
???
2、利用差商表的最外一行，构造插值多项式
)()](,,[)](,[)()( 1000100 ???????? nnn xxxxxxfxxxxfxfxN ???
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
? 一些性质
?
? ?? ????
??
?
?
n
i niiiiii
i
n
n
nn
xxxxxxxx
xf
xxf
x
xLxN
0 110
0
)())(()(
)(
],,[
)()(
??
?
的系数一样
性质 2
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
误差
0
0 1 0 0
1
00
{ } N e w t on ( )
{ } { } ( ) ( ) [,,,] ( ) ( )
( ) ( )
( ) ( ) [,,,] ( ) ( )
n
i i n
n
i i n n n n
n
n n n
x N x
x a N t N t f x x a t x t x
N a f a
f a N a f x x a a x a x
?
??
?
? ? ? ?
?
? ? ? ? ?
另 一 方 面
设 插 值 为
则 有 为
显 然
)!1(
)(],,,[ 1
0 ???
?
n
faxxf n
n
?? 性质 3
1
0
() ( ) ( ) ( ) ( )
( 1 ) !
n
n n n
fN x R x x x x x
n
??? ? ?
?同 样 的 误 差 为
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
差商性质总结
?
? ?? ????
?
n
i niiiiii
i
n xxxxxxxx
xf
xxf
0 110
0 )())(()(
)(
],,[
??
?
],,[],,[ 00 niin xxfxxf ?? ?
)!(
)(],,[
0 n
fxxf n
n
???
??
?
?
???
nk
nkaxxfxPxf n
k
n
,0
,],,[),()(
0 ?推论：若
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
1.4 Hermite插值
有时候，构造插值函数除了函数值的条件以外，还需要一定的
连续性条件，如一阶导数值等，这种插值称为 Hermite插值。
插值称为
条件的插值和定义：满足
H e r m i t e
}),,,1),(,{(,)}(,{ 00 niiikiniii kkxfxxfx ?? ? ?
n
iii
n
iii
i
xfxxfx
k
00 )}(',{,)}(,{
1
??
?
和
满足一阶导条件为例，即每个点上还要以所有 称为二重密切 Hermite插值
§ 3 Hermite Interpolation
例,设 x0 ? x1 ? x2,已知 f(x0),f(x1),f(x2) 和 f ’(x1),求多项式 P(x)
满足 P(xi) = f (xi),i = 0,1,2,且 P’(x1) = f ’(x1),并估计误差。
模仿 Lagrange 多项式的思想，设解,首先,P的阶数 = 3
? ?? 2 13 )()()()()(
?0i ii
xhx1f ’xhxfxP ?
h0(x) 有根 x1,x2,且 h0’(x1) = 0 ? x1 是重根。 )()()( 2
2
100 xxxxCxh ???
又, h0(x0) = 1 ? C0
)()(
)()()(
20
2
10
2
2
10
xxxx
xxxxxh
??
???
h2(x)
h1(x) 有根 x0,x2 ? ))()(()( 201 xxxxBAxxh ????
由余下条件 h1(x1) = 1 和 h1’(x1) = 0 可解。
与 h0(x) 完全类似。
(x)?h1 有根 x0,x1,x2 ? ?h
1 ))()(()( 2101 xxxxxxCx ?????
h1又, ’(x1) = 1 ? C1 可解。
其中 hi(xj) = ?ij,hi’(x1) = 0,(xi) = 0,’(x1) = 1?h1 ?h1
),())()(()()()( 221033 xxxxxxxKxPxfxR ?????? !4 )()( )4(fxK ??
与 Lagrange 分析
完全类似
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
)()}({,)}({
)(')()()()(
12
00
00
12
xPxgxh
xfxgxfxhxH
nn
ii
n
ii
n
i
ii
n
i
iin
?
??
??
?
?
?? ??
问题变为求函数
设，
?
?
?
?
?
?
?
?
?
?
ijji
ji
ji
ijji
xg
xg
xh
xh
?
?
)('
0)(
,0)('
)(
同样：
仿照 Lagrange插值的做法，首先确定多项式插值空间的维数，
注意到，我们的条件共有 2(n+1)个条件，所以，最高次数为 2n+1
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
1000'
0100'
0010
0001
0
0
00
??
???????
??
??
???????
??
??
n
n
nn
x
x
x
x
gghh
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?整个构造步骤如下：
1、确定多项式的最高项次数，就是函数空间的维数
2、假设一组基函数，列出插值多项式
3、列出基函数满足的公式（画表），求基函数
称为
构造基函数方法
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
误差分析
类似 Lagrange插值的分析方法
0
0
00
0
0
11
0
11
0
11
0
( 1 )
0
0
( ) ( ) ( )
{,,} ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( 1 ) !
()
( ) (
( 1 ) !
n
n
nn
n
n
kk
n
kk
n
k k n k k n
n
k k n
n
R x f x H x
x x R x
R x k x x x x x
t f t H t k x t x t x
f k x k k n
f
R x x x
k k n
?
? ? ?
?
??
??
? ? ? ? ? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ?
易知,为 若干重根
记
0
11
) ( )
n
kk
n
xx
??
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
二重密切 Hermite插值误差
( 2 2 )
22
0
()( ) ( ) ( )
( 2 2) !
n
n
fR x x x x x
n
??? ? ?
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
例,在 [?5,5]上考察 的 Ln(x)。取
21
1)(
xxf ?? ),.,,,0(105 niinx i ????
-5 -4 -3 -2 -1 0 1 2 3 4 5-0.5
0
0.5
1
1.5
2
2.5
n 越大，
端点附近抖动
越大，称为
Runge 现象
Ln(x) ? f (x)?
是否次数越高越好呢？
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
分段低阶插值
? Runge现象
例：
]1,1[ 251 1)( 2 ???? xxxf
等距节点构造 10次 Lagrange插值多项式
)(10 xL
x
)(
)(
10 xL
xf
-0.90
0.04706
1.57872
-0.70
0.07547
-0.22620
-0.50
0.13793
0.25376
-0.30
0.30769
0.23535
1901年,Runge
等距高次插值，
数值稳定性差，
本身是病态的。
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?分段线性插值
每个小区间上，作线性插值
],[),()()( 11
11
1
??
??
? ?
?
??
?
??
iii
ii
i
i
ii
i
i xxxxfxx
xxxf
xx
xxxs
? ],[,)()( 1??? iiin xxxxSxp
(1) ],[)( baCxp
n ?
(2) )(xp
n
在每个小区间上为一个不高于 1次的多项式
分段 低次 插值
特性
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?误差
],[ 1?? ii xxx
2
12
1
)2(
22
M
))((
!2
)(
)()(
?
?
?
?
?
? ?
?
????
?
?
ii
iin
xx
xxxx
f
xpxf
?
)(822M)()( 2
2
12 abhMxxnxpxf ii
n ????
??
?
? ????? ?
可以看出 ???? nxfxp
n ),()(
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
收敛，可惜只一阶精度，不够光滑。
类似，可以作二重密切 Hermite插值
关键：
分段、低阶插值
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
三次样条插值
分段低阶插值，收敛性好，但光滑性不够理想。在工业设计中，
对曲线光滑性要求高，如：流线型
设想这样一曲线：插值，次数不高于 3次，整个曲线 2阶连续导
数，称为三次样条函数插值。
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
每个小区间不高于 3次，
],[,)( 123 ?????? iiiiiii xxxdxcxbxaxS 1,,0 ?? ni ?
有 4n个未知数，我们的已知条件如下：
( 0) ( 0)
'( 0) '( 0)
''( 0) ''( 0)
( ) ( )
ii
ii
ii
ii
S x S x
S x S x
S x S x
S x f x
? ? ?
? ? ?
? ? ?
?
1,,1 ?? ni ?
ni,,0 ??
1,,1 ?? ni ?
1,,1 ?? ni ?
共 3n-3+n+1=4n-2个条件
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?m关系式
需要附加 2个条件，通常在 边界 处给出
设
],[,
)(',)('
)()(),()(
,)('
1
11
11
?
??
?? ?
?
?
?
??
??
?
ii
iiiiii
iiiiii
iii
xxx
mxSmxS
xfxSxfxS
mxS 则
所以，是 3次二重 Hermite插值，记
iii xxh ?? ? 1
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
2
13
2
113
2
12
2
112
1
( ) [ 2( ) ] ( ) ( )
1
[ 2( ) ] ( ) ( )
1
( ) ( )
1
( ) ( )
i i i i i
i
i i i i
i
i i i
i
i i i
i
S x h x x x x f x
h
h x x x x f x
h
x x x x m
h
x x x x m
h
?
??
?
??
? ? ? ?
? ? ? ?
? ? ?
? ? ?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
13
13
12
12
6
'' ( ) [ 2( ) ] ( )
6
[ 2( ) ] ( )
1
[ 6( ) 2 ]
1
[ 6( ) 2 ]
i i i i
i
i i i
i
i i i
i
i i i
i
S x h x x f x
h
h x x f x
h
x x h m
h
x x h m
h
?
?
?
?
? ? ?
? ? ?
? ? ?
? ? ?
由
)('')('' 1 iiii xSxS ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
1
11
11
2iii i i
i i i i
hhm m m
h h h h
?
??
??
??
??
1 1 1
1 1 1
( ) ( ) ( ) ( )3 i i i i i i
i i i i i i
h f x f x h f x f x
h h h h h h
? ? ?
? ? ?
?? ??
????
????
i? ici?
1,,1 ?? ni ?
112 ( [,] [,] )i i i i i if x x f x x??????
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
0
1 1 1 1
2 2 2 2
1 1 1 1
2
2
2
n n n n
n
m
mc
mc
mc
m
??
??
??
? ? ? ?
??
??
? ? ? ?
??
? ? ? ?
??
? ? ? ?
???
? ? ? ?
??
? ? ? ?
??
? ? ? ?
??
??
??
两个边界条件
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
有
iiiiii cmmm ??? ?? 11 2 ?? 1,,1 ?? ni ?
加上边值条件
(1) 固支边界条件
nn mxSmxS ?? )(',)(' 00
(2)
nn MxSMxS ?? )('',)('' 00
n
n
nnnn
M
h
xxfmm
M
h
xxfmm
2
],[32
2
],[32
11
0
1
1010
???
???
??
(3) 周期边界条件
)(')('),('')('' 00 nn xSxSxSxS ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
?M关系式
设
],[,
)('',)(''
)()(),()(
,)(''
1
11
11
?
??
??
?
?
?
?
??
??
?
ii
iiiiii
iiiiii
iii
xxx
MxSMxS
xfxSxfxS
MxS 则
记
iii xxh ?? ? 1
1
1''( )
ii
ii
x x x xS x M M
hh
?
?
????
?
三弯距法,3次多项式导 2次后，为线性函数
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
积分 2次
33
1
11
( ) ( )( ) ( ) ( )
66
ii
i i i i i
ii
x x x xS x M M c x x d x x
hh
?
??
??? ? ? ? ? ?
由
)(')(' 1 iiii xSxS ??
有
iiiiii dmmM ??? ?? 11 2 ?? 1,,1 ?? ni ?
11
11
11
( ) ( ) ( ) ( )6 6 [,,]i i i i
i i i
i i i i
f x f x f x f x f x x x
h h h h
??
??
??
?? ??
????
? ??
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
计算过程如下
)(,
)(,
)(,
)(,
)(,
11
22
11
00
nn
nn
xfx
xfx
xfx
xfx
xfx
??
?
n
n
h
h
h
h
1
2
1
?
?
1
2
1n
?
?
?
?
1
2
1n
?
?
?
?
01
12
23
1
[,]
[,]
[,]
[,]
nn
f x x
f x x
f x x
f x x
?
1
2
1
?n
c
c
c
?
1
2
1n
d
d
d
?
