[理学]李庆扬数值分析——插值法.ppt

描述事物之间的数量关系：函数有两种情况：一是表格形式——一组离散的数据来表示函数关系；另一种是函数虽然有明显的表达式，但很复杂，不便于研究和使用从实际需要出发：对于计算结果允许有一定的误差，可以把函数关系用一个简单的便于计算和处理的近似表达式来代替，从而使问题得到简化一般地，构造某种简单函数代替原来函数插值法就是一种基本方法,§0 引言,第二章 插值（Interpolation）法,,当精确函数 y = f(x) 非常复杂或未知时，在一系列节点 x0 … xn 处测得函数值 y0 = f(x0), … yn = f(xn)，由此构造一个简单易算的近似函数 g(x)  f(x)，满足条件g(xi) = f(xi) (i = 0, … n)这里的 g(x) 称为f(x) 的插值函数g(x)  f(x),,根据实际需要，可以用各种不同的函数来近似原来的函数最常用的插值函数是 …?,多项式：,代数多项式最简单，计算其值只需用到加、减乘运算，且积分和微分都很方便；所以常用它来近似表示表格函数(或复杂函数),这样的插值方法叫做代数插值法，简称插值法§1 拉格朗日多项式,n = 1,可见 P1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。

1.1 线性插值,两点式,点斜式,1.2 二次插值,n = 2,为求P2(x),将三点代入其表达式,即可得到三个方程式,从而联立方程组解出系数a0, a1, a2即可:,,方程组的解是否存在? 若存在解,是否唯一?!,当 x0 , x1 , x2互异时,方程组的解存在且唯一.,注：显然有, 求n 次插值时, 由n +1个点可有n +1个方程, 联立方程组即可求出插值多项式的n +1个系数.然而,方程组的求解也并不是一件容易的事1.2.1 待定系数法,对于线性插值的两种形式解进行适当的分析, 从中寻求规律而得到启发,就有了所谓的拉格朗日插值法(公式)和牛顿插值(公式).,,我们先来看看如何得到二次拉格朗日插值公式（和牛顿插值公式（为讨论方便，留待后述））.,,首先, 线性插值的两点式可看作是两个特殊的一次式的一种线性组合.,两点式,的一次插值多项式 ,称l0(x)和l1(x)为以x0,x1为节点的基本插值多项式，也称为线性插值的插值基函数 于是，线性插值即是用基函数的线性组合来构造的.,1.2.2 基函数法,称为拉氏基函数 ，满足 li(xj)=ij,显然有l0(x)+ l0(x)≡1.,这里， l0(x)和l1(x)具有如下性质：,l0(x0)=1, l0(x1)=0, l1(x0)=0, l1(x1)=1,,由此启发，我们希望二次插值也能由一些二次插值基函数来线性组合:,这时，l0(x), l1(x), l2(x)都是二次多项式，且应满足,满足(2.1)式的 l i(x) 是否存在?若存在，具有什么形式呢?,（2.1）,同理可得,l1(x)＝ 1(x －x0)(x －x2),,l2(x)＝ 2(x －x0)(x －x1),,此即二次拉格朗日插值公式, 其中, l0(x), l1(x), l2(x)是满足(2.1)的特殊(基本)二次插值多项式;称为二次插值基函数.,,先考虑 l0(x)。

因 l0(x)是以 x1, x2 为零点的二次多项式,所以它可写成 l0(x)＝ 0(x －x1)(x －x2), 其中0 是待定系数 又因为 l0( x0)=1，所以0(x0－x1)(x0－x2)＝1，则可有,l0(x)＝ 0(x －x1)(x －x2),,,,n  1,,,,拉格朗日 多项式,与 有关，而与 无关,节点,f,1.3 n 次插值,证明： ( 存在性可利用Vandermonde 行列式论证),反证：若不唯一，则除了Ln(x) 外还有另一 n 阶多项式 Pn(x) 满足 Pn(xi) = yi 考察 则 Qn 的阶数, n,而 Qn 有 个不同的根,,注：若不将多项式次数限制为 n ，则插值多项式不唯一例如 也是一个插值多项式，其中 可以是任意多项式Rolle’s Theorem: 若 充分光滑， ，则 存在 使得 。

推广：若,,使得,,Rn(x) 至少有 个根,n+1,(t)有 n+2 个不同的根 x0 … xn x,,注意这里是对 t 求导,,,,注： 通常不能确定 x , 而是估计 , x(a,b)将 作为误差估计上限当 f(x) 为任一个次数 n 的多项式时， , 可知 ，即插值多项式对于次数 n 的多项式是精确的例1 求经过A(0,1)，B(1,2)，C(2,3)三个插值点的插值多项式.,解：三个插值节点及对应的函数值为,由抛物插值公式得,解：,,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,高次插值通常优于低次插值,但绝对不是次数越高就越好，嘿嘿……,例3 考虑下述的插值法问题：求二次多项式P(x)，满足P(x0) = y0, 其中 是已给的数据并给出使这一问题的解存在且唯一的条件.,解：设 则 由已知条件有,即 所以,故原问题的唯一可解性就归结为上述方程组的唯一可解性而后者唯一可解的充要条件为,这就是P（x）存在且唯一的条件回顾 拉格朗日插值公式,1.5 拉格朗日插值公式的优缺点,n  1,,,,拉格朗日 多项式,与 有关，而与 无关,节点,f,拉格朗日插值公式,Lagrange插值公式(利用插值基函数很容易得到):含义直观,结构紧凑,在理论分析中非常方便;计算机上实现也很容易.,也有一些缺点：一是计算量大，这是显然的；另外，还有一个更严重的缺点，当插值节点增加时，全部插值基函数均要随之变化，整个计算工作必须从头开始：不仅原来的每一项都要改变，还要增加一项计算。

为克服上述两个缺点,努力：把插值多项式变形为便于计算的形式希望：计算改变的过程中,尽可能能利用已有的计算结果.下面我们将看到,这是可能的我们可以有具有“承袭性”的所谓牛顿公式差 商,,二次牛顿插值多项式,我们再看线性插值的点斜式:,常数(差商),由此启发，我们希望二次插值也能类似地有有规律的组合表达式:,P2(x)=0 + 1(x-x0) + 2(x-x0)(x-x1),利用P2(x0)=y0有: 0 = y0 ,,利用P2(x1)=y1有: 1 =,= f[x0,x1] ,,利用P2(x2)=y2有: 2 =,f[x0,x1],= f[x0,x1,x2] ;,f[x0,x2],x=x0时,0,,,注:1. 事实上,从上述可看出二次牛顿插值公式是用待定系数法求得的;2. 它也可看作是三个特殊函数的一种线性组合:,本质上还是基函数法.,更一般地，n+1个节点的插值多项式，我们希望由上述类似的一组特殊函数：,来线性组合为：,那么其组合系数是什么样的呢？怎么求呢？,我们同样可用待定系数法. 容易发现, 计算a0, a1, a2 ,…, an 是很有规律的.,一、均差及其性质,§2 牛顿插值,当x=x0时，Pn(x0)=a0=f0.,当x=x1时，Pn(x1)=a0+a1(x1-x0)=f1, 推得,当x=x2时，Pn(x2)=a0+a1(x2-x0)+a2(x2-x0)(x2-x1)= f2,推得,依次递推可得到a3, …, an. 为写出系数 ak的一般表达式,先引进如下均差定义.,均差有如下的基本性质:,1º k 阶均差可表示为函数值f(x0), f(x1),…, f(xk)的线性组合,即,这个性质可用归纳法证明. 这个性质也表明均差与节点的排列次序无关,称为均差的对称性,即,f[x0,x1,…,xk]= f[x1,x0,x2,…,xk]=… = f[x1, …, xk ,x0],3º 若f(x)在[a,b]上存在n阶导数, 且节点x0,x1,…,xn [a,b],则n阶均差与导数关系如下:,这个公式可直接用罗尔定理证明.,所以,,… … … …,,,Nn(x),,Rn(x),ai =,f [ x0, …, xi ],二、牛顿插值公式,Rn(x),Nn(x),,ωn+1(x),多项式Nn(x)显然满足插值条件,即Nn(xj)=f(xj),(j=1,…, n),且次数不超过n,由唯一性定理它就是前述的Ln(x),其系数为,Nn(x)称为牛顿均差插值多项式,它比拉格朗日插值多项式计算量省,且便于程序设计.,注： 由唯一性可知 Nn(x)  Ln(x)， 只是算法不同，故其余项也相同，即,, 实际计算过程为,f (x0) f (x1) f (x2) … f (xn1) f (xn),f [x0, x1] f [x1, x2] … … … … f [xn1, xn],f [x0, x1 , x2] … … … … f [xn2, xn1, xn],f [x0, …, xn],f (xn+1) f [xn, xn+1] f [xn1, xn, xn+1] f [x1, …, xn+1] f [x0, …, xn+1],均差计算可列均差表如下：,,例1 依据如下函数值表建立不超过3次的拉格朗日插值多项式及牛顿插值多项式Nn(x),并验证插值多项式的唯一性.,解: (1)拉格朗日插值多项式Ln(x).,插值基函数,拉格朗日插值多项式为:,(2) 牛顿插值多项式Nn(x).,建立如下差商表,牛顿插值多项式为:,(3) 唯一性验证.,通过比较牛顿插值多项式和拉格朗日插值多项式,知:Nn(x) = Ln(x) 这一事实与插值多项式的唯一性一致.,2, 等距节点插值公式,向前差分,向后差分,中心差分,其中,当节点等距分布时:, 差分的重要性质：, 线性：例如, 若 f (x)是 m 次多项式，则 是 次多项式，而, 差分值可由函数值算出：, 函数值可由差分值算出：,,牛顿公式, 牛顿前差公式, 牛顿后差公式,将节点顺序倒置：,注：一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为表初公式和表末公式。

§3 厄尔米特插值,不仅要求函数值重合，而且要求若干阶导数也重合 即：要求插值函数  (x) 满足 (xi) = f (xi), ’ (xi) = f ’ (xi), …, (mi) (xi) = f (mi) (xi).,。