logo资料库

插值的概念和各种基本方法.pdf

第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
资料共22页,剩余部分请下载后查看
插值的概念和基本方法
1 插值的基础知识
1.1 插值问题的提出
1.2 插值的定义
1.3 插值多项式的存在惟一性
2 拉格朗日插值
2.1 线性插值( )
2.2 抛物线插值( )
2.3 次拉格朗日插值多项式
2.4 拉格朗日插值余项
2.5 拉格朗日插值的MATLAB实现
3 均差与牛顿插值多项式
3.1 均差及其性质
3.2 牛顿插值多项式
3.3 牛顿插值的MATLAB实现
4 差分与等距节点插值多项式
4.1 差分及其性质
1. 差分概念
2. 差分的基本性质
4.2 等距节点插值多项式
1. 牛顿前插多项式
2. 牛顿后插多项式
5 分段线性插值多项式及其余项估计
5.1 分段线性插值多项式
5.2 余项估计
6 埃尔米特插值
6.1 埃尔米特插值多项式
1. 埃尔米特插值基函数
2. 埃尔米特插值函数的惟一性
3. 余项估计
6.2 分段三次埃尔米特插值
1. 分段三次埃尔米特插值基函数
2. 余项估计
7 三次样条插值
7.1 三次样条插值函数的定义
7.2 三次样条插值函数的构造
7.3 误差估计
7.4 三次样条函数的MATLAB实现
插值的概念和基本方法 内容提要:本文主要介绍了插值的概念和插值的基本方法,包括拉格朗日插值多项式、均差与 牛顿插值多项式、差分与等距节点插值多项式、分段线性插值多项式、埃尔米特插值、三次样条插 值。在介绍这些方法的同时,还介绍了均差与差分的概念。 关键字:插值理论、拉格朗日插值多项式、均差、牛顿插值多项式、三次样条插值、差分 引言:插值理论是数值积分、数值微分、数据拟合、解微分方程等数值分析应用方面的基础。 插值法的应用十分广泛,在查表和求值的计算过程中,可以根据已知数据构造插值函数来求得被插 函数在某些点的精确值。 正文: 1 插值的基础知识 1.1 插值问题的提出 在许多实际问题及科学研究中,因素之间往往存在着函数关系,但是这些关系的显式表达式不 一定都知道,通常只是由观察或测试得到一些离散数值,所以只能从这些数据构造函数的近似表达 式。 有时,虽然给出了解析表达式,但由于解析表达式过于复杂,使用或计算起来十分麻烦。这就 需要建立函数的某种近似表达,本文所讨论的插值法就是构造函数的近似表达的方法。 例如,已经测得某化学反应在不同时刻生成物的浓度如表 1 所示。 表 1 某化学反应在不同时刻生成物的浓度 时刻(秒) 5 浓度(%) 0.045 10 0.055 15 3.40 20 22.54 25 72.13 如果希望由这些数据合理地估计出它在其他时刻(如 30 秒,40 秒,50 秒……)处的浓度,这 就是一个典型的插值问题。 1.2 插值的定义 ]a b 在区间 [ , 上有定义,且已知 在 , y ( 0,1, x ≤ < < 0 为( )P x = L )成立,就称 1n + 个节点 n P x ( )i ( )P x y= i x 1 a i x x L x 称为插值节点,包含插值节点的区间 [ , 称为插值区间,而 ]a b n b ≤ x < 上的 L n f x 关于节点 ( ) f x ( ) , yL , y = f x ( ) 定义 1:设函数 y y , 0 1 , 值为 x x L x 的插值函数,点 0 1, 称为被插函数,求插值函数 n ( )P x 若 , n n 0 ,若存在简单函数 , 的方法称为插值法。 1, , ( )P x ,使 是次数不超过 次的代数多项式,即若有: + P x ( ) = a 0 a x 1 + +L n a x n 其中 为实数,就称 ia ( )P x 式,就是分段插值。 为插值多项式,相应的插值法称为多项式插值。若 (1) 为分段的多项 ( )P x 由插值定义可知,插值函数实际上是一条经过平面上 1n + 个节点 ( 可以用这条平面曲线 代替近似已知曲线 y P x ( ) f x ( ) ,如图 1 所示。 x y ,( i = = y ) , i i = L n , 0,1, )的曲线。 图 1 ※ 1 ※
1.3 插值多项式的存在惟一性 给 定 被 插 函 数 ( ) 0, 1, )的插值函数 f x , 若 插 值 节 点 为 0 y= i 是否存在?若存在,那么是否惟一?这就是插值问题的存在惟一性 P x , 则 满 足 插 值 条 件 ( )i xL , x x 1, f xi ( ( )P x iy = ) , , n ( i = L n , 问题。 定理 1:给定被插函数 ( ) f x ,插值节点 0 x x 1, )。 y= ( n , 0, 1, 2, ( )P x 满足 = i , P x ( )i i L 的插值函数 xL ,且 , n iy = f xi ( ) ,则必存在惟一的形如表达式(1) 证明: 要证明 ( )P x 存在惟一,就是要证明存在惟一的一个 a x 1 0 a x 1 1 a 0 a 0 + + +L 满足: a x n n P x ( ) + + a = + 0 a x n = n 0 a x n = n 1 L L a x 1 y 0 y 1 ⎧ ⎪ ⎪ ⎨ ⎪ L ⎪ + a ⎩ 0 a x n 1 + L a x n n n = y n (2) 显然方程组(2)的系数行列式为: V x x , 1 ( 0 , L , x n ) = L x 1 0 x 1 1 L L L L x 1 n x 2 0 x 2 1 x 2 n x n 0 x n 1 x n n L 且是范德蒙(Vandermonde )行列式。可算得 V x x , 1 ( 0 , L , x n ) 知 V x x , 1 ( 0 , x ≠L ) , n 0 。故方程组(2)存在惟一解 a a 1, 0 , aL , n ,即 x k ) (3) ,且当 i 时 x≠ , k≠ x i k ( x i − n = L i 1 − ∏∏ i 1 = ( )P x 0 = k 存在惟一。 2 拉格朗日插值 由定理 1 知,要求插值多项式 ( )P x 算复杂,且得到的不一定是 个节点的情形。 2.1 线性插值( 1n = ) ( )P x 的最简表达式。下面就先讨论 ,可以通过解方程组(2)求得 a a 1, 。但这样会导致计 0 n = 的情形,然后推广到 1n + 1n = 和 2 aL , , n i , ) i = x y ( i 0,1 给定两个不同点 ( 的次数不超过 1。 (1) 1( )P x (2) i = 0,1 y= P x 1( )i ( i 1( )P x 显然,可以取 为过 )。 x y ( , i i ) ),要求插值多项式 1( )P x 满足: ( 0,1 i = )的直线。设: + ( )P x 1 a 0 = a x1 (4) = = y 0 y 1 把两点坐标代入方程(4 ),得方程组: a + ⎧ 0 ⎨ a + ⎩ 0 x 由 0 a x 1 0 a x 1 1 x≠ 可解出 , 。 y0 x 0 y 两点之间的斜率为 1 x 1 1a − − 0a = + − x ( ) 1 P x ( ) 1 y 0 x 0 y 1 x 1 − − y 0 x 0 ,将直线表示为点斜式: 若用两点式表示,则为: P x ( ) 1 = y 0 x x 0 − − x 1 x 1 + y 1 x x 1 − − x 0 x 0 (5) ※ 2 ※
现在,就用直线 1( )P x 近似地代替被插函数 f x ,如图 2 所示。 ( ) 图 2 通常,记式(5)中出现的两个线性函数为: l x ( ) 0 l x ( ) 1 , = = x x 1 − − x 0 x 0 − − x x 1 x x 0 1 l x 为0( ) 并称 0x 上的一次插值基函数, l x 为1( ) 1x 上的一次插值基函数。插值基函数 l x 0( ) , l x 1( ) 在 对应的插值节点上取值 1,其余插值节点取值 0,且次数不超过 1,如表 2 所示。 表 2 一次插值基函数在x 0及x1上取值 节 点 值 数 数 0x 1x 函 函 l x 0( ) l x 1( ) 由表 2 和图 3 可以看出两个基函数的性质。插值函数 1 0 0 1 1( )P x 实质上是插值基函数 l x 0( ) 和 l x 1( ) 的线 性组合,组合系数是对应点上的函数值。 【例 1】给定被插函数 2x y = 及两点坐标(0,1),(1,2),构造线性插值函数 1( )P x ,并求 的近 0.32 图 3 似值。 解: 先求得线性基函数: l x ( ) 0 = x 1 − 0 1 − 1 = − x , 1 l x ( ) = x 0 − 1 0 − = x 代入式(5)得: P x 1( ) 2 (1 = − x x ⋅ + ⋅ = + , 0.3 ) 1 1 2 x P≈ 1 (0.3) 1 = .3 2.2 抛物线插值( n = 2 ) 与线性插值类似,抛物线是给定三不同点 ( 的次数不超过 2。 (1) 2( )P x )。 (2) i = 0,1,2 y= P x 2( )i ( i x y ( 2( )P x ) , ( 为过 显然,可以取 i 0,1,2 i = i x y , i i ) ( 0,1,2 i = ),要求插值多项式 2( )P x 满足: )的一条抛物线,假设: ( )P x 2 = a 0 + a x a x 1 2 + 2 (6) ※ 3 ※
+ + + a x 1 0 a x 1 1 a x 1 2 把上面三点的坐标代入方程(6),得方程组: a ⎧ + 0 ⎪ a + ⎨ 0 ⎪ + a ⎩ 0 由三点互异,可解出系数 , , 的值。 另外,同线性插值类似,也可以通过构造抛物线插值的基函数来求 a x 2 2 0 a x 2 2 1 a x 2 2 2 y 0 y 1 y = = = 2a 0a 1a 2 在对应的节点上取 1,其余点取 0,如表 3 所示。 表 3 抛物线插值的基函数x0、x1及x2上取值 节 点 1x 0x 2( )P x 的表达式。插值基函数 2x 0 1 0 ( 有因子 l x 0( ) 0 0 1 x − x 1 ) ( ⋅ x − x 2 ) ,又因为它的次数不超过 3,故 函 数 数 值 函 l x 0( ) l x 1( ) l x 2( ) l x 有0( ) 可设它的表达式为: x ) ( A ⋅ 代入,可求得: 1 0 0 1x 和 2x 两个零点,故 由上表知 l x ( ) 0 再把 x 2 ) A x x ( − = 1 l x = 0( ) 1 0 1 ) ( ⋅ − x 0 x 1 A = ( − x 2 ) x 0 − ,其中 为待定系数。 这样就求得了 0x 上的抛物线插值基函数: l 0 = ) x ( x 0 ( − − x 1 x 1 ) ( ⋅ ) ( ⋅ x x 0 x − 2 x − 2 ) 同理,可求得 1x 和 2x 上的抛物线插值基函数分别为: l 1 , = = l 2 x ( x ( 1 − − x 0 x 0 ) ( ⋅ ) ( ⋅ x x 1 x − 2 x − 2 ) ) x 0 x 0 ) ( ⋅ ) ( ⋅ x x 2 x ) − 1 x − 1 ) x ( x 2 − − ( 如图 4 所示中的中(a)、(b)和(c)分别为基函数 l x 0( ) 、 l x 1( ) 和 l x 2( ) 的图形。 ( a) ( b) ( c) 图 4 通过 , , 可求得: 2l 0l 1l P x ( ) 2 = y 0 【例 2】给定被插函数 y = f x ( ) x x ( − 1 x x ( − 0 1 x cos = ) + x x 0 x − 2 x − 2 x x x x ) ( ( ( ) ( − − − ⋅ ⋅ 0 2 x x x x ) ( ) ( ( ( − − − ⋅ ⋅ 2 0 1 2 ,用 3 个节点 x = x = , 1 x = 和 1.2 0 2 x ) ( ⋅ 0 x ) ( ⋅ 0 0.0 x x 1 ) ) 0.6 y 1 + y ) 2 (7) x ) − 1 x − 1 x x 2 构造一个抛物线插 ) ,x 1 0.6= ,x =2 1.2 和 y = 0 cos(0.0) 1 = ,y1 = cos(0.6) = 0.825336 ,y 2 = cos(1.2) = 0.362358 0.6)( − − 1.388889( = x − x − 1.2) − x 0.6)( − (0.0 0.6)(0.0 1.2) + 0.825336 1.2) 2.292599( − ( x 0.0)( x − 0.362358 + (0.6 0.0)(0.6 1.2) 0.503275( + 0.0)( − x x x 1.2) − 1.2) − − − x x − 0.0)( 0.6) ( (1.2 0.0)(1.2 0.6) − 0.6) − − − 0.0)( − x ※ 4 ※ 解:将 值多项式 2( )P x x = 0 。 0.0 代入式(7)得: x ( P x 2 ( ) 1.0 =
2.3 次拉格朗日插值多项式 n 对于 1n = 及 n = 2 ,前面已经得到一次与二次插值多项式 1( )P x 及 2( )P x 。下面将这种用插值基函 数表示的方法推广到更一般的情形。 1n + x< 设有 1 定义 2:若 次多项式 个节点 x 0 n n (
2.4 拉格朗日插值余项 nP x 和( ) 要讨论 罗尔(Rolle)定理:若 ( ) f x 的误差,先叙述一个定理。 ( ) f x 在闭区间 [ , 连续,在开区间 ( , 可导,且 )a b ]a b f a ( ) = f b ( ) ,则在 ( , )a b 中必存在 f ξ′ ξ,使得 ( ) ]a b nP x ( ) 若在 [ , 上用 = 。 0 近似 f x ,则其截断误差 ( ) nR x ( ) = f x ( ) − P xn ( ) 称为插值多项式 nP x ( ) 的余项。关 于插值余项有下面定理: 定理 2:设 ( ) ( ) nf ( )iP x ( i = L 0,1, 件 x a b∈ 对任意给定的 [ , ] y= i , ,插值余项: x 在 [ , 上连续, ]a b nP x ( ) )和条件(1 )的插值多项式,其中 [ , 是包含 内有定义。设 x 1)( ) + 在 ( , )a b ]a b nf ( n 1, 是过点 的满足条 x x L x 的任意区间,则 x x L x , , 1, , , n n 0 0 R x ( ) n = f x ( ) − P x ( ) n 1) ( ) + ξ 1)! + ω n x ( ) (12) = f n ( n ( 。 (依赖于 x ), 其中 ( , )a b ξ∈ 证明: 由给定条件知插值余项 ω = x ( ) n ( x − x 0 )( x − x 1 ) x −L ( x n ) iR x = n ( ) 0 ( i = L ),故 K x x ( )( , 0,1, R x ( ) n n = x nR x x ( ) ( − 有因子: 0 x x x x ) ( )( − −L n 0 x 1 − ) )( ( ) x 1 x −L ,设余项: x − (13) x n ) 其中 ( )K x 为与 x 有关的待定函数。 a b∈ x 固定 [ , ] t x f t ( ( ) −L ϕ = − n x x 1, , 由插值多项式及余项的定义知,点 0 ,作函数: P t K x t ( )( ( ) − n t ( ) t )( x 0 x 1 − − ) ) xL 及 x 均为 ( )tϕ 的零点,则 ( )tϕ 在 , n 由罗尔定理, ( )tϕ′ 在 ( )tϕ 的任意两个零点之间至少有一个零点,故 ( )tϕ′ 在 ( )tϕ′ 用罗尔定理,可得 ( )tϕ′′ 在 [ , ]a b 上至少有 个零点。如此类推,就知 n [ , ]a b 有 [ , ]a b 上至少有 n ( tϕ + 1) ( ) 2n + 1n + ( , )a b 在 个零点。 个零点。 内至少有 R x ( ) n ≤ M n n + ( 1 ω+ n 1)! x ( ) (14) 令 1n = R x ( ) 1 = 令 n = 2 R x ( ) 2 = f f = 1 2 x ( ) ( )( ′′ ξ ( ) ′′ ξω 1 ,得线性插值余项为: 1 x 0 2 ,得抛物线插值余项为: 1 x )( 0 6 ( ) ′′′ ξω 2 ( )( ′′ ξ x ( ) 1 2 )( = − − x x f f x x 1− ) , ξ∈ ( x x , 0 1 ) x − x 1 )( x x 2− ) , ξ∈ ( x x , 0 2 ) 【例 4】给定被插函数 2x (1)估计例 1 中的 在点 (2)给定三点坐标(-1,0.5 ),(0,1),(1,2),构造线性插值函数 y = 。 x = 处的截断误差。 1( )P x 0.3 2( )P x ,并求 的近似值和截 0.32 断误差。 解: (1)由例 1 求得: P x 1( ) f x = ( ) x= + 1 2x ※ 6 ※ 再对 一个零点,记为 nf ( ( ) ϕ ξ = 1) + n ( ξ,故有: 1)! 1) + n + K x ( ) = 0 求得 K x ( ) = nf ( n ( ( ) ( − ξ 1)( ) ξ+ 1)! + ,其中 ( , )a b ξ∈ ,且依赖于 x 。 将 ( )K x 代回式(13),就得到式(12)。 定理得证。 值得注意的是,ξ在 M 1 max = a x b < < 则有: ( , )a b x ( ) 1) + f + n n ( 内的具体位置一般不知道,不过若可以求出:
R 1 (0.3) = 0.3 2 − P 1 (0.3) ≤ 0.3(0.3 1) − = 0.09522 作为 的近似值,只能保证有一位有效数字。 1 ⋅ + 1)( x ( 0) (1 1)(1 0) x − − + + 2 ⋅ = 0.25 x 2 + 0.75 x + 1 2 f x′ 2 ln 2 ( ) x = x′′ f 2 (ln 2) ( ) x = f x ( ) 2(ln 2) max ′′ x 0 1 ≤ ≤ 由式(14)得: = 2 = 0.9609 0.9609 2! 0.32 = P 1(0.3) 1.3 可见用 (2)将各点坐标代入式(7)得: x ( 1) (0 1)(0 1) 0.5 − − + + 1)( = + x ⋅ 0.3 0)( P x ( ) 2 x x ( 1) − − ( 1 0)( 1 1) − − − − P≈ (0.3) 1.248 2 = 2 f x′′′ 2 (ln 2) ( ) x = x f 2(ln 2) ( ) max ′′′ x 1 1 − ≤ ≤ 由式(14)得: = 3 3 = 0.6660 0.6660 3! 0.32 R 2 (0.3) = 0.3 2 − P 2 (0.3) ≤ (0.3 1)(0.3 0)(0.3 1) + − − = 0.03030 可见用 P 2(0.3) 1.248 = 作为 的近似值,可以保证有两位有效数字。 = ∑ k y l x ( ) k 。 n k = 0 2.5 拉格朗日插值的 MATLAB 实现 程序 1 给定 1n + 个不同节点,构造 f x x [ , 1 0 , xL 的 n 次拉格朗日插值多项式 ]k , P x ( ) n function[c,l]=lagran(x,y) %这里 x 为 n 个节点的横坐标所组成的向量,y 为纵坐标所组成的向量 %c 为所得插值函数的系数组成的向量 w=length(x); n=w-1; l=zeros(w,w); for k=1:n+1 v=1; for j=1:n+1 if k~=j v=conv(v,poly(x(j)))/(x(k)-x(j)); end end l(k,:)=v; end c=y*l; 利用上面程序来计算例 1。 输入: >>lagran([0,1],[1,2]) 得到: ans = 1 1 这就表明所求拉格朗日插值多项式为 1x + 。 3 均差与牛顿插值多项式 3.1 均差及其性质 拉格朗日插值多项式在理论分析中非常方便,因为它的结构紧凑,利用基函数就很容易得到插 ※ 7 ※
值函数。但是拉格朗日插值多项式也有一些缺点,当插值节点增加、减少或其位置变化时,整个插 值多项式的结构都会改变,这就不利于实际计算,增加了算法复杂度。 1n + 假设有 个不同的节点及函数在节点上的值 x y , 0 点的有效方法之一是把插值多项式构造成如下形式: x )( 0 a x ( 1 x 0 + + ( ) x − − = a 0 a x ( 2 P x x ( ) n 1 n , )为待定系数,可由插值条件 y = 0 a x ( + 1 1 ,故: 。 − y = 1 x 0 − ) i = L 0,1, a nP x ( ) = 0 0 nP x a ( ) = 1 0 ), 0 L ,( x y , n n ) ,克服拉格朗日插值多项式的缺 − x a x ) ( + − + L n y= ( 0,1, P x ) ( n i x )( 0 = L )确定。 i x ) L 1 n , x n − x ( ) i (15) 0 x x ia 其中系数 ( x= 时, 当 x= 时, 当 y 1 x 1 x= 时, y 2 x 2 y 0 x 0 2 − − 1 − − 当 a 1 = − x a 2 = y 0 x 0 x 2 − ) nP x ( 2 y y − 1 0 x x − 0 1 x 1 = a 0 + a x ( 1 2 − x 0 ) + a x ( 2 2 − x 0 )( x 2 − x 1 ) y = 2 ,故: 依此方法递推可以得到系数 ( 明确的算法,下面引入均差的概念。 − − 定 义 3 : 称 f x x [ , 1 f x ( ) 1 x 1 = ] 0 f x ( 0 x 0 ia i = L n , 0,1, )的一般表达式,为使 的算法更简明,并给出一个 ia ) 为 函 数 ( ) f x 关 于 点 0x , 1x 的 一 阶 均 差 。 令 f x x x [ , 2 , 0 1 ] = ] 0 f x x [ , 2 x 2 ] − − 0 f x x [ , 1 x 1 ,这是一阶均差的均差,称为 ( ) f x 的二阶均差。一般地,称: f x x [ , 1 0 , , x k ] = L f x [ 0 , L , x k − 2 , x k x k ] − x − k 1 − f x x [ , 1 0 , , x k 1−L ] (16) k f x 的 阶均差(有时也称为差商)。 为 ( ) 均差是数值分析中的重要概念,它有如下性质: (1) 阶均差 f x ( 1 f x x [ , 1 ), k , 0 , ]k xL 可表为函数值 0 f x ( k ∑ f x x [ , 1 x k L = ] , , 0 ), f xL ( )k , 的线性组合,即: f x ) ( i x )( i x )k x i x i − − 1 + ) ( L 1 − ( x i − x 0 ) L ( x i − x i i = 0 (17) 这个性质可以用归纳法证明。这个性质也表明均差与节点的排列次序无关,称为均差的对称性, 即: ] = (2)由均差性质(1)及式(16)可得: f x x [ , 1 x k L , , 0 f x x x [ , 2 , 1 0 , L , x k ] = L = f x [ 1 , L , x x , k 0 ] (18) (3)若 ( ) f x 在 [ , ]a b 上存在 阶微商,且节点 n x x 1, 0 计算均差时通常要构造形如表 4 所示的均差表。 f x x [ , 1 0 , , x k ] = L f x [ 1 , , , , , ] L L x 1k − (19) f x x [ ] − k 0 x x − k 0 ,则 阶均差与微商关系如下: a b∈L [ , ] ( ) ξ ] ! (20) , [ , ]a b x n f n ( ) n ξ∈ n , f x x [ , 1 0 , =L x n , 表 4 均差表 )k 一阶均差 kx 0x 1x 2x 3x M 3.2 牛顿插值多项式 f f x 零阶均差 ( x 0( ) )x f 1( f x 2( ) f x 3( ) M 2 1 1 0 , f x x [ ] f x x [ ] f x x [ ] M , , 2 3 二阶均差 三阶均差 1 0 , f x x x , [ 2 f x x x , [ 3 M , 1 2 ] ] 2 1 0 , , , f x x x x [ ] M 3 根据均差定义,把 x 看成 [ , ]a b 上的一点,可得: ※ 8 ※
分享到:
收藏