上海交通大学计算方法课件(宋宝瑞)CH.4

1第五章函数的插值及其数值计算§1插值的基本概念插值方法是数值分析中一个很古老的分支，它有着悠久的历史。插值理论和方法也是现代数值分析中最基本的内容之一，它在数值积分，曲线曲面拟合，求微分方程数值解等方面有着广泛的应用。在工程技术与科学研究中，有时对一个函数只知道它在某些点上的数值，为了进一步研究其性质，需要用其他函数去近似代替它，这时就可以用插值方法。有时候，虽然函数有解析表达式，但形式过于复杂，为了便于处理，先在某些点上取值作表格函数，再通过插值建立易于处理的新函数，这也是插值理论的一个应用。先介绍一般的插值概念。设)(xf，bax,。已知它在1n个互异的点0x，…，nx处的函数值0y，1y，…，ny，即：iiyxf)(，0i，1，…，n求解插值问题就是从函数类中求)(x使iiyx)(，0i，1，…，n（1.1）2这里的)(xf称为被插函数，ba,称为插值区间，ix，0i，1，…，n，称为插值节点，（1.1）式称为插值条件，而)(x和分别为插值函数和插值函数类。通常选定的插值函数类是有限维线性空间，它可看成是某一组基niix0)(张成的线性空间：niixSpan0)(对，有niia0使得niiixax0)()(于是确定函数)(x归结为确定数列niia0。从理论上看，插值问题包含以下内容：（1）确定的基niix0)(，一般地说基不唯一，选择合适的基可以简化问题的解法；（2）讨论满足（1.1）的)(x的存在性，求法及唯一性；（3）寻找插值问题的截断误差，即余项：)()()(xxfxR的表达式与估计。3§2多项式插值本节选取常用的多项式函数类作插值函数类。多项式函数属于解析函数类，形式简单，计算方便，其导数与不定积分易于求出。下面把不超过n次的多项式函数类记为nP2.1Lagrange插值设已知)(xf，bax,在相异节点0x，1x，…，nx上的函数值iiyxf)(，0i，1，…，n，取=nP，下面求)(xf的插值函数。设2012()nnpxaaxaxax，插值的基本问题是，寻求如上的()px，使得()iipxy，0i，1，…，n.该问题等价于求解下列线性方程组：20102000201121112012nnnnnnnnnnaaxaxaxyaaxaxaxyaaxaxaxy上述线性方程组的系数矩阵为：4200021112111nnnnnnxxxxxxAxxxA的行列式为（称为Vandermonde行列式）2000211101211(,,,)1nnnnnnnxxxxxxWxxxxxx根据线性代数的知识知道010(,,,)()njinjiWxxxxx注意到诸ix互不相同，从而01(,,,)0nWxxx，上述线性方程组存在唯一解。这说明满足条件（1.1）的插值多项式是存在的，而且还是唯一的。定理2.1设)(xf，bax,0niix为ba,上的n+1个相异的节点，)(iixfy，i=0，1，…，n，则满足()iipxy，i=0，1，…，n的()pxnP是存在并且唯一的。从定理2.1的证明可看到，要求插值多项式p(x),可以通过求解一个线性方5程组得到。但这样做不但计算复杂，且难于得到p(x)的简单表达式。为了求得便于使用的简单的插值多项式p(x)，可以如§1所述，选择nP的适当的基。先构造n次插值基函数)(xlinP，i=0，1，…，n使1()0ijijijlxij，，0i，1，…，n，（2.1）由当ij时，0)(jixl可知：0()()niikkkilxcxx0i，1，…，n（2.2）其中ic是待定常数，它可由1)(iixl定出：10()niikkkicxx；0i，1，…，n。代入（2.2）得：0()nkikikkixxlxxxi=0，1，…，n再作000()()nnnkniiiiikikkixxLxylxyxx易知nLnP，即为所求的插值函数。6这种具有ij性质的基称为对偶基，以后我们还会多次构造针对不同问题的对偶基。记10()()nnkkxxx，则10()()nniikkkixxx，10()()nnkkikixxxxx，11()()()niinixlxxxx，i=0，1，…，n，101()()()nnniiinixLxyxxx例2.1已知xxf1)(，节点为10x，21x，42x，求)(2xL解1)(00xfy，21)(11xfy，41)(22xfy。)86(31)41)(21()4)(2()(20xxxxxl21(1)(4)1()(54)(21)(24)2xxlxxx)23(61)24)(14()2)(1()(22xxxxxl72220177()()884iiiLxylxxx2.2插值多项式的插值余项现在考虑用)(xLn近似)(xf所产生的误差，即插值余项)()()(xLxfxRnn当)(xf在ba,上n+1阶可导时，可以把)(xRn化为便于估计的形式，先设ixx，i=0，1，…，n，作辅助函数1()()()()()nnFtftLtKxt，bat,其中()Kx满足：1()()()()0nnfxLxKxx（2.3）当x不为插值节点时1()0nx，这样的)(xK是存在的。于是0xt，1x，…，nx，x是)(tF的n+2个相异的零点，依次对)(tF，)(tF，…，)()(tFn应用Rolle定理可知存在ba,使0=(1)(1)()()()(1)!nnFfKxn从而8(1)()()(1)!nfKxn代入（2.3）式得：(1)1()()()(1)!nnnfRxxn，ba,若x等于某一ix，则1()0nx，0)(xRn故任取bax,上式也成立。于是得出：定理2.2（多项式插值的余项）设)(xf在ba,上n+1阶可导，则存在ba,使(1)1()()()()()(1)!nnnnfRxfxLxxn注：由上式可知，当fnP时，)()(xfxLn，特别当1)(xf时，可得：0()1niilx（2.4）例2.2考察四位常用对数表作线性插值的误差。解设xxflg)(，2lg)(xexf，elg＜0.4343。设x位于0x和1x之间：1≤0x＜x＜1x，则1012lg()()()2eRxxxxx，0x≤≤1x9记表距01xxh，得4))((max21010hxxxxxxx211200.4343(lg()()8hxLxRxx=220205429.005429.0hxh当h=0.01时，6110429.5)((lgxLx（2.5）再考虑舍入误差，设iiiifxfy)(，i=0，1其中if是表值，i是舍入误差，则：5105iiify，i=0，1（2.6）把以iy，if，i=0，1构造的线性插值分别记为)(1xL，)(*1xL，注意到)(xli，i=0，1在10,xx上非负及（2.5），（2.6）式，则线性插值的舍入误差*211()()()RxLxLx1100()()iiiiiiylxflx1010max()0,1iiiiyflxi10()iilx==5105可见舍入误差比截断误差大一个量级。此时整个误差不超过6512()()5.42910510RxRx5105429.52.3Newton插值Lagrange插值公式的缺点是，当插值节点的个数有所变动时（例如为了提高精度，有时需要增加节点个数），Lagrange插值基函数)(xli，i=0，1，…，n就要随之发生变化，从而整个公式的结构也要发生变化，这在计算实践中是不方便的。为了克服上述缺点，在这一节中我们引入Newton插值公式。令)(1xNn表示n个节点0x，1x，…，1nx上的n-1次插值多项式，由于iininyxNxN)()(1，i=0，1，…，n-1所以11101()()()()nnnNxNxcxxxx此处c为常数，由条件，可以定出)())(()(1101nnnnnnnxxxxxxxNyc因此，n+1个节点0x，1x，…，nx上的n次插值多项式也可以写成下列形式：010011()()()()()nnnNxaaxxaxxxxxxNewton插值公式的系数如何确定?为此我们引进差商的概念。设已知不同的自变量nxxx,,,10上的函数值)(ixf，i=0，1，…，n，称()()[,]ijijijfxfxfxxxx，ji为)(xf的一阶差商（式均差）。一阶差商的一阶差商[,][,][,,]()ijjkijkikfxxfxxfxxxikxx叫做)(xf的二阶差商。一般说来，我们称n-1阶差商的一阶差商01112010[,,,][,,,][,,,]nnnnfxxxfxxxfxxxxx为函数)(xf的n阶差商。12根据差商定义设[,]xab为一动点，00000101101010()()[,]()[,][,][,,]()[,,,][,,,][,,,]()nnnnfxfxfxxxxfxxfxxfxxxxxfxxxfxxxfxxxxx只要把后一式代入前一式，即得：001001201()()[,]()[,,]()()fxfxfxxxxfxxxxxxx00101[,,]()()[,,,]()nnnnfxxxxxxfxxxx:()()nnNxRx其中()nnNxP且满足插值条件，称为Newton插值公式。而()nRx＝01[,,,]()nnfxxxx为插值余项。用数学归纳法易证明n阶差商10101()[,,,]()nininifxfxxxx为了作数值计算常利用形式如下的差商表x)(xf一阶差商二阶差商三阶差商0x)(0xf1x)(1xf01[,]fxx132x)(2xf12[,]fxx012[,,]fxxx3x)(3xf23[,]fxx123[,,]fxxx0123[,,,]fxxxx插值公式（2.9）中的系数就是上表中带下划线的项。因此当已知)(iixfy，i=0，1，…，n时，利用差商表可以很容易地算出的各阶差商的值。因为在n+1个不同的点0x，1x，…，nx上取给定值的次数不超过n的多项式是唯一的，所以次数相同的Newton插值多项式与Lagrange插值多项式是恒等的，它们的差异仅是书写形式不同而已，但是这种差异却为计算实践带来了很大的方便，实际上，对于Newton插值公式来说，当需要增加一个插值点时，只需要在原插值多项式的后面再添加一个新项就可以了。2.6Hermite插值为了理论和应用上的需要，有时不但要求插值函数p(x)在节点处的函数值与被插值函数f(x)相同，而且要求在节点处的导数值也相等，这就导致了下面的Hermite插值。给定f(x)在n＋1个互异的节点01,,,nxxx处的函数值()iifxy及导数值()iifxy，i=0，1，…，n，要求一个次数不超过2n＋1次的多项式21()nHx满足142121(),()niiniiHxyHxy，i=0，1，…，n，（2．19）我们从构造Lagrange插值多项式的方法得到启发，设法构造Hermite插值问题的对偶基。即构造两组次数都是2n＋1次的多项式01()(