21插值与拟合

数学建模方法——插值与拟合•能不能用一个函数图像尽可能多的经过每一点呢？插值拟合插值与拟合的关系•在工程中，常有这样的问题：给定一批数据点（它可以是设计师给定，也可能是从测量与采样中得到），需确定满足特定要求的曲线或曲面。对这个问题有两种方法。一种是插值法。要求所求曲线（面）通过所给的所有数据点。另一种方法是数据拟合（曲线拟合与曲面拟合）。人们设法找出某条光滑曲线，它最佳地拟合数据，但不必要经过所有数据点。插值与拟合的关系•插值和拟合都是函数逼近或者数值逼近的重要组成部分：他们的共同点都是通过已知一些离散点集M上的约束，求取一个定义在连续集合S(M包含于S)的未知连续函数，从而达到获取整体规律的目的，即通过“窥几斑”来达到“知全豹”。简单的讲，所谓拟合是指已知某函数的若干离散函数值{f1,f2,…,fn}，通过调整该函数中若干待定系数f(λ1,λ2,…,λn),使得该函数与已知点集的差别(最小二乘意义)最小。如果待定函数是线性，就叫线性拟合或者线性回归(主要在统计中)，否则叫作非线性拟合或者非线性回归。表达式也可以是分段函数，这种情况下叫作样条拟合。而插值是指已知某函数的在若干离散点上的函数值或者导数信息，通过求解该函数中待定形式的插值函数以及待定系数，使得该函数在给定离散点上满足约束。插值函数又叫作基函数，如果该基函数定义在整个定义域上，叫作全域基，否则叫作分域基。如果约束条件中只有函数值的约束，叫作Lagrange插值，否则叫作Hermite插值。从几何意义上将，拟合是给定了空间中的一些点，找到一个已知形式未知参数的连续曲面来最大限度地逼近这些点；而插值是找到一个(或几个分片光滑的)连续曲面来穿过这些点。内容提纲•1、插值问题•2、数据拟合1、插值问题1.1、一维插值插值问题的一般提法：已知y=f(x)（该函数未知）在互异的n+1个点x0,x1,x2,…,xn处的函数值y0,y1,y2,…,yn,构造一个过n+1个点（xk,yk）k=0,1,2,…,n的次数不超过n的多项式y=Ln(x)，（称为插值多项式）使其满足Ln(xk)=yk，（称为插值条件）然后用y=Ln(x)作为准确函数y=f(x)的近似值。此方法称为插值法。Theorem：满足插值条件的次数不超过n的多项式是唯一存在的。两点一次(线性)插值多项式:101001011yxxxxyxxxxxL三点二次(抛物)插值多项式:2120210121012002010212yxxxxxxxxyxxxxxxxxyxxxxxxxxxL1.1.1Lagrange插值法就是满足插值条件的n次多项式——Lagrange插值多项式nixxxxxxxxxxxxxxxxxlniiiiiiniii1,0,)())(()()())(()()(110110jijixlji,0,1)(满足)()(0xlyxLiniin则上式称为Lagrange插值基函数例1、已知数据表解：基函数为x12f(x)0.950.82写出f(x)的线性插值函数,并求f(1.5)的近似值。82.0,2;95.0,11100yxyxxxxxxxxl2212)(10101121)(0101xxxxxxxl线性插值函数为08.113.0)1(82.0)2(95.0)()()(11001xxxxlyxlyxL且f(1.5)≈L1(1.5)=0.885。101001011yxxxxyxxxxxLLagrange插值法的缺点•多数情况下，Lagrange插值法效果是不错的，但随着节点数n的增大，Lagrange多项式的次数也会升高，可能造成插值函数的收敛性和稳定性变差。如龙格（Runge）现象。•例：在[-5,5]上用n+1个等距节点作插值多项式Ln(x),使得它在节点处的值与函数y=1/(1+25x2)在对应节点的值相等，当n增大时，插值多项式在区间的中间部分趋于y(x)，但对于满足条件0.728|x|1的x，Ln(x)并不趋于y(x)在对应点的值，而是发生突变，产生剧烈震荡，即Runge现象。Runge现象的程序(1)•clc;clf;clearall;•m=21;•x=-1:1/(m-1):1;•y=1./(1+25*x.^2);z=0*x;•n=3;•x0=-1:1/(n-1):1;y0=1./(1+25*x0.^2);y1=lagr(x0,y0,x);•subplot(2,2,1),•plot(x,z,'r-',x,y,'m-'),holdon%原曲线•plot(x,y1,'b'),gtext('L4(x)','FontSize',12),pause%Lagrange曲线•n=5;•x0=-1:1/(n-1):1;y0=1./(1+25*x0.^2);y1=lagr(x0,y0,x);•subplot(2,2,2),•plot(x,z,'r-',x,y,'m-'),holdon%原曲线•plot(x,y1,'b'),gtext('L8(x)','FontSize',12),pause%Lagrange曲线Runge现象的程序(2)•n=7;•x0=-1:1/(n-1):1;y0=1./(1+25*x0.^2);y1=lagr(x0,y0,x);•subplot(2,2,3),•plot(x,z,'r-',x,y,'m-'),holdon,%原曲线•plot(x,y1,'b'),gtext('L12(x)','FontSize',12),pause%Lagrange曲线•n=9;•x0=-1:1/(n-1):1;y0=1./(1+25*x0.^2);y1=lagr(x0,y0,x);•subplot(2,2,4),•plot(x,z,'r-',x,y,'m-'),holdon,%原曲线•plot(x,y1,'b'),gtext('L16(x)','FontSize',12)%Lagrange曲线1.1.2分段插值法•图中看到，随着节点的增加，Lagrange插值函数次数越高，插值函数在两端容易产生龙格现象，为了改进高次插值的缺陷，就产生了分段插值。•分段插值基本思想：将被插函数逐段多项式化。•处理过程：将区间[a,b]划分：•在每个子段上构造低次多项式，然后将其拼接在一起作为整个区间[a,b]上的插值函数，这样构造出的插值函数称为分段多项式，改进了多项式插值整体性太强的缺点，可以进行局部调整而不会影响整体。bxxan0],[1iixx分段线性插值•设插值节点•若：•为已知。)(,],[,10iiinxfybaxxxx满足)(xLy上的分段线性插值。为则称是线性函数上在每个子段],[)(],[,)()(],[)2()()1(11111baxLyxxxyxxxxyxxxxxLxLyxxyxLiiiiiiiiiiiiii分段线性插值xjxj-1xj+1x0xn1.1.3三次样条插值•分段线性插值函数在结点的一阶导数一般不存在，光滑性不高，这就导致了样条插值的提出。•在机械制造、航海、航空工业中，经常要解决下列问题：已知一些数据点，如何通过这些数据点做一条比较光滑（如二阶导数连续）的曲线呢？•绘图员解决这一问题是首先把数据点描绘在平面上，再把一根富有弹性的细直条（称为样条）弯曲，使其一边通过这些数据点，用压铁固定细直条的形状，沿样条边沿绘出一条光滑的曲线，往往要用几根样条，分段完成上述工作，这时，应当让连接点也保持光滑。对绘图员用样条画出的曲线，进行数学模拟，这样就导出了样条函数的概念。三次样条插值问题提出•设在区间[a,b]上，已给n+1个互不相同的节点•a=x0x1…xn=b以及函数y=f(x)在这些节点的值f(xi)=yi,i=0,1,…,n.如果分段函数S(x)满足下列条件：•（1）S(x)在子区间[xi,xi+1]的表达式Si(x)都是次数为3的多项式；•（2）S(xi)=yi;•（3）S(x)在区间[a,b]上有连续的二阶导数。•就称S(x)为f(x)在点x0，x1，…，xn的三次样条插值函数.•即Si(x)=aix3+bix2+cix+dii=0,1,…,nxi≤x≤xi+1（4n个变量）•需要4n个方程•S(xi)=yii=0,1,…,n(n+1个方程）•S(xi-0)=S(xi+0)i=1,…,n-1在xi连续(n-1个方程）•S/(xi-0)=S/(xi+0)i=1,…,n-1在xi连续(n-1个方程）•S//(xi-0)=S//(xi+0)i=1,…,n-1在xi连续(n-1个方程）•再加两个条件:可在边界点x0与xn处给出导数的约束条件，称为边界条件。•（1）S//(x0)=f0//,S//(xn)=fn//•(2)S/(x0)=f0/,S/(xn)=fn/•(3)S//(x0)=S//(xn)=0自然边界条件（2个方程）•可以证明：满足上述4n个线性方程组有唯一解。三次样条插值问题分析总结•拉格朗日插值：其插值函数在整个区间上是一个解析表达式；曲线光滑；收敛性不能保证，用于理论分析，实际意义不大。•分段线性插值和三次样条插值：曲线不光滑（三次样条已有很大改进）；收敛性有保证；简单实用，应用广泛。1.2二维插值•二维插值是基于一维插值同样的思想，但是它是对两个变量的函数Z=f(x,y)进行插值。•求解二维插值的基本思路：构造一个二元函数Z=f(x,y)，通过全部已知结点，即f(xi,yi)=zi,(i=0,1,…n),再利用f(x,y)插值，即Z*=f(x*,y*)。•二维插值常见可分为两种：网格结点插值和散乱数据插值。•网格结点插值适用于数据点比较规范，即在所给数据点范围内，数据点要落在由一些平行的直线组成的矩形网格的每个顶点上，散乱数据插值适用于一般的数据点，多用于数据点不太规范的情况。xyO第一种（网格节点）：已知mn个节点其中互不相同，不妨设构造一个二元函数通过全部已知节点,即再用计算插值，即注意：最邻近插值一般不连续。具有连续性的最简单的插值是分片线性插值。xy(x1,y1)(x1,y2)(x2,y1)(x2,y2)O二维或高维情形的最邻近插值，与被插值点最邻近的节点的函数值即为所求。1.2.1网格节点插值法——最邻近插值将四个插值点（矩形的四个顶点）处的函数值依次简记为：xy(xi,yj)(xi,yj+1)(xi+1,yj)(xi+1,yj+1)Of(xi,yj)=f1，f(xi+1,yj)=f2，f(xi+1,yj+1)=f3，f(xi,yj+1)=f41.2.1网格节点插值法——分片线性插值插值函数为：jii1ij1jy)xx(xxyyy)yy)(ff()xx)(ff(f)y,x(fj23i121第二片(上三角形区域)：(x,y)满足iii1ij1jy)xx(xxyyy插值函数为：)xx)(ff()yy)(ff(f)y,x(fi43j141注意：(x,y)当然应该是在插值节点所形成的矩形区域内。显然，分片线性插值函数是连续的；分两片的函数表达式如下：第一片(下三角形区域)：(x,y)满足双线性插值是一片一片的空间二次曲面构成。双线性插值函数的形式如下：)dcy)(bax()y,x(f其中有四个待定系数，利用该函数在矩形的四个顶点（插值节点）的函数值，得到四个代数方程，正好确定四个系数。xy(x1,y1)(x1,y2)(x2,y1)(x2,y2)O1.2.1网格节点插值法——双线性插值yx0第二种（散乱节点）：已知n个节点其中互不相同，构造一个二元函数通