插值法与曲线拟合插值法课件.ppt

《插值法与曲线拟合插值法课件.ppt》由会员分享，可在线阅读，更多相关《插值法与曲线拟合插值法课件.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、插值法与曲线拟合插值法第1页，此课件共58页哦 上一讲的简单回顾上一讲的简单回顾 插插值值多多项项式的存在惟一性式的存在惟一性:满满足插足插值值条件条件 Pn(xi)=f(xi),(i=0,1,2,n)n次插值多项式次插值多项式Pn(x)=a0+a1x+a2x2+anxn 存在而且惟一存在而且惟一.插值余项插值余项:Rn(x)=f(x)-Pn(x)=,Lagrange插值多项式插值多项式其中其中,i=0,1,n称为称为Lagrange插值基函数插值基函数第2页，此课件共58页哦1.3 牛顿途径 对于n+1个不同的节点 ，考虑n次多项式（6）如果满足：，那么它就是n+1个点上的n次插值多项式，对

2、于这样的 ，有第3页，此课件共58页哦 优点优点:具有严格的规律性具有严格的规律性,便于记忆便于记忆.缺点缺点:不具有承袭性不具有承袭性,即每当增加一个节点时即每当增加一个节点时,不仅要增加求不仅要增加求和的项数和的项数,而且以前的各项也必须重新计算而且以前的各项也必须重新计算.为了克服这一缺点为了克服这一缺点,本讲将建立具有承袭性的插值公式本讲将建立具有承袭性的插值公式Newton插值公式插值公式.本讲主要内容本讲主要内容:Newton插值多项式的构造插值多项式的构造 差商的定义及性质差商的定义及性质 差分的定义及性质差分的定义及性质 等距节点等距节点Newton插值公式插值公式第4页，此课

3、件共58页哦一一 基函数基函数 问题问题1 求作求作n次多项式次多项式使满足使满足 (2)为了使为了使 的形式得到简化的形式得到简化,引入如下记号引入如下记号 (3)(1)第5页，此课件共58页哦 定义定义 由式由式(3)定义的定义的n+1个多项式个多项式称为称为Newton插值插值的以的以x0,x1,xn为节点的为节点的基函数基函数,即即 可以证明可以证明,这样选取的基函数是这样选取的基函数是线性无关线性无关的的,由此得由此得出的问题出的问题4.1的解的解便于求值便于求值,而且而且新增加一个节点新增加一个节点 xn+1时时只需加一个新项只需加一个新项 即即 而而 (4)第6页，此课件共58页

4、哦 依据条件依据条件(2),可以依次确定可以依次确定系数系数c0,c1,cn.例如例如,取取x=x0,得得 取取x=x1,得得 取取x=x2,得得第7页，此课件共58页哦 .为了得到计算系数为了得到计算系数ci的一般方法的一般方法,下面引进下面引进差商的概念差商的概念.第8页，此课件共58页哦二二 差商的定义差商的定义 给定给定a,b中互不相同的点中互不相同的点x0,x1,x2,以及以及f(x)在这些点处相在这些点处相应的函数值应的函数值f(x0),f(x1),f(x2),用记号用记号表示表示f(x)在在x0及及x1两点的两点的一阶差商一阶差商.用记号用记号表示表示f(x)在在x0,x1,x2

5、三点的三点的二阶差商二阶差商.一般地一般地,有了有了k-1阶差商之后阶差商之后,可以定义可以定义f(x)在在x0,x1,.,xk的的k阶差商阶差商第9页，此课件共58页哦三三 Newton插值公式插值公式由差商定义由差商定义,有有 f(x)=fx0+(x-x0)fx,x0 fx,x0=fx0,x1+(x-x1)fx,x0,x1 fx,x0,x1=fx0,x1,x2+(x-x2)fx,x0,x1,x2 .fx,x0,xn-1=fx0,xn+(x-xn)fx,x0,.,xn将以上各式，由下而上逐步代入，得到将以上各式，由下而上逐步代入，得到f(x)=f(x0)+(x-x0)fx0,x1+(x-x0

6、)(x-x1)fx0,x1,x2 +(x-x0)(x-xn-1)fx0,xn +(x-x0)(x-xn-1)(x-xn)fx,x0,xn (5)第10页，此课件共58页哦记记 Nn(x)=f(x0)+(x-x0)fx0,x1+(x-x0)(x-x1)fx0,x1,x2 +(x-x0)(x-xn-1)fx0,xn (6)Rn(x)=(x-x0)(x-xn)fx,x0,xn=fx,x0,xnwn+1(x)(7)则则(5)可表示为可表示为 f(x)=Nn(x)+Rn(x)(8)显然显然,Nn(x)是次数不超过是次数不超过n的多项式的多项式,且有且有 Rn(xi)=fx,x0,xnwn+1(xi)=0

7、,i=0,1,n即即 Nn(xi)=f(xi),i=0,1,n由此可知由此可知,如此构造的函数如此构造的函数Nn(x)就是问题就是问题1的解的解,且且 ci=fx0,xi,i=0,1,n (9)第11页，此课件共58页哦 公式公式(6)称为函数称为函数f(x)在节点在节点x0,xn上的上的n阶阶Newton插值公式插值公式,(7)式称为式称为Newton插值公式余项插值公式余项,即截断误差即截断误差.注注意到意到,余项表达式余项表达式(7)只要求被插值函数只要求被插值函数f(x)在插值区间在插值区间a,b上连续上连续.由函数由函数f(x)的的插值多项式的惟一性插值多项式的惟一性,函数函数f(x

8、)的的Newton插值多项式与插值多项式与Lagrange插值多项式实为同一个多项式插值多项式实为同一个多项式,即即 Nn(x)Ln(x)两者不过是表现形式不同而已两者不过是表现形式不同而已.由此有由此有:若若f(x)CCn+1n+1 a,b,则有则有 Rn(x)=fx,x0,xnwn+1(x)=,(10)第12页，此课件共58页哦四四 差商的性质差商的性质性质性质1(差商与函数值的关系差商与函数值的关系)证明：证明：性质性质2(对称性对称性)其中其中i0,ik是是0,1,k的任排列的任排列.证明证明:由性质由性质1可知可知.第13页，此课件共58页哦 性质性质3(差商与导数的关系差商与导数的

9、关系)f(x)CCk k a,b,证明证明:由式由式(10)即得即得.性质性质4(多项式的差商多项式的差商)设设f(x)为为n次多项式次多项式,则则其一阶差商其一阶差商 是是x的的n-1次多项式次多项式推论推论 n次多项式次多项式pn(x)的的k阶差商阶差商pnx0,xk,当当kn时时是是n-k次多项式次多项式,当当kn时恒为时恒为0证明证明:第14页，此课件共58页哦 运用运用Newton插值公式插值公式(6)进行计算时进行计算时,先计算先计算f(x)关于关于节点节点x0,xn的各阶差商的各阶差商.计算过程如下表所示计算过程如下表所示 .xk f(xk)一阶差商一阶差商 二阶差商二阶差商 三

10、阶差商三阶差商 n 阶差商阶差商第15页，此课件共58页哦计算计算Nn(x)时时,常采用常采用秦九韶算法秦九韶算法,即即 .下面给出下面给出Newton插值法的计算机插值法的计算机算法算法.开始时开始时,f(k)存放函数值存放函数值f(xk),运算完毕运算完毕f(k)存放存放k阶差商阶差商fx0,xk第16页，此课件共58页哦Newton插值算法插值算法(1)输入输入:xi,fi;(2)di=fi (i=0,1,n);(3)计算差商计算差商 对对i=1,2,n 做做 (3.1)对对j=i,i+1,n 做做 fj=(dj-dj-1)/(xj-xj-i);(3.2)对对j=i,i+1,n 做做 d

11、j=fj;(4)计算插值计算插值N(u)(4.1)输入插值点输入插值点u;(4.2)v=0;(4.3)对对i=n,n-1,1,0 做做 v=v(u-xi)+fi;(5)输出输出u,v.第17页，此课件共58页哦五五 等距节点的等距节点的Newton插值公式与差分插值公式与差分 当插值节点当插值节点x0,xn为等距分布时为等距分布时,Newton插值公式插值公式(6)可以简化可以简化.设插值节点设插值节点xj=x0+jh,j=0,1,n;h=(b-a)/n称为步长称为步长,且且x0=a,xn=b.令令x=x0+th,则当则当x0 xxn时时,0tn.基函数基函数 此时差商也可进一步化简此时差商也

12、可进一步化简,为此引进为此引进差分的概念差分的概念.定义定义 称称 f(xi)=f(xi+h)-f(xi)和和 f(xi)=f(xi)-f(xi-h)分别分别为函数为函数f(x)在点在点xi处的处的一阶向前差分一阶向前差分和和一阶向后差分一阶向后差分.第18页，此课件共58页哦 一般地一般地,称称k阶差分的差分为阶差分的差分为k+1阶差分阶差分,如二阶向前和向如二阶向前和向后差分分别为后差分分别为 计算各阶差分可按如下差分表进行计算各阶差分可按如下差分表进行.第19页，此课件共58页哦 向前差分表向前差分表第20页，此课件共58页哦 差分具有如下性质差分具有如下性质:.性质性质1(差分与函数值

13、的关系差分与函数值的关系)各阶差分均可表示为函值各阶差分均可表示为函值fj=f(xj)的线性组合的线性组合:性质性质2(前差与后差的关系前差与后差的关系):性质性质3(多项式的差分多项式的差分)若若f(x)PPn(n次多项式类次多项式类),则则其中其中第21页，此课件共58页哦 性质性质4(差分与差商的关系差分与差商的关系):性质性质5(差分与导数的关系差分与导数的关系 利用这些性质利用这些性质,可将可将Newton公式公式 Nn(x)=f(x0)+(x-x0)fx0,x1+(x-x0)(x-x1)fx0,x1,x2 +(x-x0)(x-xn-1)fx0,xn进一步简化进一步简化第22页，此课

14、件共58页哦(11)称公式称公式(11)为为Newton向前差分插值公式向前差分插值公式,其余项为其余项为(12)如果将式如果将式(6)改为按节点改为按节点xn,xn-1,x0的次序排列的的次序排列的Newton插插值公式值公式,即即第23页，此课件共58页哦 令令x=xn-th,则当则当x0 xxn时时,0tn.利用差商与向后利用差商与向后差分的关系差分的关系,式式(13)可简化为可简化为(13)(14)称式称式(14)为为Newton向后差分插值公式向后差分插值公式,其余项为其余项为第24页，此课件共58页哦 若要计算的插值点若要计算的插值点x较靠近点较靠近点x0,则用向前插值公式则用向前

15、插值公式(4.8),这时这时t=(x-x0)/n的值较小的值较小,数值稳定性较好数值稳定性较好.反之反之,若若x靠近靠近xn,则用向后插值则用向后插值公式公式(14).利用向前与向后差分的关系利用向前与向后差分的关系(差分性质差分性质2):式式(14)可表示成可表示成(15)这样这样,计算靠近计算靠近x0或或xn的点的值时的点的值时,都只需构造向前差分表都只需构造向前差分表第25页，此课件共58页哦例例 给定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)的近似值

16、.解解 先构造向前差分表如下:xi fi fi 2 2fi 3 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.由(4.8)和(4.12),分别用差分表中对角线上的值和最后一行的值,得Newton向前和向后插值公式如 下:第26页，此课件共58页哦(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),得

17、 f(0.9)N3(0.9)=2.46875.第27页，此课件共58页哦课后练习题 P217:第2题,第4题,P219:第11题.第28页，此课件共58页哦 6 6 曲线拟合曲线拟合6.1.2 曲线拟合问题仍然是已知仍然是已知 x1 xm;y1 ym,求一个简单易求一个简单易算的近似函数算的近似函数 f(x)来拟合这些数据来拟合这些数据。但是但是 m 很大；很大；yi 本身是测量值，不准确，即本身是测量值，不准确，即 yi f(xi)这时没必要取这时没必要取 f(xi)=yi,而要使而要使 i=f(xi)yi 总体上总体上尽可能地小。尽可能地小。这种构造近似函数这种构造近似函数 的方法称为的方

18、法称为曲线拟合，f(x)称为称为拟合函数拟合函数称为称为“残差残差”第29页，此课件共58页哦常见做法：常见做法：u使使 最小最小较复杂，较复杂，P284u使使 最小最小不可导，求解困难，不可导，求解困难，P283u使使 最小最小“使使 i=P(xi)yi 尽可能地小尽可能地小”有不同的准则有不同的准则第30页，此课件共58页哦6.2 线性拟合问题6.2.1|.|2 意义下的线性拟合（线性最小二乘问题）确定拟合函数确定拟合函数，对于一组数据，对于一组数据(xi,yi)(i=1,2,m)使得使得 达到达到极小极小，这里，这里 n n),称线性方程组Ax=b (1)(1)为超定方程组超定方程组;这

19、里xRn,bRm.如果A的秩r(A)=n,称A为列满秩矩阵列满秩矩阵.记残向量r=b-Ax，考虑确定一个向量x，使r2 2b-Ax2 2,达到最小的问题称为线性最小二乘问题线性最小二乘问题，这样的x称为方程组(1)的最最小二乘解小二乘解.第36页，此课件共58页哦6.3.4 最小二乘解的存在惟一性 结论1：设A是mn阶矩阵，xRn,bRm.由线性方程组理论可知，线性方程组 Ax=b (24)有解的充分必要条件是 r(A)=r(A|b).(25)第37页，此课件共58页哦 定理定理6.3.7假设方程组假设方程组(24)有解，令有解，令x是其一个是其一个解解.那么，方程组那么，方程组(24)的所有

20、解的集合为的所有解的集合为x+N(A).方程组方程组(24)有有 惟一解的充分必要条惟一解的充分必要条件是件是null(A)=0.这里，这里，null(A)表示表示A的核子空的核子空间的维数间的维数.第38页，此课件共58页哦 证明:首先首先证明任意的向量yx+N(A)都是方程组(24)的解.事实上，将y记为y=x+z,其中zN(A)，即Az=0，xx.因此，Ay=Ax+Az=b,即y满足方程组(24).反过来，若y满足方程组(24)，有 Ay-Ax=A(y-x)=0，即y-xN(A).记y=x+(y-x)，从而有yx+N(A).惟一性惟一性.因为齐次方程组Ax=0有惟一零解的充 分必要条件是

21、A为满秩矩阵，即null(A)=0.第39页，此课件共58页哦定理定理6.3.8当当mn时，时，超定方程组超定方程组(1)的最小二乘解总是存在的的最小二乘解总是存在的.最小二乘解最小二乘解惟一的充分必要条件是惟一的充分必要条件是 null(A)=0.第40页，此课件共58页哦证:记b=bb，其中b1R(A)，b2N(A）.对任意xRn,AxR(A),b1-AxR(A).因此，r22b-Ax22(b-Ax)+b22.由定理6.3.3的推论1和定理6.3.2，r22b-Ax22+b22 要使r22达到最小等价于确定x，使b-Ax22 为0，即求方程组Ax=b的解x.因为b,Ax,bAx都是R(A)

22、中的向量，因此，可以 把b看成由A的列向量线性表示，即bAx.换句话说，方程组Ax=b的解总是存在的，从而方程 组(1)的最小二乘解也总是存在的.惟一性的证明可直接由定理6.3.7得到.第41页，此课件共58页哦6.3.1 正交性的有关性质 在线性代数欧氏空间理论中，将R3中两个向量x,y之间的夹角满足的关系式 xTy=x2y2cos (2)推广到Rn.设x,yRn，由Cauchy不等式 -1 1 从而得到Rn中两个向量之间的夹角为 =arccos (3)第42页，此课件共58页哦 定理定理6.3.1 设x,y是Rn中的向量，x与y正交 的充分必要条件为xy=0.证：必要性.当x与y正交，它们

23、的夹角=/2，由(2)式，有xy=0.充分性.当xy=0,由(3)式，=/2,即x与y正交.注：如果x与y正交，记为xy第43页，此课件共58页哦定理6.3.2：设x，yRn，且xy，那 么：x+y22x22y22 证：由x+y22=(x+y)(x+y)=xx+2yx+yy 而xy=yx=0,因此 x+y22x22+y22注：注：推广到Rn中的向量组，k，如果ij=0(ij),称1，2，k是 正交向量组正交向量组.特别地特别地:如果i2=1(i=1,2,，k)，即 iTj=ij，称1，2，k 为标准正交向量组.第44页，此课件共58页哦设U是Rn中的子空间，xRn.如果x与U中任意向量正交，称

24、向量向量x与子空间与子空间U正交正交，记为xU.设U，V是Rn中两个子空间，如果任意xU和任意yV是正交的，称子空间子空间U与子空与子空间间V正交正交，记为UV.设U，V是Rn中互补的子空间.如果UV，那么称U，V互为正交补子空间正交补子空间，记U=V或V=U.可以证明，一个子空间的正交补子空间是惟一的.第45页，此课件共58页哦定理定理6.3.3 设A是nk阶矩阵，xRn,那么下列三种情况是 等价的：xR(A);Ax=0;xN(A).这里，N(A)=Ax=0,xRn称为称为A的核子空间的核子空间.证：由N(A)的定义，与显然等价.下面证明与等价.记A=(1,2,，k)，那么，iR(A)(i=

25、1,2,k).假设xR(A),即ix=0(i=1,2,，k).从而Ax=0.另一方面，如果Ax=0,那么有zRk，使Az=yR(A).这时，yx=zAx=0,即xy.由z的任意性，得Az是任意的，因此xR(A).由这个定理，由这个定理，容易得到：容易得到：推论推论1设A是nk阶矩阵，那么R(A)有惟一的正交补子 空间N(A).第46页，此课件共58页哦6.3 线性最小二乘问题设A是mn阶矩阵(mn),称线性方程组Ax=b (1)为超定方程组超定方程组;这里xRn,bRm.如果A的秩r(A)=n,称A为列满秩矩阵列满秩矩阵.记残向量r=b-Ax，考虑确定一个向量x，使r2 2b-Ax2 2,达到

26、最小的问题称为线性线性最小二乘问题最小二乘问题，这样的x称为方程组(1)的最最小二乘解小二乘解.第47页，此课件共58页哦6.3.1 正交性的有关性质 在线性代数欧氏空间理论中，将R3中两个向量x,y之间的夹角满足的关系式 xTy=x2y2cos (2)推广到Rn.设x,yRn，由Cauchy不等式 -1 1 从而得到Rn中两个向量之间的夹角为 =arccos (3)第48页，此课件共58页哦 定理定理6.3.1 设x,y是Rn中的向量，x与y正交 的充分必要条件为xy=0.证：必要性.当x与y正交，它们的夹角=/2，由(2)式，有xy=0.充分性.当xy=0,由(3)式，=/2,即x与y正交

27、.注：如果x与y正交，记为xy第49页，此课件共58页哦定理6.3.2：设x，yRn，且xy，那 么：x+y22x22y22 证：由x+y22=(x+y)(x+y)=xx+2yx+yy 而xy=yx=0,因此 x+y22x22+y22注：注：推广到Rn中的向量组，k，如果ij=0(ij),称1，2，k是 正交向量组正交向量组.特别地特别地:如果i2=1(i=1,2,，k)，即 iTj=ij，称1，2，k 为标准正交向量组.第50页，此课件共58页哦设U是Rn中的子空间，xRn.如果x与U中任意向量正交，称向量向量x与子空间与子空间U正交正交，记为xU.设U，V是Rn中两个子空间，如果任意xU和

28、任意yV是正交的，称子空间子空间U与子空与子空间间V正交正交，记为UV.设U，V是Rn中互补的子空间.如果UV，那么称U，V互为正交补子空间正交补子空间，记U=V或V=U.可以证明，一个子空间的正交补子空间是惟一的.第51页，此课件共58页哦定理定理6.3.3 设A是nk阶矩阵，xRn,那么下列三种情况是 等价的：xR(A);Ax=0;xN(A).这里，N(A)=Ax=0,xRn称为称为A的核子空间的核子空间.证：由N(A)的定义，与显然等价.下面证明与等价.记A=(1,2,，k)，那么，iR(A)(i=1,2,k).假设xR(A),即ix=0(i=1,2,，k).从而Ax=0.另一方面，如果

29、Ax=0,那么有zRk，使Az=yR(A).这时，yx=zAx=0,即xy.由z的任意性，得Az是任意的，因此xR(A).由这个定理，由这个定理，容易得到：容易得到：推论推论1设A是nk阶矩阵，那么R(A)有惟一的正交补子 空间N(A).第52页，此课件共58页哦6.3.2 矩阵的QR分解定理定理6.3.4 设A=(1,2,，n)是列满秩矩阵，iRm(i=1,2,，n)且mn.那么，A有惟一的QR分解，记为 A=QR，(4)这里，Q是有n个标准正交列的mn阶矩阵，R是有正对角元的n阶上三角矩阵.证：证：由A是列满秩矩阵可知，AA是n阶正定矩阵，因此有 惟一的Cholesky分解：AA=RR,(

30、5)这里R是有正对角元的上三角矩阵，R存在.令Q=AR,(6)那么，QQ=RAARIn,即Q是有标准正交列的mn阶矩阵.由(6)式，(4)式成立，且由(5)式的惟一性，分解式(4)也是惟一的.第53页，此课件共58页哦6.3.3 Householder矩阵与矩阵的正交三角化 定义定义1设w是欧氏空间Rn中的单位向量，形如H=I-2ww (10)的n阶矩阵称为Householder矩阵，也称 为反射(镜像)矩阵或称为Householder变 换(反射变换、镜像变换).第54页，此课件共58页哦定理6.3.5 设H是Rn中的Householder 矩阵，那么，H=H (对称性)；H=H (正交性)

31、；H2=I (对合性).证：直接验证，性质成立.由H=I-2ww,ww=1和性质，H2HH=(I-2ww)(I-2ww)=I-4wwww+4ww=I,即H=H-1，性质和成立.第55页，此课件共58页哦 定理定理6.3.6设Rn中有非零向量xy 且x2=y2，那么，存在 Householder矩阵H，使Hx=y 证：不妨令w=(x-y)/x-y2,有wTw=1.设H=I-2wwT,那么 Hx=(I-2wwT)由已知，xx=yy.所以(x-y)(x-y)=xx-2yx+yy=2(xx-yx).从而，Hx=x-(x-y)=y.证明中如果令u=x-y，那么Householder矩阵形为(11)式，即

32、H=I-uu,=uu.同样可验证Hx=y成立.第56页，此课件共58页哦 例例1 设设R3中向量中向量x=(0,4,3)和向量和向量e1，其中，其中2=x，即，即=5.按按(11)式构造一个式构造一个3阶阶Householder矩阵矩阵H，使，使Hx=e1.解解:令令u=x-e1.设设=-5,于是于是 u=(-5,4,3)又由又由uu=25+16+9=50,所以所以=25.由由H=I-uu,得得 第57页，此课件共58页哦 容易验证容易验证Hx=e1.在在Rn中，如果已知非零向量中，如果已知非零向量x=(x1,x2,，xn)和向量和向量e1x,其中，其中，=x2,即即e12=x2 由定理由定理6.3.6，存在一个形如存在一个形如(11)式或式或(10)式的式的 Householder矩阵矩阵H，使，使Hx=e1.由定理由定理6.3.6，令令u=x-e1 (13)又由又由2=x22xx和和(12)式，式，=1/2(x-e1)(x-e1)=1/2(xx-2x+2)=(-x1).(14)记记H=I-uu，容易验证，容易验证Hx=e1.第58页，此课件共58页哦