Lecture5_插值

1插值─基于Matlab的实现与分析§4多项式函数与函数的最佳逼近§4.1插值(Interpolation)§4.1.1问题的提出在工程测量、机械设计及其制造、信号分析等实践中，经常会遇到曲线的描绘或函数的确定问题，平面上的曲线方程可写成如下的形式yfx（1）2一般情况下，人们能够知道的或者说能够得到的只是曲线上的若干点，例如通过测量得到曲线上的1n个点：,,0,1,,iixyin（2）由于信息不全，这1n个点不足以确定其所在的曲线，因而人们退一步地希望在充分利用这些数据的前提下，确定一条“简单的”并且与该未知曲线“最接近”的曲线。此外，在科学研究和计算中，往往回遇到复杂函数的分析与计算，有时用简单的函数来代替，可能会去掉不必要的麻烦而使问题比较容易地得到解决。3只需对自变量做加、减法和乘法运算就能得到函数值是多项式函数显著的特点之一，因此，从计算的角度来说多项式函数是最简单的，因此，在函数最佳逼近方面，“简单的函数（曲线）”指的就是多项式函数（类）；所谓“最接近”或者严格地说最佳逼近，就是从指定的一类简单的函数中寻找一个和给定的函数“最贴近”的函数，从几何（空间）的角度看，函数最佳逼近就是从指定的一类简单的函数（点的集合）中寻找一个和给定的函数（定点）之间距离最短的函数（点）。函数空间中不同的距离度量确定了不同的逼近准则，不同的逼近准则定义了不同的函数最佳逼近。4在插值问题中，最佳逼近准则是：在已知的全部点处，简单函数（插值多项式）的函数值与未知函数的函数值相等，即kkPxy，0,1,2,,knL（3）§4.1.2关于插值问题的基本定理定理：给定1n个曲线上点,,0,1,,iixyinL，如果ix，0,1,,inL互不相同，那么，在所有次数不超过n次的多项式函数中，存在唯一的多项式函数nPx，满足条件（3）。证明：次数不超过n的多项式nPx可写成01nnnPxaaxaxL（4）5的形式，要证明在所有次数不超过n次的多项式函数中，存在唯一的满足条件（3）的多项式函数nPx，等价与证明线性方程组01nniiniiPxaaxaxyL，0,1,,inL（5）即00001111111nnnnnnnayxxayxxayxxLLMMMMOML（６）有唯一解，线性方程组（6）有唯一解的充分必要条件是系数矩阵满秩，因为方程组（6）的系数矩阵是Vandomonder矩阵，这类矩阵满6秩的充分必要条件是ix，0,1,,inL互不相同，因此，当ix，0,1,,inL互不相同时，存在唯一的次数不超过n次的多项式满足条件（3）。§4.2构造插值多项式的方法一点说明可以通过解线性方程组（5），得到插值多项式（4）的系数ia，0,1,,inL，但是…人们找到了更直接更好的办法。§4.2.1拉格朗日（Lagrange）插值法§4.2.1.1构造插值多项式的基函数7001110111njkjkjjkkknkkkkkkknxxLxxxxxxxxxxxxxxxxxxxxxxxLLLL，0,1,2,,knL（7）§4.2.1.2拉格朗日插值多项式0nkkkLxLxy（8）§4.2.1.3简单的证明8因为拉格朗日插值多项式的基函数有如下的性质：010,njkkjjkjjkxxxxLxxxjkxx0,1,2,,knL（9）所以拉格朗日插值多项式0nkjkjkkkkjLxLxyLxyy，0,1,2,,knL（10）满足插值的条件。附程序1：Lagrange_Fun_01.m附程序2：LagrangeInterp_01.m附程序2：LagrangeInterp_02.m9§4.2.1.4拉格朗日插值多项式的余项——误差令1010nnknkxxxxxxxxL当被插值函数fx在区间,ab具有直到1n阶导数时，存在一点,ab使得：111!nnnnfRxfxLxxn§4.2.1.5拉格朗日插值法的不足10在实际问题中，观测的数据可能会不断增加，如果用拉格朗日插值公式构造插值多项式，那么，每当增加数据就要重新计算多项式的系数，由此增加许多不必要的计算工作量。§4.3牛顿（Newton）插值法将插值多项式nPx写成下面的形式010201011nnnPxaaxxaxxxxaxxxxxxLL（11）其系数的确定有如下的特点：计算第k个系数只用到前k对数据，如000naPxy，11101011010nPxayyaxxxx，20120220212220120202110202020211020102021101211nPxaaxxaxxxxyayaaxxxxxxyyyyxxxxxxxxyyyyxxxxxxxx12因此，当数据增加时，不需要重新计算已有的多项式系数，例如，在已得到插值多项式（11）的情况下，当新增加一对数据11,nnxy时，只需要在原有的插值多项式的基础上增加一项101nnaxxxxxxL（12）因此，对于新的插值多项式1010201011101nnnnnPxaaxxaxxxxaxxxxxxaxxxxxxLLL只需要计算系数1na。1314§4.4简单的例子与高次多项式插值的Runge现象附程序3：Plot_Runge_01.m-1-0.8-0.6-0.4-0.200.20.40.60.81-0.500.511.52RungePhenomenoninInterpolationwithHighDegreePolynomialFunction:f(x)=1/1+25x2TheInterpolationNodesTheInterpolationPolynomial15§4.5分段低次多项式插值1厄米特（Hermite）多项式插值如果插值条件为：对给定的正整数m，在每个区间1,kkxx，0,1,2,,knL，,,,kkkkmmkkPxyPxyPxyM0,1,2,,knL（13）这时的插值问题称为厄米特插值问题。16§4.6（三次）样条（Spline）插值§4.6.1插值条件要求要求所求的插值多项式Sx（三次样条函数）1.在每个区间1,kkxx，0,1,2,,knL，是次数不超过三次的多项式；2.kkSxy，0,1,2,,knL；3.Sx在区间..上具有二阶连续导数。17§4.6.2确定三次样条函数的条件根据三次样条插值的要求，样条插值函数在每个小区间1,kkxx，0,1,2,,knL，上都是三次多项式，每个三次多项式有4个系数，总共需要确定4n个系数，因此，需要4n个独立条件才能保证唯一地确定满足要求的三次样条插值函数。已知：条件2给出了1n条件：kkSxy，0,1,2,,knL；（14）18条件3要求Sx在区间0,nxx上具有二阶连续导数，所以，插值函数在中间插值节点kx，1,2,,1knL，处，必须满足条件：00kkSxSx，1,2,,1knL；（15）00kkSxSx，1,2,,1knL；（16）00kkSxSx，1,2,,1knL；（17）这样已经有个条件：13142nnn还需要2个条件，才能保证对插值函数的唯一性要求；为此，通常在插值区间的端点处附加2个条件：19第一类边界条件：固定端点的斜率：固定边界条件：00Sxy，nnSxy（18）第二类边界条件：给定端点的的二阶导数：自由边界条件：00Sxy，nnSxy..（19）第三类边界条件：周期性条件：0mmnSxSx1,2m(20)20§4.6.3三次样条插值函数的构造1.设待求的三次样条插值函数Sx在各插值节点处的一阶、二阶导数为kkSxm，0,1,2,,knL；(21)kkSxM，0,1,2,,knL；(22)由于插值函数Sx在各小区间1,kkxx，0,1,2,,knL，上都是三次多项式，所以二阶导数Sx是一次多项式，记1kkkhxx，01kn；(23)利用Lagrange插值公式，Sx在各个区间1,kkxx上可表示为：2111kkkkkkxxxxSxMMhh，01kn(24)对式（24）的两端积分两次，得到样条函数每个区间1,kkxx上的表达式：3311166kkkkkkkkkkkkxxxxxxxxSxMMCDhhhh，01kn(25)在每个小区间的左端点kx处2266kkkkkkkkhhSxMCCSxM，01kn(26)22和右端点1kx处22111166kkkkkkkkhhSxMDDSxM，01kn，(26)3311131113116666kkkkkkkkkkkkkkkkkkkkkkkkkkkkxxxxxxxxSxMMCDhhhhxxxxMhxxfxhhxxxxMhxxfxhh，01kn(25)23利用插值条件：kkSxy得到一阶导数的表达式：221122111122226kkkkkkkkkkkkkkkkkkkkkxxxxCDSxMMhhhxxxxyyhMMMMhhh01kn，(27)由此确定了2n个系数：,,01kkCDkn。再利用一阶导数在中间1n个点处的连续性：2400kkSxSx，11kn；（28）得到1n个等式（方程）：11111026kkkkkkkkkhyyhSxMMMh11026kkkkkkkkkhyyhMMMSxh11kn（29）经进一步整理：1111111636kkkkkkkkkkkkkhhhhyyyyMMMhh2511kn（30）最终归结为求解1n阶的三对角线性方程组Axb的问题，其中：1222332321110036636006660063nnnnhhhhhhhhhAhhhhLOMOMOOOL（31）2610021021322132122312112166nnnnnnnnnnnnnnyyhyyMhhyyyyhhbyyyyhhyyyyhMhhM（32）27121nMMxMM（33）对于自然边界条件，有00,0nMM（34）附程序：Interpolation_Spline_02.m附程序：Interpolation_Spline_03.m28