第4章 插值和拟合优秀PPT.ppt

第4章 插值和拟合现在学习的是第1页，共68页4.2 多项式插值多项式插值 通常用函数y=f(x)表示许多实际问题的某种内在规律的数量关系，其中相当一部分是通过实验或观测数据得到的。虽然f(x)在某个区间a,b上是存在的，有的还是连续的，但却只能给出a,b上一系列点xi的函数值yi=f(xi)，(i=0,1,n)。这只是一张函数表。有的函数虽有解析表达式，但由于计算复杂，使用不方便，也造一个函数表。如：椭圆积分数值表，概率分布数值表等。为了某种目的，有时需要不在表上的函数值。因此，我们希望根据给定函数表，构造一个既能反映f(x)的特性，又便于计算的简单函数P(x)，用P(x)近似f(x)。第第4章章 插值和拟合插值和拟合现在学习的是第2页，共68页通常选一类较简单的函数，如代数多项式或分段代数多项式，作为P(x)，并使P(xi)=f(xi)对所有i=0,1,n成立。这样确定的就是希望得到的插值函数。下面给出定义定义定义 4.1.1设y=f(x)是区间a,b上的连续函数，记作f Ca,b。已知f 在a,b上 n+1 个互异互异点 a x0,x1,xn-1,xn bxi xj (i j)处的值 yi=f(xi)，i=0,1,2,n第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第3页，共68页若有不超过n次的多项式Ln(x)=c0+c1x1+c2x2+cnxn 满足 Ln(xi)=yi，i=0,1,2,n(4.1.1)则称Ln(x)为函数f(x)在区间a,b上通过点列的插值多项式插值多项式。其中，a,b称为插值区间插值区间，称为插值节点插值节点，求函数值f(x)的点x(xi)称为插值点插值点，f(x)称为被插函数被插函数，Ln(x)称为插值函数插值函数，式(4.1.1)称为插值条件插值条件。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第4页，共68页插值函数除代数多项式外，常用的还有三角多项式。插值条件除(4.1.1)式外，还可以(如Hermit插值)加上导数条件。本课程只介绍代数多项式插值。函数插值是数值计算的基本工具，如本课程后面的数值微分、数值积分、微分方程的数值解法等都要用到函数插值。插值法在工程实际和许多学科的理论分析中有广泛的应用。函数插值的基本问题有：存在唯一性、构造方法、截断误差和收敛性，以及数值计算的稳定性等。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第5页，共68页定理定理 4.1.1 定义4.1.1的插值多项式Ln(x)是存在唯一的证证 定义4.1.1的插值条件可表示为(4.1.2)这是以为未知数的线性方程组，其系数矩阵的行列式是范德蒙(Vandermonde)行列式。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第6页，共68页因为其中的xi xj，所以 0，因而(4.1.2)式存在唯一解 。存在性的含义是插值问题有解，唯一性的含义是插值多项式与构造方法无关。定理4.1.1的证明过程，利用Gram法则非常简洁的证明了存在性和唯一性，同时还给出了构造插值多项式的一种方式，解(n+1)维线性方程组(4.1.2)式，得到系数 。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第7页，共68页 4.2.1 Lagrange插值法插值法但是用解线性方程组式(4.1.2)的方法确定插值多项式的系数是不大行得通的。因为范德蒙矩阵是病态的。当n稍大一些，不仅工作量相当可观，而且可能满足不了精度要求。事实上，不解方程组就可以得到满足定义4.1.1的插值多项式。下面从低次插值多项式入手，从中找出规律，从而得出一般的表达式。通过两个点(x0,y0)和(x1,y1)(即n=1)的插值多项式是不超过1次的多项式，是直线。由直线的两点式有第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第8页，共68页为了找规律，将其按yi(i=0,1)归类，得到(4.2.2)由该式可知，yj的系数中，分子含(x-xi)(ij)因子，分母含(xj-xi)(ij)因子。据此猜测当n=2时，过三个点(x0,y0)、(x1,y1)和(x2,y2)的插值多项式可能是验证：L2(x0)=y0，L2(x1)=y1，L2(x2)=y2。满足定义4.1.1的插值条件，根据唯一性，它是过三个点(x0,y0)、(x1,y1)和(x2,y2)不超过2次的插值多项式。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第9页，共68页推广到过(n+1)个点 ，不超过n次的插值多项式 (4.2.6)其中 (4.2.4)是仅与(n+1)个插值节点 有关的(n+1)个n次多项式，称为拉格拉格朗日朗日(Lagrange)插值基函数插值基函数，在插值节点处有性质 (4.2.5)第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第10页，共68页其中的ik是Kronecker delta。如此构造的Ln(x)显然是不超过n次的多项式，由插值基函数的性质(4.2.5)，式(4.2.6)显然满足定义4.1.1的插值条件式(4.1.1)，因此，根据唯一性，式(4.2.6)就是由定义4.1.1所定义的插值多项式，称为拉格朗日插值公式拉格朗日插值公式。有两点提请注意：(1)插值基函数仅由插值节点确定，与被插函数无关(2)对于插值节点，只要求互异，不要求排序。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第11页，共68页因此，若以 为插值节点，对函数f(x)=1构造插值多项式，y0=y1=yn=1代入式(4.2.6)，得到插值基函数的另一个性质(4.2.7)因此插值基函数(4.2.4)是单位正交基。如果对式(4.2.6)令x=xi，(i=0,1,n)，得到(n+1)个线性方程，即方程组第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第12页，共68页由插值基函数的性质(4.2.5)，系数矩阵是单位阵，因此直接得到解向量yi=Ln(xi)，i=0,1,n。这正是预期的。例例4.2.1 已知函数f(x)的三个点(0,1)、(-1,5)和(2,-1)，写出Lagranger插值基函数和插值多项式。解解三个点，n=2，x0=0,x1=-1,x2=2，由式(4.2.4)，插值基函数代入式(4.2.6)，得第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第13页，共68页4.2.2 插值的余项插值的余项(误差分析)由定义4.1.1定义的插值多项式在插值节点与被插函数严格相等，即Ln(xi)=f(xi)，i=0,1,n。这些点之外，则会有误差Rn(x)=f(x)Ln(x)。Rn(x)称为插值多项式的余项余项，也就是插值的截断误差截断误差或方法误差方法误差。定理定理 4.2.1 设被插函数f Cn+1a,b，Ln为函数 f 在区间a,b上n+1个互异节点a x0,x1,xn-1,xn b的最高为n次的插值多项式。对于a,b上的每一个x，(a,b)内存在一点x=(x)，使得 (4.2.9)第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第14页，共68页证证如果x是一个插值节点xi，定理命题显然为真，等式(4.2.9)两边都是0。如果x xi(i=0,1,n)，记(4.2.8)构造以t为自变量的辅助函数(t)=f(t)Ln(t)wn+1(t)(4.2.12)其中是使(x)=0 的实数(此处x是固定的)。即这样一来，(t)Cn+1a,b，并且(t)有n+2个零点x,x0,x1,xn根据Rolls Theorem，(t)在(a,b)内至少有n+1个互异零点。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第15页，共68页类似的(t)在(a,b)内至少有n个互异零点。以此类推，我们最终得到，(n+1)(t)在(a,b)内至少有1个零点，就是x。而(n+1)(t)=f(n+1)(t)Ln(n+1)(t)w(n+1)(t)=f(n+1)(t)(n+1)!因此有0=f(n+1)(x)(n+1)!代入该式得到定理得证定理4.2.1的一个有用的特例是推论推论4.2.1第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第16页，共68页推论推论4.2.1 设 f(x)C2a,b，并记 M2=maxaxb|f(x)|，则f(x)过点(a,f(a)和(b,f(b)的线性插值余项R1(x)有上界估计式，xa,b(4.2.13)证证 见习题4.4。例例 4.2.2 已知sin(0.32)=0.314567,sin(0.34)=0.333487，有6位有效数字(1)用线性插值求sin(0.33)的近似值；(2)证明在区间0.32,0.34上用线性插值计算sin(x)时至少有4位有效数字。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第17页，共68页解解 (1)(xx1)=-0.01，(xx0)=0.01，(x0 x1)=-0.02sin(0.33)L1(0.33)=0.3145670.5+0.3334870.5=0.324027(2)根据定理1.2.1，求得相对误差，即知有效数字 M2=maxsin(x)(x0.32,0.34)=sin(0.34)=0.333487(ba)2=0.0004，由推论4.2.1|R1(x)|0.3334870.510-4，x0.32,0.34 相对误差，x0.32,0.34所以结果至少有4位有效数字。线性插值损失2位有效数字。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第18页，共68页4.2.3 均差均差(Divided Difference)和牛顿插值法和牛顿插值法(Newton Form of the Interpolation Polynomial)关于定理4.1.1，教材上用Gram法则非常简洁的同时证明了插值多项式的存在性和唯一性。但是，没有给出一种实用的构造插值多项式的方法。在此，我们换一种方法证明定理4.1.1，证明过程给出一种实用的构造插值多项式的方法。证证 首先证明唯一性设有两个n次插值多项式Pn(x)和Qn(x)均满足插值条件 Pn(xi)=yi，Qn(xi)=yi，i=0,1,2,n于是有Pn(xi)=Qn(xi)，i=0,1,2,n第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第19页，共68页即多项式Pn(x)Qn(x)至少有n+1个零点：xi，i=0n对于一个n次多项式，如果它不是0多项式，则只能有n个零点。因此Pn(x)Qn(x)一定是零多项式，即 Pn(x)=Qn(x)再证存在性，用归纳法对于 n=0，P0(x0)=y0 的存在是显然的设n=k1时,最高为k1次的多项式Pk1(x)存在,它满足 Pk1(xi)=yi，i=0,1,2,k1构造如下形式的插值多项式Pk(x)Pk(x)=Pk1(x)+ck(xx0)(xx1)(xxk1)(A)第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第20页，共68页这显然是一个最高为k次的多项式，且满足Pk1(x)的所有插值条件，即 Pk(xi)=Pk1(xi)=yi，i=0,1,2,k1用条件Pk(xk)=yk确定系数ck，得到Pk1(xk)+ck(xkx0)(xkx1)(xkxk1)=yk(B)由于x0,x1,xk互异，故由(B)式一定能解出ck证毕丛存在性证明过程给可以看出，其中的多项式P0,P1,Pn具有这样的性质，每一个Pk都可以方便的在Pk1的基础上加一项得到：P0(x)=c0 P1(x)=c0+c1(xx0)第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第21页，共68页 P2(x)=c0+c1(xx0)+c2(xx0)(xx1)Pk(x)=c0+c1(xx0)+c2(xx0)(xx1)+ck(xx0)(xxk1)紧凑形式(C)式中依惯例当i10时，连乘积=1。这样的多项式称为Interpolation Polynomial in Newtons Form。由点列和(D)计算ck(k=0,1,2,n)第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第22页，共68页c0 y0for k=1 to n do u ck1 d xkxk1 for i=k 2 to 0 step 1 do u u(xkxi)+ci d d(xkxi)end do ck (yku)/d end do第第4章章 插值和拟合插值和拟合 多项式插值多项式插值说明 内循环计算Pk1(xk)和(xkx0)(xkxk1)其中 u 部分用秦九绍算法秦九绍算法或称Horners algorithm计算Pk1(xk)Note：xk不是Pk1(x)的插值节点。Pk1(x)的插值节点是x0,x1,xk1。现在学习的是第23页，共68页也就是说，若ck已确定，可以用秦九绍算法秦九绍算法计算Newton插值多项式Pk(x)。为了更清楚，记di=xxi重写Pk(x)Pk(x)=c0+c1d0+c2d0d1+ckd0d1dk1 =(ck dk1+ck1)dk2+ck2)dk3+c1)d0+c0该式的伪代码程序u ckfor i=k 1 to 0 step 1 dou u(xxi)+ci end do第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第24页，共68页前两页的伪代码程序只是演示如何将存在性证明中的构造方法转化为可用于电脑编程的过程。更有效率的计算Newton插值多项式系数c0,c1,ck方法是利用均差。用插值条件(4.1.1)式，即(E)确定系数c0,c1,c2,cn的线性方程组系数矩阵是(n+1)阶下三角阵。因为(F)第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第25页，共68页 以3个插值节点，即n=2，为例 P2(x)=c0+c1(xx0)+c2(xx0)(xx1)以 x=x0，x=x1，x=x2代入上式，得到未知数为c0,c1,c2的线性方程组，矩阵形式为下三角形(G)按正序解出ck c0=f(x0)c1=(f(x1)c0)/(x1x0)=(f(x0)f(x1)/(x0 x1)c0仅取决于f(x0)，c1取决于f(x0)和f(x1)，第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第26页，共68页为表示这种依赖关系，引入记号c0=f x0=f(x0)，c1=f x0,x1=(f(x0)f(x1)/(x0 x1)。c2(x2x0)(x2x1)=f(x2)c1(x2x0)c0 c2(x2x0)(x2x1)(x0 x1)=f(x2)f(x0)(x0 x1)f(x0)f(x1)(x2x0)=x0f(x2)f(x0)+f(x0)f(x1)x1f(x2)f(x0)x2f(x0)f(x1)f(x1)+f(x1)=f(x0)f(x1)(x1x2)f(x1)f(x2)(x0 x1)c2(x2x0)=f(x0)f(x1)/(x0 x1)+f(x1)f(x2)/(x1x2)=f x0,x1+f x1,x2c2=f x0,x1f x1,x2/(x0 x2)=f x0,x1,x2(由式(D)令k=0,1,2得到同样结果。)第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第27页，共68页推广(递推得到)c3=f x0,x1,x2f x1,x2,x3/(x0 x3)=f x0,x1,x2,x3可以证明 cn=f x0,x1,xn1f x1,x2,xn/(x0 xn)=f x0,x1,xn即有 称为1阶,2阶,j阶,n阶均差均差(divided differences)。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第28页，共68页有了均差，只要给出函数表(xi,f(xi)，就可以构造均差表。下面是n=3的均差表x0 fx0|fx0,x1 fx0,x1,x2 fx0,x1,x2,x3x1 fx1|fx1,x2 fx1,x2,x3x2 fx2|fx2,x3x3 fx3|(竖线左边两列是函数表，竖线右边3列是1,2,3阶均差)得到三次Newton插值多项式N3(x)=f(x0)+fx0,x1(xx0)+fx0,x1,x2(xx0)(xx1)+fx0,x1,x2,x3(xx0)(xx1)(xx2)Newton插值多项式的系数ck是均差表顶行的均差均差。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第29页，共68页Note：由存在性证明过程，均差与点列的顺序无关。根据唯一性，N(x)就是L(x)。例例 4.2.3 用牛顿插值法构造例4.2.1中的2次插值多项式。解解 用函数的3个点(0,1),(-1,5),(2,-1)作均差表01|-41-15|-22-1|N2(x)=1+(-4)(x0)+1(x0)(x+1)=x23x+1正如预料之中，结果与用Lagrange插值法相同。但却无计算Lagrange插值基函数之麻烦。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第30页，共68页 Newton插值法的更方便之处是当增加新的插值节点或其他插值条件时,可以利用原有结果，构造满足新插值条件的多项式。例例 4.2.4 设已知f(x)的如下值：f(-1)=-2，f(0)=-1，f(1)=0，f(0)=0构造不超过3次的多项式p3(x)，使满足插值条件 p3(-1)=-2，p3(0)=-1，p3(1)=0，p3(0)=0解解 首先作过f(x)的3个点(-1,-2),(0,-1),(1,0)的均差表这3个点显然在一条直线上，因此2阶均差为0。-1-2|100-1|110|N2(x)=-2+(x+1)=x1 第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第31页，共68页把点的顺序变换一下，结果也一样：10|100-1|1-1-2|N2(x)=0+(x1)令p3(x)=N2(x)+c3(xx0)(xx1)(xx2)，由p3(0)=0确定c3,p3(x)=1+c3(xx1)(xx2)+c3(xx0)(xx2)+c3(xx0)(xx1)p3(0)=1+c3x1x2+c3x0 x2+c3x0 x1=1+0+(-c3)+0=0，c3=1所以p3(x)=(x1)+(xx0)(xx1)(xx2)=(x1)+(x+1)x(x1)=x31第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第32页，共68页 Newton插值插值的余项的余项 根据均差的定义，把x看作a,b上的一点，则有f x,x0=f(x)f(x0)/(xx0)f(x)=f(x0)+(x x0)f x,x0f x,x0,x1=f x,x0 f x0,x1/(xx1)f x,x0=f x0,x1+(x x1)f x,x0,x1f x,x0,xn 2=f x0,x1,xn 1+(x xn 1)f x,x0,xn 1f x,x0,xn 1=f x0,x1,xn+(x xn)f x,x0,xn后一式代入前一式，即得第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第33页，共68页 f(x)=f(x0)+(xx0)f x,x0=f(x0)+(xx0)f x0,x1+(xx1)f x,x0,x1=f(x0)+(xx0)f x0,x1+(xx0)(xx1)f x0,x1,x2+(xx0)(xx1)(xxn1)f x0,x1,xn+(xx0)(xx1)(xxn1)(xxn)f x,x0,x1,xn=Nn(x)+Rn(x)其中Rn(x)=f(x)Nn(x)=wn+1(x)f x,x0,x1,xn(H)wn+1(x)=(xx0)(xx1)(xxn)第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第34页，共68页由于 f(x)=Nn(x)+wn+1(x)f x,x0,x1,xn根据插值多项式的唯一性，Nn(x)=Ln(x)，因此两种插值多项式的余项也相等。事实上，利用Rolls Theorem可证明n+1阶均差与n+1阶导数的关系：Lagrange形式的插值余项要求被插函数的n+1阶导数存在，而Newton形式的插值余项不要求被插函数的导数存在，因而可用于f(x)是由函数表给出或不可导的场合。式(H)更具有一般性。第第4章章 插值和拟合插值和拟合 多项式插值多项式插值现在学习的是第35页，共68页4.3 分段低次插值分段低次插值 4.3.1 Runge现象和分段线性插值现象和分段线性插值第第4章章 插值和拟合插值和拟合现在学习的是第36页，共68页4.3.2 分段分段Hermite三次插值三次插值Hermite插值插值某些实际问题不但要求在插值节点上函数值相等，而且还要求导数值也相等，Hermite插值满足这种要求设f C1a,b，且在插值节点a x0,x1,xn-1,xn b，其中xi xj (i j)，yi=f(xi),mi=f(xi),(i=0,1,2,n)要求插值多项式满足插值条件 H(xi)=yi，H(xi)=mi，(i=0,1,2,n)(4.3.12)这2n+2个插值条件可唯一确定一个最高不超过2n+1次的插值多项式第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值现在学习的是第37页，共68页 H2n+1(x)=a0+a1x1+a2x2+a2n+1x2n+1 仍采用Lagrange插值基函数的方法。插值基函数k(x)(对应于函数插值条件)和k(x)(对应于导数插值条件)(k=0,1,n)，共有2n+2个，每一个都是2n+1次多项式，且满足条件k(xi)=ki，k(xi)=0k(xi)=0，k(xi)=ki(i,k=0,1,n)于是，满足插值条件(4.3.12)式的插值多项式可表示为(4.2.13)由条件(A)，上式显然有H2n+1(xk)=yk，H2n+1(xk)=mk，(k=0,1,n)剩下的问题就是构造满足条件(A)的基函数k(x)和k(x)。第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值(A)现在学习的是第38页，共68页可利用Lagrange插值基函数(4.2.4)式构造k(x)和k(x)。由于lk(x)是n次多项式，k(x)和k(x)是2n+1次多项式因此设k(x)=(ax+b)lk2(x)，式中a,b是待定系数，由式(A)确定。因为lk(xk)=1，故解出求lk(xk)：式(4.2.4)取对数第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值现在学习的是第39页，共68页 关于x求导令x=xk，得到所以 (4.3.14)同理 k=0,1,n第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值现在学习的是第40页，共68页既然能够求出式(4.2.13)H2n+1(x)的基函数k(x)和k(x),也就证明了其存在。可用反证法证明其唯一性假设H2n+1(x)和P2n+1(x)均满足插值条件式(4.3.12)，则 2n+1(x)=H2n+1(x)P2n+1(x)在每个插值节点xk均有二重根，故2n+1(x)有n+1对重根，即2n+2个零点。但2n+1(x)是不高于2n+1次的多项式，因此2n+1(x)0,即H2n+1(x)=P2n+1(x)。唯一性得证。第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值现在学习的是第41页，共68页仿照Lagrange插值余项的证明方法，可证：若被插函数f C2n+2a,b，则其插值余项为 (4.3.15)其中x=(x)(a,b)，下面要用的是n=1的Hermite插值多项式H3(x)。第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值现在学习的是第42页，共68页分段分段Hermite三次插值三次插值 关于2个插值节点xi和xi+1，由(4.3.13)式，=yii(x)+yi+1i+1(x)+mii(x)+mi+1i+1(x)由(4.3.14)式，令n=1，k=i或k=i+1，得插值基函数 (4.3.9)第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值现在学习的是第43页，共68页定义定义 4.3.2 设 f C1a,b，对于划分：a=x0 x1xn-1 xn=b记子区间的最大长度h=max0in1(xi+1xi)，以及 yi=f(xi),mi=f(xi)，i=0,1,2,n 则称分段三次函数Hh(x)=yii(x)+yi+1i+1(x)+mii(x)+mi+1i+1(x)xxi,xi+1，i=0,1,n1(4.3.13)为f(x)在区间a,b上关于划分的分段分段Hermite三次插值多项式三次插值多项式。其中，插值基函数插值基函数为三次多项式(4.3.9)。第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值现在学习的是第44页，共68页如此定义的分段三次多项式满足边界条件边界条件 (4.3.10)和内接点处的衔接条件衔接条件 i=0,1,2,n1 (4.3.13)因此，Hh(x)及其导数Hh(x)在区间a,b上都是连续的.可以证明，对于一阶导数连续的函数fC1a,b，不仅Hh(x)一致收敛于f(x)，而且Hh(x)一致收敛于f(x)。第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值现在学习的是第45页，共68页采用分段Hermite三次插值三次插值既可避免高次插值多项式的Runge现象现象，又可克服分段线性插值不光滑的缺陷。例例(Problem4.7)第第4章章 插值和拟合插值和拟合 分段低次插值分段低次插值现在学习的是第46页，共68页4.4 三次样条插值三次样条插值前面讨论的分段低次插值多项式都具有一致收敛性，但光滑性较差，Hh(x)在内节点处的二阶导数一般不连续，而且只有已知被插函数在所有插值节点的导数值，才能构造Hh(x)，而某些应用场合不可能也无必要知道被插函数在内节点处的导数值，这使Hh(x)的利用不甚方便，也不符合某些场合的要求。如飞机、船体的外形往往要求有二阶光滑度，即二阶导数连续。第第4章章 插值和拟合插值和拟合现在学习的是第47页，共68页把富有弹性的细长木条(即所谓样条)用压铁固定在样点上，其余部分自由弯曲，然后画下细木条形成的曲线，该曲线就称为样条曲线，它是由分段三次曲线拼接而成。在拼接点，即样点处，要求二阶导数连续。如图4-6的上图是船体横截面的部分外形的样条模型，下图是它的力学模型。样条曲线S(x)具有下列性质：其中，m(x)为转角；M(x)为弯矩，折线函数；Q(x)为剪力，阶跃函数，即每一段是常数。S(x)三次第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第48页，共68页下面讨论最常用的三次样条函数定义定义 4.4.1 若函数S(x)C2a,b，对于给定的一个划分：a=x0 x1 xn=b，(n2)(4.4.1)S(x)在每个小区间xi,xi+1上都是不超过三次的多项式,则称S(x)是区间a,b上关于划分的三次样条函数三次样条函数。若S(x)还满足插值条件S(xi)=f(xi)，i=0,1,2,n (4.4.2)则称S(x)为f(x)在区间a,b上关于划分的三次样条插值多项式三次样条插值多项式，其中，f(x)Ca,b。第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第49页，共68页假设由下表构造一个三次样条S(x)，x|x0 x1 x2 xn1 xny|y0 y1 y2 yn1 yn在每一个子区间x0,x1,x1,x2,xn1,xn，S(x)是不同的三次多项式，用Si(x)表示xi,xi+1上的S(x)。于是 Si1(x)和Si(x)在x=xi对应于同一个插值条件，即Si1(xi)=Si(xi)=yi，i=1,2,n1第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第50页，共68页因此S(x)在内节点自然连续。每个Si(x)有4个待定系数,S(x)共有4n个待定系数，因此需要4n个条件。按定义，有下列条件用于构造S(x)(1)在每个子区间xi,xi+1有2个插值条件Si(xi)=yi和Si(xi+1)=yi+1，i=0,1,2,n1，共2 n个(2)S(x)在n1个内节点的连续性，共n1个 Si1(xi)=Si(xi)，i=1,2,n1(4.4.4)(3)S(x)在n1个内节点的连续性，共n1个 Si1(xi)=Si(xi)，i=1,2,n1(4.4.5)因此，共有4n2个条件，确定4n个系数，余2个自由度，可根据需要加以利用。第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第51页，共68页通常用下列3种类型的附加条件，称为边界条件边界条件：(1)固支条件固支条件，已知两端点的一阶导数值 S(x0)=f(x0)，S(xn)=f(xn)(4.4.6)(2)已知两端点的二阶导数值 S(x0)=f(x0)，S(xn)=f(xn)(4.4.7)特别当 f(x0)=f(xn)=0时，称为自然边界条件自然边界条件。(3)周期条件周期条件 S0(x0)=Sn1(xn)，S0(x0)=Sn1(xn)(4.4.8)S(x)的周期条件由已知f(x0)=f(xn)确定。三种边界条件都有它们的实际意义和力学背景。第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第52页，共68页三弯矩算法三弯矩算法 推导区间xi,xi+1上的Si(x)首先，记Mi=M(xi)=S(xi)，且满足S(xi0)=Mi=S(xi 0)(i=1,2,n1)由于Si(x)是xi,xi+1上的三次插值多项式，因此Si(x)是xi,xi+1上的线性插值多项式，满足Si(xi)=Mi，Si(xi1)=Mi1，由Lagrange插值法有 (4.4.12)两次积分，得到 (4.4.13)第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第53页，共68页式中C、D是积分常数，由插值条件Si(xi)=yi，Si(xi+1)=yi+1代入确定：代入式(4.4.13)得到 (4.4.14)xxi,xi+1，i=0,12,n1式中Mi，Mi1未知。第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第54页，共68页只要确定了M0，M1,Mn，区间a,b上的S(x)就得到了。利用S(x)的连续性确定M1,Mn-1。在内节点S(x)必须满足Si-1(xi)=Si(xi)(i=1,2,n-1)，对Si(x)求导，再代入x=xi，得式(4.4.14)中令i=i-1得到 Si-1(x)，求导，代入x=xi，得到Si-1(xi)，第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第55页，共68页令Si-1(xi)=Si(xi)(i=1,2,n1，即所有内节点)，并注意到(yi+1yi)/hi=fxi,xi+1，(yiyi-1)/hi-1=fxi-1,xi，fxi,xi+1fxi-1,xi/(hi+hi-1)=fxi-1,xi,xi+1，得 hi-1Mi-1+2(hi+hi-1)Mi+hiMi+1=6fxi,xi+16fxi-1,xi两边除以(hi+hi-1)=xi+1xi-1，并令i=hi-1/(hi+hi-1)，i=hi/(hi+hi-1)得iMi-1+2Mi+iMi+1=6fxi-1,xi,xi+1=di i=1,2,n1 (4.4.18)这是待定值Mi(i=0,1,2,n)满足的线性方程组，因其每一式有3个弯矩，故称为三弯矩方程。于是，对于n+1 个未知数Mi(i=0,1,2,n)，有n1个线性方程。可以任选M0和 Mn的值，然后解方程组得到M1,M2,Mn-1。第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第56页，共68页一个不错的选择是M0=Mn=0，即自然边界条件，由此得到的样条函数称为自然三次样条。这样得到的n1阶线性方程组的系数矩阵是三对角阵，且(等间距时i=i=0.5)对称、严格对角占优 若M0和Mn不是0，则上式中d1用d11M0，dn1用dn1n1 Mn替代即可。这就是第2种边界条件。(接讲义)第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第57页，共68页三转角算法三转角算法 利用Hermite三次插值，可以得到三转角方程在第i个区间xi,xi+1上的Hermite三次插值为 Si(x)首先，记Mi=M(xi)=S(xi)，且满足S(xi0)=Mi=S(xi 0)(i=1,2,n1)，满足Si(xi)=Mi，Si(xi1)=Mi1，(4.4.13)第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第58页，共68页三转角算法三转角算法 利用Hermite三次插值，可以得到三转角方程在第i个区间xi,xi+1上的Hermite三次插值为 Si(x)首先，记Mi=M(xi)=S(xi)，且满足S(xi0)=Mi=S(xi 0)(i=1,2,n1)由于Si(x)是xi,xi+1上的三次插值多项式，因此Si(x)是xi,xi+1上的线性插值多项式，满足Si(xi)=Mi，Si(xi1)=Mi1，由Lagrange插值法有 (4.4.12)两次积分，得到 (4.4.13)第第4章章 插值和拟合插值和拟合 三次样条插值三次样条插值现在学习的是第59页，共68页4.6离散数据的曲线拟合离散数据的曲线拟合插值：插值：用给定函数族中的某函数精确的匹配给定的数据 P(xi)=f(xi)，i=0,12,n拟合：拟合：用给定函数族中的函数尽量的靠近给定的数据大量的实际问题中，已知节点的函数值通常是一些实验观测数据，是有误差的。要求在每个节点都与这些数据精确匹配是欠合理的。例如，Problem4.18，观察某匀速直线运动s=at+b，得到一组数据，确定参数a、b。第第4章章 插值和拟合插值和拟合现在学习的是第60页，共68页表格中的数据明显不在一条直线，与直线有偏差。若用大于一次的插值多项式代替直线，反而不合适。而且，为了使得到的函数更准确，往往增加观测次数多得到一些数据。如果采用以前讲的插值法处理，则产生节点数大于插值多项式次数的矛盾。当希望用低次多项式逼近所要求的函数，且实验数据又可任取多个时，就无法要求P(xi)=f(xi)精确成立。这就该用拟合了。给定一组数据xi|x0 x1x2xm f(xi)|y0 y1y2ym 第第4章章 插值和拟合插值和拟合 离散数据的曲线拟合离散数据的曲线拟合现在学习的是第61页，共68页用n次多项式Pn(x)=c0+c1x+cnxn 拟合f(x)，nm，要满足P(xi)=f(xi)，(i=0,1,2,m)，即(1)这个方程有n+1个未知数i(i=0,1,2,n)，m+1个方程由于n m，即方程个数多于未知数个数，通常是矛盾方程组,用一般的联立解方程组的方法是不行的。取其中n+1个方程解得一个解向量，这n+1个方程中换一个，得到另一个解向量。第第4章章 插值和拟合插值和拟合 离散数据的曲线拟合离散数据的曲线拟合现在学习的是第62页，共68页因此不能要求P(xi)=f(xi)，(i=0,1，2,m)精确成立，只能要求多项式尽可能的接近给定数据，即允许每个等式可以稍有偏差：(2)用矩阵描述：y=+其中，y=y0,y1,ymT,=0,1,nT,=0,1,mT 第第4章章 插值和拟合插值和拟合 离散数据的曲线拟合离散数据的曲线拟合现在学习的是第63页，共68页其中第i列i=0,12,n其中第j行，j=0,1,2,m于是 =0(x),1(x),n(x)=(x0),(x1),(xn)T我们希望确定 时，使误差向量 达到最小。度量向量的量是范数，1范数和范数都有绝对值的计算不方便在此处使用，因此用2范数。使 最小。第第4章章 插值和拟合插值和拟合 离散数据的曲线拟合离散数据的曲线拟合现在学习的是第64页，共68页这就给出了一种衡量拟合精度的准则，称为最小二乘原理。依据最小二乘原理拟合曲线的方法，称为最小二乘法最小二乘法。最小二乘法用于构造拟合曲线，就是