北京理工博士入学考试 数值分析第5章第1部分

1、1第五章习题第五章习题P171 1,2,3,4,5,6,8,9,10中中 Lagrange和和Newton法各选两个题目法各选两个题目 13 16(降阶法降阶法,基函数基函数,待定系数待定系数)2x0 x1x2x3x4xg(x)(xfy 函函数数：在在一一些些点点处处测测得得( (或或计计算算得得到到) )函函数数值值:nixfyii2 , 1 , 0 )( 使使得得求求一一个个简简单单易易算算的的函函数数),(xg(),iig xy ),()(,0 xfxgxxn 上上在在.)()(的的插插值值函函数数称称为为xfxg,表表达达式式未未知知或或非非常常复复杂杂 f(x)第五章第五章 插值法插

2、值法()(),iig xf x 即即0,1,2in 多项式多项式插值多项式插值多项式问问题题：3.)()(多多项项式式过过这这组组互互异异节节点点的的插插值值为为xfxn ,1,)(10处处的的函函数数值值互互异异点点个个上上在在已已知知函函数数nxxxnbaxf nixfyii, 1 , 0 )( ,n求求一一个个次次数数不不超超过过 的的多多项项式式()(0,1,2,) (*)niixy in ,为为插插值值区区间间称称ba,为插值节点为插值节点ix 01( )nnnxaa xa x 满足插值条件满足插值条件niniyyyyxxxx001 Lagrange插值插值1.1 插值多项式插值多项

3、式40,1i 0,1 2i ，0,1 2 3i ，插插值值多多项项式式的的几几何何意意义义：1(,()(0,1,)( )iinnnxf xinnx 次次多多项项式式插插值值，是是过过个个点点作作一一条条 次次多多项项式式曲曲线线近近似似被被插插值值函函数数曲曲线线 一一次次多多项项式式二二次次多多项项式式三三次次多多项项式式5基本问题基本问题:1( )nx . .插插值值多多项项式式是是否否存存在在唯唯一一？2( )( )( )?nnxf xx . .若若存存在在，截截断断误误差差3( )nx . .如如何何求求？6应满足方程组应满足方程组的系数的系数)1 , 0(niain nnnnnnnn

4、nnyxaxaxaayxaxaxaayxaxaxaa22101121211000202010 1nn 个个互互异异节节点点上上的的 次次插插值值多多项项式式存存在在唯唯一一:()(0,1,2,)niixy in 满满足足插插值值条条件件系系数数矩矩阵阵为为200021112111nnnnnnxxxxxxxxx ,0()niji jijxx 其其行行列列式式的的值值为为 01( )nnnxaa xa x 存存在在唯唯一一性性： 若若范范德德蒙蒙特特矩矩阵阵，0 方方程程组组的的解解存存在在唯唯一一，所所以以710( )(),nniixxx 其其中中1.2 插值多项式的误差估计插值多项式的误差估计

5、,1,10互互异异节节点点上上是是设设 nbaxxxn, )()(次次插插值值多多项项式式的的过过这这组组节节点点的的是是nxfxn ,)()1(baCxfn 若若有有则则对对任任意意的的, bax ),( )()!1()()()()(1)1(baxnfxxfxRnnnn :1 . 5定定理理0,nxa xb 通通常常取取8(1)100( )( )( )() (1)!nnnff xT xxxxxn ，介介于于和和 之之间间(1)0( )( )( )() ( , )(1)!nnniiff xxxxa bn ，nTaylor阶阶多多项项式式余余项项：01()()()nf xf xf x已已知知，(

6、 )0(),0,1,kfxkn 已已知知n次次插插值值多多项项式式余余项项：(2)( )(1)20000000()()( )()()()()()2!nnnfxfxT xf xfxxxxxxxn 与与泰泰勒勒多多项项式式比比较较9, 0)(),()1( xnxba 使使得得存存在在 niixnnxxnfxR0)1()(! ) 1()()( 5.1( )( )( )nnRxf xx 定定理理的的证证明明：( )nRx (0,),ixx in 任任意意固固定定构构造造辅辅助助函函数数反反复复利利用用罗罗尔尔定定理理(1)()( )(1)!0,nnxRK xn , 0)!1)()()()1()1( n

7、xKfxnnxn )!1()()()1( nfxKxn ,2)(0nxxxnt个个不不同同的的根根有有 (0,1, )ixx in 当当时时显显然然成成立立)1 , 0(0)(nixRin 0( )( )( )()nniitRtK xtx 0()niixx ( )K x10(1)1 , max |( )|,nnxa bfxM 若若则则| )()( |)!1(| )(|101nnnxxxxxxnMxR (1)01( )( )()()() ( , )(1)!nnnfR xxxxxxxa bn 11101( )( )()()2fR xxxxx 2012( )( )()()()6fRxxxxxxx 1

8、n 当当时时，线线性性插插值值余余项项：2n 当当时时，抛抛物物线线插插值值余余项项：1220102000201121112012 nnnnnnnnnnaa xa xa xyaa xa xa xyaa xa xa xy 通通过过解解线线性性方方程程组组求求插插值值多多项项式式，原原因因：系系数数矩矩阵阵为为范范德德蒙蒙矩矩阵阵，通通常常是是病病态态的的2012( )nnnxaa xa xa x 用用表表达达式式计计算算近近似似值值误误差差较较大大如如何何求求插插值值多多项项式式？不不可可取取13 1.3 拉格朗日插值多项式拉格朗日插值多项式时时当当1 n0101xxxyyy01,aa x 即即

9、求求线线性性函函数数满满足足插插值值条条件件1x这这里里把把线线性性函函数数表表示示成成基基 ，的的线线性性组组合合00101011yaa xyaa x 和和线线性性函函数数还还可可以以表表示示成成其其它它基基的的线线性性组组合合拉拉格格朗朗日日多多项项式式的的思思想想：01( )( )lxlx构构造造其其它它的的基基，例例如如和和把把线线性性函函数数都都可可以以表表成成：0 01 1( )( )a lxa lx 01,aa使使系系数数很很容容易易求求得得, ,0011,yaya 如如140 x1x10 x1x11xx 0 xx 11001)()()(yxlyxlxL 0( )lx一一次次多多

10、项项式式满满足足1( )lx一一次次多多项项式式满满足足01xx 1001( )xxlxxx 10 xx 0110( )xxlxxx Lagrange线线性性插插值值Lagrange一一次次插插值值多多项项式式100()L xy 满满足足，111()L xy ， 1.3 拉格朗日插值多项式拉格朗日插值多项式时时当当1 n0101xxxyyy1次拉格朗日插值基函数次拉格朗日插值基函数构造基函数构造基函数0110 xxxy0101xxxy152n 当当时时12()()xxxx02()()xxxx2001122( )( )( )( )Lxlx ylx ylx y 012012xxxxyyyy0102

11、()()xxxx1200102()()( )()()xxxxlxxxxx 1012()()xxxx0211012()()( )()()xxxxlxxxxx 0120( )100 xxxxlxy：0121( )010 xxxxlxy：0122( )001xxxxlxy：0122021()()( )()()xxxxlxxxxx Lagrange抛抛物物线线插插值值Lagrange二二次次插插值值多多项项式式200()L xy 满满足足，211()L xy ，222()L xy ，2次拉格朗日插值基函数次拉格朗日插值基函数构造基函数构造基函数16x0 x1x2)(0 xl)(2xl)(1xl二次二次

12、Lagrange基函数基函数)()()(2010210 xxxxxxxxxl )()()(2101201xxxxxxxxxl )()()(1202102xxxxxxxxxl 17二次二次Lagrange插值多项式插值多项式)()()()()()()()()()(2120210121012002010212xfxxxxxxxxxfxxxxxxxxxfxxxxxxxxxL 18,1n 一一般般地地 对对于于个个节节点点，已已知知( )inl x构造 次多项式，构造 次多项式，011 ()()()() ( )iinixxxxxxxxl x 01100100iiinxxxxx (), 0,1,iif

13、xyin ，011()()()()iiiiiinxxxxxxxx1 () 0 ijijl xij 满满足足，011011iiiniiinxxxxxyyyyy 0 0( )( )( )( )ni in nLxy lxy l xy lx，00(),nLxy 满足满足11(),nLxy ( )nnLxy 19 niiinxlyxL0)()( nijjjijnijjjinijjjixxxxxxxxxl000)()()()()( ,)1 , 0)(插插值值基基函函数数次次为为称称Lagrangennixli ( )nLxnLagrange称称为为 次次插插值值多多项项式式20)()()()()()(10

14、10010111001xfxxxxxfxxxxxfxLxfLxL )()()()()()()()()()(2120210121012002010212xfxxxxxxxxxfxxxxxxxxxfxxxxxxxxxL )()()()()()()()()()()()()()()()()()()()()(32313032102321202310131210132003020103213xfxxxxxxxxxxxxxfxxxxxxxxxxxxxfxxxxxxxxxxxxxfxxxxxxxxxxxxxL ）线线性性插插值值插插值值（插插值值节节点点次次10,1xxLagrange）抛抛物物线线插插值值插

15、插值值（插插值值节节点点次次210,2xxxLagrange）插插值值（插插值值节节点点次次3210,3xxxxLagrange211ln11.5(11.5)L 12 11 10 xx取取解：线性插值解：线性插值，分别用分别用Lagrange线性插值和抛物线插值求线性插值和抛物线插值求ln11.5的近似值，并估计截断误差。的近似值，并估计截断误差。例例:已知函数已知函数 的函数表如下的函数表如下6391. 2 5649. 2 4849. 2 3979. 2 3026. 2 ln14 13 12 11 10 xyx 011010110( )xxxxL xyyxxxx 11.51211.5112.

16、39792.48492.4414111212111112114849. 21211123979. 2)(1 xxxL2222211,1211,1211max |( )|max,11xxMfxx21|(11.5)|(11.511)(11.512)|2MR3211.033 10118 2(12)(13)(11)(13)( )2.39792.4849(1112)(1113)(1211)(1213)(11)(12)2.5649(1311)(1312)xxxxL xxx 二二次次插插值值，取取01(2),101max |( )|( )|()()|2xxfR xxxxx .442275. 2)5 .11(

17、5 .11ln2 L(2)21( )(ln )fxxx 1ln11.5(11.5)2.4414L012111213xxx 23.442275. 2)5 .11(5 .11ln2 L,1122max| )( |max3312,1112,113 xxfMxx| )135 .11)(125 .11)(115 .11( |6| )5 .11(|32 MR5319.39 10118 ln11.52.4422754 有有 位位有有效效数数字字02(3),2012max |( )|( )|()()()|6xxfR xxxxxxx (3)32( )(ln )fxxx 31102 24 niiinxlxfxL0

18、)()()(n次拉格朗日插值多项式次拉格朗日插值多项式: 000()()( )()()njjnj ijinjijj iijjj ixxxxlxxxxx n次拉格朗日插值基函数次拉格朗日插值基函数:01( )inl xx xx基基函函数数只只和和节节点点 , , , ,有有关关，与与函函数数值值无无关关( )il x改改变变节节点点或或增增加加节节点点，基基函函数数都都会会改改变变25的的基基次次多多项项式式空空间间nPnnxxx，21 )1(nxxxxxx)()( )( 1 )2(0200 ，nixxxxxlnijjjiji, 1 , 0 ,)()()( (3) 0 10100)()( )(

19、1 )4(niixxxxxxxx，:)()(xTTaylornxfn多多项项式式次次的的!)()(! 2)()()()()()(0)(00)2(200)1(00nxfxxxfxxxfxxxfxTnnn niiinxlxfxL0)()()(:)()(xLLagrangenxfn插插值值多多项项式式次次的的262 牛顿（牛顿（NewtonNewton）插值）插值)()()()(10102010 nnxxxxaxxxxaxxaa希望每加一个节点时，希望每加一个节点时，只附加一项上去即可。只附加一项上去即可。.)(都都需需要要重重新新计计算算全全部部基基函函数数增增加加一一个个节节点点，插插值值虽虽然

20、然易易算算，但但若若要要xlLagrangei( )nLx将将表表示示为为如如何何表表示示？考考虑虑线线性性插插值值0101xxxyyy1010010()()( )()f xf xLxyxxxx 1010010()()( )()f xf xNxyxxxx 27 jijijixxfxxxfxf,)()( 称称上上的的值值在在一一组组互互异异节节点点已已知知函函数数,)(10 xxxf),(,)(均均差差的的一一阶阶差差商商关关于于为为jixxxf kjikikjjixxxfxxxxfxxf, 定义：差商定义：差商( (亦称均差亦称均差) ),)(的的二二阶阶差差商商关关于于为为kjixxxxf2

21、.1 差商差商28 kkkkxxxfxxxxxfxxxf,10021110 一般地一般地 差商的性质：差商的性质：010(),()nikiijj if xf xxxxx 2. kkkxxxbxxxaxxxf,101010 则则若若),()()(xbxaxf 1.线性性线性性.,)(10阶阶差差商商的的关关于于为为kxxxxfk01()()niinif xx 29)()()()()(1xPxxxPxPxLniinn ikjkijkjixxxfxxxfxxxf, 3.对称性对称性,1,. 4次次多多项项式式的的一一阶阶差差商商为为次次多多项项式式关关于于 nxxni)()()(innxPxPxL

22、令令,)(次次多多项项式式为为设设nxPn所所以以且且次次多多项项式式仍仍为为则则, 0)(,)( ixLnxL iinninxxxPxPxxP )()(,从而有从而有次多项式次多项式为为其中其中,1)(1 nxPn)(1xPn 30差商表差商表ix)(ixf0 x)(0 xf1x)(1xf 10,xxf2x)(2xf 21, xxf 210,xxxf3x)(3xf 32,xxf 321,xxxf 3210,xxxxf一阶差商一阶差商 二阶差商二阶差商三阶差商三阶差商31 101100,)(,xxxfxxxxfxxf 2.2 牛顿插值多项式牛顿插值多项式 000,)()()(xxfxxxfxf

23、 nnnxxxfxxxxxxxxxfxxxxxxfxxxfxN,)()( ,)(,)()()(10110210101000 nnnnxxxxfxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxf,)()( ,)()( ,)(,)()()(101010110210101000 .)()(次次牛牛顿顿插插值值多多项项式式的的称称为为nxfxNn 210221010,)(,xxxxfxxxxxfxxxf nnnnxxxfxxxxxfxxxf,)(,01010 nixRxNxfiini, 1 , 0 0)()()( )()(xRxNnn 32 nnnxxxfxxxxxxxxxfxxxxx

24、xfxxxfxN,)()( ,)(,)()()(10110210101000 :)()(xNnxfn次次牛牛顿顿插插值值多多项项式式的的 nnnxxxxfxxxxxxxR,)()()(1010 插插值值余余项项：Newton插插值值余余项项：Lagrange)!1()()()()()1(10 nfxxxxxxxRnnn 33 )()!1()(,)(1)1(101xnfxxxxfxnnnn )()(xNxLnn 由插值多项式的唯一性得由插值多项式的唯一性得 !)(,)(10nfxxxfnn 差商与导数的关系差商与导数的关系 iinixxni00max min 其其中中34010()2.,()ni

25、niijj if xfxxxxx ikjkijkjixxxfxxxfxxxf,. 3 nnnxxxfxxxxxxxxxfxxxxxxfxxxfxN,)()( ,)(,)()()(10110210101000 niiinxlxfxL0)()()(差商的性质：差商的性质：)()(xNxLnn 由由于于同同两两者者的的最最高高次次项项系系数数相相0()()()njjiiiijjixxfxxx 35差商表差商表ix)(ixf0 x)(0 xf1x)(1xf 10,xxf2x)(2xf 21, xxf 210,xxxf3x)(3xf 32,xxf 321,xxxf 3210,xxxxf一阶差商一阶差商

26、二阶差商二阶差商三阶差商三阶差商1)(0 xx )(010 xxj )(020 xxj 30001010120120123( )()(),()(),()()(),Nxf xxxf xxxxxxf xxxxxxxxxf xxxx33001230( )( )() ,jf xNxxxf x x x xx 36线性插值线性插值ln11.52.44140.0035(11.511)(11.512)2.442 二次插值二次插值21( )( )NxNx )11(0870.03979.2)(1 xxN4414.2)115.11(0870.03979.25.11ln 例：用牛顿法求例：用牛顿法求ln11.5近似值

27、近似值ixiixy ln 112.3979122.4849132.5649一阶差商一阶差商0.08700.0800二阶差商二阶差商-0.00351x-11(x-11)(x-12)0.0035(11)(12)xx 373,3 ,3, 132)(:610356fxxxxf求求其其六六阶阶差差商商若若例例 利利用用差差商商和和导导数数的的关关系系解解 :. 4 , 3 , 2 , 1 , 0, 3 , 2 , 1 , 0, 1)(:3 ffxxxf则差商则差商设设例例10 !)(,)(10nfxxxfnn !6)(3,3 ,3)6(610 ff 2 382.3 差分差分向前差分向前差分 向后差分向后

28、差分 中心差分中心差分 )(221hiixff 其中其中当节点等距分布时当节点等距分布时: :),., 0(0nihixxi iiifff 11 iiifff2121 iiifff , 2 111 kfffikikik 212111 iifffkkik , 2 111 kfffikikik39差分表差分表ix)(ixf0 x)(0 xf1x)(1xf)(10ff 2x)(2xf)(2202ff 3x)(3xf一阶差分一阶差分 二阶差分二阶差分三阶差分三阶差分)(21ff )(32ff )(3212ff )(3303ff 2212kkkkffff二阶向前差分二阶向前差分332133kkkkkff

29、fff三阶向前差分三阶向前差分40差分的重要性质：差分的重要性质：gbfagbfa )( 例例如如2. 差分值可由函数值算出差分值可由函数值算出：!)1).(1( jjnnnjn 其其中中jknnjjknfjnf 0)1(jknjnknfjnf 0)1(1. 线性性：线性性：kkkkffff 1222kkkkffff 1222413. 差分和差商的关系差分和差商的关系kkkhkfxxf!,00 knkknnnhkfxxxf!,1 ()0( ),!kkff xxk 由由导导数数和和差差商商的的关关系系得得kkkhff0)()( 4. 差分和导数的关系差分和导数的关系42).(,.,.)(,)()

30、( :1000100 nnnxxxxxxfxxxxfxfxN牛牛顿顿公公式式牛顿前差公式牛顿前差公式则则设设,0htxx ),(, )()!1().(1()(0)1(1nnnnxxfhnntttxR 0000!) 1() 1(.)()(fnntttftfthxNxNnnn )()!1()()(1)1(xnfxRnnn 2.4 等距节点插值公式等距节点插值公式43).(,.,.)(,)()(:101xxxxxxfxxxxfxfxNnnnnnnn 牛牛顿顿公公式式htxxn 设设牛顿后差公式，将节点顺序倒置牛顿后差公式，将节点顺序倒置nnnnnnnnfnntttfttftfthxNxN !) 1(

31、) 1(! 2) 1()()(2),(, )()!1().(1()(0)1(1nnnnxxfhnntttxR )()!1()()(1)1(xnfxRnnn 44差分表差分表ix)(ixf0 x)(0 xf1x)(1xf)(10ff 2x)(2xf)(2202ff 3x)(3xf一阶差分一阶差分 二阶差分二阶差分三阶差分三阶差分1t)(! 2110jtj )(21ff )(32ff )(3212ff )(3303ff )(! 3120jtj 1t)(! 2110jtj )(! 3120jtj 45f(x) = ex Interpolation at 0 446f(x) = ex, Interpolation at 0 1 447f(x) = ex, Interpolation at 0 1 4 3 4822511)(xxf 4922511)(xxf 503 分段线性插值分段线性插值), 1 , 0( )( ) 1 (niyxii ,)()1, 1 , 0( ,)2(1为为线线性性函函数数上上在在xnixxii .,)()(10的的分分段段线线性性插插值值函函数数过过节节点点为为称称nxxxxfx bxxxxann 110 个个不不同同的的节节点点给给定定上上设设在在1, nba问题：问题：使使得得求求函函数数)(x ), 1 , 0( )(nixfyii