数值分析插值课件

1、Ch6 插值法,6.1 引言 6.2 拉格朗日插值多项式 6.3 牛顿插值多项式 6.4 埃尔米特插值多项式 6.5 分段低次插值、三次样条插值多项式,6.1 引言 许多实际问题都用函数 来表示某种内在规律的数量规律的数量关系，其中相当一部分函数是通过实验或观测的得到的.一般得到的只是 上一系列点 上的函数值 这只是一张函数表; 有的函数虽有解析表达式，但由于分析性质复杂,例如 的计算,找不到原函数,用牛顿-莱布尼兹公式不可行.,因此我们希望找到简单函数 近似 f(x). 通常我们用代数多项式或分段代数多项式作为 , 并使 这样确定的 就是我们希望得到的插值函数,即p(x)通过所有的离散点.,

2、若 p(x)为分段多项式，就是分段多项式插值。若 p(x) 为三角多项式，就称为三角插值。,插值法定义,设函数 在区间 上有定义，且 已知在点 上的值 若存在一个次数不超过n次的多项式 满足,则称 p(x) 为插值多项式，相应的插值法称为多项式插值。,插值区间,插值节点,插值条件,我们需要解决以下的问题:,p(x)是否存在?是否唯一? 如何构造 p(x)? 收敛性及分析误差 |f (x)-p(x)|?,插值多项式存在的唯一性 设 P(x) 是次数不超过n次的满足插值条件P(xi) =yi i =0, 1, , n , 得到的插值多项式. 用 Hn 代表所有次数不超过n 次的多项式集合， 于是

3、. 所谓次数不超过n次插值多项式P(x)存在且唯一， 就是指在集合 Hn中有且只有一个 P(x)满足插值条件.,限定次数,6.2 Lagrange 插值多项式,事实上,由插值条件可得 这是一个关于 的 元线性方程组。,此方程组的系数行列式,于是,此线性方程组有唯一解. 即次数不超过n次的插值多项式 存在且唯一.,范得蒙行列式,注: 如果不要求”次数不超过n次”, 满足插值条件的多项式就不唯一了. 例如:,Lagrange插值多项式的构造,一次插值 ，这时找一次多项式 , 使 满足条件 从几何上看，这就是过两点 的直线. 由解析几何知识知道，这条直线可用点斜式表示为,或写成,若记 ， 则 还可以

4、写成,称为插值基函数，且有如下特点 即,二次插值(n=2) 插值基函数,插值基函数特点:,一般情形,求作 n次多项式,称为Lagrange插值基函数.,次多项式 有 个零点 ，所以 其中 为待定常数，把 代入上式，注意到 ，得 则,一般地，因 次多项式 有 个零点: 且 ， 于是得 的 n次插值多项式可写成,易验证有 即 满足插值条件. 称 为拉格朗日（Lagrange）插值多项式， 称为以 为节点的拉格朗日（Lagrange）插值基函数。 上述构造插值多项式的方法称为基函数法。,例 已知如下数据,试构造三次插值多项式 L(x). 解,误差,分析,考察,易知,Lagrange 插值多项式的误差

5、分析,称为插值多项式的余项。,构造辅助函数,假设 f (x) 有直到 n+1阶的导数,有n+2个零点. 反复应用罗尔定理, 有,所以,由于 的具体位置不可能给出,通常考虑的是截断误差限.,解,n = 1,分别利用x0, x1 以及 x1, x2 计算,利用,这里,而,sin 50 = 0.7660444,外推 /* extrapolation */ 的实际误差 0.01001,利用,内插 /* interpolation */ 的实际误差 0.00596,内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。,n = 2,sin 50 = 0.7660444,2次插值的实际误差

6、0.00061,高次插值通常优于低次插值,但绝对不是次数越高就越好，嘿嘿,鉴赏Lagrange插值,1. 提供给我们构造插值多项式的一种方法: 利用基函数构造插值多项式. L(x)形式整齐、规范. 2. 误差分析中要求f (x)的高阶导数存在, 对于f (x)是由离散的点给出的情形或f (x)的导数不存在时, 无法分析误差. 3. 无承袭性. 增加一个节点,所有基函数需重新计算.,6.3 Newton插值多项式,差商的一个性质： （用归纳法易证） 对称性：,定义 差商,关键：找不同的元素相减作分母,构造差商表,n 次Newton插值公式,给定n+1个插值点(xi, f(xi), i = 0,

7、1, 2, n, xi互异， 类似地，有二阶至 n 阶差商的定义得 (xx0) (xx0)(xx1) (xx0)(xxn1) 上述所有n +1个等式相加，得,其中， 插值误差为：,n次Newton 插值公式,差商的性质,差商与导数的关系,Newton 插值多项式的误差,即:,例如,例 给定四个插值点(2,17), (0,1), (1,2), (2,19), 计算 N2(0.9), N3(0.9).,解,所以， N2(0.9) = 17 8(0.9+2)+3(0.9+2)0.9 = 1.63; N3(0.9) = N2(0.9)+1.250.9(0.9+2)(0.9 1)= 1.30375.,引

8、入差分定义: 向前差分、向后差分、中心差分. 差分与差商的关系. 差分的计算:做差分表. 利用差分表,写等距节点的Newton插值多项式.,等距节点的Newton插值多项式,等距节点的Newton插值公式与差分,一阶向前差分 /* forward difference */,一阶向后差分 /* backward difference */,一阶中心差分 /* centered difference */,当节点等距分布时:,一般地,称k阶差分的差分为k+1阶差分,如二阶向前和向后差分分别为,计算各阶差分可按如下差分表进行.,其中,差分具有如下性质,性质1(差分与函数值的关系) 各阶差分均可表示

9、为函数值的线性组合:,性质2(前差与后差的关系):,性质3(多项式的差分) 若f(x)Pn(n次多项式类), 则,性质4(差分与差商的关系):,性质5(差分与导数的关系）,(11),称公式(11)为Newton向前差分插值公式,其余项为,(12),利用这些性质,可将Newton公式进一步简化为,令x=xn-th, 则当x0 x xn时,0tn. 利用差商与向后差分的关系, 式(13)可简化为,(13),如果将Newton插值公式改为按节点xn,xn-1,x0的次序排列的Newton插值公式,即,其余项为,注：一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为表初公式和表末

10、公式。,称式(14)为Newton向后差分插值公式,(14),例 给定 f (x)在等距节点上的函数值表如下: xi 0.4 0.6 0.8 1.0 f(xi) 1.5 1.8 2.2 2.8 分别用Newton向前和向后差分公式求f(0.5)及f(0.9)的近似值. 解 先构造向前差分表如下: xi fi fi 2fi 3fi 0.4 1.5 0.6 1.8 0.3 0.8 2.2 0.4 0.1 1.0 2.8 0.6 0.2 0.1 x0=0.4, h=0.2, x3=1.0. 分别用差分表中对角线上的值和最后一行的值,得Newton向前和向后插值公式如下:,(1),(2),当 x=0.

11、5时,用公式(1),这时t=(x-x0)/h=0.5. 将t=0.5代入(1),得 f (0.5)N3(0.5)=1.64375. 当x=0.9时, 用公式(2), 这时t=(x3-x)/h=0.5. 将t=0.5代入(2), 得 f (0.9)N3(0.9)=2.46875.,鉴赏Newton插值多项式,1. Newton插值具有承袭性质，即,要计算各阶差商值.差商表易于用程序生成.,牛顿插值的误差不要求函数的高阶导数存在, 所以更具有一般性。它对 f(x)是由离散点给出的函数情形或 f(x)的导数不存在的情形均适用。,3. 引入记号: f x0 = f (x0) , t0(x) = 1,

12、t1(x) = x x0, t2(x) = (x x0)(x x1), , tn(x) = (x x0)(x x1) (x xn1)， 于是 n 次Newton插值公式可表为 称 t0(x), t1(x), t2(x), , tn(x) 为Newton插值的基函数.,练习：,提示：用Newton插值,6.4 Hermite 插值多项式,有的实际问题，构造插值函数除了函数值的条件以外，还要求在节点上的导数值相等，这种插值称为Hermite插值.,当函数 在区间 上的 个 节点 处函数值 及导数值 给定时，要求一个次数不超过 的多项式 满足,可以证明Hemite插值多项式是存在唯一的.,构造Her

13、mite插值多项式,采用Lagrange插值多项式中插值基函数的方法构造. 设,其中 都是次数不超过 的多项式，且满足 先确定,其中 为待定系数，由插值条件知, 在 处有 解之得,设,于是 再确定 类似的可以求得 所以,仿照Lagrange插值的讨论方法，可以得出埃尔米特插值的余项 表达式，设 在 存在 阶导数，则有,误差分析,例 设 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 多项式的思想，设,解

14、首先，P 的阶数 =,3,h0(x),有根,x1, x2，且 h0(x1) = 0 x1 是重根。,又: h0(x0) = 1 C0,h2(x),h1(x),有根 x0, x2 ,由余下条件 h1(x1) = 1 和 h1(x1) = 0 可解。,与h0(x) 完全类似。,有根 x0, x1, x2 ,与 Lagrange 分析完全类似,例 设 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), 并估计误差。,法二 分析 已知 x0 x1 x2,

15、 多项式 P(x) 满足 P(xi) = f (xi)，i = 0, 1, 2， 牛顿插值多项式N(x)= f(x0)+ fx0, x1(x-x0 ) + fx0, x1 , x2(x-x0 )(x-x1) , 设P(x) = N(x)+A(x-x0 )(x-x1)(x-x2) , 利用P(x1) = f (x1), 可解得A. 法三 可做带相同节点的差商表写插值多项式.,6.5 分段低次插值、三次样条插值,在区间 上用插值多项式 近似函数 ，是否 的次数越高，逼近效果越好呢，回答是否定的。由于次数越高计算工作量也越大，积累误差也越大；在整个区间上作个高次多项式，当局部插值节点的值有微小误差时

16、，就可能引起整个区间上函数值的较大变化，使计算不稳定(Runge现象)。,例如 给定函数 ，它在区间 上各价导数均存在，但在 上取 个等距节点 ，所作的拉格朗日插值多项式 如图所示，所给的是 的图形。,n 越大， 端点附近抖动 越大，称为 Runge 现象,解决方法之一:可用分段低次插值,例如:分段线性插值就是通过插值点用折线段连接起来 逼近 .设已知节点 上函数值 ，记 求一折线段满足,在小区间上都是线性函数,优点:分段低次插值很好的逼近f(x). 缺点:仅在节点处连续,光滑性的要求无法达到.,用分段线性插值逼近上述例子的效果，取 n =10。,相同数据3次样条插值与Lagrange插值效果

17、比较 Cubic Spline Interpolation Lagrange Interpolation,三次样条插值函数,分段低次插值，收敛性好，但光滑性不够理想。为了得到光滑度更高的插值函数，引入样条插值函数。“样条”名词来源于工程中船体和汽车等的外形设计： 给出外形曲线上的一组离散点(样点),(xi, yi),i = 0, 1, 2, , n, 将有弹性的细长木条或钢条(样条)在样点上固定,使其在其它地方自由弯曲,这样样条所表示的曲线,称为样条曲线(函数).,在数学上，它表现为近似于一条分段的三次多项式，它要求在节点处具有一阶和二阶连续导数。,定义 给定 a, b上 n +1个节点：a

18、= x0 x1 xn = b 及节点上的函数值 f(xi) = yi, i = 0, 1, 2, n, 若 S(x) 满足： (1) S(xi) = yi, i = 0,1, n ; (2) S(x)在xi, xi+1上至多是一个三次多项式； (3) S(x)C2a, b. 则称 S(x) 为 f(x) 关于节点 x0, x1, xn 的三次样条插值函数，称 xi 为样条节点。,在xi, xi+1上构造一个三次多项式,共有 4n 个未知量，因此需要 4n 个条件。 由定义中的 (1)知，有n+1个条件； 由定义中的 (3) 知，有3n 3个条件，即 再附加2个边界条件，就可得到4n个条件。三次

19、分段样条插 值函数可唯一确定。 M关系式：用节点处的二阶导数表示样条插值函数。 m关系式：用节点处的一阶导数表示样条插值函数。,M关系式,引入记号： 因为 S(x) 为 xi, xi+1 上的三次多项式, 所以,S(x)为一次函数, 我们用节点上的二阶导数值 Mi 表示线性函数。设 其中， 对(1.29)积分两次, 得,将S(xi) = yi, S(xi+1) = yi+1,代入(1.30)得到二元一次方程组, 解得,将 C，D 代入(1.30)式，得到 xi, xi+1 上的三次样条插值函数,在 xi 点， 左导数 = 右导数,(1.32)式为 n +1个未知数 M0, M1, Mn 的 n -1个方程组，补充两个边界条件后，方程组(1.32)就有唯一解。,三弯矩方程,Mj在力学上解释为细梁在xj截面处的弯矩,下面给出三种边界条件： (1) 给定 M0, Mn的值， 可以得到 n -1个未知量的 n -1个方程的方程组,对角占优的三对角带状矩阵,可用追赶法求解,M0=0, Mn=0时，