多项式插值与逼近.ppt
多项式插值与逼近多项式插值与逼近现在学习的是第1页，共15页 对于插值曲线而言，曲线上的这些数据点与参数域内的点构成一种对应关系。一组数据点决定一个参数分割，称为对数据点实行参数化(parametrization)对数据点实行参数化有如下方法：1.均匀参数化(等距参数化)法 仅适合于数据点多边形各边（或称弦长）接近相等的场合。注意：即使数据点各弦长严格相等，也不表示插值曲线的参数化是均匀的，插值曲线的参数化与数据点的参数化有关，但不是一回事。2.积累弦长参数化(简称弦长参数化)法 其中，为向前差分矢量3.向心参数化法（平方根法）-10-1u=0=+iiiuuPiP-1012-1u=0=+iiiu uP现在学习的是第2页，共15页4.福利（Foley，1989）参数化法（修正弦长参数化法）有些看不懂-10i-1u=0=+kiiiu uP3.2 多项式插值曲线 当构造多项式插值曲线时，必须使曲线方程的待定系数矢量的个数等于给定的插值条件数即数据点数目。在构造顺序通过数据点Pi(i=0,1,n)的多项式插值曲线时，（1）若采用的多项式基为幂基时，得插值曲线方程为nj=0(u)=jjpau现在学习的是第3页，共15页 设已对数据点实行了参数化，决定了参数分割01:.unu uu将参数值代入曲线方程，使之满足插值条件nij=0(u)=jjiipauP可将其写成矩阵的形式，也可以将插值曲线方程写成嵌套乘积的形式，这样便于编程，减少舍入误差。用此方法来构造插值曲线时，需要解线性方程组，当n很大时，系数矩阵呈现病态，此方法不可取现在学习的是第4页，共15页(2)拉格朗日多项式插值法是最古老的插值方法.参数形式的拉格朗日插值曲线方程为：njj=0(u)=p(u)jpL其中，是拉格朗日基，它满足插值条件(u)jLnijiij=0(u)=p(u)=P jpLiji0 ij(u)=1 i=jjL给定约束方程，其中的符号是克罗内克尔符号现在学习的是第5页，共15页 拉格朗日基具有规范性，公式具有明显的规律性，数据点Pi在曲线方程中显示的出现，这些都是拉格朗日插值的优点，缺点在于数据点改变时，原来的数据不能使用，必须重新计算。（4）牛顿均差形式-10ji=1=0(u)=d+d(u-u)jnjip这里引入了另外一组基：1，u,(u-u0)*(u-u1).,矢量dj是数据点Pi的j阶均差矢量。（5）埃尔米特插值此方法不是对n+1个点及其导矢进行插值，而是在两个数据点P0、P1及其直到K阶的导矢之间进行插值1(r)i=0=0(u)=(u)kirirpp H有点不懂现在学习的是第6页，共15页3.3最小二乘逼近最小二乘逼近 本节所讲的最小二乘逼近的分析方法与学过的理论相似，只是曲线的方程采用了基表示的参数多项式形式。根据前几节的知识，对于给定数据点，可以选择适当的方法进行参数化，决定一个参数分割，然后根据插值曲线所满足的插值条件，就可以得到线性方程组(其中插值曲线的次数n小于数据点的数目m)k=0(u)=niikiaPK=0,1,m相应的可以写成矩阵形式，由条件知，矢量方程的个数m+1大于未知矢量的个数n+1，这样的方程是超定的。一般情况下，方程的解不存在，即一般不存在严格依次通过这些数据点的曲线P(u),只能寻求在某种意义下最为接近这些数据点的参数多项式曲线来逼近曲线。现在学习的是第7页，共15页 通常，用逼近曲线上参数值为Uk的点P(Uk)与数据点Pk间距离的平方和 2kkk=0=(u)-P=+mxyzJPJJJ达到最小来刻划逼近的程度。下面就是根据求偏导来计算。由于输入比较麻烦，就不详细了现在学习的是第8页，共15页3.4 弗格森参数三次曲线弗格森参数三次曲线 由于高次参数多项式曲线存在缺点，不适合用来插值，而低次多项式曲线又难以用来描述形状复杂的曲线。唯一的选择就是：将一段段低次曲线在满足一定的连接条件下逐段拼接起来。这样以分段(piecewise)方式定义的曲线称为组合(composite)曲线。3.4.1 参数三次曲线方程参数三次曲线方程 参数三次（parametric cubic）曲线，简称PC曲线，若采用幂基表示230123(t)=a+0,1pa t ata tt可见，曲线段是定义在规范参数域0,1上的。下面就需要确定四个系数矢量ai，进而确定曲线段方程。(3.1)现在学习的是第9页，共15页 通常采用的方法是，规定曲线段两端点及其切矢。下面就将(3.1)式对t求导，并将t=0,1代入，得到如下方程 001231123=(0)+a+=(1)a=p(0)+2+3=p 1apaaapaaa可以写成矩阵的形式，可以求解出系数矢量。0123(0)1000p(1)0010=-33-2-1p(0)2-211p(1)paaaa现在学习的是第10页，共15页将上式代入（3.1）得23(0)1000p(1)0010(t)=1-33-2-1p(0)2-211p(1)ppttt上式实际上是与标量形式的三次埃尔米特插值相对应的参数形式，即是定义在0,1上的参数三次埃尔米特插值。将上式中前两个矩阵相乘即可得四个混合函数(blending functions)，也即三次埃尔米特基(3.5)现在学习的是第11页，共15页3.4.2 参数三次曲线的几何特征此部分内容有点模糊3.4.3 三次埃尔米特插值的域变换 实践中，我们往往想得到任意参数域 上的三次埃尔米特插值，解决方法是对(3.5)中的参数作域变换。+1-=t(u)=-iiiiiu utuu代入（3.5）得P=P(t(u)令ii+1u,uuii+1u,uu现在学习的是第12页，共15页分别用参数域端点Ui和Ui+1代入，即得i+1i+1=(t(u)=p(0)=(t(u)=p(1)iipppp曲线段两端点保持不变。现在学习的是第13页，共15页现在学习的是第14页，共15页现在学习的是第15页，共15页
