第六章 插值 /* 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 x4 x
g(x) ? f(x)
§ 1 拉格朗日多项式 /* Lagrange Polynomial */
n i y x P i i n,...,0,) ( = =
求 n 次多项式 使得 n
nn xaxaaxP ???= ?10)(
条件,无重合节点，即 ji xx ?ji ?
n = 1 已知 x0,x1 ; y0,y1,求 xaaxP
101 )( ?=
使得
1 1 1 0 0 1 ) (,) ( y x P y x P = =
可见 P1(x) 是过 ( x0,y0 ) 和 ( x1,y1 ) 两点的直线。
) ( ) ( 0
0 1
0 1
0 1 x x x x
y y y x P -
-
- ? =
1 0
1
x x
x x
-
-
0 1
0
x x
x x
-
- = y
0 + y1
l0(x) l1(x)
? = = 1
0
) (
i i i
y x l
称为 拉氏基函数 /* 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
i i n y x l x P
0
) ( ) (,则显然有 Pn(xi) = yi 。
li(x) 每个 li 有 n 个根 x0 … xi … xn
?
=
- = - - - = n
j
j ? i
j i n i i i x x C x x x x x x C x l
0
0 ) ( ) )...( )...( ( ) (
? - = = j ? i
j i
i i i x x C x l ) ( 1 1 ) (
?
=
? -
-= 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
n ????? ?10
，且 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
i n x x x K x R
0
) ( ) ( ) (
任意固定 x ? xi (i = 0,…,n),考察 ?
=
- - =
n
i
i x t x K t Rn t
0
) ( ) ( ) ( ) ( ?
?(x)有 n+2 个不同的根 x0 … xn x ),(,0)()1( ba
xxn ?=? ???
! ) 1 ( ) ( ) ( ) 1 ( ? - ? n x K R x n n ?
注意这里是对 t 求导
= ? - - ? ? ! ) 1 )( ( ) ( ) ( ) 1 ( ) 1 ( n x K L f x n n x n ? ?
! ) 1 (
) ( ) ( ) 1 (
? =
?
n
f x K x n ?
?
=
?
-?=
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…
) 18 5 ( 50 sin 1 0 ? ? ? L 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 1 ???????? ?R
内插 /* interpolation */ 的实际误差 ? 0.00596
内插通常优于外推。选择
要计算的 x 所在的区间的
端点，插值效果较好。
§ 1 Lagrange Polynomial
n = 2
2
3
))((
))((
2
1
))((
))((
21))((
))(()(
4363
46
3464
36
3646
342 ?-- --??-- --??-- --=
????
??
????
??
????
?? xxxxxxxL
) 18 5 ( 50 sin 2 0 ? ? ? L 0.76543
2 3c o s21;)3)(4)(6(!3
c o s)(
2 ??---
-=
xx xxxxR ????
?
00077.018500044.0 2 ???????? ?R ?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 x4 x
g(x) ? f(x)
§ 1 拉格朗日多项式 /* Lagrange Polynomial */
n i y x P i i n,...,0,) ( = =
求 n 次多项式 使得 n
nn xaxaaxP ???= ?10)(
条件,无重合节点，即 ji xx ?ji ?
n = 1 已知 x0,x1 ; y0,y1,求 xaaxP
101 )( ?=
使得
1 1 1 0 0 1 ) (,) ( y x P y x P = =
可见 P1(x) 是过 ( x0,y0 ) 和 ( x1,y1 ) 两点的直线。
) ( ) ( 0
0 1
0 1
0 1 x x x x
y y y x P -
-
- ? =
1 0
1
x x
x x
-
-
0 1
0
x x
x x
-
- = y
0 + y1
l0(x) l1(x)
? = = 1
0
) (
i i i
y x l
称为 拉氏基函数 /* 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
i i n y x l x P
0
) ( ) (,则显然有 Pn(xi) = yi 。
li(x) 每个 li 有 n 个根 x0 … xi … xn
?
=
- = - - - = n
j
j ? i
j i n i i i x x C x x x x x x C x l
0
0 ) ( ) )...( )...( ( ) (
? - = = j ? i
j i
i i i x x C x l ) ( 1 1 ) (
?
=
? -
-= 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
n ????? ?10
，且 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
i n x x x K x R
0
) ( ) ( ) (
任意固定 x ? xi (i = 0,…,n),考察 ?
=
- - =
n
i
i x t x K t Rn t
0
) ( ) ( ) ( ) ( ?
?(x)有 n+2 个不同的根 x0 … xn x ),(,0)()1( ba
xxn ?=? ???
! ) 1 ( ) ( ) ( ) 1 ( ? - ? n x K R x n n ?
注意这里是对 t 求导
= ? - - ? ? ! ) 1 )( ( ) ( ) ( ) 1 ( ) 1 ( n x K L f x n n x n ? ?
! ) 1 (
) ( ) ( ) 1 (
? =
?
n
f x K x n ?
?
=
?
-?=
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…
) 18 5 ( 50 sin 1 0 ? ? ? L 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 1 ???????? ?R
内插 /* interpolation */ 的实际误差 ? 0.00596
内插通常优于外推。选择
要计算的 x 所在的区间的
端点，插值效果较好。
§ 1 Lagrange Polynomial
n = 2
2
3
))((
))((
2
1
))((
))((
21))((
))(()(
4363
46
3464
36
3646
342 ?-- --??-- --??-- --=
????
??
????
??
????
?? xxxxxxxL
) 18 5 ( 50 sin 2 0 ? ? ? L 0.76543
2 3c o s21;)3)(4)(6(!3
c o s)(
2 ??---
-=
xx xxxxR ????
?
00077.018500044.0 2 ???????? ?R ?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,
