第二章 插值方法/* Interpolation */
2.1 引言
函数逼近
问题的引出：现实应用中常用函数()y f x =表示某种内在规律的数量关系，但是情况往往是：
1）()y f x =在某个区间[a,b]存在，有时候是连续的，但是只能通过实验或观测得到一系列点i x 的函数值i y （得到函数表），而无法得到()f x 的表达式
2）函数表达式已知，但计算复杂（如()sin y x =，()lg y x =等）使用不方便，通常也使用函数表。如：三角函数表，对数表，平方根表，立方根表等。
问题：有时需要求不在函数表上的函数值怎么办？ 解决方法：根据所给的
()y f x =的函数表，构造一个简单的函数()
P x 近似替
代()f x （存在误差！），称为函数逼近。
称()P x 为逼近函数，()f x 为被逼近函数。
()P x 通常选择一类比较简单的函数，如代数多项式或分段代数多项式。
函数逼近的方法有很多，例如Taylor 级数，Fourier 级数，有限元方法、边界元方法，小波分析等，大学科叫逼近论。
本课程讨论连续函数的逼近，主要介绍插值法。 插值 （interpolation ）
已知()[],,y f x x a b =∈的函数表
求：()P x 使
()i i y P x =
0,1,2,,i n
= —— 插值问题
称()P x 为()f x 的插值函数；()f x 为被插值函数；0
1
n
x x x
为插值结点；
[],a b 为插值区间；求插值函数()P x 的方法称为插值法。
当()P x 为多项式时，相应的插值法为多项式插值；()P x 为分段的多项式，称
为分段插值；()P x 为三角多项式，称为三角插值。
插值法的几何示意图，P14图2.1
多项式插值是数值分析的基本工具，常用来计算被插函数的近似函数值，零、极点，导数、积分（第四章 数值积分和数值微分），解微分方程（第五章）、积分方程等。
2.2 拉格朗日插值
2.2.1 插值多项式的存在唯一性
问题：用不同的多项式插值方法得到的插值多项式的形式有可能不同，它们是否等价？（可以转化为相同的标准式？）
答案是肯定的！
两点确定一条直线（ 一次多项式 ） 三点确定一个抛物线（ 二次多项式 ） 是否n+1点确定一个n 次多项式？ 给定n +1个互异的插值点0
1
n
x x x
，求符合插值条件()
i
i y P x =的次数不
超过n 的插值多项式
()2
012n
n P x a a x a x a x
=++++ ——（标准式）
()
P x 存在且唯一！证明见P14，定理2.1。
可以通过求解方程组得到系数012,,n a a a a ，从而得到()P x 的表达式，但是这
样做不但计算复杂，且难以得到()P x 的简单表达式。
当n=20时，在108次/秒的计算机上计算需要几十万年！ 2.2.2 线性插值与抛物插值 线性插值
当n=1时：
已知 x k , x k+1；y k , y k+1， 求线性插值多项式 101()L x a a x =+ 使得：1()k k
L x y =且111()k k L x y ++=.
可见，1()L x 是过(,)k k x y 和11(,)k k x y ++的一条直线。
()111()k k k k k k
y y L x y x x x x ++-=+
-- 点斜式
11111()k k k k k k
k k
x x x x L x y y x x x x ++++--=
+
--
两点式
令()11k k k k
x x l x x x ++-=
-，()11k k k k
x x l x x x ++-=
-则：()()111()k k k k L x l x y l x y ++=+
称()k l x 及()1k l x +为一次插值基函数，或线性插值基函数。 注意：基函数 ()10
i j ij i j l x i j
δ=?==?≠?
抛物线插值
当n=2时：
已知x k-1，x k , x k+1；y k-1, y k , y k+1， 求二次插值多项式 2()L x 使得：211()k k L x y --=，2()k k L x y =，211()k k L x y ++=。
可见，2()L x 是过11(,)k k x y --，(,)k k x y 和11(,)k k x y ++的抛物线。
利用基函数法构造
()1
i j ij i j l x i j
δ=?==?
≠? i , j = k -1, k , k +1
因此构造
()()()
()()
11111k k k k k k k x x x x l x x x x x +---+--=
--
()()()
()()1111k k k k k k k x x x x l x x x x x -+-+--=
--
()()()
()()
11111k k k k k k k x x x x l x x x x x -++-+--=
--
此时：
()()()21111()k k k k k k L x l x y l x y l x y --++=++
称()1k l x -，()k l x 及()1k l x +为二次插值基函数，或抛物插值基函数。 2.2.3 拉格朗日插值多项式
从n=1和n ＝2的情形，可推广到n>1的情形： 只要构造n 次插值的基函数满足：
()10
i j ij i j l x i j
δ=?==?
≠? ,0,1,2,,i j n = 注意：n ＋1个节点
然后令n 次插值多项式 ()1
()n
n i
i
i L x l x y ==∑
显然有()n i i L x y =成立。
每个()0i l x =有n 个根，分别为0111,,,,,i i n x x x x x -+ ，因此第i 个基函数()i l x 可以写成：
()()()()()()()01110
n
i i i i n i j j i
j l x C x x x x x x x x x x C x x -+≠==-----=-∏
又： ()1i i l x =，故：()
1
n
i j i i
j j C x
x ≠==-∏
因此：
()()()()()()
()()()()()
01110111i i n i i i i i i i i n x x x x x x x x x x l x x x x x x x x x x x -+-+-----=
-----
这n +1个n 次多项式()()()01,,n l x l x l x 为节点01,,,n x x x 上的n 次插值基函数。
n 次插值多项式 ()0
()n
n i
i
i L x l x y ==
∑称为拉格朗日插值多项式。
记：()()()()101n n x x x x x x x ω+=---
则：()()()()()()10111n
i i i n x x x x x x x x x x x ω+-+'=----- 于是：()
()()10
1
()n
n n i
i i
n x L x y x x x ωω+=+=
'-∑
问题：如图2.1（P14），插值多项式在插值点上的误差为0，但是在其他位置上的估计误差是未知的。
如何估计出在其他点上的误差限？
1）如果()f x 是n 次多项式，则()f x 和()n L x 等价，误差为0； 2）如果()f x 不是n 次多项式，如何处理?
为了解决第2）种情况，我们引入差值余项的概念，估计出插值多项式估计误差的上界！
2.2.4 插值余项（ Remainder ）
在[a,b]上用()n L x 近似()f x ，其截断误差()()()n n R x f x L x =-，称为插值多项式的余项或插值余项。
定理2.2：关于插值余项的估计（P18）
证明：插值多项式在n+1个插值点上的误差为0，因此
()0n R x =至少有n +1个根，可以写成
()()()()()10
n
n i n i R x K x x x K x x ω+==-=∏
——要求()n R x 需求()K x
任意固定,0,1,,i x x i n ≠= （估计x 点的误差），构造变量为t 的函数
()()()()0n
n i i t R t K x t x ?==--∏ —— 此时，()K x 为与t 无关的常量！
()0t ?=有n +2个根，分别为01,,,,n x x x x ，故()t ?在[a,b]上有n ＋2个零点；
由罗尔定理，()t ?'在()t ?的两个零点之间至少有一个零点，故()t ?'在[a,b]上有n ＋1个零点；（注意：()t ?'是对t 求导）
同理，()t ?''在[a,b]上有n 个零点，()
()1n t ?+在[a,b]上有1个零点。
中间步骤：（注意，对t 求导！）
()()()
()()()()
1110n n n n n i i t R t K x t x ?+++=??=-- ?
??
∏
()
()()
()()
()()()()
11110n n n n n n
i i t f
t L t K x t x ?
++++=??=
--- ?
??
∏
()n L t 为n 次多项式，故而()
()1n n L t +为0。因此，
()
()()
()()()111!n n t f
t n K x ?
++=
-+
因此记做：(
)
()()
()()()111!0n n f
n K x ?ξξ++=
-+=
于是：()()
()
()()1,,1!
n f
K x a b n ξξ+=
∈+且依赖于x 。
故：()()()()
()
()()1111!
n n n n f
R x K x x x n ξωω+++==
+
余项表达式只有在()f x 的高阶导数存在时才能应用，又因为(),a b ξ∈的具体位置通常不可能给出，因此常计算()n L x 逼近()f x 的截断误差限：
()()()1
11!
n n n M R x x n ω++≤
+， 其中 ()
()11m ax n n a x b
M f
x ++≤≤=。
注意：当()f x 为任一个次数≤ n 的多项式时，()()10n f x +≡, 可知()0n R x ≡。即n 次插值多项式对于次数≤ n 的多项式是精确的。
附例1：给定1,0,1,2,3,4,5i x i i =+= 下面哪个是()2l x 的图像？
P19例2.1
2.3 逐次线性插值法则
拉格朗日插值法的缺陷
增加插值节点时，原来算出的数据均不能利用，必须重新计算。 为克服这一缺陷，通常用逐次线性插值法求得高次插值。 逐次线性插值
()01I x 是以01,x x 为节点的1次拉格朗日插值公式，实际上是过点()()00,x f x 和
()()1
1
,x f x 的直线，采用点斜式：
()()()()()100,10010
f x f x I x f x x x x x -=+
--
()02I x 是以02,x x 为节点的1次拉格朗日插值公式，同理有：
()()()()()200,20020
f x f x I x f x x x x x -=+
--
令：
()()()()
()0,20,10,1,20,1121
I x I x I x I x x x x x -=+
--
容易证明：
()()()()
()()()
0,200,100,1,200,10010,10021
I x I x I x I x x x I x f x x x -=+
-==-
()()()()
()()()
0,210,110,1,210,11110,11121
I x I x I x I x x x I x f x x x -=+-==-
()()()()
()()()
0,220,120,1,220,12210,22221
I x I x I x I x x x I x f x x x -=+
-==-
由插值公式的唯一性可知，()012I x 是以012,,x x x 为节点的2次拉格朗日插值多项式。
发现：两个一次多项式可以通过线性插值得到二次插值多项式。 依此类推：
()()()()
()0,1,,2,0,1,,10,1,2,,0,1,,111
k k k k k k k k I x I x I x I x x x x x ------=+
-- 点斜式
是以01,,,k x x x 为节点的k 次拉格朗日插值多项式。 注：过点()()10,1,,1,k k x I x -- 和()()0,1,,2,,k k k x I x - 的直线。 实际上：
()()10,1,2,,0,1,,10,1,,2,11
k k k k k k k k
k k x x x x I x I I x x x x x -------=
+
--
两点式
是对两个低次插值的线性插值，这种通过低次插值再作线性插值生成高次插值的方法称为逐次线性插值。 Aitken 法
利用公式：()()()()
()0,1,,2,0,1,,10,1,2,,0,1,,111
k k k k k k k k I x I x I x I x x x x x ------=+-- 递推
表2.1 Neville 法
验证 ()()()()
()1,20,10,1,20,1020
I x I x I x I x x x x x -=+
--
利用公式：()()()()
()1,2,,0,1,,10,1,2,,0,1,,100
k k k k k I x I x I x I x x x x x ---=+-- 递推
表2.2
每增加一个计算节点就计算一行，如果精度不满足要求，再增加一个节点，前面的计算完全有效！
问题：如何判断精度是否满足要求？增加多少个节点能够停止计算？ 误差估计
由插值多项式存在的唯一性，仍有（P18 定理2.2）
()()
()
()
()111!n n n f
R x x n ξω++=
+，(),a b ξ∈ 这里可采用一种更简便的方法。当(
)
()1n f x +在插值区间变化不大时，设
()
()1n f
x L +≈，则有：
()()()()0,1,,101!
k k L f x I x x x x x k ---≈-- ()()()()()0,1,,2,02!
k k k k L f
x I x x x x x x x k ---≈
---
两式相除:
()()()()
0,1,,110,1,,2,k k k k k
f x I x x x f x I x x x -----≈--
可转化为：
()()()()()10,1,,10,1,,2,0,1,,11
k k k k
k k k x x f x I x I
x I x x x -------≈
--
因此：如果 ()()0,1,,2,0,1,,1k k k I x I x ε---< 则可以认为：
()()0,1,,1k f x I x -≈ 满足精度要求。
P21 例2.2
注意：满足精度要求时，算法停止
2.4 差商(divided difference ,亦称均差)与牛顿插值公式
2.4.1 差商及其性质
Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数()i l x 都需重新算过。公式不具有继承性，不利于编程。
可以将()n L x 改写成下面的形式：
()()()()()01020101()n n n L x a a x x a x x x x a x x x x -=+-+--++--
希望每增加一个节点时，只附加一项上去即可。
01,,,n
a a a 为待定系数。
P22：关于01,,,n a a a 的递推公式，用解方程的方法计算复杂！ 如何计算01,,,n a a a 的值？我们先引入差商的概念 差商(亦称均差) /* divided difference */
[]()()000
,k k k f x f x f x x x x -=
-为函数()f x 关于0,k x x 的一阶差商。
一阶差商的几何意义：弦截线的斜率
[][][]
001011
,,,,k k k f x x f x x f x x x x x -=
-为函数()f x 关于01,,k x x x 的二阶差商。
一般地，称：
[][][]
012011011
,,,,,,,,,,k k k k k k f x x x x f x x x f x x x x x ----=
- 为函数()f x 关于
01,,,k x x x （k +1
个点）的k 阶差商。
差商的基本性质
? 性质1：差商的对称性
事实上： []()
()010
1
,,,k
i k i k i
f x f x x x x ω=+=
'∑
其中： ()()10
k
k i i x x x ω+==-∏ ()()10
k
k i i
j j j i
x x x ω+=≠'=-∏ 这个结论可以用数学归纳法证明，这个性质说明差商的值与节点的排列顺序无关，称为差商的对称性。即：
[][][]01102120,,,,,,,,,,,k k k f x x x f x x x x f x x x x ===
? 性质2：差商的另一种定义
由性质1和差商的定义可知（将0x 和1k x -互换位置）
[][][]
1011010
,,,,,,,,k k k k f x x f x x x f x x x x x --=
-
? 性质3：差商与导数的关系
()f x 在[],a b 上存在n 阶导数，且节点[]01,,,,n x x x a b ∈ ，则n 阶差商与
导数关系如下：
[]()
()
[]01,,,,
,!
n n f
f x x x a b n ξξ=
∈
这个公式可以直接用罗尔定理证明。类似2.2.4 插值余项，定理2.2，P18。 ? 性质4：线性 ( P43 习题15 ) 若： ()()()12f x af x bf x =+
那么： [][][]01020,,,,,,k k k f x x af x x bf x x =+ 提示：用数学归纳法证明 ? 性质4：
把x 看成[],a b 上的一个点，若()f x 是x 的n 次多项式，则一阶差商[]0,f x x 是x 的n －1次多项式；二阶差商[]01,,f x x x 是x 的n －2次多项式； 一般地：
n 次多项式()f x 的k 阶差商[]
011,,,,k f x x x x - 是x 的n －k 次多项式（k n ≤），当k >n 时，k 阶差商为零。 由性质3可以证明。 差商的计算
P23 表2.4 2.4.2 牛顿插值公式
把x 看成[],a b 上的一个点，可得：
()()[]()000,f x f x f x x x x =+-
[][][]()001011,,,,f x x f x x f x x x x x =+- ——由差商的定义式反推得到
[][][]()0110101,,,,,,,,,,,n n n n f x x x x f x x x f x x x x x x -=+-
把后一式代入前一式，就可以得到：
()()[]()[]()()[]()()[]()()()
001001201010101,,,,,,,,,n n n n n n f x f x f x x x x f x x x x x x x f x x x x x x x f x x x x N x R x ω-+=+-+--++--+=+
其中：
()()[]()[]()()[]()()
0010012010101,,,,,,n n n N x f x f x x x x f x x x x x x x f x x x x x x x -=+-+--++--
满足插值条件，称为牛顿插值多项式。
对比2.4.1中()n L x 的形式：
()()()()()01020101()n n n L x a a x x a x x x x a x x x x -=+-+--++--
各项的系数 []()01,,,0,1,,k k a f x x x k n ==
P24 例2.3
注意：四阶差商近似常数，由性质4（n 次多项式()f x 的k 阶差商
[]01
1,,,,k f
x x x x - 是x 的n －k 次多项式），常数可以认为是0次多项式，此时n =k ，说明()f x 可以用4次多项式近似逼近，误差较小！
2.5 差分与等距节点插值公式
实际应用中，经常遇到等距离节点的情形（等间距采样），这时插值公式可以进一步简化，计算也简单得多。此时要研究等距节点的插值公式，首先从差分说起……
2.5.1差分及其性质 差分的定义
已知：节点等距分布 ()00,1,,k x x kh k n =+= ，()k k f f x =，这里h 为常数，称为步长。
称：
1k k k
f f f +?=-
1k k k f f f -?=-
(
)()112
2
2
2
k k k
k k h
h
f f x f x
f f δ+-=+--=
-
分别为()f x 在k x 处以h 为步长的向前差分（forward difference ），向后差分（backward difference ）和中心差分（centered difference ）。符号,,δ??分别称为向前差分算子，向后差分算子和中心差分算子。
二阶差分定义为：
2
1212k k k k k k
f f f f f f +++?=?-?=-+
一般地，m 阶差分定义为：
1
1
1m
m m k k k
f f f --+?=?
-?
1
1
1m m m k k k f f f ---?=?
-?
1
1
1
1
2
2
m
m m k k k f δ
δ
δ
--+-=-
注意：11112
2
m m m k k k f δδδ--+-=-不是由1m k f δ-和11m k f δ--递归得到！
因为求一阶中心差分k f δ用到的12
k f +和12
k f -不是函数表上的值，如果用
函数表上的值则一阶中心差分可写成：
112
k k k f f f δ++=-，112
k k k f f f δ--=-；
因此，二阶中心差分2112
2
k k k f δδδ+-=-。
不变算子I ： I k k f f = 移位算子E ： 1E k k f f +=
注：E I ?=-；1I E -?=-；1/21/2E E δ-=-
差分的性质
? 性质1：各阶差分均可用函数值表示
()()
()0
0E I 1E
1n
n
n
j
j n
n j
k k k n k j j j n n f f f f j j -+-==?????=-=
-=- ? ???
??∑
∑
()
()
()
1
I E
1E 1n
n
n
n j
n j
n
j n
k k k k j n j j n n f f f f j j ----+-==????
?=-=
-=
- ? ???
??
∑∑ 其中：()()
11!
n n n n j j j --+??
=
???
，即 j n C
? 性质2：可用各阶差分表示函数值，如：
()
0E
I n
n
n
j
n k k k k
j n f f f f j +=??==+?=? ???
∑
? 性质3：差商与差分的关系
[]111,k k k k k k k
f f f f x x x x h
+++-?=
=-
[][][]
2
121122
2,,1,,2k k k k k k k k
k k
f x x f x x f x x x f x x h
++++++-=
=
?-
依此类推：
[]()11,,,1,2,,!m
k k k m k
m
f x x x f m n m h
++=
?=
同理可证，对于向后差分
[]()11,,,1,2,,!m
k k k m k
m
f x x x f m n m h
--=
?=
? 性质4：线性
()()()a f x b g x a f b g ?+=?+?
? 性质5：差分与导数的关系
()
()
[]()()11,,,,,1,2,,!
!m m
k k k m k
k
k m m
f
f x x x f x
x m n m m h
ξξ+++==
?∈=
因此： ()()m m m k f h f ξ?=
差分的计算
差分计算可通过构造差分表得到 P26，表2.6 2.5.2 等距节点插值公式
将牛顿插值公式中的各阶差商用相应的差分代替，就可以得到各种形式的等距节点插值公式。 牛顿前插公式
()()()n n f x N x R x =+
等距节点：()0,0,1,2,,k x x k h k n =+=
要计算0x 附件点x 的函数()f x 的值，令()0,01x x t h t =+≤≤， 则：()()()00k x x x t h x k h t k h -=+-+=- 于是：()()()()1101k
k k j j x x x t t t k h ω++==-=--∏
()()
()[]()[]()()()()()
0001001012
0000
,,,,1112!
!
n n n n n
N x N x t h f x f x x x x f x x x x x x x t t t t t n f t f f f n -=+=+-++-----+=+?+
?++
? ()()
()
()()
()()
()()
()()()
1111
01!1,,1!
n n n n n n f
R x x n t t t n h
f
x x n ξωξξ++++=
+--=
∈+
牛顿后插公式
节点倒序排列：(),0,1,2,,k n x x k h k n =-=
要计算n x 附件点x 的函数()f x 的值，令(),10n x x t h t =+-≤≤ 则：()()()k n n x x x t h x k h t k h -=+--=+ 于是：()()()()1101k
k k j j x x x t t t k h ω++==-=++∏
()()
()[]()[]()()()()()
11012
,,,,1112!
!
n n n n n n n n n n n
n n n N x N x t h f x f x x x x f x x x x x x x t t t t t n f t f f f n --=+=+-++--+++-=+?+
?++
? ()()
()
()()
()()
()()
()()()
1111
01!
1,,1!
n n n n n n f
R x x n t t t n h
f
x x n ηωηη++++=
+++=
∈+
注：一般当 x 靠近0x 时用前插，靠近n x 时用后插，故两种公式亦称为表初公式和表末公式。 P27 例2.4
注：若()f x 是n 次多项式，则()(),0m f x m n ?≤≤是n －m 次多项式。当n>m 时，()0m f x ?=。
2.6 Hermite （埃尔米特）插值
Hermite 插值多项式
拉格朗日插值多项式和牛顿插值多项式与被逼近函数在插值点上有相同的函数值，但是插值多项式与被逼近函数()y f x =一般不相切（导数不同）——光滑性差！
Hermite 插值多项式：求与()y f x =在插值点01,,,n x x x 上具有相同的函数值
和导数值（甚至高阶导数值）的插值多项式。 Hermite 插值多项式的构造
问题：设节点01n a x x x b ≤<<<≤ ，()j j y f x =，()j j m f x '=()0,1,,j n = ，要求插值多项式()H x ，满足条件：
()j j H x y =，()j j
H x m '= ()0,1,,j n =
求解：构造基函数()j x α和()j x β满足：
()
1,
0,
j k jk
j k x j k
α
δ=?=?≠?， ()0j k x α'=
()0j k x β=，()j k jk x βδ'=. (),0,1,2,,j k n =
则Hermite 插值多项式()()21n H x H x +=可以写成：
()()()210
n
n j
j
j
j j H x y x m
x αβ+=??=
+??∑
如何构造()j
x α
和()j x β？（P29详细步骤）
利用Lagrange 插值基函数()j l x ，令：
()()()2
j j x ax b l x α=+ ——2n+1阶多项式
()j x α需要满足：
()()()2
1j j j j j x ax b l x α=+=
()()()()()20j j j j j j j j j x l x al x ax b l x α??''=++=?
?
将()1j j l x =带入，于是有：
()1 20 j
j j ax b a l x +=???
'+=??
解得：()2j j a l x '=-，()12j j j b x l x '=+ 由于：
()()()()()
()()()()
011011j j n j j j
j j j j j n x x x x x x x x l x x
x x x x x x x -+-+----=
----
两端取对数，再求导得：（分母部分转化为常数项，求导后为0）
()01n
j j k j k
k j
l x x x =≠'=
-∑
于是得出如下结论：
()()()
20,1
12n j j j k k j j k x x x l x x x α=≠??=--??-????
∑
同理可得：
()()()2j j j
x x x l
x β=-
插值余项
仿照拉格朗日插值余项的证明方法可得
()()()()
()()()222
21121!
n n n f
R x f x H x x n ξω+++=-=
+
P30 例 2.5
牛顿插值法 插值法是利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。如果这特定函数是多项式，就称它为插值多项式。当插值节点增减时全部插值基函数均要随之变化，这在实际计算中很不方便。为了克服这一缺点，提出了牛顿插值。牛顿插值通过求各阶差商，递推得到的一个公式： f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0 )...(x-xn-1)+Rn(x)。 插值函数 插值函数的概念及相关性质[1] 定义：设连续函数y-f(x) 在区间[a,b]上有定义，已知在n+1个互异的点 x0,x1,…xn上取值分别为y0,y1,…yn （设a≤ x1≤x2……≤xn≤b)。若在函数类中存在以简单函数P(x) ，使得P(xi)=yi,则称P(x) 为f(x)的插值函数. 称x1,x2,…xn 为插值节点，称[a,b]为插值区间。 定理：n次代数插值问题的解存在且唯一。
牛顿插值法C程序 程序框图#include . 牛顿插值法一、实验目的：学会牛顿插值法，并应用算法于实际问题。 x?x)f(二、实验内容：给定函数，已知： 4832401.2)?.?1449138f(2.f.f(20)?1.414214(2.1) 549193.)?1f(2.4516575(f2.3)?1. 三、实验要求：以此作为函数2.15插值多项式在处的值，用牛顿插值法求4 次Newton（ 1）2.15?N(2.15)。在MATLAB中用内部函数ezplot绘制出的近似值4次Newton插值多项式的函数图形。 （2）在MATLAB中用内部函数ezplot可直接绘制出以上函数的图形，并与作出的4次Newton插值多项式的图形进行比较。 四、实验过程： 1、编写主函数。打开Editor编辑器，输入Newton插值法主程序语句： function [y,L]=newdscg(X,Y,x) n=length(X); z=x; A=zeros(n,n);A(:,1)=Y';s=0.0; p=1.0; for j=2:n for i=j:n A(i,j)=(A(i,j-1)- A(i-1,j-1))/(X(i)-X(i-j+1)); end end C=A(n,n); for k=(n-1):-1:1 C=conv(C,poly(X(k))); d=length(C);C(d)=C(d)+A(k,k); end y(k)= polyval(C, z); L(k,:)=poly2sym(C); 0 / 3 . %%%%%%%%%%%%%%%%%% t=[2,2.1,2.2,2.3,2.4]; fx=sqrt(t); wucha=fx-Y; 以文件名newdscg.m保存。 2、运行程序。 （1）在MATLAB命令窗口输入： >> X=[2,2.1,2.2,2.3,2.4]; Y =[1.414214,1.449138,1.483240,1.516575,1.549193]; x=2.15;[y,P]=newdscg(X,Y,x) 回车得到： 第5章信号的抽取与插值 5.1前言 至今，我们讨论的信号处理的各种理论、算法及实现这些算法的系统都是把抽样频率f视为恒定值，即在一个数字系统中只有一个抽样率。但是，在实际工作中，我们经常会s 遇到抽样率转换的问题。一方面，要求一个数字系统能工作在“多抽样率（multirate）”状态，以适应不同抽样信号的需要；另一方面，对一个数字信号，要视对其处理的需要及其自身的特征，能在一个系统中以不同的抽样频率出现。例如： 1. 一个数字传输系统，即可传输一般的语音信号，也可传输播视频信号，这些信号的频率成份相差甚远，因此，相应的抽样频率也相差甚远。因此，该系统应具有传输多种抽样率信号的能力，并自动地完成抽样率的转换； 2. 如在音频世界，就存在着多种抽样频率。得到立体声声音信号（Studio work）所用的抽样频率是48kHz，CD产品用的抽样率是44.1kHz，而数字音频广播用的是32kHz[15]。 3. 当需要将数字信号在两个具有独立时钟的数字系统之间传递时，则要求该数字信号的抽样率要能根据时钟的不同而转换； 4.对信号（如语音，图象）作谱分析或编码时，可用具有不同频带的低通、带通及高通滤波器对该信号作“子带”分解，对分解后的信号再作抽样率转换及特征提取，以实现最大限度减少数据量，也即数据压缩的目的； 5. 对一个信号抽样时，若抽样率过高，必然会造成数据的冗余，这时，希望能在该数字信号的基础上将抽样率减下来。 以上几个方面都是希望能对抽样率进行转换，或要求数字系统能工作在多抽样率状态。近20年来，建立在抽样率转换理论及其系统实现基础上的“多抽样率数字信号处理”已成为现代信号处理的重要内容。“多抽样率数字信号处理”的核心内容是信号抽样率的转换及滤波器组。 减少抽样率以去掉过多数据的过程称为信号的“抽取（decimatim）”，增加抽样率以增加数据的过程称为信号的“插值（interpolation）。抽取、插值及其二者相结合的使用便可实现信号抽样率的转换。 滤波器组，因名思义，它是一组滤波器，它用以实现对信号频率分量的分解，然后根 124 #include 第二章 插值法 1．当1,1,2x =-时，()0,3,4f x =-,求()f x 的二次插值多项式。 解： 0120121200102021101201220211,1,2, ()0,()3,()4;()()1 ()(1)(2)()()2()()1 ()(1)(2) ()()6 ()()1 ()(1)(1) ()()3 x x x f x f x f x x x x x l x x x x x x x x x x x l x x x x x x x x x x x l x x x x x x x ==-===-=--==-+-----==------= =-+-- 则二次拉格朗日插值多项式为 2 20 ()()k k k L x y l x ==∑ 0223()4() 14 (1)(2)(1)(1)23 537623 l x l x x x x x x x =-+=---+ -+= +- 2．给出()ln f x x =的数值表 用线性插值及二次插值计算的近似值。 解：由表格知， 01234012340.4,0.5,0.6,0.7,0.8;()0.916291,()0.693147()0.510826,()0.356675()0.223144 x x x x x f x f x f x f x f x ======-=-=-=-=- 若采用线性插值法计算ln 0.54即(0.54)f ， 则0.50.540.6<< 2 112 1 221 11122()10(0.6)()10(0.5)()()()()() x x l x x x x x x l x x x x L x f x l x f x l x -==----= =---=+ 6.9314 7(0.6) 5.10826( x x =--- 1(0.54)0.62021860.620219L ∴=-≈- 若采用二次插值法计算ln 0.54时， 1200102021101201220212001122()() ()50(0.5)(0.6) ()() ()() ()100(0.4)(0.6) ()()()() ()50(0.4)(0.5) ()() ()()()()()()() x x x x l x x x x x x x x x x x l x x x x x x x x x x x l x x x x x x x L x f x l x f x l x f x l x --==------==-------= =----=++ 500.916291(0.5)(0.6)69.3147(0.4)(0.6)0.51082650(0.4)(0.5 x x x x x x =-?--+---?--2(0.54)0.61531984 0. 615320L ∴=-≈- 3．给全cos ,090x x ≤≤ 的函数表，步长1(1/60),h '== 若函数表具有5位有效数字，研究用线性插值求cos x 近似值时的总误差界。 解：求解cos x 近似值时，误差可以分为两个部分，一方面，x 是近似值，具有5位有效数字，在此后的计算过程中产生一定的误差传播；另一方面，利用插值法求函数cos x 的近似值时，采用的线性插值法插值余项不为0，也会有一定的误差。因此，总误差界的计算应综合以上两方面的因素。 当090x ≤≤ 时， 令()cos f x x = 取0110,( )606018010800 x h ππ===?= 令0,0,1,...,5400i x x ih i =+= 则5400902 x π = = 当[]1,k k x x x -∈时，线性插值多项式为 (){} 2 1 ()(11),5,10,20: 1252 1()1,(0,1,2,,)()2,(0,1,2,,)() ()2 35,20:1100 (i i i i n n k k k Newton f x x n x f x x i i n f x n x y i n Newton N x S x n x k y f x = -≤≤=+=-+====-+ = 题目：插值多项式和三次样条插值多项式。已知对作、计算函数在点处的值；、求插值数据点 的插值多项式和三次样条插值多项式；、对计算和相应的函数值),()() (1,2,,99)4:()max ()()max ()n k n k n k n k n k n k k k N x S x k E N y N x E S y S x ==-=- 和； 、计算，； 解释你所得到的结果。 算法组织: 本题在算法上需要解决的问题主要是：求出第二问中的Newton 插值多项式 )(x N n 和三次样条插值多项式()n S x 。如此，则第三、四问则迎刃而解。计算两 种插值多项式的算法如下： 一、求Newton 插值多项式)(x N n ，算法组织如下： Newton 插值多项式的表达式如下： )())(()()(110010--???--+???+-+=n n n x x x x x x c x x c c x N 其中每一项的系数c i 的表达式如下： 1102110) ,,,(),,,(),,,(x x x x x f x x x f x x x f c i i i i i -???-???= ???=- 根据i c 以上公式，计算的步骤如下： ?? ??? ?? ?????+??????? ???????????----) ,,,,(1) ,,,(),,,,(),(,),,(2)(,),(),(11101111011010n n n n n n n n x x x x f n x x x f x x x f n x x f x x f x f x f x f 、计算、计算、计算、计算 二、求三次样条插值多项式)(x S n ，算法组织如下： 第二章插值法 2.在区间[-1,1]上分别取n=10,20用两组等距节点对龙哥函数f(x)=1/(1+25*x^2)做多项式插值及三次样条插值，对每个n值，分别画出插值函数及f（x）的图形。 （1）多项式插值 ①先建立一个多项式插值的M-file； 输入如下的命令（如牛顿插值公式）： function [C,D]=newpoly(X,Y) n=length(X); D=zeros(n,n) D(:,1)=Y' for j=2:n for k=j:n D(k,j)=(D(k,j-1)- D(k-1,j-1))/(X(k)-X(k-j+1)); end end C=D(n,n); for k=(n-1):-1:1 C=conv(C,poly(X(k))) m=length(C); C(m)= C(m)+D(k,k); end ②当n=10时，我们在命令窗口中输入以下的命令： clear,clf,hold on; X=-1:0.2:1; Y=1./(1+25*X.^2); [C,D]=newpoly(X,Y); x=-1:0.01:1; y=polyval(C,x); plot(x,y,X,Y,'.'); grid on; xp=-1:0.2:1; z=1./(1+25*xp.^2); plot(xp,z,'r') 得到插值函数和f（x）图形： ③当n=20时，我们在命令窗口中输入以下的命令：clear,clf,hold on; X=-1:0.1:1; Y=1./(1+25*X.^2); [C,D]=newpoly(X,Y); x=-1:0.01:1; y=polyval(C,x); plot(x,y,X,Y,'.'); grid on; xp=-1:0.1:1; z=1./(1+25*xp.^2); plot(xp,z,'r') 得到插值函数和f（x）图形： 第六章习题解答 2、利用梯形公式和Simpson 公式求积分2 1 ln xdx ? 的近似值，并估计两种方法计算值的最大 误差限。 解：①由梯形公式： 21ln 2 ()[()()][ln1ln 2]0.3466222 b a T f f a f b --= +=+=≈ 最大误差限 3''2 ()111 ()()0.0833******** T b a R f f ηη-=-=≤=≈ 其中，(1,2)η∈ ②由梯形公式： 13()[()4()()][ln14ln()ln 2]0.38586262 b a b a S f f a f f b -+= ++=++≈ 最大误差限 5(4)4()66 ()()0.0021288028802880 S b a R f f ηη-=-=≤≈， 其中，(1,2)η∈。 4、推导中点求积公式 3''()()()()() ()224 b a a b b a f x dx b a f f a b ξξ+-=-+< 第二章 插值法与数值微分 1. 设y = 在100,121,144x =三处的值是很容易求得的, 试以这三个点建立y = 的 二次插值多项式, 并用此多项式计算,且给出误差估计.用其中的任意两点,构造线性插值函数,用得到的三个线性插值函数, 计算,并分析其结果不同的原因. 解: 已知012012100,121,144;10,11,12x x x y y y ======, 建立二次Lagrange 插值函数可得: ()()()()()()() ()()()() ()() 21211441001441011 100121100144121100121144121100 12 144121144100x x x x L x x x ----= +------+ -- ()211510.7228L ≈=. 误差()() ()()()()2012012,,,,3! f R x x x x x x x x x x ξξξ'''= ---∈,所以 2 0.00065550.001631R << 利用前两个节点建立线性插值函数可得: ()()() ()() 11211001011100121121100x x L x --= + -- ()111510.7143L ≈=. 利用后两个节点建立线性插值可得: ()()() ()() 11441211112121144144121x x L x --= + -- ()111510.7391L ≈=. 利用前后两个节点建立线性插值可得: ()()() ()() 21441001012100144144100x x L x --= + -- ()111510.6818L ≈=. 与,二次插值比线性插值效果好,利用前两个节点的线性插值比其他两个线性插值 《数值分析》课程实验一：插值与拟合 一、实验目的 1. 理解插值的基本原理，掌握多项式插值的概念、存在唯一性； 2. 编写MATLAB 程序实现Lagrange 插值和Newton 插值，验证Runge 现象； 3. 通过比较不同次数的多项式拟合效果，理解多项式拟合的基本原理； 4. 编写MATLAB 程序实现最小二乘多项式曲线拟合。 二、实验内容 1. 用Lagrange 插值和Newton 插值找经过点(-3, -1), (0, 2), (3, -2), (6, 10)的三次插值公式，并编写MATLAB 程序绘制出三次插值公式的图形。 2. 设 ]5,5[,11 )(2 -∈+= x x x f 如果用等距节点x i = -5 + 10i /n (i = 0, 1, 2, …, n )上的Lagrange 插值多项式L n (x )去逼近它。不妨取n = 5和n = 10，编写MATLAB 程序绘制出L 5(x )和L 10(x )的图像。 3. 在某冶炼过程中，根据统计数据的含碳量与时间关系如下表，试求含碳量与时间t 的拟合曲线。 (1) 用最小二乘法进行曲线拟合； (2) 编写MATLAB 程序绘制出曲线拟合图。 三、实验步骤 1. (1) Lagrange 插值法：在线性空间P n 中找到满足条件： ?? ?≠===j i j i x l ij j i , 0,, 1)(δ 的一组基函数{}n i i x l 0)(=，l i (x )的表达式为 ∏ ≠==--= n i j j j i j i n i x x x x x l ,0),,1,0()( 有了基函数{}n i i x l 0)(=，n 次插值多项式就可表示为 ∑==n i i i n x l y x L 0)()( (2) Newton 插值法：设x 0, x 1, …, x n 是一组互异的节点，y i = f (x i ) (i = 0, 1, 2, …, n )，f (x )在处的n 阶差商定义为 1102110] ,,,[],,,[],,,[x x x x x f x x x f x x x f n n n n --= - 则n 次多项式 ) ())(](,,[) )(](,,[)](,[)()(11010102100100----++--+-+=n n n x x x x x x x x x f x x x x x x x f x x x x f x f x N 差商表的构造过程： 题目一:多项式插值 某气象观测站在8:00(AM)开始每隔10分钟对天气作如下观测,用三次多项式插值函数(Newton)逼近如下曲线,插值节点数据如上表,并求出9点30分该地区的温度(x=10)。 二、数学原理 假设有n+1个不同的节点及函数在节点上的值(x 0,y 0),……(x n ,y n ),插值多项式有如下形式: ）（） ）（（）（）（）（n 10n 102010n x -x )(x -x x -x x P x x x x x x -??-+??+-++=αααα (1) 其中系数i α(i=0,1,2……n)为特定系数,可由插值样条i i n y x P =） （(i=0,1,2……n)确定。 根据均差的定义,把x 瞧成[a,b]上的一点,可得 f(x)= f(0x )+f[10x x ，](0x -x ) f[x, 0x ]= f[10x x ，]+f[x,10x x ，] (1x -x ) …… f[x, 0x ,…x 1-n ]= f[x, 0x ,…x n ]+ f[x, 0x ,…x n ](x-x n ) 综合以上式子,把后一式代入前一式,可得到: f(x)= f[0x ]+f[10x x ，](0x -x )+ f[210x x x ，，](0x -x )(1x -x )+ …+ f[x, 0x ,…x n ](0x -x )…(x-x 1-n )+ f[x, 0x ,…x n ,x ]） （x 1n +ω= N n (x)+） （x n R 其中 N n (x)= f[0x ]+f[10x x ，](0x -x )+ f[210x x x ，，](0x -x )(1x -x )+ …+ f[x, 0x ,…x n ](0x -x )…(x-x 1-n ) (2) 第二章插值法 一、内容分析与教学建议 本章内容统称为插值法，包括Lagrange插值、逐步线性插值、Newton 插值、Hermite 插值、分段多项式插值、有理函数插值等内容，既是教学的重点。 在教学上，注意由浅入深，由直观到抽象，多用实例和图形作解释，建立插值概念，注意讲解上述插值是如何根据实际问题要求的提高而先后发展起来的。培养学生分析问题和解决问题的能力。 （一）L agrange插值 1、回顾《高等数学》的Taylor公式，讲解Taylor公式是根据某一点的多个信息得到近似多项式的插值思想。 2、将上述思想应用到多点的信息，即根据所给的多点的数据，建立插值多项式。 3、讲解过程中，沿着“发现问题→提出解决方法→方法的存在性和惟一性→建立Lagrange插值公式→误差公式”这样一个思路去讲解Lagrange插值的思想和方法。 （二）逐步线性插值 1、讲解为什么要建立逐步线性插值？这是由于Lagrange插值没有承袭性，当需要增加一个插值节点时，以前所做的工作要全部重做。 2、逐步线性插值是一个将高次插值转化成逐步线性插值的迭代过程，正是这一点使得逐步线性插值具有了承袭性。 3、强调逐步线性插值是求一点处近似值的快速方法，不太适合建立插值解析式。 （三）N ewton插值 1、Newton 插值克服了上述两类插值的缺点，继承了它们的优点：即具有承袭性，又是一个完整的解吸式，便于理论研究和分析。 2、首先掌握差分和差商的概念以及它们的性质，在此基础上建立Newton 插值公式和误差公式。 3、Newton 插值公式实际上是Lagrange插值公式的另外一种表现形式，这揭示了一种 习题6.1 1. 求三个一次多项式)(x g 、)(x h 和)(x f 的积)()()(x h x g x f ??.它们的零点分别为0.2,0.5,1.3. 2. 求多项式9425)(25-+-=x x x x g 被 736)(2+-=x x x f 相除后的结果. 习题6.2 1. 已知函数)(x f 在]7,1[上具有二阶连续导数， 5)("≤x f ，且满足条件12)7(,1)1(==f f .求线性插值多项式和函数值)5.3(f ，并估计其误差. 2. 求函数=)(x f e x 3-在]4,0[上线性插值多项式，并估计其误差. 3. 求将区间 [π/6, π/2] 分成n 等分)2,1(=n ，用x x f y sin )(==产生1+n 个节 点，然后根据（6.9）和（6.13）式分别作线性插值函数)(1x P 和抛物线插值函数)(2x P .用它们分别计算sin (π/5) (取四位有效数字)，并估计其误差. 4.给出节点数据00.27)00.3(=-f ，00.1)00.0(=f ，00.2)00.1(=f ，00.17)00.2(=f ，作三次拉格朗日插值多项式计算)4.1(f ，并估计其误差. 5. 给出节点数据03.37)15.3(=-f ，24.7)00.1(=-f ，05.1)01.0(=f ，03.2)02.1(=f ， 0 6.17)03.2(=f ，05.23)25.3(=f 作五次拉格朗日插值多项式和基函数，并写出估计其误差的公式. 6. 已知5.030sin =ο，7071.045sin =ο，190sin =ο，求ο40sin 的近似值，并估计 其误差. 习题6.3 1. 已知函数)(x f 在]7,1[上具有二阶连续导数， 5)("≤x f ，且满足条件12)7(,1)1(==f f .求一阶牛顿插值多项式和函数值)5.3(f ，并估计其误差. 2. 求函数=)(x f e x 3-在]4,0[上六阶牛顿插值多项式和估计误差的公式. 3. 将区间 [π/6, π/2] 分成n 等分)2,1(=n ，用x x f y sin )(==产生1+n 个节点，求二阶和三阶牛顿插值多项式)(2x P 和)(3x P .用它们分别计算sin (π/7) (取四位有效数字)，并估计其误差. 4.给出节点数据00.27)00.3(=-f ，00.1)00.0(=f ，00.2)00.1(=f ，00.17)00.2(=f 作三阶牛顿插值多项式计算)4.1(f ，并估计其误差. 5. 给出节点数据03.37)15.3(=-f ，24.7)00.1(=-f ，05.1)01.0(=f ，03.2)02.1(=f ， 0 6.17)03.2(=f ，05.23)25.3(=f 作五阶牛顿插值多项式和差商，并写出估计其误差的公式. 6. 已知5.030sin =ο，7071.045sin =ο，190sin =ο，用牛顿插值法求ο40sin 的近 似值，并估计其误差. 习题6.4 1. 给定函数)(x f 在点4/,6/10π=π=x x 处的函数值5.0)(0=x f ， 1707.0)(1=x f 和导数值0866.0)(0'=x f ，1707.0)(1'=x f ，且1)()4(≤x f ，求函数 )(x f 在点10,x x 处的3阶埃尔米特插值多项式)(3x H 和误差公式. 2. 求函数=)(x f e x 3-在]4,0[上五阶埃尔米特插值多项式，并估计其误差. 3. 将区间 [π/6, π/2] 分成n 等分)2,1(=n ，用x x f y sin )(==产生1+n 个节点，然后根据（6.42）和（6.44）式分别作埃尔米特插值多项式及其误差公式.用它们分别计算sin (π/5) (取四位有效数字)，并估计其误差. 一、填空题： 1． 满足()a a f x x =，()b b f x x =，()c c f x x =的拉格朗日插值余项为 。 答：()() ()()()3! a b c f R x x x x x x x ξ'''= --- 2．已知函数()f x 的函数值()()()()()0,2,3,5,6f f f f f ，以及均差如下 ()()()()() 00,0,2 4,0,2,35,0,2,3,51,0,2,3,5,60 f f f f f ===== 那么由这些数据构造的牛顿插值多项式的最高次幂的系数是 答： 1 二、选择题 1. 通过点()()0011,,,x y x y 的拉格朗日插值基函数()()01,l x l x 满足（ ） A ．()00l x ＝0，()110l x = B ． ()00l x ＝0，()111l x = C ．()00l x ＝1，()110l x = D ． ()00l x ＝1，()111l x = 答：D 2．. 已知等距节点的插值型求积公式 ()()35 2 k k k f x dx A f x =≈∑?，那么3 k k A ==∑（ ） A ．1 B. 2 C. 3 D. 4 答：C 3．过点(x 0,y 0), (x 1,y 1)，…，(x 5,y 5)的插值多项式P(x)是( )次的多项式。 (A). 6 (B).5 (C).4 (D).3． 答：B 三、证明题 1. 设 f (x) = (x-1) (x-2) .证明对任意的x 有： f [1, 2, x)]= 1 证明:f [1, 2] = [f (1) – f (2)]/ (1 – 2) = [0 – 0]/ (-1) = 0, 对任意的x 有 F[2, x] = [f (2) – f (x)]/ (2 – x) = [0 – (x-1) (x-2)]/ (2 – x) = (x-1), 所以 f [1, 2, x] = [f (1, 2) - f (2, x)]/ (1 – x) = [0 - (x-1)]/ (1 – x) = 1 2.设 在 上具有二阶连续导数，且 ，求证： 牛顿插值法 摘要：值法利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。如果这特定函数是多项式，就称它为插值多项式。利用插值基函数很容易得到拉格朗日插值多项式，公式结构紧凑，在理论分析中甚为方便，但当插值节点增减时全部插值基函数均要随之变化，整个公式也将发生变化，这在实际计算中是很不方便的，为了克服这一缺点，提出了牛顿插值。 牛顿插值通过求各阶差商，递推得到的一个公式：f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x 0)...(x-xn-1)+Rn(x) 关键词：牛顿插值法流程图程序实现 一、插值法的由来 在许多实际问题及科学研究中，因素之间往往存在着函数关系，然而，这种关系经常很难有明显的解析表达，通常只是由观察与测试得到一些离散数值。有时，即使给出了解析表达式，却由于表达式过于复杂，不仅使用不便，而且不易于进行计算与理论分析。解决这类问题的方法有两种：一种是插值法,另一种是拟合法。插值法是一种古老的数学方法，它来自生产实践，早在一千多年前，我国科学家在研究历法上就应用了线性插值与二次插值，但它的基本理论却是在微积分产生之后才逐渐完善的，其应用也日益增多，特别是在计算机软件中，许多库函数，如等的计算实际上归结于它的逼近函数的计算。逼近函数一般为只含有算术运算的简单函数，如多项式、有理分式（即多项式的商）。在工程实际问题当中，我们也经常会碰到诸如此类的函数值计算问题。被计算的函数有时不容易直接计算，如表达式过于复杂或者只能通过某种手段获取该函数在某些点处的函数值信息或者导数值信息等。因此，我们希望能用一个“简单函数”逼近被计算函数，然后用该简单函数的函数值近似替代被计算函数的函数值。这种方法就叫插值逼近或者插值法。 逐次线性插值法优点是能够最有效地计算任何给定点的函数值，而不需要写出各步用到的插值多项式的表达式。但如果解决某个问题时需要插值多项式的表达式，那么，它的这个优点就成了它的缺点了。能不能根据插值条件构造一个插值多项式，它既有具体的表达式，又很容易用它计算任何点的函数值呢？牛顿插值法能作到这一点。 第二章 插值方法/* Interpolation */ 2.1 引言 函数逼近 问题的引出：现实应用中常用函数()y f x =表示某种内在规律的数量关系，但是情况往往是： 1）()y f x =在某个区间[a,b]存在，有时候是连续的，但是只能通过实验或观测得到一系列点i x 的函数值i y （得到函数表），而无法得到()f x 的表达式 2）函数表达式已知，但计算复杂（如()sin y x =，()lg y x =等）使用不方便，通常也使用函数表。如：三角函数表，对数表，平方根表，立方根表等。 问题：有时需要求不在函数表上的函数值怎么办？ 解决方法：根据所给的 ()y f x =的函数表，构造一个简单的函数() P x 近似替 代()f x （存在误差！），称为函数逼近。 称()P x 为逼近函数，()f x 为被逼近函数。 ()P x 通常选择一类比较简单的函数，如代数多项式或分段代数多项式。 函数逼近的方法有很多，例如Taylor 级数，Fourier 级数，有限元方法、边界元方法，小波分析等，大学科叫逼近论。 本课程讨论连续函数的逼近，主要介绍插值法。 插值 （interpolation ） 已知()[],,y f x x a b =∈的函数表 求：()P x 使 ()i i y P x = 0,1,2,,i n = —— 插值问题 称()P x 为()f x 的插值函数；()f x 为被插值函数；0 1 n x x x 为插值结点； [],a b 为插值区间；求插值函数()P x 的方法称为插值法。 当()P x 为多项式时，相应的插值法为多项式插值；()P x 为分段的多项式，称 为分段插值；()P x 为三角多项式，称为三角插值。 插值法的几何示意图，P14图2.1 多项式插值是数值分析的基本工具，常用来计算被插函数的近似函数值，零、极点，导数、积分（第四章 数值积分和数值微分），解微分方程（第五章）、积分方程等。 2.2 拉格朗日插值 2.2.1 插值多项式的存在唯一性 问题：用不同的多项式插值方法得到的插值多项式的形式有可能不同，它们是否等价？（可以转化为相同的标准式？） 答案是肯定的！ 两点确定一条直线（ 一次多项式 ） 三点确定一个抛物线（ 二次多项式 ） 是否n+1点确定一个n 次多项式？ 给定n +1个互异的插值点0 1 n x x x ，求符合插值条件() i i y P x =的次数不 超过n 的插值多项式 ()2 012n n P x a a x a x a x =++++ ——（标准式） 第五章 插值与最小二乘法 5.1 插值问题与插值多项式 实际问题中若给定函数是区间上的一个列表函数 ，如果,且f(x)在区间上是连续的，要求用一个简单的，便于计算的解析表达式在区间上近似f(x)，使 (5.1.1) 就称为的插值函数，点称为插值节点，包含插值节点的区间称为插值区间. 通常，其中是一组在上线性 无关的函数族，表示组成的函数空间表示为 (5.1.2) 这里是(n+1)个待定常数，它可根据条件(5.1.1)确定.当 时，表示次数不超过n次的多项式集合， ，此时 (5.1.3) 称为插值多项式，如果为三角函数，则为三角插值，同理还有 分段多项式插值，有理插值等等.由于计算机上只能使用+、-、×、÷运算，故常用的就是多项式、分段多项式或有理分式，本章着重讨论多项式插值及分段多项式插值，其他插值问题不讨论. 从几何上看，插值问题就是求过n+1个点的曲线，使它近似于已给函数，如图5-1所示. 插值法是一种古老的数学方法，它来自生产实践.早在一千多年前，我国科学家在研究历法时就应用了线性插值与二次插值，但它的基本理论却是在微积分产生以后才逐步完善的，其应用也日益广泛.特别是由于计算机的使用和航空、造船、精密机械加工等实际问题的需要，使插值法在理论上和实践上得到进一步发展.尤其是近几十年发展起来的样条(Spline)插值，获得了极为广泛的应用，并成为计算机图形学的基础. 本章主要讨论如何求插值多项式、分段插值函数、三次样条插值、插值多项式的存在唯一性及误差估计等.此外，还讨论列表函数的最小二乘曲线拟合问题与正交多项式. 讲解： 插值多项式就是根据给定n+1个点 ，求一个n次多项式： 使 即 这里是n+1个待定系数，根据n+1个条件得到的方程组是关于参数 的线性方程组。当节点互异时由于系数行列式 所以解是存在唯一的。但直接求解较复杂，也得不到统一的表达式。所以通常求插值多项式不用这种方法，而使用下节给出的基函数方法。 5.2 Lagrange插值 5.2.1 线性插值与二次插值 最简单的插值问题是已知两点及，通过此两点的插值多项式是一条直线，即两点式 简介：本程序用牛顿插值法对函数表， X值选取为1.5测试本程序。 源程序： #include } cout<<"请输入x的值：x="; cin>>xx; for(i=0;i 第五章光学模型及其算法实现 一、复习要求 1．简单光反射模型 2．增量式光反射模型 3．局部光反射模型 4．光源模型 5．简单光透射模型 6．光线跟踪显示技术 二、内容提要 1．简单光反射模型 （1）基本光学原理 ①照度定律 普通物理学中的照度定律(Lambert余弦定律)： π I=K f I L cosθ, θ∈ [0, 2 式中，反射常数K f与物体表面性质有关，也描述物体的颜色。 注意：按一般规定，入射光L是从表面上一点指向光源的矢量。 ②材质分配 事实上，一个物体的颜色就是它所反射出的光的颜色，取决于光源的颜色和该物体对光的反射性。例如，将一个阳光下的红球放到只有黄灯照明的室内，它就变成黑的了，因为那里没有任何红色光可被反射，而所有黄色光都被吸收了。 在使用光照时，原有的“绘图颜色”概念已不能适用，而采用“材质”一词。 定义：材质(material)被定义为一个物体对环境光、漫反射光、镜面反射光的反射性。它们分别以一个对应的RGB值表示，称为材质的Ambient,Diffuse,Specular分量（即光学定律中的反射系数K a, K d, K s）。 材质还可以包括另一种辐射性，用于描述自身发光的物体，例如汽车尾灯或夜光表。通 111 / 13 常，灯具的表面也被看成是一个自发光体。 ③ 折射和透射 Snell 正弦定律（或称折射定律）属于几何光学原理，用于确定两个物体间的入射角与折射角的关系： 1 2 21ηηθθ=sin sin 式中，θ1表示在物体1 表面处的入射角，而θ2表示在物体2内部的折射角；η1和η2分别是这两个物体的折射率。 如图5-1所示，除了从同侧光源射过来的反射光外，观察者还将会看到从另一侧光源穿过物体后射出的透射光： 图5-1 光的折射和透射 （2）简单光反射模型(Phong 模型)的导出 图5-2 光的反射 简单光反射模型只模拟物体表面对光的反射作用，并不考虑物体表面的透射和散射作用。在简单光反射模型中一个点光源照射到物体表面一点，再反射出来的光，可分为三部分：环境光（泛光）、漫反射光镜面反射光。 在Phong 模型中，物体表面的光照效果是环境反射光、光源的漫反射光和镜面反射光的 第五章插值 插值在科学计算和工程技术中有广泛应用。例如由实验得到一系列点x0, x1,…, x n对应的值y0, y i,…, y n，要构造函数y = f (x)，使y i=f(x i)，这就是简单的插值问题。插值核心问题是：存在性、唯一性、表示方法以及误差分析。插值和逼近有广泛应用，例如构造曲线曲面等。 5.1 代数插值 用代数多项式作为工具来研究插值的方法叫做代数插值。 插值 插值问题就是根据已知数据来构造函数y = f (x )的近似表达式。常用方法就是利用多项式P n (x )，使n i y x P i i n ,2,1,0,)( == ，作为f (x )的近似。多项式求值方便，且有导数。称P n (x )为f (x )的一个插值函数，称x 0, x 1,…, x n 为插值节点。用代数多项式作为工具来研究插值的方法叫做代数插值。设x 0 < x 1< …< x n ，记a = x 0, b = x n ，则[a, b]为插值区间。 设所要构造的插值多项式为：n n n x a x a x a a x P ++++= 2210)(，由插 值条件 n i y x P i i n ,,1,0,)( ==。得到如下线性代数方程组： n i y a x a x a i n n i i ,2,1,0,110==+++?。该线性方程组的系数行列式为 ∏ ≤ < ≤ - = = n i j j i n n n n n n x x x x x x x x x x x D 2 1 2 1 1 2 ) ( 1 1 1 ，为范得蒙行列式。当 j i x x≠，; ,2,1n i =n j ,2,1 =时，D ≠0，所以P n(x)由a0, a1,…, a n唯一确定。5.2 Lagrange插值 已知y = f (x)在给定点x0, x1上的值为y0，y1。线性插值就是构造一个一次多项式P1(x) = ax + b，使它满足条件P1 (x0) = y0，P1 (x1) = y1。几何解释就是一条直线。由解析几何，) ( ) ( 1 1 1 x x x x y y y x P- - - + =或 1 1 1 1 1 ) (y x x x x y x x x x x P - - + - - =。 例用线性插值求115（x* = 10.723805）。解：设x y=，取x0 = 100，x1 = 121，则y0= 10，y1= 11，从而 71428 . 10 ) 100 115 ( 100 121 10 11 10 ) 115 ( 115 1 = - - - + = ≈P。 用简单的曲线近似地代替复杂的曲线，最简单的曲线是二次曲线。设函数y=f (x) 在给定互异的自变量值x0, x1, x2上对应的函数值为y0, y1, y2，二次插值就是构造一个二次多项式2 2 1 2 ) (x a x a a x P+ + =，使之满足2,1,0 , ) ( 2 = =i y x P i i ，称抛物插值。令 2 2 1 1 2 ) ( ) ( ) ( ) (y x l y x l y x l x P+ + =，牛顿插值法试验报告
第五章 信号的抽取与插值
牛顿插值法C语言程序
计算方法简明教程插值法习题解析
matlab_牛顿插值法_三次样条插值法
数值分析 插值法
第六章习题答案数值分析
第二章插值法与数值微分
数值分析实验插值与拟合
MATLAB 牛顿插值法例题与程序
第二章 插值法
第六章 函数的插值方法
第二章插值法习题及解答
正文牛顿插值法
第二章 插值法
第五章 插值与最小二乘法
牛顿插值法的c++程序
第五章光学模型及其算法实现
计算方法讲义课件 五 插值
相关主题
文本预览