1、Ch6 插值法,6.1 引言6.2 拉格朗日插值多项式6.3 牛顿插值多项式6.4 埃尔米特插值多项式6.5 分段低次插值、三次样条插值多项式,6.1 引言 许多实际问题都用函数 来表示某种内在规律的数量规律的数量关系，其中相当一部分函数是通过实验或观测的得到的.一般得到的只是 上一系列点 上的函数值 这只是一张函数表; 有的函数虽有解析表达式，但由于分析性质复杂,例如 的计算,找不到原函数,用牛顿-莱布尼兹公式不可行.,因此我们希望找到简单函数 近似 f(x).通常我们用代数多项式或分段代数多项式作为 ,并使 这样确定的 就是我们希望得到的插值函数,即p(x)通过所有的离散点.,若 p(x)
2、为分段多项式，就是分段多项式插值。若 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次插值的实际误差 0.00061,高次插值通常优于低
6、次插值,但绝对不是次数越高就越好，嘿嘿,鉴赏Lagrange插值,1. 提供给我们构造插值多项式的一种方法:利用基函数构造插值多项式.L(x)形式整齐、规范.2. 误差分析中要求f (x)的高阶导数存在, 对于f (x)是由离散的点给出的情形或f (x)的导数不存在时, 无法分析误差.3. 无承袭性. 增加一个节点,所有基函数需重新计算.,6.3 Newton插值多项式,差商的一个性质： （用归纳法易证）对称性：,定义 差商,关键：找不同的元素相减作分母,构造差商表,n 次Newton插值公式,给定n+1个插值点(xi, f(xi), i = 0, 1, 2, n, xi互异， 类似地，有二阶
7、至 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(差分与函数值的关系) 各阶差分均可表示为函数值的线性组合:,性质2(前差与后差的关系):,性质3
9、(多项式的差分) 若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 时用后插，故两种公式亦称为表初公式和表末公式。,称式(14)为Newton向后差分插值公式,(14
10、),例 给定 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.5时,用公式(1),这时t=(x-x0)/h=0.5. 将t
11、=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, t1(x) = x x0, t2(x) = (x x0)(x
12、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插值多项式是存在唯一的.,构造Hermite插值多项式,采用Lagrange插值多项式中插值基函数的方
13、法构造.设,其中 都是次数不超过 的多项式，且满足先确定,其中 为待定系数，由插值条件知, 在 处有解之得,设,于是再确定类似的可以求得所以,仿照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 多项式的思想，设,解 首先，P 的阶数 =,3,h0(x),有根,x1, x2，且 h0(x1) =
14、 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, 多项式 P(x) 满足 P(xi) = f (xi)，i = 0, 1, 2，
15、牛顿插值多项式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 分段低次插值、三次样条插值,在区间 上用插值多项式 近似函数 ，是否 的次数越高，逼近效果越好呢，回答是否定的。由于次数越高计算工作量也越大，积累误差也越大；在整个区间上作个高次多项式，当局部插值节点的值有微小误差时，就可能引起整个区间上函数值的较大变化，使计算不稳定(Runge现象)。,例如 给定函数
16、 ，它在区间 上各价导数均存在，但在 上取 个等距节点 ，所作的拉格朗日插值多项式 如图所示，所给的是 的图形。,n 越大，端点附近抖动越大，称为Runge 现象,解决方法之一:可用分段低次插值,例如:分段线性插值就是通过插值点用折线段连接起来逼近 .设已知节点上函数值 ，记 求一折线段满足,在小区间上都是线性函数,优点:分段低次插值很好的逼近f(x).缺点:仅在节点处连续,光滑性的要求无法达到.,用分段线性插值逼近上述例子的效果，取 n =10。,相同数据3次样条插值与Lagrange插值效果比较Cubic Spline Interpolation Lagrange Interpolatio
17、n,三次样条插值函数,分段低次插值，收敛性好，但光滑性不够理想。为了得到光滑度更高的插值函数，引入样条插值函数。“样条”名词来源于工程中船体和汽车等的外形设计： 给出外形曲线上的一组离散点(样点),(xi, yi),i = 0, 1, 2, , n, 将有弹性的细长木条或钢条(样条)在样点上固定,使其在其它地方自由弯曲,这样样条所表示的曲线,称为样条曲线(函数).,在数学上，它表现为近似于一条分段的三次多项式，它要求在节点处具有一阶和二阶连续导数。,定义 给定 a, b上 n +1个节点：a = x0 x1 xn = b 及节点上的函数值 f(xi) = yi, i = 0, 1, 2, n,
18、 若 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个条件。三次分段样条插 值函数可唯一确定。 M关系式：用节点处的二阶导数表示样条插值函数。 m关系式：用节点处的一
19、阶导数表示样条插值函数。,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在力学上解释为细梁在
20、xj截面处的弯矩,下面给出三种边界条件： (1) 给定 M0, Mn的值， 可以得到 n -1个未知量的 n -1个方程的方程组,对角占优的三对角带状矩阵,可用追赶法求解,M0=0, Mn=0时，称为自然边界条件,(2) 给定条件：S(x0) = m0, S(xn) = mn, 分别由x0, x1, xn-1, xn上的三次样条插值函数 此二式和(1.32)组成 n+1 个方程的方程组：,（3）若 f(x)为以 xn-x0 为周期的周期函数，即 y0 = yn，则要求S(x) 也为周期函数，即S(x0) = S(xn), 于是有 即 m0 = mn, M0 = Mn, 此时(1.32)变为n个
21、未知量、n个方程的方程组。,即为关于M0, M1,Mn的等式,例 已知离散点: (1.1, 0.4000), (1.2, 0.8000), (1.4, 1.6500), (1.5, 1.8000), 取自然边界条件 M0 = Mn = 0, 构造三次样条插值函数，并计算 f(1.25).,解 n = 3. h0= x1- x0 = 0.1, h1= 0.2, h2=0.1,因此，分段的三次样条插值函数为,m关系式 用一阶导数表示的样条插值函数,给定插值点 (xi, yi), 设S (xi) = mi, i = 0,1,2, n, 则 xi, xi+1上的三次Hermite插值为 利用S(x)在节点处连续,二阶导数连续,及边界条件确定出 m0, m1, mn, 可得a, b上的三次样条插值.,mj细梁在xj截面处的转角,三种边界条件：,三转角方程,三次样条插值是低次的插值,在节点处有很好的光滑性. 如果 f(x)C a,b ,三次样条插值 S(x)在a,b上一致收敛到 f(x),
