资源描述
1第五章 函数的插值及其数值计算1 插值的基本概念插值方法是数值分析中一个很古老的分支，它有着悠久的历史。插值理论和方法也是现代数值分析中最基本的内容之一，它在数值积分，曲线曲面拟合，求微分方程数值解等方面有着广泛的应用。在工程技术与科学研究中，有时对一个函数只知道它在某些点上的数值，为了进一步研究其性质，需要用其他函数去近似代替它，这时就可以用插值方法。有时候，虽然函数有解析表达式，但形式过于复杂，为了便于处理，先在某些点上取值作表格函数，再通过插值建立易于处理的新函数，这也是插值理论的一个应用。先介绍一般的插值概念。设 ， 。已知它在 个互异的点 ， 处的函数值 ，)(xfba,1n0xn0y， ，即：1yn， ，1，niiyxf)(求解插值问题就是从函数类 中求 使)(x， ，1，n （1.1）iiyx)(02这里的 称为被插函数， 称为插值区间，)(xfba,， ，1 ，n ，称为插值节点， （1.1）式称为插值条件，而 和ix0 )(x分别为插值函数和插值函数类。通常选定的插值函数类是有限维线性空间，它可看成是某一组基张成的线性空间：niix0)(niixSpa0)(对 ，有 使得nia0niixax0)()(于是确定函数 归结为确定数列 。)(xni从理论上看，插值问题包含以下内容：（1）确定 的基 ，一般地说基不唯一，选择合适的基可以简化nii0)(问题的解法；（2）讨论满足（1.1）的 的存在性，求法及唯一性；)(x（3）寻找插值问题的截断误差，即余项： )()(xfR的表达式与估计。32 多项式插值本节选取常用的多项式函数类作插值函数类。多项式函数属于解析函数类，形式简单，计算方便，其导数与不定积分易于求出。下面把不超过 n 次的多项式函数类记为 nP2.1 Lagrange 插值设已知 ， 在相异节点 ， ， 上的函数值)(xfba,0x1nx， ， 1， ， n， 取 = ，下面求 的插值函数。iiyf)(0nP)(f设，201() npxaxa插值的基本问题是，寻求如上的 ，使得 ，()()iipy， 1， ， n.0i该问题等价于求解下列线性方程组： 2010011201nnnaxaxy 上述线性方程组的系数矩阵为：4200112nnnxxA A 的行列式为（称为 Vandermonde 行列式） 20011012(,)nnnnxxWx 根据线性代数的知识知道 010(,)()njijixx注意到诸 互不相同，从而 ，上述线性方程组存在唯ix,W一解。这说明满足条件（1.1）的插值多项式是存在的，而且还是唯一的。定理 2.1 设 ， 为 上的 n+1 个相异的节点，)(xfba,0nixba,，i=0，1 ， ， n，则满足)(iixfy，i=0，1 ， ， n()iipxy的 是存在并且唯一的。()pxnP从定理 2.1 的证明可看到，要求插值多项式 p(x),可以通过求解一个线性方5程组得到。但这样做不但计算复杂，且难于得到 p(x)的简单表达式。为了求得便于使用的简单的插值多项式 p(x)， 可以如1 所述，选择 的适当的基。nP先构造 n 次插值基函数 ，i=0，1 ， ， n 使)(xlinP， ， 1， ， n， （2.1）1()0ijijjlxi， i由当 时， 可知：ij)(jixl， 1， ， n （2.2）0()niikklxc0i其中 是待定常数，它可由 定出：i )(ixl； ， 1， ， n。10()niikkc0i代入（2.2）得：i=0， 1， ， n0()nkikixl再作 00()()nn kiiiikixLxylxy易知 ，即为所求的插值函数。nP6这种具有 性质的基称为对偶基，以后我们还会多次构造针对不同问题的ij对偶基。记 ，则 ，10()nnkkxx10()()nniikkxx，10()()nnkkiixx， i=0，1 ， ， n，1()niiilx10()nniiixLy例 2.1 已知 ，节点为 ， ， ，求xf)(102x4)(2xL解 ， )(1fy， 。0y 1)(fy863)4(2)(20 xxl 21 1()(54)()l)3(6)4()(22 xxxl722017()()84iLxylx2.2 插值多项式的插值余项现在考虑用 近似 所产生的误差，即插值余项)(xLn)(f)(xLfxRnn当 在 上 n+1 阶可导时，可以把 化为便于估计的形式，)(xfba, R先设 ，i=0，1 ， ， n，作辅助函数，1()()()nFtfLtKxtba,其中 满足：()Kx（2.3）1()()0nnfxx当 x 不为插值节点时 ，这样的 是存在的。10K于是 ， ， ， 是 的 n+2 个相异的零点，依次对 ，0txnx)(tF)(tF， 应用 Rolle 定理可知存在 使)(F)(tn ba,0= (1)(1)()1!nnfKxn从而8(1)!nfKx代入（2.3）式得：，(1)1()!nnnfRxxba,若 x 等于某一 ，则 ， 故任取 上式也成立。i1()0nRnx,于是得出：定理 2.2（多项式插值的余项） 设 在 上 n+1 阶可导，则存在)(xfba,使ba, (1)1() ()!nnnnfRxfLxx注：由上式可知，当 时， ，特别当 时，可得：fP)(fnf（2.4）0()1nilx例 2.2 考察四位常用对数表作线性插值的误差。解 设 ， ， 0.4343。xflg)(2lg)(xef设 x 位于 和 之间：1 ，则0019， 1012lg()()eRxx0x1记表距 ，得01h 4)(max21010 hx2110.3(lg)(8LR= 220549.hx当 h=0.01 时，（2.5）61149.5)(lgxL再考虑舍入误差，设， i=0，1iiiffy)(其中 是表值， 是舍入误差，则：ifi，i=0，1 （2.6）50iiify把以 ， ，i=0，1 构造的线性插值分别记为 ， ，注意到i )(xL*1，i=0， 1 在 上非负及（2.5） ， （2.6）式，则线性插值的舍入误差)(xli 0,x*21()()RL101100()()iiylxfl10ma(),iifli10()ilx= 51可见舍入误差比截断误差大一个量级。此时整个误差不超过 6512().4910Rx2.52.3 Newton 插值Lagrange 插值公式的缺点是，当插值节点的个数有所变动时（例如为了提高精度，有时需要增加节点个数） ，Lagrange 插值基函数 ，)(xlii=0，1 ， ， n 就要随之发生变化，从而整个公式的结构也要发生变化，这在计算实践中是不方便的。为了克服上述缺点，在这一节中我们引入 Newton 插值公式。11令 表示 n 个节点 ， ， 上的 n-1 次插值多项式，由于)(1xNn0x11x， i= 0，1 ， ， n-1iini yN)()所以 101()()()nn nxcxx此处 c 为常数，由条件，可以定出 )()(110nnnxxNyc因此，n+1 个节点 ， ， 上的 n 次插值多项式也可以写成下列形0x1式： 010011()()()()n n nNaaxx Newton 插值公式的系数如何确定?为此我们引进差商的概念。设已知不同的自变量 上的函数值n,10，i=0，1， ， n， 称)(ixf，(),ijijfxffji为 的一阶差商（式均差） 。一阶差商的一阶差商)(xf ,()ijjkijkfxfxfxi12叫做 的二阶差商。一般说来，我们称 n-1 阶差商的一阶差商)(xf 01201 0,nnnfxfxf 为函数 的 n 阶差商。)(xf根据差商定义设 为一动点，,ab0011000()(),()nnnfxfxxfffx 只要把后一式代入前一式，即得： 001001201(),(),()fxfxf ),()nnnxfxx :()nNxR其中 且满足插值条件，称为 Newton 插值公式。而nP 为插值余项。()nx01,()nfx用数学归纳法易证明 n 阶差商 1010(),niifxfx为了作数值计算常利用形式如下的差商表13x 一阶差商 二阶差商 三阶差商)(f001x)(1f01,fx222012,fx3x)(3f3,fx30123,fx插值公式（2.9）中的系数就是上表中带下划线的项。因此当已知，i=0，1， ， n 时，利用差商表可以很容易地算出的各阶差商的)(iixfy值。因为在 n+1 个不同的点 ， ， 上取给定值的次数不超过 n 的多0x1nx项式是唯一的，所以次数相同的 Newton 插值多项式与 Lagrange 插值多项式是恒等的，它们的差异仅是书写形式不同而已，但是这种差异却为计算实践带来了很大的方便，实际上，对于 Newton 插值公式来说，当需要增加一个插值点时，只需要在原插值多项式的后面再添加一个新项就可以了。2.6 Hermite 插值为了理论和应用上的需要，有时不但要求插值函数 p(x)在节点处的函数值与被插值函数 f(x)相同，而且要求在节点处的导数值也相等，这就导致了下面的14Hermite 插值。给定 f(x) 在 n1 个互异的节点 处的函数值 及导01,nx ()iifxy数值 ，i=0 ， 1， ， n， 要求一个次数不超过 2n1 次的多项式()ifxy满足21nH， i=0，1 ， ， n， 2121(),()niiniiHxyxy（219）我们从构造 Lagrange 插值多项式的方法得到启发，设法构造 Hermite 插值问题的对偶基。即构造两组次数都是 2n1 次的多项式 01()jjlxl和i=0，1 ， ， n 使其满足：i， j=0，1 ， ， n 0011(),();jiijjijlxlx（220）则满足插值条件（2.19）的 2n1 次多项式就是（221）2100()()()nnnjjHxylxylx由（220）知 是 的二重零点，因此可设,ijjl20()(j jxablx其中 a， b 为待定常数， j=0，1 ， ， n 是 2.1 节中定义的 n 次jl15Lagrange 插值基函数，于是只要选择常数 a， b 满足2()(1)(0jjjjaxbllxl整理有 ()12()0jjjabxl解上述方程得： ()12jjalbx类似于上述做法，令： 21()(j jlcdl同理可求得 jdx将 a,b,c,d 代入（ 2.21）并整理可得 2210()()()nnjjjjjHxyxylx定理 2.4 Hermite 插值问题（ 2.19）的解是存在且唯一的。证明 存在性上面已证。为证唯一性，假设有另一 也满足条2121()nnQxP件（2.19） ，令： ，易知 是212121()()()nnnxQHxP,0,i16的二重零点，于是，次数不超过 2n1 的多项式 有 2n2 个零点，()x ()x必 从而 。02121()()nnQxHHermite 插值函数的误差与 Lagrange 插值的误差估计十分类似，有如下定理，读者可仿照定理 2.2 自己证明。定理 2.5 （Hermite 插值的余项） 设 在 上 2n+2 阶可导，x)(xfba,和诸 皆位于区间 内，则存在 使ixba,ba,(2)221211()()!nnnnfRxfHxx2.7 Newton-Hermite 插值公式本节讨论一类具有重节点的多项式插值方法，即 Newton-Hermite 插值方法。因为此类插值问题要求在节点处满足任意给定的导数条件，所以也常被称为切触插值问题。设 （2.22）1x2sx，为事先指定的实数，其中 为正()0,;,hkky 1,s整数（2.23）121ns17我们要构造一个次数不高于 n 的多项式 ，使)(xpnP， （2.24）)()(hkhyxpsk,1;,0 下面我们用类似于 Newton 插值的方法来解这个问题。第一步：根据（2.22） ， （2.24）式写出数列（2.25）ssxxx,2211 （2.25）中， 连续写 次，再将（2.25）中的数据重新顺序编号，得到kk（2.26）nx,10（2.26）称为有重节点的插值节点组。第二步：对于节点组（2.26）和插值条件（2.24） ，用 2.3 节中同样的方法作出差商表。这里对重节点的差商作补充规定： ()()1,!hhkkkhfxyfx个第三步：写出形如（2.10）的 ， 就是所要求的 Newton-)(Nn)(nHermite 插值多项式例 2.5 设节点为 ，设求 ， 使0123,xx()Hx5P18， ， ，1(3) 2H2)0(1)(H， ，4 。()解 重写节点组 并作差商表：1,03,x 一阶差商 二阶差商 三阶差商 四阶差商 五阶差商)(f-3 21-3 4-3 810 2 2570 2 1 3619261 1 1 0 81381453623 235()(3)()()()()2487Hxxxxx即为所求之插值多项式。193 分段线性插值讨论了 Lagrange 插值法以后，自然会问：当插值节点无限加密时，必在 上收敛于 吗？)(xLnba,)(xf即使对于性质很好的函数，答案也是否定的。Runge 指出，无穷次可微函数 21)(xf在 上用等距节点插值时，在区间两端会产生剧烈振荡的现象。图 3.15,给出了 与 的示意图。可以证明：在等距节点下当 )(xf)(10Lx时， 收敛于 。而 时 不收敛。63.n)(xf)(Ln20图 3.1因此在实际实用中，往往不采用高次插值多项式，而改用分段的低次插值多项式去近似函数。由于分段的低次插值多项式对函数通常有较好的逼近性态，因而近年来有着十分广泛的应用。其中突出的如样条函数。本段先介绍分段线性插值。设 ， ，已知它在节点 上的函数)(xfyba,0xa1bxn值 ，i=0，1， ， n。 试求 ， 使i )(xIb,（1） ，i=0，1 ， ， n；iyxI)(（2） 在 ，i=0，1 ， ， n 上是一次多项式。,i满足上述条件的 称之为 在 上以 为节点的分段线性插值)(xI)(xfba,nix0多项式。满足所述条件的 是存在的，只要把在 ，i=0，1 ， ， n-1 上)(I ,i的线性插值多项式逐段拼接起来就得出 了。)(xI， ，i=0，1 ， ， n1 ；iiiixyxyI 11)( ,i对于分段线性插值多项式我们也可以构造 型的基，只要令：ij210)/()(110xxl 其 他 点 10x)/()()11jjjj xxl 其 他 点 11jjxj=1，2， ， n-10)/()()11nn xxl 1nnx他显然有 i,j=0，1， ， n。因此 可表示为ijijxl)( )(I0()jiIxylx记 ，i=0，1， ， n-1， 。对于 时iiixh1 1ma()inh0h趋向于 的收敛问题，有)(xI)(f定理 3.1 （分段线性插值收敛的充分条件）若 在 上连续，则当)(xfba,时， 在 上一致收敛于 。0h)(xIba, )(xf证 由 的连续性， ，i= 0，1， ， n-1，)(xf1,i使 和 分别取得 在 上的最大值 和1,iixii)(xfi iM最小值 ，于是im22，)()(iiffxIf 1,ix再由 在 上的一致连续性， 0， 0 使 ， ，)(xfba, uvba, 时，有 。于是当 h 时， ， 使vu)(vfu,xk10nk 证毕。)()(kkffxIf由定理 3.1 可知，刚才我们讨论的 Runge 函数， ，21)(xf它在等距节点组上的 n 次插值多项式 不收敛，而其在同一节点5,x )(xLn组上的分段线性插值多项式一致收敛于 。)(f4 三次样条插值虽然分段线性插值 较好地解决了收敛问题，但是 在内节点上通常)(xI )(xI是不可导的。而在实际应用中，如高速飞行器的机翼设计、船体放样等，需要分段插值函数有二阶可导性。为此，下面讨论三次样条插值。4.1 三次样条函数样条（Spline）本来是在船体放样绘制光滑曲线时用的一种细木条。用压铁把细木条固定在一些已知点上，细木条就形成一条相当光滑的曲线。23数学上的样条函数是从这个物理模型中抽象出来的，其中常用的三次样条函数的定义如下：对函数 ， 与 上的一组节点：)(xS,ba, 0x1bxn若（1） 在 ，i=0，1， ， n-1 上都是三次多项式，)(xS,i（2） 在 上有二阶连续导函数，ba则称 为 上以 为节点的三次样条函数。)(x,nix0若再要求：（3） ， i=0，1， ， n()()iiSyf则称 为 上以 为节点的 的插值三次样条函数。x,banix0)(xf4.2 三次样条插值的计算设给定一区间 ，且,ba 0x1bxn任意给定一组常数 ， ， ，要求构造一个插值三次样条函数 ，0y1ny )(xS使得如下插值条件得以满足：24，j=0，1 ， ， n （4.1）jyxS)(今以 表示 ，j=0，1， ， n 。由于 为分段 3 次多项式，jMj )(xS所以 在区间 上为一线性函数。因而它可由过 与)(jxS,jjx ),1jjM两点的线性插值函数,j（ ） （4.2）jjjj hxxS11)( jjx1所决定，其中 。1jjjh为了最后求出 在 上的表达式，只须对（4.2）式积分两次，并)(xS,jj定出积分常数就够了。当 时，,1jjxjjjj hxMhxS6)(6)()( 3131 jjjjjj hxMyy 1221 )6()( （4.3）jjjj hxhxxS2)(2)()( 11（4.4）16jjjjyM25由（4.3）可知，为求 ，关键是设法确定各个 ，j=0，1 ， ， n。而)(xSjM为了求得各个 ，必须引用样条节点处的光滑连接条件jM（4.5）)()0(jjxSx按（4.4）有 jjjj hyMhxS1136)( 111(0)jjjjj jj由（4.5）可得连续性方程111636jjjjjj MhhMj=1， ， n1 （4.6）jjyy11它给出了 n+1 个未知数 ，j= 0，1， ， n 的 n-1 个方程式，按它尚不足以j唯一确定 。还须补充两个“边界条件” ，这有下述几种情况：jM（1）假定 。于是按照前面公式，可得方程：nybSa)(,)(026（47）)(6211010nnnn hyM（2）假定 ，相当于直接给出 ， .0(),)Sayb 0Myn无论（1）或（2） ，均可概括为（4.8）0102nndM引入记号， ，j=1 ， 2， ， n-1 （4.9）1jjhjj则（4.6）可改写为 1111 /)(/)(62 jj jjjjjjj hhyyMj=1，2， ， n-1 （4.10）所以由（4.8） ， （4.10）确定的线性方程组为27= （4.11） 2020112110nn nMM1210ndd1210其中 ，j=0，1 ， ， n-1 表示（4.11）的右端项。jd如果满足条件)(xSj=0，1，2. （4.12）)()( bajj则称之为以 b-a 为周期的三次周期样条函数。显然，对于 3 次周期样条函数，应该要求（4.10）对 j=n 的情况也成立，如果再注意到 的性质，而把nM0（4.10）中的 换成 ，则相应于 3 次周期样条函数的方程组为0Mn= （4.13） 20002011332 11nn nM12321ndd1232128其中 10,nnnnhM线性代数方程组（4.11）常可用追赶法来求解，而方程组（4.13）则可把先作为参数，求解其中 n-1 个方程中的 n-1 个未知数 ，n 1M， （其解依赖于 ） ，然后代入最后一个方程以求出 ，同时21nn n， ， ，也随之确定了。1M4.3 误差界与收敛性三次样条函数的收敛性与误差估计比较复杂，这里不加证明地给出一个主要结果。定理 4.1 设 ， 为满足第一类或第二类边界条件的三4(),fxCab)(xS次插值样条函数，令 ，则有估计式101m,0,1iiiinhn()()(4)a| |,2kk kkxbfxfxh其中 01253,.3848CC这个定理不但给出了三次样条插值函数 S(x)的误差估计，且指出了当时，S(x) 及其一阶导数 S(x) 和二阶导数 S(x) 均分别一致收敛于 f(x)，hf(x)， f(x).29B-样条函数空间上面导出的三次样条插值函数分别在每个子区间上有一表达式，这在应用上和理论分析中都很不方便，如果利用基函数表示往往更为方便。设给定一组节点 （5.1）0x1Nx1又设分段函数满足条件：1于每个区间 ，j=0， ， N 上， 是一个次数不超过 n 的,1j )(xS实系数代数多项式；2 于 上具有直到 n-1 阶的连续导函数。则称 为 n)(xS), )(xSy次样条函数。常把以（5.1）为节点的 n 次样条函数的总体记为 ，,1Nn称为样条节点。Nx,1下面来给出样条函数类 中任一样条函数的一般表达式。nS),(1Nx对于任意给定的以（5.1）为节点的 n 次样条函数 ，12(),)NSxxn根据定义，其在每个子区间 ，j=0， ， N 上均为一 n 次多项式，特,1jx别地，于子区间 内是一 n 次多项式，不妨设其为,(1)(xpP30今考虑 于 上的表达式。由定义， 于 上的表达式仍)(xS,21 )(xS,21为一 n 次多项式。若设该 n 次多项式为 ，并考虑下述 n 次多项式的性质：)(qn)()(xpxnn按 n 次样条函数的定义， 与 于点 处的值及 1 阶、2 阶，一直pnq1到 n-1 阶导数值皆相等：，i= 0， ， n-1)()(11xinin亦即，i= 0， ， n-1)(1i是故 是 的 n 重根，即 含 这个因子，由于 是一 n1x)(xn)()(x次多项式，所以存在某常数 ，使得：1C（5.2）nx)()1亦即（5.3）nnnCpxq)()(1它说明 于区间 上的表达式恰为其前一区间上的表达式加上)(xS,21的某一常数倍，这样一来， 于 上的统一表达式应为：n1)(xS,231（5.4）1112(),()nnpxxSxC为把（5.4）式写成一个统一的表达式，引入记号（5.5）0),0max(xm)(则（5.4）所示的 又可紧凑地表示为)(xSnnxCp)(12()x继续采用这种分析方法，可得 于整个实轴上的表达式为（5.6）1()()NnnjjjSxpx)(x此即为下述定理所叙述的事实定理 5.1 任一 均可唯一地表现为),()21NxxnS（5.7）1(NnnjjjpC)(x其中 ， ，j=1， ， N 为实数。)xpnPj显然，由（5.7）式所给出的任一函数 必然满足 n 次样条函数的定义，)(xS亦即 ，因而定理 5.1 可进一步写成：),()21NnxSx32定理 5.2 为使 必须且只须存在 和 N),()21NxxSn)(xpnP个实数 使得（5.7）式成立：NC,211()()Nnnjjxpx()x定理 5.1 和定理 5.2 说明函数系 1,.,(),.()nnnN构成 n 次样条函数类 的一组基，线性空间 的S21Nx S),(1Nx维数为 N+n+1。
展开阅读全文