Download presentation
Presentation is loading. Please wait.
1
第2章 插 值 法 第1节 引言 第2节 拉格朗日插值 第3节 均差与牛顿插值多项式 第4节 埃尔米特插值 第5节 分段低次插值
第2章 插 值 法 第1节 引言 第2节 拉格朗日插值 第3节 均差与牛顿插值多项式 第4节 埃尔米特插值 第5节 分段低次插值 第6节 三次样条插值
2
2.1 引 言 2.1.1 插值问题的提出 设函数 在区间 上有定义,且已知在点 上的值 ,若存在一简 单函数 ,使 (1.1)
2.1 引 言 插值问题的提出 设函数 在区间 上有定义,且已知在点 上的值 ,若存在一简 单函数 ,使 (1.1) 成立,就称 为 的插值函数,点 称为插值节点,包含节点的区间 称为插值区间,求插值函数 的方法称为插值法.
3
若 是次数不超过 的代数多项式, 即 (1.2) 其中 为实数,就称 为插值多项式,相应的插值法称为多项式插值. 若 为分段的多项式,就称为分段插值. 若 为三角多项式 ,就称为三角插值. 本章只讨论多项式插值与分段插值.
4
从几何上看,插值法就是确定曲线 ,使其通过 给定的 个点 ,并用它近似已知曲线 .
从几何上看,插值法就是确定曲线 ,使其通过 给定的 个点 ,并用它近似已知曲线 . 见图. P(x) f(x) x0 x1 x2 x3 x4 x
5
2.1.2 多项式插值 设在区间 上给定 个点 上的函数值 ,求次数不超过 的多项式 ,使 (1.3)
多项式插值 设在区间 上给定 个点 上的函数值 ,求次数不超过 的多项式 ,使 (1.3) 由此可以得到关于系数 的 元线性方程组
6
(1.4) 此方程组的系数矩阵为 (1.5) 称为范德蒙德(Vandermonde)矩阵,由于 互异,故
7
因此线性方程组(1.4)的解 存在且唯一. 定理1 满足条件(1.3)的插值多项式 是存在唯一的.
8
2.2 拉格朗日插值 2.2.1 线性插值与抛物插值 对给定的插值点,可以用多种不同的方法求得形如(1.2)的插值多项式.
2.2 拉格朗日插值 线性插值与抛物插值 对给定的插值点,可以用多种不同的方法求得形如(1.2)的插值多项式. 先讨论 的简单情形. (1.2) 问题: 给定区间 及端点函数值 , 要求线性插值多项式 , 使它满足
9
其几何意义就是通过两点 的直线. 如图2-2. 图2-2
10
由 的几何意义可得到表达式 (点斜式), (两点式), (2.1) 由两点式看出, 是由两个线性函数 (2.2) 的线性组合得到,其系数分别为 及 ,即 (2.3)
11
显然, 及 也是线性插值多项式,在节点 及 上满足条件 称 及 为线性插值基函数, 图形见图2-3.
12
图2-3
13
下面讨论 的情形. 假定插值节点为 , , ,要求二次插值多项式 使它满足 几何上 是通过三点 的抛物线. 可以用基函数的方法求 的表达式,此时基函数 是二次函数,且在节点上满足条件 (2.4)
14
接下来讨论满足(2.4)的插值基函数的求法, 以求 为例, 由插值条件,它应有两个零点 及 , 可表示为 (2.4) 其中 为待定系数, 可由插值条件 定出 于是
15
同理 二次插值基函数 , , 在区间 上的 图形见图2-4.
16
图2-4
17
利用 , , , 立即得到二次插值多项式 (2.5) 显然, 它满足条件 将 , , 代入 (2.5) , 得
18
2.2.2 拉格朗日插值多项式 将前面的方法推广到一般情形,讨论如何构造通过 个节点 的 次插值多项式 . 根据插值的定义 应满足
拉格朗日插值多项式 将前面的方法推广到一般情形,讨论如何构造通过 个节点 的 次插值多项式 根据插值的定义 应满足 (2.6) 为构造 , 先定义 次插值基函数.
19
定义1 若 次多项式 在 个节点 上满足条件 (2.7) 就称这 个 次多项式 为节点 上的 次插值基函数.
20
与前面的推导类似, 次插值基函数为 (2.8) 显然它满足条件(2.7). 于是,满足条件(2.6)的插值多项式 可表示为 (2.7) (2.6) (2.9)
21
由 的定义,知 形如(2.9)的插值多项式 称为拉格朗日插值多项式, 而(2.3)与(2.5)是 和 的特殊情形. (2.9) 若引入记号 (2.3) (2.5) (2.10) 容易求得
22
于是公式(2.9)可改写成 (2.11) 注意: 次插值多项式 通常是次数为 的多项式, (2.9) 特殊情况下次数可能小于 . 例如通过三点 的二次插值多项式 ,如果三点共线,则 就是一条直线,而不是 抛物线,这时 是一次多项式.
23
2.2.3 插值余项与误差估计 (2.10) 若在 上用 近似 , 则其截断误差为 也称为插值多项式的余项.
插值余项与误差估计 若在 上用 近似 , 则其截断误差为 也称为插值多项式的余项. 定理2 设 在 上连续, 在 内 存在,节点 是满足条件(2.6) 的插值多项式,则对任何 ,插值余项 (2.6) (2.14) 这里 且依赖于 , 是(2.10)所定义的.
24
证明 由给定条件知 在节点 上为零,即 ,于是 (2.13) 其中 是与 有关的待定函数. 现把 看成 上的一个固定点,作函数 根据 的假设可知 在 上连续, 在 内存在.
25
根据插值条件及余项定义,可知 在点 及 处均为零,故 在 上有 个零点, 根据罗尔定理, 在 的两个零点间至少有一个零点, 故 在 内至少有 个零点. 对 再应用罗尔定理,可知 在 内至少有 个零点. 依此类推, 在 内至少有一个零点,记为 ,使
26
于是 且依赖于 将它代入(2.13), 就得到余项表达式(2.12). 余项表达式只有在 的高阶导数存在时才能应用. (2.13) 但 在 内的具体位置通常不可能给出, 如果可以求出 那么插值多项式 逼近 的截断误差限是 (2.14)
27
当 时,线性插值余项为 (2.15) 当 时,抛物插值余项为 (2.16)
28
利用余项表达式(2.12),当 时,由于 ,于是有 由此得 (2.17) 特别当 时,有 (2.18)
29
利用余项表达式(2.12)还可知,若被插函数 由于 ,故 ,即它的插值多项式
30
例1 证明 ,其中 是关于点 的插值基函数. 证明 利用公式(2.17)可得
31
例2 已知 的值并估计截断误差. 用线性插值及抛物插值计算 解 由题意, 取 (点斜式), 用线性插值计算,取 由公式(2.1)
33
由(2.15),其截断误差 其中 于是
34
用抛物插值计算,由公式(2.5)得 (2.5)
35
这个结果与6位有效数字的正弦函数表完全一样,
这说明查表时用二次插值精度已相当高了. 由(2.14), 截断误差限 其中 于是
37
例2 设 ,试证 其中 证明 通过两点 及 的线性插值为 于是
40
Matlab 实现 例 对正弦曲线上的数据点(0, 0), (pi/2, 1), (pi, 0), (3pi/2, -1)进行多项式插值
44
Polyval还可以计算多项式在向量上的值
47
也可以使用内部命令polyfit进行插值
48
一维插值函数interp1() y1=interp1(x,y,x1,方法) 其中x,y是插值数据,x1为用户指定的一组新的插值点的 横坐标,可以是标量、向量或矩阵。方法: 默认为‘linear’(线性插值,在两个样本点间简单的采 用直线拟合) ‘nearest’(最近点等值方式) ‘cubic’(三次Hermite插值,新版本改为‘pchip’) ‘spline’(三次分段样条插值,建议使用,端点处的信息系 统自动选取)
49
【例】已知的数据点来自函数 根据生成的数据进行插值处理,得出较平滑的曲线。 根据给出的函数可以直接生成数据,并绘图
55
2.3 均差与牛顿插值公式 2.3.1 插值多项式的逐次生成 利用插值基函数很容易得到拉格朗日插值多项式,公
2.3 均差与牛顿插值公式 插值多项式的逐次生成 利用插值基函数很容易得到拉格朗日插值多项式,公 式结构紧凑,在理论分析中甚为方便,但当插值节点增减 时全部插值基函数 均要随之变化,整个 公式也将发生变化,甚为不便.为了计算方便可重新设计一 种逐次生成插值多项式的方法.
56
当 时,记线性插值多项式为 ,插值条件为 由点斜式 将 看成是零次插值 的修正,即 其中 是函数 的差商. 对于三个节点的二次插值 ,插值条件为
57
插值多项式 显然 由 得 系数 是函数 的“差商的差商”.
58
一般情况,已知 在插值点 上的值为 ,要求 次插值多项式 满足条件
(3.1) 则 可表示为 (3.2) 其中 为待定系数,可由插值条件确定. 这里的 是由基函数 逐次递推得到的,这一点与拉格朗日插值不同.
59
均差及其性质 称 为函数 关 于点 的一阶均差. 定义2 称为 的二阶均差.
60
一般地,称 (3.3) 为 的 阶均差 (均差也称为差商).
61
均差有如下的基本性质: (1) 阶均差可表为函数值 的线 性组合, 即 (3.4) 这个性质可用归纳法证明. 这性质也表明均差与节点的排列次序无关,称为均差 的对称性.
62
即 (2) 由性质(1)及(3.3)可得 (3.3)’ (3.3) (3) 若 在 上存在 阶导数,且节点 则 阶均差与导数关系如下: (3.5) 这公式可直接用罗尔定理证明.
63
所以
64
均差计算可列均差表如下(表2-1).
65
牛顿插值公式 根据均差定义,一次插值多项式为 二次插值多项式为
66
根据均差定义,把 看成 上一点, 可得
67
只要把后一式依次代入前一式,就得到 其中 (3.6)
68
(3.7) 是由(2.10)定义的. 显然,由(3.6)确定的多项式 满足插值条件, 且次数不超过 , 其系数为 它就是形如(3.1)的多项式, (2.10) (3.6) 称 为牛顿(Newton)均差插值多项式. (3.1) 系数 就是均差表2-1中加横线的各阶均差,它比拉格朗日插值计算量省,且便于程序设计.
69
事实上,利用均差与导数关系式就可以证明这一点.
(3.7)为插值余项,由插值多项式唯一性知,它与 拉格朗日插值多项式的余项应该是等价的. 事实上,利用均差与导数关系式就可以证明这一点. (3.7) 但(3.7)更有一般性,它在 是由离散点给出的情形或 导数不存在时也是适用的. 牛顿插值多项式的优点还在于它的递进性,当增加 插值节点时,只要在原来插值多项式的基础上增加一项 即可.
70
给出 的函数表(见表2-2),求4次牛顿插 值多项式,并由此计算 的近似值. 例4 首先根据给定函数表造出均差表.
71
从均差表看到4阶均差近似常数,5阶均差近似为0.
故取4次插值多项式 做近似即可. 按牛顿插值公式,将数据代入 于是
72
截断误差 这说明截断误差很小,可忽略不计.
73
2.3.4 差分形式的牛顿插值公式 实际应用时经常遇到等距节点,即 的情形,这里 为常数,称为步长, 这时插值公式可以进一步
差分形式的牛顿插值公式 实际应用时经常遇到等距节点,即 的情形,这里 为常数,称为步长, 这时插值公式可以进一步 简化,计算也简单得多. 设 点的函数值为 ,称 为 处以 为步长的一阶(向前)差分. 类似地称 为 处的二阶差分. 一般地称 (3.8) 为 处的 阶差分.
74
为了表示方便,再引入两个常用算子符号 称为不变算子 , 称为步长为 的移位算子,由此 (3.9) 其中 为二项式展开系数,(3.9) 说明各阶差分均可由函数值给出.
75
反之,由 可得 (3.10) 从而有均差与差分的关系:
76
一般地有 (3.11) 由(3.11)和(3.5)又可得到差分与导数的关系: (3.12) 其中
77
由给定函数表计算差分可由以下形式差分表给出.
78
在牛顿插值公式(3.6)中,用(3.11)的差分代替均差,
并令 ,则得 (3.13) (3.13)称为牛顿前插公式,由(3.7)式得其余项为 (3.14)
79
给出 在 例5 处的函数值,试用4次牛顿前插公式计算 的近似值并估计误差. 解 为使用牛顿插值公式,先构造差分表.
80
得 取 则
81
由(3.14)可得误差估计 (3.14) 其中
82
2.4 埃尔米特插值 有些实际的插值问题不但要求在节点上函数值相等, 而且还要求对应的导数值也相等,甚至要求高阶导数也相等.
2.4 埃尔米特插值 有些实际的插值问题不但要求在节点上函数值相等, 而且还要求对应的导数值也相等,甚至要求高阶导数也相等. 满足这种要求的插值多项式就是埃尔米特插值多项式.
83
2.4.1 重节点均差与泰勒插值 关于均差,有 定理3 设 为 上的相异节点,则 是其变量的连续函数.
重节点均差与泰勒插值 关于均差,有 定理3 设 为 上的相异节点,则 是其变量的连续函数. 如果 上的节点互异,根据差商定义,若 则有 由此定义重节点均差
84
类似地可定义重节点的二阶均差,当 时,有 当 时,有 一般地,可定义 阶重节点的均差,由(3.5)得 (4.1)
85
在牛顿均差插值多项式中若令 则由(4.1)可得泰勒多项式
(4.2) 这实际上是在点 附近逼近 的一个带导数的插值多项式,它满足条件 (4.3) (4.2)称为泰勒插值多项式,它就是一个埃尔米特插值多项式,余项为
86
(4.4) 它与插值余项(2.12)中令 的结果是一致的. 泰勒插值是牛顿插值的极限形式,是只在一点 给出 个插值条件所得到的 次埃尔米特插值多项式. 一般地只要给出 个插值条件(包括函数和导数值)就可以构造出次数不超过 次的埃尔米特多项式.
87
2.4.2 两个典型的埃尔米特插值 考虑满足条件 及 的插值多项式及其余项表达式. 由给定的4个条件,可确定次数不超过3的插值多项式.
两个典型的埃尔米特插值 考虑满足条件 及 的插值多项式及其余项表达式. 由给定的4个条件,可确定次数不超过3的插值多项式. 由于此多项式通过点 故其形式为
88
待定常数 ,可由条件 确定, 通过计算可得 为了求出余项 的表达式, 可设 其中 为待定函数.
89
构造 显然 且 故 在 内有5个零点(二重根算两个). 反复应用罗尔定理,得 在 内至少有一个 零点ξ, 故有
90
于是 余项表达式为 (4.5) 式中 位于 和 所界定的范围内.
91
例6 给定 试求 在 上的三次埃尔米特插值多项式 ,使它满足
并写出余项表达式. 解 由所给节点可求出 为了构造牛顿均差插值,先构造均差表
92
于是有 令 再由条件 ,可得
93
解出 于是所求的三次埃尔米特多项式为
94
余项
95
另一个典型例子是两点三次埃尔米特插值,插值节点取为 及 ,插值多项式为 ,插值条件为
(4.6) 采用基函数的方法,令 (4.7) 其中 是关于节点 及 的三次埃尔米特插值基函数,分别满足
97
根据给定条件可令 显然 再利用 及
98
解得 于是求得 (4.8) 同理可得 (4.9)
99
为求 ,由给定条件可令 直接由 ,得到 (4.10) 同理 (4.11)
100
最后代入,得 (4.12)
101
余项 ,类似(4.5)可得 (4.13)
102
2.5 分段低次插值 2.5.1 高次插值的病态性质 根据区间 上给出的节点做出的插值多项式 在次数 增加时逼近 的精度不一定也增加.
分段低次插值 高次插值的病态性质 根据区间 上给出的节点做出的插值多项式 在次数 增加时逼近 的精度不一定也增加. 这是因为对任意的插值节点,当 时, 不 一定收敛到 .
103
考虑函数 ,它在 上的各阶导数均 存在. 以 上的 个等距节点 所构造的拉格朗日插值多项式为 令 则
104
表2-5列出了 时的 的计算结果及 在 上的误差
105
- 5 4 3 2 1 0.5 1.5 2.5
106
可见,随 的增加, 的绝对值几乎成倍增加. 这说明当 时 在 上是不收敛的. Runge证明了,存在一个常数 ,使得当 时, 而当 时 发散.
107
从图上看到,在 附近, 与 偏离很远, 这说明用高次插值多项式 近似 效 果并不好. 通常不用高次插值,而用分段低次插值.
108
下图是用Matlab完成的Lagrange插值(附程序):
109
plot(x, z, ’r’, x, y, ’k:’ ,x, y1, ’r’)
附:Lagrange插值程序 n=11; m=61; x= -5:10/(m-1):5; y=1./(1+x.^2); z=0*x; x0=-5:10/(n-1):5; y0=1./(1+x0.^2); y1=lagr1(x0, y0, x); plot(x, z, ’r’, x, y, ’k:’ ,x, y1, ’r’) gtext(‘Lagr.’), gtext(‘y=1/(1+x^2)’) title(‘Lagrange’)
110
附:Lagrange插值子程序 lagr1:
function y=lagr1(x0,y0,x) n=length(x0); m=length(x); for i=1:m z=x(i); s=0.0; for k=1:n p=1.0; for j=1:n if j~=k p=p*(z-x0(j))/(x0(k)-x0(j)); end s=p*y0(k)+s; y(i)=s;
111
2.5.2 分段线性插值 由于升高插值多项式的阶数有时并不能达到提高精度 的效果, 所以实际中往往采用分段插值的思想.
分段线性插值 由于升高插值多项式的阶数有时并不能达到提高精度 的效果, 所以实际中往往采用分段插值的思想. 分段插值的基本思想是将插值区间划分为若干个小区间, 然后在每个小区间上做满足一定条件的低阶插值. 所谓分段线性插值就是通过插值点用折线段连接起来 逼近
112
设已知节点 上的函数值 记 求一折线函数 , 满足: 在每个小区间 上是线性函数. 则称 为分段线性插值函数.
113
由定义可知 在每个小区间 上可表示为 (5.1) 分段线性插值的误差可利用插值余项(2.15)得到 或写成 (5.2) 其中
114
由此还可以得到 在 上一致成立, 故 在 上一致收敛到 .
115
下图是用Matlab完成的分段线性插值(附程序):
116
plot(x, z, ’r’, x, y, ’k:’, x, y1, ’r’)
附:分段线性插值程序 n=11; m=61; x=-5:10/(m-1):5; y=1./(1+x.^2); z=0*x; x0=-5:10/(n-1):5; y0=1./(1+x0.^2); y1=interp1(x0, y0, x); plot(x, z, ’r’, x, y, ’k:’, x, y1, ’r’) gtext(‘Piece. –linear.’), gtext(‘y=1/(1+x^2)’) title(‘Piecewise Linear’) 注:interp1(x0,y0,x)为Matlab中现成的分段线性插值程序.
117
2.5.3 分段三次埃尔米特插值 分段线性插值函数 的导数是间断的,若在节点 上除已知函数值 外还给出导数值 就可以构造出一个导数连续的分段
分段三次埃尔米特插值 分段线性插值函数 的导数是间断的,若在节点 上除已知函数值 外还给出导数值 就可以构造出一个导数连续的分段 插值函数 ,满足条件 在每个小区间 上是三次多项式.
118
根据两点三次埃尔米特插值插值多项式(4.12),
在区间 上的表达式为 (5.3) 上式对于 成立.
119
利用三次埃尔米特插值的余项(4.13),可得误差估计
于是有 定理3 设 为 在节点 上的分段三次埃尔米特插值多项式,则有 其中
120
三次样条插值
121
2.6.1 三次样条函数 定义3 若函数 且在每个小区间 上是三次多项式,其中 是给定节点, 则称 是节点 上的三次样条函数.
三次样条函数 定义3 若函数 且在每个小区间 上是三次多项式,其中 是给定节点, 则称 是节点 上的三次样条函数. 若在节点 上给定函数值 并成立 (6.1) 则称 为三次样条插值函数.
122
由于 在每个小区间 上有4个待定系数, 共有 个小区间,所以共有 个待定参数. 因为 在 上二阶导数连续,所以在节点 处应满足连续性条件 (6.2) 这些共有 个条件,再加上 本身还要满足的 个插值条件,共有 个条件,还需要2个才能确定 .
123
通常可在区间 端点 上各加一个条件 (称为边界条件), 常见的边界条件有以下3种: 1. 已知两端的一阶导数值,即 (6.3) 2. 已知两端的二阶导数,即 (6.4) 其特殊情况为 (6.4)‘ (6.4)‘称为自然边界条件.
124
3. 当 是以 为周期的周期函数时,则要求 也是周期函数. 这时边界条件应满足 (6.5) 此时插值条件(6.1)中 这样确定的样条函数 称为周期样条函数.
125
2.6.2 样条插值函数的建立 下面利用 的二阶导数值 表示 . 由于 在区间 上是三次多项式,故 在 上是线性函数, 可表示为 (6.7)
样条插值函数的建立 下面利用 的二阶导数值 表示 . 由于 在区间 上是三次多项式,故 在 上是线性函数, 可表示为 (6.7) 对 积分两次并利用 及 , 可定出积分常数, 于是得三次样条表达式
126
(6.8) 这里 ,是未知的.
127
为了确定 ,对 求导得 (6.9) 由此可求得
128
类似地可求出 在区间 上的表达式,从而得 利用 可得 (6.10) 其中
129
(6.11) 对第一种边界条件(6.3),可导出两个方程 (6.12) (6.3)
130
如果令 那么(6.10)及(6.12)可写成矩阵形式 (6.13) (6.10) (6.12)
131
对第二种边界条件(6.4),直接得端点方程 (6.14) 如果令 , 则(6.10)和(6.14) 也可以写成(6.13)的矩阵形式. (6.4)
132
对于第三种边界条件(6.5),可得 (6.15) (6.5) 其中 (6.10)和(6.15)可以写成矩阵形式
133
方程组, 在力学上解释为细梁在 截面处的弯矩,称 为 的矩,
(6.16) (6.8) (6.13)和(6.16)是关于 的三对角 方程组, 在力学上解释为细梁在 截面处的弯矩,称 为 的矩, (6.13) 方程组(6.13)和(6.16)称为三弯矩方程. (6.13)和(6.16)的系数矩阵为严格对角占优阵,有 唯一解, 求解方法可见第5章第4节追赶法,将解得结果代入 (6.8)的表达式即可.
134
设 为定义在 上的函数,在节点 上的值如下: 例7 试求三次样条函数 ,使它满足边界条件
135
解 由(6.11)及(6.12) (6.11) (6.12) 由此得矩阵形式的方程组(6.13)为
136
求解得
137
代入(6.8)得 (6.8) (曲线见图2-6)
138
图2-6
139
给定函数 节点 例8 用三次样条插值求 取 直接上机计算可求出 在表2-6所列各点的值.
141
下图是用Matlab完成的样条插值(附程序):
142
附:样条插值程序 n=11; m=61; x=-5:10/(m-1):5; y=1./(1+x.^2); z=0*x; x0=-5:10/(n-1):5; y0=1./(1+x0.^2); y1=interp1(x0, y0, x, ’spline’); plot(x, z, ’r’, x, y, ’k:’, x, y1, ’r’) gtext(‘Spline’), gtext(‘y=1/(1+x^2)’) title(‘Spline’) 注:interp1(x0, y0, x, ’spline’)为Matlab中现成的样条插值程序.
143
也可以将三种插值结果画在一起:
144
2.6.3 误差界与收敛性 定理4 设 为满足第一种或第二 种边界条件(6.3)或(6.4)的三次样条函数, 令 则有估计式 (6.3)
误差界与收敛性 设 为满足第一种或第二 种边界条件(6.3)或(6.4)的三次样条函数, 定理4 令 (6.3) (6.4) 则有估计式 (6.17) 其中
145
这个定理不但给出了三次样条插值函数 的误差
估计. 还说明了当 时, 及其一阶导数 和 二阶导数 均分别一致收敛于 , 及
152
高元插值及Matlab实现
156
mesh(X,Y,Z) 绘制网格图
157
>> surf(Z) 绘制表面图
158
>> surf(X,Y,Z)
162
单调数据点上的二元插值
Similar presentations