1、第四章第四章 多项式插值与函数逼近多项式插值与函数逼近/*Polynomial Interpolation and Approximation of Functions*/本章主要内容：本章主要内容：1 1、Lagrange插值方法插值方法2 2、Newton插值方法插值方法3 3、Hermite插值方法插值方法4 4、三次样条三次样条插值方法插值方法5 5、函数逼近、函数逼近:最佳平方最佳平方逼近和逼近和最佳一致最佳一致逼近逼近 实际问题中经常要涉及到实际问题中经常要涉及到函数值的计算函数值的计算问题：问题：（1）如果如果函数表达式函数表达式本身比较复杂，且需要多次本身比较复杂，且需要多次重
2、复计算重复计算时，时，计算量会很大；计算量会很大；（2）有的函数甚至有的函数甚至没有表达式没有表达式，只是一种，只是一种表格函数表格函数，而我们需，而我们需要的函数值可能不在该表格中。要的函数值可能不在该表格中。对于这两种情况，我们都需要寻找一个对于这两种情况，我们都需要寻找一个计算方便且表达简单计算方便且表达简单的函数来的函数来近似代替近似代替，这就是，这就是数值逼近数值逼近问题。问题。问题背景问题背景1 1 插值问题插值问题 /*Interpolation Problem*/（插值的定义（插值的定义）4 1 1.Def1n 已知定义于区间已知定义于区间 上的实值函数上的实值函数 在在 个个
3、互异互异节点节点 处的函数值处的函数值 ，若函数集合，若函数集合 中的函中的函数数 满足满足,a b()f x 0,niixa b 0()niif x ()x 0 1 2()(),()iixf xin 则称则称 为为 在函数集合在函数集合 中关于中关于节点节点 的一个的一个插插值函数值函数，并称，并称 为为被插值函数被插值函数,a,b,a,b为为插值区间插值区间，为插值节点，（为插值节点，（*）式为）式为插值条件插值条件。()x 0niix()f x()f x 0niix 设设 00max,minnniiiiMxmx 外插法外插法：内插法内插法：用用 计算被插值函数计算被插值函数 在点在点 处
4、的近似值处的近似值 ()x(,)xm M()f x用用 计算被插值函数计算被插值函数 在点在点 处的近似值处的近似值 ()x ,(,)xa b xm M ()f x插值插值类型类型代数代数插值：集合插值：集合 为多项式函数集为多项式函数集 x0 x1x2x3x4xg(x)f(x)几何几何意义：意义：()yg x()yf x 有理有理插值：集合插值：集合 为有理分式函数集为有理分式函数集 三角三角插值：集合插值：集合 为三角函数集为三角函数集 代数插值的代数插值的存在唯一性存在唯一性 21,nnHspanx xx 设设 20120()(),nnixxaa xa xa x aRin 即即代入插值条
5、件：代入插值条件：0 1 2()(),iixf xin 2001020002101 12111212()()()()()()nnnnnnnnnnnnxaa xa xa xf xxaa xa xa xf xxaa xa xa xf x 方程组的系数矩阵是方程组的系数矩阵是Vandermonde矩阵矩阵20002111021101()nnijj i nnnnnxxxxxxxxxxx 方程组存在唯一解，因此满足插值条件方程组存在唯一解，因此满足插值条件(*)的不超过的不超过n次的插值多项式是次的插值多项式是唯一存在唯一存在的的.4 1 1.Th截断截断误差误差插值插值余项余项设设 在区间在区间 a,
6、ba,b上连续，上连续，在区间在区间 a,ba,b上存在上存在,是满足插值条件（是满足插值条件（*）的不超过）的不超过n次的插值多项式，则对次的插值多项式，则对 存在存在 ，满足，满足其中其中 。且当且当 在区间在区间 a,ba,b有上有上界界 时，有时，有()()nfx1()()nfx()x ,xa b(),xa b 111()()()()()()()!nnnfR xf xxxn 10()()nniixxx 1()()nfx 1nM 111()()()!nnnMR xxn 代数插值的插值余项代数插值的插值余项4 1 2.Th/*Remainder*/2 2 代数插值多项式的构造方法代数插值多
7、项式的构造方法一、一、拉格朗日多项式拉格朗日多项式 /*Lagrange Polynomial*/niyxPiin,.,0,)(求求 n 次多项式次多项式 使得使得nnnxaxaaxP 10)(条件：条件：无重合节点，即无重合节点，即jixx ji n=1已知已知 x0,x1;y0,y1，求，求xaaxP101)(使得使得111001)(,)(yxPyxP 可见可见 P1(x)是过是过(x0,y0)和和(x1,y1)两点的两点的直线直线。)()(0010101xxxxyyyxP 101xxxx 010 xxxx =y0+y1l0(x)l1(x)10)(iiiyxl10()ijijijl xij
8、 称为称为拉氏基函数拉氏基函数 /*Lagrange Basis*/，满足条件满足条件 li(xj)=ij njijjijixxxxxl0)()()(与与 有关，而与有关，而与 无关无关n 1希望找到希望找到li(x)，i=0,n 使得使得 li(xj)=ij；然后令；然后令 niiinyxlxP0)()(，则显然有，则显然有Pn(xi)=yi。li(x)每个每个 li(x)有有 n 个根个根 x0 xi-1、xi+1 xn j i jiiiixxCxl)(11)(niiinyxlxL0)()(Lagrange Polynomial节点节点f0110()()()()()()niiiinijjj
9、 il xC xxxxxxxxCxx 01110111()()()()()()()()()()()iiniiiiiiiinxxxxxxxxxxl xxxxxxxxxxx 例如例如 也是一个插值也是一个插值多项式，其中多项式，其中 可以是可以是任意任意多项式。多项式。0()()()()nniiP xLxq xxx ()q x（2）Lagrange插值多项式结构插值多项式结构对称对称，形式简单，形式简单.111()()()()()()()!nnnnfR xf xL xxn （3）误差估计误差估计注注：（1）若不将多项式次数限制为若不将多项式次数限制为 n，则插值多项式，则插值多项式不唯一不唯一。（
10、4）当插值当插值节点增加节点增加时，时，拉氏基函数需要拉氏基函数需要重新重新计算，计算，n较大时，计算量非常大较大时，计算量非常大,故故常用于理论分析。常用于理论分析。二二、牛顿插值牛顿插值 /*Newtons Interpolation*/Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函数全部基函数 li(x)都需重新算过。都需重新算过。将将 Ln(x)改写成改写成.)()(102010 xxxxaxxaa).(10 nnxxxxa的形式，希望每加一个节点，的形式，希望每加一个节点，只附加一项只附加一项上去即可。上去即可。?差商差商(亦称亦称
11、均差均差)/*divided difference*/),()()(,jijijijixxjixxxfxfxxf 1阶差商阶差商/*the 1st divided difference of f w.r.t.xi and xj*/)(,kixxxxfxxfxxxfkikjjikji 2阶差商阶差商11101010111010,.,.,.,.,.,kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)阶差商：阶差商：kiikikxxfxxf010)()(,.,事实上事实上其中其中,)()(01 kiikxxx kijjjiikxxx01)()(差商的值与差商的值与 xi
12、的的顺序顺序无关！无关！,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf ).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN12 n+11+(x x0)2+(x x0)(x xn 1)n+1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ai=f x0,xi 010122012,(),f x x xf x x xxxf x x x
13、x 3注：注：由由唯一性唯一性可知可知 Nn(x)Ln(x)，只是只是算法不同算法不同，故，故其其余项也相同余项也相同，即，即10111()(),.,()()()!nxnnnff x xxxxn 0()minmax(),.,(,)!nnff xxxxn 实际计算过程为（实际计算过程为（建立差商表建立差商表）f x0,x1f x1,x2 f xn 1,xnf x0,x1,x2 f xn 2,xn 1,xnf x0,xn xn+1 f(xn+1)f xn,xn+1 f xn 1,xn,xn+1 f x1,xn+1 f x0,xn+1f(x0)f(x1)f(x2)f(xn 1)f(xn)x0 x1x
14、2xn 1xn例例3：已知函数已知函数 的函数表：的函数表：()yf x xi 1 2 3 4 5yi=f(xi)1 4 7 8 6写出写出4次次Newton插值多项式插值多项式解：解：构造差商表构造差商表1124374856()iix f x3312 0132 1316 12441 31012112331123424()()()()()()()()()()()N xxxxxxxxxxx 4324198333124122424()N xxxxx 4 分段插值分段插值 /*piecewise Interpolation*/一、高次插值评述一、高次插值评述11111()()()()()()()!n
15、nnnfRxf xHxxn 1 1、从插值余项角度分析、从插值余项角度分析 为了提高为了提高插值精度插值精度，一般来说应该，一般来说应该增加增加插值节点的个数，这插值节点的个数，这从插值余项的表达式也可以看出，但不能简单地这样认为，原因从插值余项的表达式也可以看出，但不能简单地这样认为，原因有三个：有三个：插值余项与插值余项与节点的分布节点的分布有关；有关；余项公式成立的前提条件是余项公式成立的前提条件是 有有足够阶连续导数足够阶连续导数（即函数（即函数足够光滑），但随着节点个数的增加，这个条件一般很难成立；足够光滑），但随着节点个数的增加，这个条件一般很难成立；随着节点个数的增加，随着节点个
16、数的增加，可能会增大。可能会增大。()f x1()()nf 随着节点个数增加到随着节点个数增加到某个值某个值，误差反而会增加。，误差反而会增加。注意下面图中注意下面图中曲线曲线的变化情况！的变化情况！例例3：在在 5,5上考察上考察 的的Ln(x)。取。取211()f xx 1050(,.,)ixi inn -5-4-3-2-1 0 1 2 3 4 5-0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端点端点附近误差附近误差越大，称为越大，称为Runge 现象现象Ln(x)f(x)2n()yf x 5n 10n 5 三次样条插值三次样条插值/*Cubic Spline Interp
17、olation*/许多实际工程技术中一般对许多实际工程技术中一般对精度精度要求非常高，要求非常高，（1）要求近似曲线在节点要求近似曲线在节点连续连续；（2）要求近似曲线在节点处要求近似曲线在节点处导数连续导数连续，即，即充分光滑充分光滑。分段插值分段插值不能保证节点的光滑性，而不能保证节点的光滑性，而Hermite插值需要知道节点处的导数值，实际中无法确定插值需要知道节点处的导数值，实际中无法确定。问题背景问题背景一、一、三次样条三次样条函数的力学背景函数的力学背景 在工程技术和数学应用中经常遇到这样一类在工程技术和数学应用中经常遇到这样一类数据处数据处理理问题：在平面上给定了一组问题：在平面
18、上给定了一组有序的离散点列有序的离散点列，要求用，要求用一条一条光滑曲线光滑曲线把这些点按次序连接起来。把这些点按次序连接起来。.压铁压铁弹性木条弹性木条.数据点数据点形象地称之为形象地称之为样条曲线样条曲线 在力学上，通常均匀在力学上，通常均匀细木条细木条可以看作可以看作弹性细梁弹性细梁，压压铁铁看作是作用在梁上的看作是作用在梁上的集中载荷集中载荷，“样条曲线样条曲线”就模拟就模拟为弹性细梁在外加集中载荷作用下的为弹性细梁在外加集中载荷作用下的弯曲变形曲线弯曲变形曲线。设设细梁刚度系数为细梁刚度系数为 ，弯矩为，弯矩为 ，样条曲线的曲率为，样条曲线的曲率为 AM()k x由力学知识：由力学知
19、识：()()Ak xM x 3221()()yk xy 1y 当当 时（即时（即“小挠度小挠度”的情况）的情况）上述微分方程简化为：上述微分方程简化为：()AyM x 是是线性函数线性函数()M x40()()yx 因此，因此，“样条曲线样条曲线”可近似认为是可近似认为是三次三次多项式多项式二、二、三次样条三次样条函数定义及求法函数定义及求法3 1.Def 设在区间设在区间 上给定一个分割，上给定一个分割，定义在定义在 上的函数上的函数 如果满足下列条件：如果满足下列条件：(1)(1)在每个小区间在每个小区间 内是内是三次三次多项式多项式(2)(2)在整个在整个 区间上，区间上，为为二阶二阶连
20、续可导函数，即连续可导函数，即在在每个节点每个节点 处处,a b011nnaxxxxb ,a b()S x11 2,(,)iixxin ,a b()S x1 21(,)ix in00012()()()(),kkiiSxSxk 则称则称 为为三次三次样条函数样条函数()S x假设现在假设现在已知已知函数函数 在节点处的函数值：在节点处的函数值：()f x01 2()(,)iiyf xin 如果如果三次三次样条函数样条函数 满足满足()S x01 2()()(,)iiS xf xin 则称则称 为插值于为插值于 的的三次三次样条函数，简称样条函数，简称三次三次样条样条插值函数插值函数。()f x(
21、)S x如何求如何求 的的三次三次样条样条插值函数插值函数:()S x()f x1012121(),(),()(),nnns xxxxsxxx xS xsxxxx 23()iiiiis xabx c xd x 4n个未知数个未知数3n-1个条件个条件线性线性插值函数插值函数1 1、M连续方程与连续方程与 的表达式的表达式()S x记记0 1 2()(,)iiMSxin 因为因为 在每一个子区间在每一个子区间 上都是上都是线性函数线性函数 ()S x 1,iixx 111(),iiiiiiiiixxx xs xMMxxxhh 两边积分两边积分2211122()()(),iiiiiiiiiixxx
22、 xs xMMAxxxhh 两边再积分一次两边再积分一次3311166()()(),iiiiiiiiiiixxx xs xMMAx Bxxxhh？001 21()()(,)iiiis xs xin 由由112121(,)iiiiiiMMMdin 11iiiihhh 11116()iiiiiiiiiyyyydhhhh 1iiiihhh 116,iiif xx x 其中其中代入插值条件：代入插值条件：11(),()iiiiiis xys xy 写成写成方程组方程组的形式：的形式：01111222221211120000200002000002nnnnnnnnMdMdMdMd 上述方程组称为上述方程
23、组称为 的的M连续方程连续方程()S x n-1个方程个方程n+1个未知数个未知数三弯矩三弯矩方程方程M、m连续方程的求解：需要补充连续方程的求解：需要补充附加条件附加条件3 3、边界条件边界条件/*boundary conditions*/已知端点的已知端点的斜率斜率：00(),()nnfxyfxy 已知端点的已知端点的二阶导数二阶导数：00(),()nnfxyfxy 设设 是以是以 为周期的为周期的周期函数周期函数，对，对 附加附加周期性周期性条件：条件：()yf x ba()S x000()()()()ppnSxSx 0 1 2,p 即要求即要求三次三次样条插值函数在端点处样条插值函数在
24、端点处函数函数值值、一阶一阶导数值和导数值和二阶二阶导数值相同。导数值相同。M连续方程在各类边界条件下的求解方法连续方程在各类边界条件下的求解方法 对于第对于第一一类类边界条件边界条件220110111122()()()x xxxs xMMAhh 01,xx x 221122()()()nnnnnnnnxxx xs xMMAhh 1,nnxxx 1000()()s xmf x ()()nnnns xmf x 由由得得10012hmMA 2nnnnhmMA100101162()yyMMmhh 1162()nnnnnnnyyMMmhh 0d nd 从而得到方程组（从而得到方程组（三对角三对角）：）
25、：0011112222222211112100002000020000020000020000012nnnnnnnnnnMdMdMdMdMdMd 可用可用追赶法追赶法求解求解注：注：三次样条与分段三次样条与分段 Hermite 插值的根本区别在于插值的根本区别在于S(x)自身光滑自身光滑，不需要知道，不需要知道 f 的的导数值导数值（除了在（除了在2个个端点处的函数值）；而端点处的函数值）；而Hermite插值依赖于插值依赖于f 在许多在许多插值节点的导数值插值节点的导数值。f(x)H(x)S(x)性质性质3 3（误差误差估计）估计）设函数设函数 ，是区间是区间 的一个分割，的一个分割，是是关
26、于关于 的带有的带有型型(斜率边界斜率边界)或或型型(二阶导数边界二阶导数边界)边界条边界条件的插值函数，则有误差估计件的插值函数，则有误差估计其中其中 是是分割比分割比，并且系数，并且系数 与与 是是最优估计最优估计。4(),f xC a b ,a b()S x()f x440 1 2 3()()max()(),rrra x bf xS xC M hr maxminiiiihh 012513384248,CCC 132,C maxiihh 0C1C性质性质说明说明：三次样条插值函数本身连同它的：三次样条插值函数本身连同它的一一、二二、三三阶导数分别收敛到阶导数分别收敛到 及其及其相应导数相应导数，具有，具有强收敛强收敛性。性。()f x
