北京理工大學數(shù)值分析總復習實用教案

1、1考試(kosh)時帶計算器 上機題請在11月30日晚9:30之前交，交打印稿。 答疑時間：11月28，29, 30（即星期3, 4，5）晚上(wn shang)7:309:30，上機作業(yè)也在答疑時間交。 答疑地點：中教816。第1頁/共68頁第一頁，共69頁。2第一章 誤差(wch) 絕對（相對(xingdu)）誤差 ( 限 ) 有效數(shù)字(yu xio sh z)第2頁/共68頁第二頁，共69頁。3 有效數(shù)字(yu xio sh z)x: 精確(jngqu)值x*: 近似值, 其科學(kxu)記數(shù)法為),0(10. 0*121 aaaaxmn若nmxx 1021|*|則稱近似值 x*具有n位

2、有效數(shù)字.第3頁/共68頁第三頁，共69頁。4第二章 解線性方程組的直接(zhji)方法 列主元素(yun s)法 LU分解(fnji)法 (Doolittle分解(fnji)法) (追趕法) 平方根法與改進的平方根法 條件數(shù)bAx 求第4頁/共68頁第四頁，共69頁。511u1 kiliiu1 jiu1 1 iil1klkil1ilijuiiuju1iu121l12u22uju11kliju), 2 , 1(nj ), 3 , 2(nk ), 1,(niij kil), 1(nik 對i=2,3, n,ja1 111uak )(112211jiiijijiijululula iiiikiik

3、ikkiuululula)(112211 第5頁/共68頁第五頁，共69頁。6,LUA bLUxbAx , bLy 先求再求yUx 得x. 直接三角(snjio)分解法或Doolittle分解法.y第6頁/共68頁第六頁，共69頁。7 A: 對稱(duchn)正定陣Cholesky分解(fnji)TLLA 21l11l22l1nl2nl2il1iliilnilnnlTL)(),(jillajiij 設 li =L的第 i個行向量, 則,1111al )2(1111 klalkk對 i=2,3,n,)(2121 iiiiiiillaliiiikiikikkikilllllllal)(112211

4、 )., 1(nik 第7頁/共68頁第七頁，共69頁。8bxLLbAxT 先求 Ly=b, 再求 LTx=y. 平方根法或Cholesky分解(fnji)法.y第8頁/共68頁第八頁，共69頁。9第三章 解線性方程組的迭代(di di)解法 Jacobi迭代法 Gauss-Seidel迭代法 迭代法收斂的條件(tiojin)(充要條件(tiojin), 充分條件(tiojin)bAx 求第9頁/共68頁第九頁，共69頁。10 Jacobi迭代法,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ii

5、iniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k)(k)(k+1), 2 , 1(ni Tknkkkxxxx)()(2)(1)(, 第10頁/共68頁第十頁，共69頁。11 Gauss-Seidel迭代法,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ininiiiiiiiiiibxaxaxaxaxa ,111111iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k+1)(k+1)(k+1), 2 , 1(ni 第11頁/共68頁第十一頁，共69頁。12 迭代法收斂(shulin)

6、的充分必要條件 )0()()1(,xgMxxkk任意(rny)收斂(shulin). 1)( M 迭代法收斂的充分條件若A為嚴格對角占優(yōu)或不可約對角占優(yōu), 則求解Ax=b 的Jacobi迭代法和Gauss-Seidel迭代法均收斂.若A為對稱正定陣, 則求解Ax=b的Gauss-Seidel迭代法收斂.第12頁/共68頁第十二頁，共69頁。13第四章特征值與特征向量的計算第四章特征值與特征向量的計算(j sun) 冪法和反冪法第13頁/共68頁第十三頁，共69頁。14設A為n階實矩陣, 其特征值為1, 2, , n, 相應(xingyng)的特征向量為u1, u2, , un. 且滿足條件 n

7、 32 u1, u2, , un線性無關(wgun). 冪法 冪法: 求1及其相應(xingyng)的特征向量.此時1一定是實數(shù)! 1通常稱為主特征值. 1 第14頁/共68頁第十四頁，共69頁。15 冪法的計算公式 kkkkkkkxyxAyx )()()()1()(max 任取初始(ch sh)向量x(0)=y(0)0, 對k=1, 2, , 構造向量序列 x(k), y(k)1 k)max(11)(uuyk 當k充分(chngfn)大時第15頁/共68頁第十五頁，共69頁。16反冪法 用于計算矩陣按模最小的特征值及其特征向量, 也可用來計算對應于一個(y )給定近似特征值的特征向量, 是目

8、前求特征向量最有效的方法. 反冪法第16頁/共68頁第十六頁，共69頁。17 反冪法迭代(di di)公式為 任取初始向量(xingling)x(0)=y(0)0, 構造向量(xingling)序列)., 2 , 1 , 0()max()1()1()1()(1)1( kxxyyAxkkkkk 迭代向量(xingling)x(k+1)可以通過解方程組求得)()1(kkyAx nkx 1)max( )max()(nnkuuy 當k充分大時第17頁/共68頁第十七頁，共69頁。18第五章 插值法 Lagrange插值 Newton插值 Hermite插值第18頁/共68頁第十八頁，共69頁。19問題

9、(wnt):ix2x1xnx)(iixfy 1y2yny0 x0y求 Ln(x).(1) 至多n次多項式;)., 1 , 0()()(niyxfxLiiin (2)第19頁/共68頁第十九頁，共69頁。20 Lagrange插值)()()()()(1100 xlyxlyxlyxlyxLnniin 其中(qzhng) li (x) 為插值基函數(shù)(1) n次多項式);, 1 , 0( , 0)(, 1)(ijnjxlxljiii ,)()()(0 nijjjijixxxxxl)., 1 , 0(ni 截斷誤差)()()(xLxfxRnn . )()!1()(0)1( niinxxnf (2)第20

10、頁/共68頁第二十頁，共69頁。21 差商一階差商jijijixxxfxfxxf )()(,二階差商kikjjikjixxxxfxxfxxxf , k階差商kkkkxxxxxfxxxfxxxf 02111010,第21頁/共68頁第二十一頁，共69頁。22 Newton插值公式(gngsh)(,)()(0100 xxxxfxfxNn )(,10210 xxxxxxxf)()(,11010 nnxxxxxxxxxf一般通過差商表進行(jnxng)計算).()(xNxLnn 截斷誤差同Lagrange插值公式(gngsh).第22頁/共68頁第二十二頁，共69頁。23 Hermite插值多項式ix

11、2x1xnx)(iixfy 1y2yny0 x0y)( iixfy 1y2yny0y求 H(x).(1) 至多(zhdu)(2n+1)次多項式;)., 1 , 0(, )( ,)(niyxHyxHiiii (2)第23頁/共68頁第二十三頁，共69頁。24)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHyxHyxHynn )(xhiixixnx0 x1(2n+1)次多項式 ),()( 21)(2xlxxxlxhiiii 其中(qzhng)li (x)是 Lagrange插值基函數(shù).第24頁/共68頁第二十四頁，共69頁。25)()()()(1100 xhyxhy

12、xhyxHnn )()()(1100 xHyxHyxHynn )(xHiixixnx0 x1(2n+1)次多項式),()()(2xlxxxHiii 其中(qzhng)li (x)是 Lagrange插值基函數(shù).第25頁/共68頁第二十五頁，共69頁。26 截斷誤差)()()(xHxfxR .)()()()!22()(22120)22(nnxxxxxxnf Hermite插值的一般形式(xngsh)(見課本122頁)第26頁/共68頁第二十六頁，共69頁。27第六章 函數(shù)(hnsh)逼近 最小二乘一次 (二次)多項式擬合(n h) 函數(shù)(hnsh)的最佳平方逼近第27頁/共68頁第二十七頁，共6

13、9頁。28問題(wnt): 給定n個數(shù)據(jù)點 (xi , yi) (i=1, 2, , n)ix2x1xnxiy1y2yny求,2210 xaxaay (或 y=a0+a1x ) 使得(sh de) 212210)( niiiixaxaay達到(d do)最小. 最小二乘一次 (二次)多項式擬合第28頁/共68頁第二十八頁，共69頁。29 212210210)(),( niiiixaxaayaaaF 令利用多元(du yun)函數(shù)取極值的必要條件得到正則方程組n niix1 niix12 niiy1 niix1 niix12 niix12 niix13 niix14 niix13 niiiyx1

14、 niiiyx120a1a2a由上式求得a0, a1, a2, 得到(d do)最小二乘擬合二次多項式.第29頁/共68頁第二十九頁，共69頁。30 最小平方(pngfng)線性多項式逼近3 函數(shù)的最佳(zu ji)平方逼近 設 f (x)是區(qū)間a, b上的連續(xù)函數(shù)(hnsh), 求線性多項式函數(shù)(hnsh) (x)=a0+a1x 使得, .2)()(2)()(10 babadxxaaxfdxxxf為最小為最小 (x)稱為函數(shù) f (x)在區(qū)間 a, b 上的一次最佳平方逼近多項式.即求a0, a1使得 .2)()(min2)()()(10 baxgbadxxgxfdxxaaxf線性多項式線性

15、多項式第30頁/共68頁第三十頁，共69頁。31 二次最佳平方(pngfng)逼近多項式設 f (x)是區(qū)間a, b上的連續(xù)函數(shù)(hnsh), 求二次多項式函數(shù)(hnsh) (x)=a0+a1x+ a2x2 使得, (x)稱為函數(shù) f (x)在區(qū)間 a, b 上的二次最佳(zu ji)平方逼近多項式. .2)()(min2)()()(2210 baxgbadxxgxfdxxaxaaxf二次多項式二次多項式第31頁/共68頁第三十一頁，共69頁。32第七章 數(shù)值(shz)微分與數(shù)值(shz)積分 復化梯形(txng)公式 復化Simpson公式(gngsh) Romberg算法 Gauss型求積

16、公式 代數(shù)精確度 截斷誤差第32頁/共68頁第三十二頁，共69頁。33 代數(shù)(dish)精確度設有求積公式(gngsh) nkkkbaxfAdxxf0)()(若它對 f (x)=1, x, x2, xm 都能精確成立(即上式等號成立), 但對 f (x)=xm+1 上式等號不成立, 則稱該求積公式具有(jyu)m次代數(shù)精確度. 第33頁/共68頁第三十三頁，共69頁。34 復化梯形(txng)公式 bannfffffhdxxf)(22)(1210其中(qzhng),nabh .),(ihaxxffiii 截斷誤差nbaTTdxxffR )()(.:nT ).,(),( 122bafhab 第3

17、4頁/共68頁第三十四頁，共69頁。35 復化Simpson公式(gngsh) .:)(2)(43)(2242123120nmbammSffffffffhdxxf 區(qū)間(q jin)a, b n等分, n=2m其中(qzhng).nabh 截斷誤差).,(),(180)()()4(4bafhabSdxxffRnbaS 第35頁/共68頁第三十五頁，共69頁。36 梯形(txng)值序列 mT2 遞推算法(sun f) mhTTmm2122所有新增加(zngji)節(jié)點的函數(shù)值之和.其中.2mmabh 第36頁/共68頁第三十六頁，共69頁。37 Romberg算法(sun f)1T32T16T8

18、T4T2T2S4S8S16S32S4C8C16C32C8D16D32D8S3448TT 16C1516816SS 636481616CCD 第37頁/共68頁第三十七頁，共69頁。38 Gauss型求積公式(gngsh)()(1knkkbaxfAdxxf Ak: 求積系數(shù)(xsh),xk: 求積節(jié)點(ji din)如果該求積公式具有(2n-1)階代數(shù)精確度, 則稱其為Gauss型求積公式.設有求積公式第38頁/共68頁第三十八頁，共69頁。39 區(qū)間(q jin)-1, 1上的Guass型求積公式 nkkkxfAdxxf111)()(其中求積節(jié)點(ji din)xk為n階Legendre多項式

19、的零點; Ak, xk 的值可查表得到. 一般(ybn)a, b上的Gauss型求積公式可用換元法轉(zhuǎn)化成-1, 1上的Gauss型求積公式.222)(11dtabtabbafdxxfba 第39頁/共68頁第三十九頁，共69頁。40第八章 非線性方程(fngchng)解法 二分法(對分區(qū)間(q jin)法)求 f (x) = 0 的根 簡單(jindn)迭代法 (收斂的充分條件) 牛頓法第40頁/共68頁第四十頁，共69頁。4112 kkabx*|x . 12lnlnln abk 設a, b是 f (x)=0的有根區(qū)間(q jin), 用二分法迭代 給定精度(jn d), 迭代次數(shù)k 滿足下式

20、, 能保證滿足精度(jn d) 二分法(對分區(qū)間(q jin)法)第41頁/共68頁第四十一頁，共69頁。42 簡單(jindn)迭代法)(0)(xgxxf 構造(guzo)遞推公式 01),(xxgxnn適當(shdng)選取.以 逐次逼近 f (x)=0的根. nx如何構造收斂的迭代法?第42頁/共68頁第四十二頁，共69頁。43定理(dngl)考慮(kol)方程 x = g(x), g(x)Ca, b, 若( I ) 當 xa, b 時， g(x)a, b；( II ) 0 L 1 使得 | g(x) | L 對 xa, b 成立(chngl)。則任取 x0a, b，由 xk+1 = g

21、(xk) 得到的序列 收斂于g(x) 在a, b上的唯一不動點。并且有誤差估計式： 0kkx|11|*|1kkkxxLxx ( k = 1, 2, )|1|*|01xxLLxxk k第43頁/共68頁第四十三頁，共69頁。44 牛頓(ni dn)法原理(yunl)：將非線性方程線性化 ( Taylor 展開 ), 1 ,0()()(1 nxfxfxxnnnnxyx*xnxn+1第44頁/共68頁第四十四頁，共69頁。45第九章 常微分方程(wi fn fn chn)數(shù)值解法 構造常微分方程離散格式的三種(sn zhn)方法 單步法常見(chn jin)格式 多步法常見格式 重要概念: 局部截斷

22、誤差第45頁/共68頁第四十五頁，共69頁。46 用差商近似(jn s)導數(shù) 數(shù)值積分方法(fngf) Taylor多項式近似(jn s)方法 構造常微分方程離散格式的三種方法第46頁/共68頁第四十六頁，共69頁。47 Euler法 改進(gijn)Euler法 經(jīng)典(jngdin)四階RK方法 單步法常見(chn jin)格式第47頁/共68頁第四十七頁，共69頁。48 多步法常見(chn jin)格式 Simpson公式(gngsh) Adams顯隱(xin yn)公式 Adams預測-校正公式第48頁/共68頁第四十八頁，共69頁。49 局部(jb)截斷誤差 整體(zhngt)截斷誤差

23、Taylor展開(zhn ki)方法 幾個重要概念 數(shù)值方法的階數(shù)第49頁/共68頁第四十九頁，共69頁。50數(shù)值(shz)分析總復習例題第50頁/共68頁第五十頁，共69頁。51分析(fnx) 333231222111aaaaaaA對稱TLL 333231222111llllll0 333222312111llllll0),(jiijlla 其中(qzhng) li為矩陣 L的第 i個行向量.,1111al ,112121lal ,113131lal ,2212222lal ,2231213232lllal .2322313333llal 一. 用平方根法求線性方程組AX=b, 其中(qzh

24、ng),22484548416 A,321 xxxX.1034 b第51頁/共68頁第五十一頁，共69頁。52, 4161111 al, 144112121 lal, 2113131 lal解:,1111al ,112121lal ,113131lal ,2212222lal ,2231213232lllal .2322313333llal 一. 用平方根法求線性方程組AX=b, 其中(qzhng),22484548416 A,321 xxxX.1034 b第52頁/共68頁第五十二頁，共69頁。53一. 用平方根法求線性方程組AX=b, 其中(qzhng), 2152212222 lal,

25、3)(2221313232 lllal, 32322313333 llal解: 332021004LybxLLT , 4161111 al, 144112121 lal, 2113131 lal,22484548416 A,321 xxxX.1034 b第53頁/共68頁第五十三頁，共69頁。54解:先解 Ly=b, 再解 LTx=y, 1034332021004321yyy,621 y 621300320214321xxx.2449 x 332021004LybxLLT 一. 用平方根法求線性方程組AX=b, 其中(qzhng),22484548416 A,321 xxxX.1034 b第5

26、4頁/共68頁第五十四頁，共69頁。55二. 設有方程組寫出Jacobi迭代, Gauss-Seidel迭代的計算公式, 兩種迭代法是否(sh fu)收斂? 為什么? ,251084,118104,134410321321321xxxxxxxxxJacobi迭代法不收斂(shulin),Gauss-Seidel迭代法.第55頁/共68頁第五十五頁，共69頁。56三. 按下表求 f (x)的四次Hermite插值多項式H(x), 并寫出截斷誤差R (x)=f (x)H(x)的表達式.ix)(ixf)( ixf01212101.212231)(432xxxxxH 第56頁/共68頁第五十六頁，共6

27、9頁。57四. (1) 求形如 )10()()(21)(212110 xxxfxfdxxf的求積公式, 使其至少(zhsho)具有兩次代數(shù)精確度, 該公式是否具有三次代數(shù)精確度?解(1) 由已知, 當 f (x)分別(fnbi)為1, x, x2時, 求積公式等號成立. 即1110 dx)11(21 2110 dxx)(2121xx 31102 dxx)(212221xx .32121,3212121xx41103 dxx)(213231xx 故該公式(gngsh)具有3次代數(shù)精確度.第57頁/共68頁第五十七頁，共69頁。58四. (2) 選用合適的數(shù)值積分方法計算的近似值, 要求(yoqi

28、)計算結果具有3位有效數(shù)字.dxx 102)cos(解設 f (x)=cos(x2), xk=k/8 (k=0, 1, , 8), fk=f (xk), 則f0=1f1=0.999877932f2=0.998047511f3=0.990128588f4=0.968912422f5=0.924671261f6=0.845924499f7=0.720949381f8=0.540302306梯形(txng)值序列T1=0.770151152T2=0.869531786T4=0.895758895T8=0.902332842Simpson值序列(xli)S2=0.902658664S4=0.90450

29、1264S8=0.904524157梯形值序列的逐次分半算法故904524157. 0)cos(102 dxx第58頁/共68頁第五十八頁，共69頁。59五. 設(1) 用迭代公式 求方程 f (x)=0在x0=2.0附近的一個根, 試問(shwn)此迭代法是否收斂? (2) 用合適的方法求 f (x)=0在x0=2.0附近的根, 要求計算結果具有4位有效數(shù)字., 1)(23 xxxxf21111kkkxxx 解 (1) 迭代(di di)函數(shù)為,111)(2xxxg 驗證(ynzhng) g(x)在區(qū)間1.7, 2.0上滿足壓縮映像定理, 故該迭代法收斂.(2) 可用Newton迭代法求根,

30、 取x0=2.0, 寫出迭代公式后計算三次得x1=1.857142857, x2=1.839544514, x3=1.839286811. 故x3即為所求方程近似根.第59頁/共68頁第五十九頁，共69頁。60六. 確定(qudng)求解初值問題 .)(,),(0yaybxayxfy的二步隱式Adams方法(fngf)5(12111 nnnnnfffhyy 中的參數(shù)(cnsh), 使該方法成為三階方法, 并寫出其局部截斷誤差主項.).()(241, 85)4(41hOxyhRnn 可用數(shù)值積分方法或Taylor展開方法第60頁/共68頁第六十頁，共69頁。61七. 據(jù)資料記載(jzi), 某地

31、某年間間隔30天的日出日落時間如下5月1日5月31日6月30日4:514:174:1619:3819:50日出(r ch)日落(r lu)19:04日出日落時間表請問: 這一年中哪一天白天最長?解 用Newton插值公式較為方便, 答案為:這一年中以6月22日的白天最長.第61頁/共68頁第六十一頁，共69頁。62練習(linx)1. 第126頁. 求解線性方程組 Ax=b, 其中A如右圖所示, 試構造一個與求解三對角方程組的追趕法類似(li s)的直接方法. 2222112211nnnn . 0, 0, 1 iiii 其中(qzhng)第62頁/共68頁第六十二頁，共69頁。632. 確定如下(rxi)求積公式中的求積系數(shù), 使其具有盡可能高的代數(shù)精確度).( )( )()()(1010bfBafBbfAafAdxxfba 提示: 用三次(sn c)Hermite插值多項式來近似函數(shù) f (x).第63頁/共68頁第六十三頁，共69頁。64 3. 若干年以前, 美國原子能委員會準備將濃縮的放