数值计算方法—解线性方程组的迭代法

25数值分析—插值─基于Matlab的实现与分析§4多项式函数与函数的最佳逼近§4.1插值(Interpolation)§4.1.1问题的提出在工程地质测量、机械设计及其制造、信号分析等实践中，经常回遇到曲线的描绘或函数的确定问题，平面上的曲线方程可写成如下的形式xfy（１）一般情况下，人们能够知道的或者说能够得到的只是曲线上的若干点，如通过测量可以得到曲线上niyxii,,1,0,（２）的1n个点，由于信息不全，这1n个点不足以确定其所在的曲线，因而人们退一步地希望在充分利用这些数据的前提下，确定一条“简单的”且与未知曲线“最接近”的曲线；此外，在科学研究和计算中，往往回遇到复杂函数的分析与计算，有时用简单的函数来代替，可能会去掉不必要的麻烦而使问题比较容易地得到解决。只需对自变量做加、减法和乘法运算就能得到函数值是多项式函数显著的特点之一，因此，从计算的角度来说多项式函26数是最简单的，因此，在函数最佳逼近方面，“简单的函数（曲线）”指的就是多项式函数（类）；所谓“最接近”或者严格地说最佳逼近，就是从指定的一类简单的函数中寻找一个和给定的函数“最贴近”的函数，从几何（空间）的角度看，函数最佳逼近就是从指定的一类简单的函数（点的集合）中寻找一个和给定的函数（定点）之间距离最短的函数（点）。函数空间中不同的距离度量确定了不同的逼近准则，不同的逼近准则定义了不同的函数最佳逼近。在插值问题中，最佳逼近准则是：在已知的全部点处，简单函数（被插值多项式）的函数值与未知函数的函数值相等，即kkyxPnk,,2,1,0（３）§4.1.2关于插值问题的基本定理定理：给定1n个曲线上点niyxii,,1,0,,，如果ix，ni,,1,0互不相同，那么，在所有次数不超过n次的多项式函数中，存在唯一的多项式函数xPn，满足条件（３）。证明：次数不超过n的多项式xPn可写成nnnxaxaaxP10（４）27的形式，要证明在所有次数不超过n次的多项式函数中，存在唯一的多项式函数xPn，满足条件（３），等价与证明线性方程组ininiinyxaxaaxP10ni,,1,0（５）即nnnnnnnyyyaaaxxxxxx10101100111（６）有唯一解，线性方程组（６）有唯一解的充分必要条件是系数矩阵满秩，因为方程组（６）的系数矩阵是Vandomonder矩阵，满秩的充分必要条件是ix，ni,,1,0互不相同，因此，当ix，ni,,1,0互不相同时，存在唯一的次数不超过n次的多项式满足条件（３）。§4.1.3构造插值多项式的方法１）一点说明可以通过解线性方程组（６），得到插值多项式（４）的系数1a，ni,,1,0，但是２）拉格朗日（Lagrange）插值法（１）构造插值多项式的基函数28nkkkkkkknkknkjjjkjkxxxxxxxxxxxxxxxxxxxxxxxxxL111011100nk,,2,1,0（７）（２）拉格朗日插值多项式nkkkyxLxL0（８）（３）简单的证明因为拉格朗日插值多项式的基函数有如下的性质：kjxxxxxxxxxLjknkjjjkjk,010nk,,2,1,0（９）所以拉格朗日插值多项式kkkknjjkjkyyxLyxLxL0nk,,2,1,0（１０）满足插值的条件。（４）拉格朗日插值法的不足在实际问题中，观测的数据可能会不断增加，如果用拉格朗日插值公式构造插值多项式，那么，每当增加数据就要重新计算多项式的系数，由此增加许多不必要的计算工作量。３）牛顿（Newton）插值法29将插值多项式xPn写成下面的形式110102010nnnxxxxxxaxxxxaxxaaxP（１１）其系数的确定有如下的特点：计算第k个系数只用到前k对数据，如000yxPan，010101011xxyyxxaxPan因此，当数据增加时，不需要重新计算已有的多项式系数，例如，在已得到插值多项式（１１）的情况下，当新增加一对数据11,nnyx时，只需要在原有的插值多项式的基础上增加一项110nnxxxxxxa因此，对于新的插值多项式nnnnnxxxxxxaxxxxxxaxxxxaxxaaxP1011101020101只需要计算系数1na。30４）简单的例子与高次多项式插值的Runge现象Plot_LangInterp-3-2-10123-4-3-2-101234RungePhenomenoninInterpolationwithHighDegreePolynomial31Plot_Runge-1-0.8-0.6-0.4-0.200.20.40.60.81-0.500.511.52RungePhenomenoninInterpolationwithHighDegreePolynomial----f(x)=1/(1+25x2)----InterpolationPolynomialofDegree10５）分段低次多项式插值６）厄米特（Hermite）多项式插值如果插值条件为：mkkmkkkkyxPyxPyxP,,,nk,,2,1,0（３）这时的插值问题称为厄米特插值问题。32７）（三次）样条（Spline）插值（１）插值条件要求所求的插值多项式xS（三次样条函数）a在每个区间kkxx,1，nk,,2,1,0，是次数不超过三次的多项式；bkkyxS，nk,,2,1,0；cxS在区间nxx,0上具有二阶连续导数。（２）确定三次样条函数的条件根据三次样条插值的要求，样条插值函数在每个小区间kkxx,1，nk,,2,1,0，上都是三次多项式，每个三次多项式有四个系数，总共需要确定n4个系数，因此，需要n4个条件才能保证唯一地确定满足要求的三次样条插值函数。已知条件b给出了1n条件：kkyxS，nk,,2,1,0；（4）33条件c要求xS在区间nxx,0上具有二阶连续导数，所以，插值函数在中间插值节点kx，1,,2,1nk，处，必须满足条件：00kkxSxS，1,,2,1nk；（5）00kkxSxS，1,,2,1nk；（6）00kkxSxS，1,,2,1nk；（7）这样已有24n个条件，还需要2个条件，才能保证对插值函数的唯一性要求；为此，通常在插值区间的端点处附加2个条件：１）定端点的斜率：固定边界条件：00yxS，nnyxS（８）２）给定端点的的二阶导数：自由边界条件：00yxS，nnyxS（９）３）期性条件：nmmxSxS02,1,0m（１０）34（２）三次样条插值函数的构造１）设待求的三次样条插值函数xS在各插值节点处的一阶、二阶导数为kkmxS，nk,,2,1,0；（１２）kkMxS，nk,,2,1,0；（１３）由于插值函数xS在各小区间kkxx,1，nk,,2,1,0，上都是三次多项式，所以二阶导数xS是一次多项式，记kkkxxh1，1,,2,1,0nk（１４）利用Lagrange插值公式，xS可表示为：11kkkkkkMhxxMhxxxS，1,,2,1,0nk（１５）对式（１５）的两端积分kkkkkkkkkkkkhxxDhxxCMhxxMhxxxS1133166351,,2,1,0nk（１6）kkkkkkkkMhxSCCMhxS66221,,2,1,0nk（１7）12112166kkkkkkkkMhxSDDMhxS1,,2,1,0nk（１8）111221122162222kkkkkkkkkkkkkkkkkkkkkMMhhyyMhxxMhxxhDCMhxxMhxxxS1,,2,1,0nk（１9）利用条件00kkxSxS，1,,2,1nk；（20）kkkkkkkkkMMhhyyMhxS1111162006211kkkkkkkkkxSMMhhyyMh1,,2,1,0nk（21）11111116626kkkkkkkkkkkkkhyyhyyMhMhhMh1,,2,1,0nk（22）令kkkkhhh11，kkkkhhh1，1,,2,1nk（2３）36clearpackclfx=-pi:0.2:pi;xi=-pi:0.3:pi;f=x.*exp(x).*cos(x);y=csape(x,f,'complete',[1,-1]);fplot('t*exp(t)*cos(t)',[-pi,pi])holdonfnplt(y,'r')-3-2-10123-80-70-60-50-40-30-20-10010