北京理工博士入學考試 數(shù)值分析第5章第1部分

1、1第五章習題第五章習題P171 1,2,3,4,5,6,8,9,10中中 Lagrange和和Newton法各選兩個題目法各選兩個題目 13 16(降階法降階法,基函數(shù)基函數(shù),待定系數(shù)待定系數(shù))2x0 x1x2x3x4xg(x)(xfy 函函數(shù)數(shù)：在在一一些些點點處處測測得得( (或或計計算算得得到到) )函函數(shù)數(shù)值值:nixfyii2 , 1 , 0 )( 使使得得求求一一個個簡簡單單易易算算的的函函數(shù)數(shù)),(xg(),iig xy ),()(,0 xfxgxxn 上上在在.)()(的的插插值值函函數(shù)數(shù)稱稱為為xfxg,表表達達式式未未知知或或非非常常復復雜雜 f(x)第五章第五章 插值法插

2、值法()(),iig xf x 即即0,1,2in 多項式多項式插值多項式插值多項式問問題題：3.)()(多多項項式式過過這這組組互互異異節(jié)節(jié)點點的的插插值值為為xfxn ,1,)(10處處的的函函數(shù)數(shù)值值互互異異點點個個上上在在已已知知函函數(shù)數(shù)nxxxnbaxf nixfyii, 1 , 0 )( ,n求求一一個個次次數(shù)數(shù)不不超超過過 的的多多項項式式()(0,1,2,) (*)niixy in ,為為插插值值區(qū)區(qū)間間稱稱ba,為插值節(jié)點為插值節(jié)點ix 01( )nnnxaa xa x 滿足插值條件滿足插值條件niniyyyyxxxx001 Lagrange插值插值1.1 插值多項式插值多項

3、式40,1i 0,1 2i ，0,1 2 3i ，插插值值多多項項式式的的幾幾何何意意義義：1(,()(0,1,)( )iinnnxf xinnx 次次多多項項式式插插值值，是是過過個個點點作作一一條條 次次多多項項式式曲曲線線近近似似被被插插值值函函數(shù)數(shù)曲曲線線 一一次次多多項項式式二二次次多多項項式式三三次次多多項項式式5基本問題基本問題:1( )nx . .插插值值多多項項式式是是否否存存在在唯唯一一？2( )( )( )?nnxf xx . .若若存存在在，截截斷斷誤誤差差3( )nx . .如如何何求求？6應滿足方程組應滿足方程組的系數(shù)的系數(shù))1 , 0(niain nnnnnnnn

4、nnyxaxaxaayxaxaxaayxaxaxaa22101121211000202010 1nn 個個互互異異節(jié)節(jié)點點上上的的 次次插插值值多多項項式式存存在在唯唯一一:()(0,1,2,)niixy in 滿滿足足插插值值條條件件系系數(shù)數(shù)矩矩陣陣為為200021112111nnnnnnxxxxxxxxx ,0()niji jijxx 其其行行列列式式的的值值為為 01( )nnnxaa xa x 存存在在唯唯一一性性： 若若范范德德蒙蒙特特矩矩陣陣，0 方方程程組組的的解解存存在在唯唯一一，所所以以710( )(),nniixxx 其其中中1.2 插值多項式的誤差估計插值多項式的誤差估計

5、,1,10互互異異節(jié)節(jié)點點上上是是設設 nbaxxxn, )()(次次插插值值多多項項式式的的過過這這組組節(jié)節(jié)點點的的是是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 任任意意固固定定構(gòu)構(gòu)造造輔輔助助函函數(shù)數(shù)反反復復利利用用羅羅爾爾定定理理(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 通通過過解解線線性性方方程程組組求求插插值值多多項項式式，原原因因：系系數(shù)數(shù)矩矩陣陣為為范范德德蒙蒙矩矩陣陣，通通常常是是病病態(tài)態(tài)的的2012( )nnnxaa xa xa x 用用表表達達式式計計算算近近似似值值誤誤差差較較大大如如何何求求插插值值多多項項式式？不不可可取取13 1.3 拉格朗日插值多項式拉格朗日插值多項式時時當當1 n0101xxxyyy01,aa x 即即

9、求求線線性性函函數(shù)數(shù)滿滿足足插插值值條條件件1x這這里里把把線線性性函函數(shù)數(shù)表表示示成成基基 ，的的線線性性組組合合00101011yaa xyaa x 和和線線性性函函數(shù)數(shù)還還可可以以表表示示成成其其它它基基的的線線性性組組合合拉拉格格朗朗日日多多項項式式的的思思想想：01( )( )lxlx構(gòu)構(gòu)造造其其它它的的基基，例例如如和和把把線線性性函函數(shù)數(shù)都都可可以以表表成成：0 01 1( )( )a lxa lx 01,aa使使系系數(shù)數(shù)很很容容易易求求得得, ,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次拉格朗日插值基函數(shù)次拉格朗日插值基函數(shù)構(gòu)造基函數(shù)構(gòu)造基函數(shù)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次拉格朗日插值基函數(shù)次拉格朗日插值基函數(shù)構(gòu)造基函數(shù)構(gòu)造基函數(shù)16x0 x1x2)(0 xl)(2xl)(1xl二次二次

12、Lagrange基函數(shù)基函數(shù))()()(2010210 xxxxxxxxxl )()()(2101201xxxxxxxxxl )()()(1202102xxxxxxxxxl 17二次二次Lagrange插值多項式插值多項式)()()()()()()()()()(2120210121012002010212xfxxxxxxxxxfxxxxxxxxxfxxxxxxxxxL 18,1n 一一般般地地 對對于于個個節(jié)節(jié)點點，已已知知( )inl x構(gòu)造 次多項式，構(gòu)造 次多項式，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)(插插值值基基函函數(shù)數(shù)次次為為稱稱Lagrangennixli ( )nLxnLagrange稱稱為為 次次插插值值多多項項式式20)()()()()()(10

14、10010111001xfxxxxxfxxxxxfxLxfLxL )()()()()()()()()()(2120210121012002010212xfxxxxxxxxxfxxxxxxxxxfxxxxxxxxxL )()()()()()()()()()()()()()()()()()()()()(32313032102321202310131210132003020103213xfxxxxxxxxxxxxxfxxxxxxxxxxxxxfxxxxxxxxxxxxxfxxxxxxxxxxxxxL ）線線性性插插值值插插值值（插插值值節(jié)節(jié)點點次次10,1xxLagrange）拋拋物物線線插插值值插

15、插值值（插插值值節(jié)節(jié)點點次次210,2xxxLagrange）插插值值（插插值值節(jié)節(jié)點點次次3210,3xxxxLagrange211ln11.5(11.5)L 12 11 10 xx取取解：線性插值解：線性插值，分別用分別用Lagrange線性插值和拋物線插值求線性插值和拋物線插值求ln11.5的近似值，并估計截斷誤差。的近似值，并估計截斷誤差。例例:已知函數(shù)已知函數(shù) 的函數(shù)表如下的函數(shù)表如下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 有有 位位有有效效數(shù)數(shù)字字02(3),2012max |( )|( )|()()()|6xxfR xxxxxxx (3)32( )(ln )fxxx 31102 24 niiinxlxfxL0

18、)()()(n次拉格朗日插值多項式次拉格朗日插值多項式: 000()()( )()()njjnj ijinjijj iijjj ixxxxlxxxxx n次拉格朗日插值基函數(shù)次拉格朗日插值基函數(shù):01( )inl xx xx基基函函數(shù)數(shù)只只和和節(jié)節(jié)點點 , , , ,有有關(guān)關(guān)，與與函函數(shù)數(shù)值值無無關(guān)關(guān)( )il x改改變變節(jié)節(jié)點點或或增增加加節(jié)節(jié)點點，基基函函數(shù)數(shù)都都會會改改變變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希望每加一個節(jié)點時，希望每加一個節(jié)點時，只附加一項上去即可。只附加一項上去即可。.)(都都需需要要重重新新計計算算全全部部基基函函數(shù)數(shù)增增加加一一個個節(jié)節(jié)點點，插插值值雖雖然

20、然易易算算，但但若若要要xlLagrangei( )nLx將將表表示示為為如如何何表表示示？考考慮慮線線性性插插值值0101xxxyyy1010010()()( )()f xf xLxyxxxx 1010010()()( )()f xf xNxyxxxx 27 jijijixxfxxxfxf,)()( 稱稱上上的的值值在在一一組組互互異異節(jié)節(jié)點點已已知知函函數(shù)數(shù),)(10 xxxf),(,)(均均差差的的一一階階差差商商關(guān)關(guān)于于為為jixxxf kjikikjjixxxfxxxxfxxf, 定義：差商定義：差商( (亦稱均差亦稱均差) ),)(的的二二階階差差商商關(guān)關(guān)于于為為kjixxxxf2

21、.1 差商差商28 kkkkxxxfxxxxxfxxxf,10021110 一般地一般地 差商的性質(zhì)：差商的性質(zhì)：010(),()nikiijj if xf xxxxx 2. kkkxxxbxxxaxxxf,101010 則則若若),()()(xbxaxf 1.線性性線性性.,)(10階階差差商商的的關(guān)關(guān)于于為為kxxxxfk01()()niinif xx 29)()()()()(1xPxxxPxPxLniinn ikjkijkjixxxfxxxfxxxf, 3.對稱性對稱性,1,. 4次次多多項項式式的的一一階階差差商商為為次次多多項項式式關(guān)關(guān)于于 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 差商與導數(shù)的關(guān)系差商與導數(shù)的關(guān)系 iinixxni00max min 其其中中34010()2.,()ni

25、niijj if xfxxxxx ikjkijkjixxxfxxxfxxxf,. 3 nnnxxxfxxxxxxxxxfxxxxxxfxxxfxN,)()( ,)(,)()()(10110210101000 niiinxlxfxL0)()()(差商的性質(zhì)：差商的性質(zhì)：)()(xNxLnn 由由于于同同兩兩者者的的最最高高次次項項系系數(shù)數(shù)相相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求求其其六六階階差差商商若若例例 利利用用差差商商和和導導數(shù)數(shù)的的關(guān)關(guān)系系解解 :. 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 其中其中當節(jié)點等距分布時當節(jié)點等距分布時: :),., 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差分的重要性質(zhì)：差分的重要性質(zhì)：gbfagbfa )( 例例如如2. 差分值可由函數(shù)值算出差分值可由函數(shù)值算出：!)1).(1( jjnnnjn 其其中中jknnjjknfjnf 0)1(jknjnknfjnf 0)1(1. 線性性：線性性：kkkkffff 1222kkkkffff 1222413. 差分和差商的關(guān)系差分和差商的關(guān)系kkkhkfxxf!,00 knkknnnhkfxxxf!,1 ()0( ),!kkff xxk 由由導導數(shù)數(shù)和和差差商商的的關(guān)關(guān)系系得得kkkhff0)()( 4. 差分和導數(shù)的關(guān)系差分和導數(shù)的關(guān)系42).(,.,.)(,)()

30、( :1000100 nnnxxxxxxfxxxxfxfxN牛牛頓頓公公式式牛頓前差公式牛頓前差公式則則設設,0htxx ),(, )()!1().(1()(0)1(1nnnnxxfhnntttxR 0000!) 1() 1(.)()(fnntttftfthxNxNnnn )()!1()()(1)1(xnfxRnnn 2.4 等距節(jié)點插值公式等距節(jié)點插值公式43).(,.,.)(,)()(:101xxxxxxfxxxxfxfxNnnnnnnn 牛牛頓頓公公式式htxxn 設設牛頓后差公式，將節(jié)點順序倒置牛頓后差公式，將節(jié)點順序倒置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為為線線性性函函數(shù)數(shù)上上在在xnixxii .,)()(10的的分分段段線線性性插插值值函函數(shù)數(shù)過過節(jié)節(jié)點點為為稱稱nxxxxfx bxxxxann 110 個個不不同同的的節(jié)節(jié)點點給給定定上上設設在在1, nba問題：問題：使使得得求求函函數(shù)數(shù))(x ), 1 , 0( )(nixfyii