数值分析PPT课件第2章 插值法.ppt

《数值分析PPT课件第2章 插值法.ppt》由会员分享，可在线阅读，更多相关《数值分析PPT课件第2章 插值法.ppt（91页珍藏版）》请在三一办公上搜索。

1、在工程技术与科学研究中，常会遇到函数表达式过于复杂而不便于计算，且又需要计算众多点处的函数值；或已知由实验（测量）得到的某一函数 y=f(x)在区间a,b中互异的n+1个xi ( i=0, 1, . ,n)处的值yi=f(xi) (i=0,1,.,n), 需要构造一个简单易算的函数P(x)作为y=f(x)的近似表达式,y=f(x)P(x) , 使得 P(xi)= f(xi) = yi (i=0,1, ., n),这类问题就称为插值问题， P(x)称为插值函数， P(x)一般取最简单又便于计算得函数。,第2章 插 值 法,P(x) f(x),f(x),y=f(x)P(x) , 使得 P(xi)=

2、 f(xi) = yi (i=0,1, ., n) 其它点 P(x) f(x) = y,2.1.1 插值问题,设 y= f(x) 是区间a , b 上的一个实函数, xi ( i=0, 1, . ,n)是a,b上n+1个互异实数,已知 y=f(x) 在 xi 的值 yi=f(xi) (i=0,1,.,n), 求一个次数不超过n的多项式Pn(x)使其满足,Pn(xi)=yi (i=0,1, ., n) (5-1),这就是多项式插值问题.,2.1 引言,其中Pn(x) 称为 f(x) 的n次插值多项式, f(x) 称为被插函数, xi(i=0,1, .,n)称为插值节点, (xi, yi) (i=

3、0,1, ,n) 称为插值点, a,b 称为插值区间, 式(5-1)称为插值条件。,从几何意义来看,上述问题就是要求一条多项式曲线 y=Pn(x), 使它通过已知的n+1个点(xi,yi) (i=0,1, ,n),并用Pn(x)近似表示f(x).,即 P(x)=a0+a1x+a2x2+.+anxn,其中ai为实数，就称P(x) 为 插值多项式，相应的插值法称为多项式插值，若P(x)为分段的多项式，就称为分段插值，若P(x)为三角多项式,就称为三角插值，本章只讨论插值多项式与分段插值。,本章主要研究如何求出插值多项式，分段插值函数，样条插值函数；讨论插值多项式P(x)的存在唯一性、收敛些及误差估

4、计等。,定理1 设节点 xi (i=0,1, ,n)互异, 则满足插值条件 Pn(xi)=yi (i=0,1, ., n)的次数不超过n的多项 式存在且唯一.,证 设所求的插值多项式为,Pn(x)=a0+a1x+a2x2+.+anxn (5-2),则由插值条件式Pn(xi)=yi (i=0,1, ., n) 可得关于系数a0 ,a1 , ,an的线性代数方程组,2.1.2 插值多项式的存在性和唯一性,此方程组有n+1个方程, n+1个未知数, 其系数行列式是范德蒙(Vandermonde)行列式：,（5-3）,由克莱姆法则知方程组 (5-3) 的解存在唯一. 证毕。,考虑最简单、最基本的插值问

5、题.求n次插值多项式 l i(x) (i=0,1, ,n),使其满足插值条件,2.2.1 基函数,可知, 除 xi点外, 其余都是 li(x)的零点, 故可设,Lagrange法1736-1813,2.2 拉格朗日插值,其中A为常数, 由li(xi)=1可得,称之为拉格朗日基函数, 都是n次多项式 。,n=1时的一次基函数为:,即已知函数 f(x)在点x0和x1点的函数值 y0=f(x0)，y1=f(x1).,求线性函数 L(x)=a0+ a1x使满足条件：L(x0)=y0 , L(x1)=y1.,此为两点线性插值问题,或用直线的两点式表示为：,插值基函数的特点：,记,n=2时的二次基函数为

6、:,可知其满足,2.2.2 拉格朗日插值多项式,利用拉格朗日基函数l i(x), 构造次数不超过n的多项式,称为拉格朗日插值多项式,再由插值多项式的唯一性,得,特别地, 当 n =1时又叫线性插值,其几何意义为过两点的直线. 当 n =2时又叫抛物（线）插值, 其几何意义为过三点的抛物线.,注意 :(1) 对于插值节点,只要求它们互异,与大小次序无关;,以 xi (i=0,1,n)为插值节点, 函数 f(x) 1作插值多项式, 由插值多项式的唯一性即得基函数的一个性质,(2) 插值基函数l i(x) 仅由插值节点xi (i=0,1, ,n)确定, 与被插函数 f(x)无关;,(3) 插值基函数

7、l i(x) 的顺序与插值节点xi (i=0,1, ,n) 的顺序一致.,这是因为若取(x)=xk (k=0,1,n),由插值多项式的唯一性有,特别当k=0时,就得到,所以,例1 已知 用线性插值(即一次插值多项式)求 的近似值。,插值多项式为,( ),例2 求过点(-1,-2), (1,0), (3,-6), (4,3)的抛物线插值(即三次插值多项式).,解 以,以为节点的基函数,分别为:,则拉格朗日的三次插值多项式为,截断误差Rn(x)=f (x) -Ln(x)也称为n次Lagrange插值多项式的余项。以下为拉格朗日余项定理。,定理2 设 f (x) 在区间 a ,b上存在 n+1 阶导

8、数, xi a, b (i=0,1, , n) 为 n+1个互异节点, 则对任何x a ,b, 有,2.2.3 插值余项,且与x有关),证 由插值条件和n+1(x) 的定义, 当x=xk 时 , 式子显然成立, 并且有 n+1(xk)=0 ( k=0,1,n ), 这表明x0 , x1, , xn 都是函数n+1(x) 的零点, 从而 n+1(x) 可表示为,其中K(x)是待定函数。,对于任意固定的xa,b, xxk ,构造自变量 t 的辅助函数,由式 n+1(xk)=0 和式 Ln(xk)=yk ( k=0,1,n ),以及,可知：x0 , x1, , xn 和 x 是(t) 在区间a,b上

9、的 n+2个互异零点, 因此根据罗尔 (Rolle) 定理, 至少存在一点 =(x) (a,b),使,即,所以,一般来说,外推比内插效果差,在估计误差时下列不等式很有用。,解,插值多项式为,因为,故,于是,另见书p29的例1.,用二次插值计算ln11.25的近似值,并估计误差.,例4 给定函数表,解 取节点x0=10,x1=11,x2=12,作二次插值有,ln11.25L2(11.25),在区间10,12上lnx 的三阶导数的上限M3=0.002,可得误差估计式,实际上,ln11.25=2.420368, |R2(11.25)|=0.000058.,2.3.1 均差及其基本性质,定义1 称,为

10、 f (x)在x0、x1点的一阶均差.一阶均差的均差(差商),称为函数f (x)在x0、x1 、x2 点的二阶均差.,英1642-1727,2.3 均差与牛顿插值公式,一般地，n-1阶均差的均差,称为f (x)在x0 , x1 , , xn点的 n 阶均差。,差商的计算步骤与结果可列成均差表，如下,一般f(xi) 称为f(x) 在xi点的零阶均差，记作fxi。,表5-1（均差表）,给出节点x0,x1,xn和函数值(x0),(x1),(xn),可按如下的差商表顺序逐次计算各阶差商值.,这一性质可以用数学归纳法证明，它表明均差与节点的排列次序无关，即,fx0 , x1 , x2 , ., xn=

11、fx1 , x0 , x2 , ., xn= = fx1 , x2 , ., xn , x0 ,性质1 均差可以表示为函数值的线性组合，即,称之为均差的对称性（也称为对称性质）。,性质2 由性质1立刻得到,或,性质3 n次多项式f(x)的k阶差商,当kn时是一个n-k次多项式;当kn时恒等于0.,性质4 若f(x)在a,b上存在n阶导数, 且节点x0 , x1 , xna,b ,则至少存在一点 a, b 满足下式,例1 f (x)=6x8+7x510, 求f 1,2, ,9及f 1,2, ,10.,解 f (8)(x)=68 !, f 1,2, ,9=-6, f (9)(x)=0, f 1,2

12、, ,10=0.,2.3.2 牛顿插值多项式,设x是a，b上一点，由一阶均差定义得,同理，由二阶均差定义,如此继续下去，可得一系列等式,得,得,依次把后式代入前式，最后得,其中,可见, Nn(x)为次数不超过n 的多项式,且易知 Rn(xi)= 0 即 Nn(xi)= yi , (i=0,1, ,n) 满足插值条件, 故其为插值问题的解, Nn(x)称为牛顿插值多项式。,Rn(x)称为牛顿型插值余项。,由插值多项式的唯一性知，它与拉格朗日插值多项式是等价的,即 Ln(x) Nn(x),且有如下递推形式,和余项公式,由此即得性质4。且,例1 已知f(x)=shx的数表,求二次牛顿插值多项式,并由

13、 此计算f(0.596)的近似值。,解 由上表可得过前三点的二次牛顿插值多项式为,又,可得过前四点的三次牛顿插值多项式,故,可得N3(x)的截断误差,设函数y=f(x)在等距节点xi=x0+ih (i=0,1, ,n)上的函数值为fi=f(xi)(h为步长),定义2 fi=fi+1-fi 和 fi=fi-fi-1分别称为函数f(x)在点xi处的一阶向前差分和一阶向后差分。,一般地, f(x) 在点 xi 处的 m 阶向前差分和 m 阶向后差分分别为,mfi= m-1fi+1- m-1fi 和 mfi= m-1fi - m-1fi-1,2.4 差分与等距节点插值,2.4.1 差分及其性质,构造差

14、分表5-2,容易证明，差分有如下基本性质,性质1 各阶差分均可用函数值表示. 即,且有等式 nfi= nfi+n .,性质3 均差与差分的关系式为,性质2 函数值均可用各阶差分表示. 即,且有差分与微商的关系式为,差分的其它性质参看本章p59习题8，9，10，11.,代入牛顿插值公式 ,可得,称为牛顿向前插值公式，其余项为,插值节点为 xi=x0+ih (i=0,1, ,n), 如果要计算 x0附近点 x 处的函数值f(x), 可令 x=x0+th (0 t n),2.4.2 等距节点差值公式,类似地, 若计算 xn 附近的函数值 f(x), 可令 x=xn+th (- n t 0) ，可得牛

15、顿向后插值公式,及其余项,例2 设 y=f(x)=ex, xi=1, 1.5, 2, 2.5, 3, 用三次插值多项 式求f(1.2) 及f(2.8)的近似值.,解 相应的函数值及差分表如下:,求f(1.2)用牛顿前插公式, 且由 1.2=1+0.5t, 得t=0.4,求f(2.8)用牛顿后插公式,且由 2.8=3+0.5t, 得t= -0.4,2.5.1 三次埃尔米特插值多项式,设 y=f(x)是区间a, b上的实函数, x0, x1 是a, b上相异两点, 且 x0 x1, y=f (x) 在xi上的函数值和一阶导数值分别为 yi=f (xi) (i=0,1)和mi = f (xi) (i

16、=0,1), 求三次多项式 H3(x), 使其满足：,H3(x)称为三次埃尔米特插值多项式。,法1822 -1901,2.5 埃尔米特(Hermite)插值,构造三次埃尔米特插值多项式如下:,定理3 满足条件式 的三次埃尔米特插值多项式存在且唯一。,由,可将它写成,即,可得满足条件的三次埃尔米特插值多项式为,定理4 设f(x)在包含x0、x1的区间a,b内存在四阶导数，则当xa,b时有余项,设,则当x(x0 , x1)时,余项有如下估计式（误差限）,2.5.2 误差估计,且与x有关),例2 已知f(x)=x1/2及其一阶导数的数据见下表,用埃尔米特插值公式计算1251/2的近似值,并估计其截断

17、误差.,解,得,由,可求得,2.6 分段低次插值,先看下面的例子,对(x)=(1+25x2)-1,在区间-1,1上取等距节点 xi=-1+ih, i=0,1,10,h=0.2,作(x)关于节点 xi(i=0,1,10)的10次插值多项式 L10(x), 如图所示,x,y,o,1,-1,0.5,1,1.5,y=L10(x),这个现象被称为Runge现象. 表明高次插值的不稳定性. 实际上, 很少采用高于7次的插值多项式.,2.6.1 分段线性插值,求一个分段函数P(x), 使其满足: P(xi)=yi (i=0,1, ., n); 在每个子区间xi，xi+1 上是线性函数.称满足上述条件的函数P

18、(x)为分段线性插值函数.,或,由线性插值的误差即得分段线性插值在区间xi, xi+1上的余项估计式为,因此,在插值区间a,b上有余项,2.6.2 分段抛物线插值,2.6.3 分段三次Hermite插值,已知,求一个分段函数H(x), 使其满足:,(2) 在每个子区间xi, xi+1 上，H(x)是次数不超过3的 多项式.称满足上述条件的函数H(x)为分段三次Hermite插值函数.,或,分段三次埃尔米特插值在区间xi, xi+1上的余项估计式为,因此，在插值区间a, b上有余项,例3 构造函数f(x)=lnx在1x10上的数表, 应如何选取步长h,才能使利用数表进行分段插值时误差不超过0.5

19、10-4 。,解,欲使,即进行分段线性插值时，应取h210-2，误差不超过0.510-4。,欲使,即进行分段三次埃尔米特插值时,应取误差不超过0.510-4 。,2.7.1 问题的提出,定义 给定区间a,b的一个划分 a=x0 x1xn=b， yi=f (xi) (i=0,1,n),如果函数S(x)满足：,S(xi )=yi (i=0,1,n); 在每个小区间xi, xi+1 (i=0,1,.,n-1)上是次数不超过3的多项式;(3) 在每个内节点xi (i=1,2,.,n-1)上具有二阶连续导数, 则称 S(x) 为关于上述划分的一个三次多项式样条 函数，简称三次样条。,2.7 三次样条插值

20、,S(x)在每个小区间xi , xi+1上是一个次数不超过3的多项式, 因此需确定四个待定常数, 一共有n个小区间,故应确定4n个系数, S(x)在n-1个内节点上具有二阶连续导数，应满足条件,即有3n-3个连续条件，再加上S(x) 满足的插值条件n+1个，共计4n-2个，因此还需要2个条件才能确定S(x)，通常补充两个边界条件。,2.7.2 三弯矩方程,在xi , xi+1上是一次多项式, 且可表示为,对 积分两次并利用S(xi)=yi和S(xi+1)=yi+1定出积分常数得,对S(x)求导得,所以,(i=1,2,.,n-1),由,得,其中,由公式,1. 边界条件为,得,即,从中解出Mi (i=0,1,.,n) 得三次样条S(x).,从中解出Mi(i=1,2,.,n-1)得 三次样条S(x)。,3、周期函数 M0 =Mn,整理得,其中,从中解出Mi(i=1,2,.,n),得三次样条S(x).,2.7.3 三转角方程,所以,同理,其中：,同三弯矩方程一样，有三种条件：,1、已知,(6-42),由S(x)二阶连续可微，即,则方程组化为：,即矩阵形式为：,3、已知,则有：,