数值分析02插值ppt课件.ppt

第二章,插值,1 引 言,一、引例,已经测得在某处海洋不同深度处的水温如下：深度（M） 466 741 950 1422 1634水温（oC）7.04 4.28 3.40 2.54 2.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米）处的水温.,这就是本章要讨论的“插值问题”,二、插值问题的定义,当精确函数 y = f(x) 非常复杂或未知时，在区间,这个问题称为“插值问题”,(2.1.1),近似函数 g(x) f(x)，满足条件,由此构造一个简单易算的,上一系列节点 处测得函数值,这里的 g(x) 称为f(x) 的插值函数。,节点 x0 xm称为插值节点,条件（2.1.1)称为插值条件，区间 称为插值区间。,插值函数的类型有很多种,最常用的插值函数是 ?,代数多项式,用代数多项式作插值函数的插值称为代数插值，即选取次数不超过n的多项式 Pn(x) ，使得 Pn (xj) = yj (j = 0, 1 n) (2.1.2),本章主要讨论的内容,插值问题,插值法,插值函数,2 代 数 插 值,代数插值,一、插值问题解的存在唯一性？二、插值多项式的常用构造方法？三、插值函数的误差如何估计？,一、插值多项式的存在唯一性：,设所要构造的插值多项式为：,由插值条件,得到如下线性代数方程组：,此方程组的系数行列式为,因此，Pn(x) 由a0, a1, an唯一确定。,范得蒙行列式 ！,定理,(唯一性) 满足 的 n 阶插值,多项式Pn(x)存在且唯一。,注：通过解上述方程组求得插值多项式 的方法,怎样可以不通过求解方程组而获得插值多项式呢?,（可能是病态方程组）, 当阶数n越高时，病态越重。,并不可取.这是因为当n较大时解方程组的计算量,较大，而且方程组系数矩阵的条件数一般较大,在n次多项式空间Pn中找一组合适的基函数 ,使,不同的基函数的选取导致不同的插值方法.,Lagrange插值,Newton插值,二、拉格朗日(Lagrange)插值,1线性插值 (n=1),x0,x1,(x0 ,y0),(x1 ,y1),f(x),P1(x),n = 1,已知 x0 , x1 ; y0 , y1 ，求,l0(x),l1(x),2抛物插值(n=2),p2(x) f(x),因过三点的二次曲线为抛物线，故称为抛物插值。,3n次拉格朗日插值公式,设连续函数y = f（x）在a, b上对给定n + 1个,不同结点： x0, x1, , xn ,分别取函数值,y0, y1, , yn,其中 yi = f (xi) i = 0, 1, 2, n,试构造一个次数不超过n的插值多项式,使之满足条件,i = 0, 1, 2, n,若能求得n次多项式lk (x) , k = 0, 1, n，,则,i = 0, 1, 2, n,即Pn (x)满足插值条件（2.1.2）.,满足,因此，令,又由lk (xk) = 1，得：,的表达式推导：,根据lk (x)的定义，xk以外所有的结点都是lk (x)的根，,从而得 n 阶拉格朗日（Lagrange）插值公式：,4 、插值余项/* Remainder */,定理4.3.1 若,在a , b内存在, 则在a , b上的,n+1个互异的点，对 f（x) 所作的n次Lagrange插值多项式 有误差估计,注： 通常不能确定 , 而是估计 ,x(a,b)，将 作为误差估计上限。,当 f(x) 为任一个次数 n 的多项式 时， , 可知 ，即插值多项式对于次数 n 的多项式是精确的。,解：,n = 1,分别利用x0, x1 以及 x1, x2 计算,利用,利用,计算得：sin 50 0.76008,sin 50 = 0.7660444,利用x0, x1 作为插值节点的实际误差 0.01001,利用x1, x2作为插值节点的实际误差 0.00596,n = 2,sin 50 = 0.7660444,2次插值的实际误差 0.00061,三、牛顿插值（Newtons Interpolation ）,Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数li(x) 都需要重新计算。,希望每加一个节点时，只附加一项上去即可。,1引入,能否重新在 中寻找新的基函数 ？,利用插值条件 代入上式，得关于 的线性代数方程组:,设,当 互异时，系数矩阵非奇异，且容易求解,How complex the expression are!,2差商,2.1 差商的定义(亦称均差),定义1：设有函数f (x)以及自变量的一系列,的值 f(xi) , 称,为f (x)在点xi , xj处的一阶差商，并记作f xi , xj，,互不相等的 （即在 时， ）,又称,为f (x)在点xi, xj, xk处的二阶差商,称,为f (x)在点x0, x1, xk处的k阶差商。,利用插值条件和差商的定义,可求出 的系数 :,从而,因此，每增加一个结点，Newton插值多项式只增加一项，克服了Lagrange插值的缺点。,差商可列表计算：,f (x0)f (x1)f (x2)f (xn1)f (xn),f x0, x1f x1, x2 f xn1, xn,f x0, x1 , x2 f xn2, xn1, xn,f x0, , xn,xi,yi,一阶差商,二阶差商,n 阶差商, ,xn+1 f (xn+1) f xn, xn+1 f xn1, xn, xn+1 f x1, , xn+1 f x0, , xn+1,由差商定义可知： 高阶差商是两个低一阶差商的差商。,例: 给定 的数据表 2.20 2.40 2.60 2.80 3.00 0.78846 0.87547 0.95551 1.02962 1.098611.构造差商表2.分别写出二次、四次Newton插值多项式,解:差商表,一阶差商,二阶差商,三阶差商,四阶差商,2.2 差商的性质:,性质1(差商与函数值的关系): 记 ,则,性质2 （对称性）： 差商的值与结点排列顺序无关，即,性质3 (差商与导数的关系):,设 在 上有 阶导数,且,则存在 使得,性质4 (特征定理):,3.牛顿差值余项,由插值多项式的唯一性可知 ， 故其余项也相同，即,定理： Newton插值多项式的余项为,其中,四、等距节点插值,1引入(微商的离散化),2差分的定义,设函数 在等距节点 上的,值 为已知,这里 为常数,称为步长.,定义: 偏差,分别称为 在 处以 为步长的向前差分,向后差分,以及中心差分.,3、差分表,计算各阶差分可按如下差分表进行：,4、差分的性质,性质1 (差分与函数值的关系): 各阶差分均可表示 为函数值的线性组合:,其中，,性质2 (前差与后差的关系):,性质3 (多项式的差分): 若 f(x)Pn (n次多项式类), 则,性质4 (差分与差商的关系): 在等距节点的前提下，,性质5 (差分与导数的关系）：在等距节点的前提下，,性质6：常数的差分等于零.,性质7：差分算子为线性算子，即,性质8：,这个性质类比于,性质9：,（类比于分部积分法则 ）,5、等距节点的牛顿插值公式,牛顿公式:, 牛顿前插公式,利用差分的性质, 可将Newton公式简化为,(1),称公式(1)为Newton向前差分插值公式,其余项为,(2), 牛顿后插公式,如果将Newton插值公式改为按节点 的,(3),次序排列的Newton插值公式,即,令x=xn-th, 则当x0 xxn时,0tn. 利用差商与向后差分的关系, 式(3)可简化为,(4),称式(4)为Newton向后差分插值公式。,其余项为,注：一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为表初公式和表末公式。,例 给定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=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.,五、Hermite 插值,1引入,在实际问题中，对所构造的插值多项式，不仅,要求函数值重合，而且要求若干阶导数也重合。,即：要求插值函数 P(x) 满足:,（1）,把此类插值多项式称为,带导数的插值多项式，记为H (x)。,埃米尔特（Hermite）插值多项式或称,H (x) 存在且唯一,2.推导,只讨论函数值与导数值个数相等的情况.,设在节点 上,要求插值多项式 ,满足条件,(5),这里给出的 个条件,可唯一确定一个次数不超过 的多项式 其形式为,如根据条件(5)来确定 个系数 ,显然非常复杂,因此,仍采用求Lagrange插值多项式的基函数方法.,先求插值基函数 及 ,共有 个,每一个基函数都是 次多项式,且满足条件,(6),于是满足条件(5)的插值多项式 可写成用插值基函数表示的形式,即,(7),由条件(6),显然有,下面的问题就是求满足条件(6)的基函数 及 为此,可利用Lagrange插值基函数 .令,其中 是式,所表示的基函数.由条件式(6),有,整理,得,解得,由于,两端取对数再求导,得,于是,同理可得,(8),(9),3. Hermite 插值余项,还可以证明满足条件(5)的插值多项式是唯一的.,用反证法,假设 及 均满足条件(5),于是,在每个节点 上均有二重根,即 有 重根.,但 是不高于 次的多项式,故 .,唯一性得证.,仿照Lagrange插值余项的证明方法,作为带导数插值多项式(7)的重要特例是n=1的情形.,这时可取节点为 及 ,插值多项式为 ,满足条件,(11),相应的插值基函数为 ,它们满足条件,根据(8)式及(9)式的一般表达式,可得,于是满足条件(11)的插值多项式是,其余项为 ,由式(10)得,注： N 个条件可以确定 阶多项式。,其余项为,N 1,要求在1个节点 x0 处直到m0 阶导数都重合的插值多项式即为 在 点处的Taylor多项式,4.举例,例：设 x0 x1 x2, 已知 , 求多项式 P(x)满足,解：首先，P 的阶数为3, 模仿 Lagrange 多项式的 思想，设,其中,且 , 并估计误差。,h0(x),有根,x1, x2，且 x1 是重根。,又: h0(x0) = 1 C0,h2(x),与h0(x) 完全类似。,h1(x),有根 x0, x2 ,由余下条件 h1(x1) = 1 和 可解。,有根 x0, x1, x2,又: C1 可解。,与 Lagrange 分析完全类似,解:设,hi(x),一般地，已知 x0 , , xn 处有 y0 , , yn 和 ，求 H2n+1(x),满足 。,其中,由余下条件 和 可解Ai 和 Bi ,这样的Hermite 插值唯一,有根 x0 , , xn, 除了xi 外都是2重根 ,设,则,六、分段低次插值,1.多项式插值的龙格现象,例：在5, 5上考察 的Ln(x)。取,n 越大，端点附近抖动越大，称为Runge 现象,2. 分段线性插值,在每个区间 上，用1阶多项式 (直线) 逼近 f (x):,记 ,易证：当 时，,一致,y= f(x),y=p(x),若令,则 是分段一次的连续函数且满足条件,则 即为分段线性插值的基函数,基函数 只在 附近不为零,在其它地方均为零。,这种性质称为局部非零性质。相应的分段线性插值,函数为：,分段线性插值的误差估计,定理1 如果 在 上二阶连续可微,则分段线性插值函数 的余项有以下估计,其中,3. 分段三次Hermite插值,给定节点 ， 在节点 上的函数值及导数值分别为 。,其中基函数为,是分段三次，总体是直至一阶导数连续，插值函数为,在每个子区间 上作两点三次Hermite插值，因此,七、三次样条插值,1.引入,要求：插值曲线既要简单，又要在曲线的连接处比较光滑。,这样的分段插值函数在分段上要求多项式次数低，,这种插值方法称为样条插值。,它所对应的曲线称为样条曲线，其节点称为样点，,把满足这样条件的插值函数，称为样条插值函数，,而在节点上不仅连续，还存在连续的低阶导数，,定义：设对y = f (x)在区间a, b上给定一组节点,a = x0 x1 x2 xn = b和相应的函数值y0, y1, yn，,如果s(x)具有如下性质：,（1）在每个子区间xi-1, xi (i = 1, 2, n)上s (x)是不高 于三次的多项式,（2）s (x)，s (x)，s (x)在 a, b上连续；则称s (x)为三次样条函数.如再有,（3） s (xi ) = f (xi) (i = 0, 1, 2, n)， 则称s (x)为y = f (x)的三次样条插值函数。,注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f 在所有插值点的导数值。,S(x),H(x),f(x),2. 三弯矩方程,设f (x)是定义在 a, b区间上的一个二次连续可微函数，,为分划：,在每一个小区间xi-1, xi i = 1, n 上都是三次多项式，,S (x)在 xi-1, xi 上的表达式为：,其中 ，将（12）两次积分得：,（12）,Ai 和Bi 为积分常数。,因为,所以它满足方程：,（13）,求 Mi，确定S (x)的表达式。微分（13）式,于是,（14）,则（13）可以写为,各项除以hi + hi+1，并记,3. 边界条件,（1）D1-样条：给定两端点导数值,于是可得,有,分别补充为方程组（13）的第一个和最后一个方程组，得D1-样条的三弯矩方程为：,（2）D2-样条：给定边界条件,得三弯矩方程,若取 M0 = Mn=0，称为三次自然样条。,（3）周期样条：若f(x0 ) = f (xn), 则可将s (x0 ) = f (x0) 或 s (xn ) = f (xn) 去掉，,再加入条件,可得周期样条的三弯矩方程,补充（13）中的最后及第一个方程,经补充后的方程组（13）为,（14）,其中，对端点条件，有,对端点条件，有,（14 ）是一个三对角方程组，可用追赶法解之。,此方程组系数严格对角占优 ！从而存在唯一解。,求出了Mi (i = 0, 1, n)，也就求得了S (x)在各个小区间的表达式Si (x)（i = 0, 1, 2, n）,4.算法,若取等距节点 hi = h, i = 1, n 1,（1） i = 1, 2, , n,hi = xi xi-1,（2） i = 1, 2, n,（3）解n 1阶三对角方程组，得,M1 , M2 , Mn-1,代入端点条件计算M0 , Mn,（4）,若取 ，计算,5. 三次样条插值函数的收敛性,定义: 设 是区间 上的连续函数，记,函数 的范数.,为,定理 设被插值函数 为满足边界,条件或的3次样条插值函数，则在插值区间,上成立余项估计式,其中,