數(shù)值分析計(jì)算方法復(fù)習(xí)(典型例題)

1、計(jì)算方法復(fù)習(xí)計(jì)算方法復(fù)習(xí)典型概念例題典型概念例題Final Exam Review零零 緒論緒論誤誤差差及及算算法法誤差誤差算法算法分類分類度量度量傳播傳播舍入舍入截?cái)嘟財(cái)嘟^對(duì)絕對(duì)相對(duì)相對(duì)有效數(shù)字有效數(shù)字一元函數(shù)一元函數(shù)n元函數(shù)元函數(shù)一一 插值與逼近插值與逼近插值法插值法工具工具多項(xiàng)式插值多項(xiàng)式插值分段多項(xiàng)式分段多項(xiàng)式插值插值差商差商差分差分插值基函數(shù)插值基函數(shù)存在唯一性存在唯一性誤差估計(jì)誤差估計(jì)插值公式插值公式Hermite插值插值分段線性分段線性分段三次分段三次Hermite插值插值三次樣條插值三次樣條插值函數(shù)逼近函數(shù)逼近預(yù)備知識(shí)預(yù)備知識(shí)函數(shù)逼近方法函數(shù)逼近方法范數(shù)范數(shù)內(nèi)積內(nèi)積正交多項(xiàng)式正

2、交多項(xiàng)式最佳一致逼近最佳一致逼近最佳平方逼近最佳平方逼近最小二乘擬合最小二乘擬合三角函數(shù)逼近三角函數(shù)逼近帕德逼近帕德逼近例例1觀測物體過原點(diǎn)的直線運(yùn)動(dòng)觀測物體過原點(diǎn)的直線運(yùn)動(dòng),得到所示數(shù)據(jù)得到所示數(shù)據(jù),求運(yùn)動(dòng)方程求運(yùn)動(dòng)方程.時(shí)間t/s00.91.93.03.95.0距離s/m010305080110解解作直線模型作直線模型: at+s=0n為觀測點(diǎn)數(shù)為觀測點(diǎn)數(shù)定義殘差向量定義殘差向量:T1122(,)nnVats atsats22( )I aV21()niiiats21122nniiiiiatt s12()niiiidIats tda所以所以:2 53.632 1078dIada 令令:2 5

3、3.632 10780dIada 20.1007a 所求運(yùn)動(dòng)方程為所求運(yùn)動(dòng)方程為:20.10070ts二二 數(shù)值積分?jǐn)?shù)值積分?jǐn)?shù)數(shù)值值積積分分基本概念基本概念Gauss求積公式求積公式代數(shù)精度代數(shù)精度插值型求積公式插值型求積公式收斂及穩(wěn)定性收斂及穩(wěn)定性數(shù)值求積思想數(shù)值求積思想N-C公式公式Romberg求積公式及外推加速求積公式及外推加速梯形公式梯形公式辛普森公式辛普森公式例例2試確定常數(shù)試確定常數(shù)A,B,C及及,使求積公式使求積公式:解解22( )()(0)( )f x dxAfBfCf代數(shù)精確度盡可能高，并確定上述公式的代數(shù)精代數(shù)精確度盡可能高，并確定上述公式的代數(shù)精確度。是否為高斯型求積公

4、式確度。是否為高斯型求積公式. 1xf令令:224dxABC xxf220 xdxAC 2xxf22222163x dxAC 3f xx233320 x dxAC 整理得整理得:AC24AB283A 4xxf24442645x dxAC4325A283235125 109A169B 109C 5f xx255520 x dxAC 6f xx22666221288122735x dxAC所以代數(shù)精確度為所以代數(shù)精確度為5次次.因?yàn)榇鷶?shù)精確度為因?yàn)榇鷶?shù)精確度為23=5次次,是高斯型求積公式是高斯型求積公式.標(biāo)準(zhǔn)標(biāo)準(zhǔn)Simpson公式公式:11141( )( )d( )2( 1)(0)( 1)666

5、I ff ttS ffff( )( )dbaI ff xx22abbaxt141( )()( )()( )6626baS fbaf aff b)2 , 1 , 0(,2njjhaxnabhj22 jx12 jxjx2njjjjxfxfxfhfI121222)()(4)(3)(njjjjnxfxfxfhfS121222)()(4)(3)()()(2)(4)(3)(112112bfxfxfafhdxxfnjjnjjba復(fù)化復(fù)化 Simpson 公式公式 將區(qū)間將區(qū)間0,10,1劃分為劃分為8 8等分等分, ,應(yīng)用應(yīng)用復(fù)化梯形法復(fù)化梯形法求得求得 x f (x)0 11/8 0.99739782/8

6、 0.98961583/8 0.97672674/8 0.95885105/8 0.93615566/8 0.90885167/8 0.87719251 0.8414709 718)()(2)(2kkbfxfafhT71) 1 (82)0(281kfkff=0.9456909 例例1試用數(shù)據(jù)表計(jì)算積分試用數(shù)據(jù)表計(jì)算積分xxxfsin)(10sin)(dxxxfI對(duì)于函數(shù)對(duì)于函數(shù)解解應(yīng)用應(yīng)用復(fù)化復(fù)化Simpson法法計(jì)算計(jì)算,得得比較上面兩個(gè)結(jié)果比較上面兩個(gè)結(jié)果T8和和S4,它們都需要提供它們都需要提供9個(gè)點(diǎn)個(gè)點(diǎn)上的函數(shù)值工作量基本相同上的函數(shù)值工作量基本相同,然而精度卻差別很然而精度卻差別很大

7、大.同積分的同積分的準(zhǔn)確值準(zhǔn)確值I(f)=0.9460831比較比較,復(fù)化梯形法復(fù)化梯形法的結(jié)果的結(jié)果T8=0.9456909只有只有兩位有效數(shù)字兩位有效數(shù)字, 而復(fù)化而復(fù)化Simpson法的結(jié)果法的結(jié)果S4=0.9460832卻有卻有六位有效數(shù)字六位有效數(shù)字.41312124)()(2)(4)(3jjjjbfxfxfafhS4131) 1 (8228124)0(381kkfkfkff=0.9456909 三三 線性方程組線性方程組直接法直接法Gauss消去法消去法矩陣三角分解法矩陣三角分解法向量和矩陣范數(shù)向量和矩陣范數(shù)追趕法追趕法矩陣條件數(shù)矩陣條件數(shù)三三 線性方程組線性方程組迭代法迭代法基本

8、概念基本概念雅可比迭代雅可比迭代迭代收斂速度迭代收斂速度高斯高斯-塞德爾迭代塞德爾迭代迭代格式迭代格式收斂條件收斂條件SOR迭代迭代常用的算子范數(shù)常用的算子范數(shù)：njijamaxAni1|1（行范數(shù)）（行范數(shù)） niijamaxAnj11|1（列范數(shù)）（列范數(shù)） )(|2AAATmax（譜范數(shù)（譜范數(shù)(spectral norm)） 定義定義7 設(shè)設(shè)A Rn n的特征值為的特征值為i: (i=1,n) iimaxA稱為稱為A的譜半徑的譜半徑.特殊地：特殊地： 00(1,2, )iiiAmaxinHamilton-Cayley定理定理 設(shè)設(shè) A 是一個(gè)是一個(gè)n階方陣，特征多項(xiàng)式為階方陣，特征多項(xiàng)

9、式為 fIA則則（的的n次多項(xiàng)式）次多項(xiàng)式） fA0 當(dāng)當(dāng)k 時(shí)，時(shí)，Bk 0 ( B ) 1 設(shè)線性方程組設(shè)線性方程組x=Bx+g有惟一解，那么逐次逼有惟一解，那么逐次逼近法對(duì)任意初始向量近法對(duì)任意初始向量x收斂的充分必要條件是收斂的充分必要條件是迭代矩陣迭代矩陣B的譜半徑的譜半徑 ( B ) 1*1*1*10()().kkkkkxBxgxBxgxxB xxBxx*11lim()0lim0( )1.kkkkxxBB因此因此一、逐次逼近法收斂的條件一、逐次逼近法收斂的條件定理定理2定理定理3證明證明例例3解解設(shè)線性方程組設(shè)線性方程組 的系數(shù)矩陣為的系數(shù)矩陣為:Axb(1)寫出寫出Jacobi

10、迭代法的迭代格式迭代法的迭代格式 (2)確定確定a的取值范圍，使方程組對(duì)的取值范圍，使方程組對(duì)應(yīng)的應(yīng)的Gauss-Seidel迭代收斂。迭代收斂。 (1) 線性方程組線性方程組Jacobi 迭代迭代211 1 211aa12311232123322xaxxbxxxbxaxxb(2) 線性方程組線性方程組Gauss-Seidel迭代矩陣迭代矩陣: 31( )( )1121( )21321( )312312222kkkkkkkkkbaxxxxxxbxxaxb 211 1 211aa2 0 0011 1 00 0 2110 0 0aa12 0 0011 1 00 0 2110 0 0G SaBa G

11、 SIB12 0 0011 1 00 0 2110 0 0aa 20110 0 220 0 0aa 21122aa 令令0G SIB得得1021232a21a 1122a四四 非線性方程求根非線性方程求根求根法求根法二分法二分法不動(dòng)點(diǎn)迭代法及收斂性理論不動(dòng)點(diǎn)迭代法及收斂性理論牛頓迭代法牛頓迭代法插值型迭代插值型迭代弦截法弦截法拋物線法拋物線法f (x) = 0 x = g (x)等價(jià)變換等價(jià)變換f (x) 的的根根g (x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)2 單個(gè)方程的迭代法單個(gè)方程的迭代法f(x)=0化為等價(jià)方程化為等價(jià)方程x=g(x)的方式是不唯一的的方式是不唯一的,有的收有的收斂斂,有的發(fā)散有的發(fā)散

12、For example：2x3-x-1=0一、不動(dòng)點(diǎn)迭代一、不動(dòng)點(diǎn)迭代由此可見，這種迭代格式是發(fā)散的由此可見，這種迭代格式是發(fā)散的則迭代格式為則迭代格式為1231kkxx 如果將原方程化為等價(jià)方程如果將原方程化為等價(jià)方程123xx取初值取初值00 x112301xx312312xx5512323xx 如果將原方程化為等價(jià)方程如果將原方程化為等價(jià)方程321xx仍取初值仍取初值00 x7937. 021213301xxx3 = 0.9940 x4 = 0.9990 x5 = 0.9998x6 = 1.0000 x7 = 1.0000已經(jīng)收斂已經(jīng)收斂,故原方程的解為故原方程的解為 x = 1.000

13、0 同樣的方程同樣的方程不同的迭代格式不同的迭代格式 有不同的結(jié)果有不同的結(jié)果什么形式的什么形式的迭代法能夠迭代法能夠收斂呢收斂呢? ?9644. 027937. 1213312xx依此類推依此類推,得得局部收斂性定理局部收斂性定理 設(shè)設(shè)x*為為g的不動(dòng)點(diǎn)的不動(dòng)點(diǎn), g(x)與與g(x)在包含在包含x*的某的某鄰域鄰域U(x*) (即開區(qū)間即開區(qū)間)內(nèi)連續(xù)內(nèi)連續(xù), 且且|g(x*)|0,當(dāng)當(dāng)x0 x*- , x*+ 時(shí)時(shí), 迭代法產(chǎn)生的序列迭代法產(chǎn)生的序列xk x*- , x*+ 且收斂于且收斂于x*.定理定理2用一般迭代法求用一般迭代法求x3-x-1=0的正實(shí)根的正實(shí)根x*容易得到容易得到:

14、 g(x)在包含在包含x*的某鄰域的某鄰域U(x*) 內(nèi)連續(xù)，內(nèi)連續(xù)，且且|g(x*)|1將方程變形成等價(jià)形式：將方程變形成等價(jià)形式：31xx則迭代函數(shù)為則迭代函數(shù)為:31)(xxg32) 1(31)(xxg因此迭代格式因此迭代格式 在在x*附近收斂附近收斂311kkxx例例4解解用一般迭代法求方程用一般迭代法求方程x-lnx2在區(qū)間在區(qū)間(2, )內(nèi)的根，內(nèi)的根，要求要求|xk-xk-1|/|xk|=10-8令令f(x)=x-lnx-2f(2)0,故方程在故方程在(2,4)內(nèi)至少有一個(gè)根內(nèi)至少有一個(gè)根又又011)(xxfx (2, )因此因此f(x)=0在在(2, )內(nèi)僅有一個(gè)根內(nèi)僅有一個(gè)根

15、x*將方程化為等價(jià)方程：將方程化為等價(jià)方程：x2lnxxxgln2)(5 . 0|1| )(|xxgx (2, 4)例例5解解因此，因此， x0 (2, ), xk+12lnxk產(chǎn)生的序列產(chǎn)生的序列 xk 收斂于收斂于x*取初值取初值x x0 03.0,3.0,計(jì)算結(jié)果如下：計(jì)算結(jié)果如下： k xi 0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.1446487815 3.1457022096 3.1460371437 3.1461436118 3.1461774529 33.1461916281

16、1 3333.146193204另一種迭代格式另一種迭代格式1)1 (1kkkkxlnxxx 0 3.000000000 1 3.1479184332 3.1461934413 3.146193221五五 常微分方程數(shù)值解常微分方程數(shù)值解數(shù)值解法數(shù)值解法單步法單步法線性多步法線性多步法方程組與高階方程方程組與高階方程重要概念重要概念重要構(gòu)造方法重要構(gòu)造方法局部截?cái)嗾`差局部截?cái)嗾`差方法精度方法精度差分構(gòu)造差分構(gòu)造泰勒展式構(gòu)造泰勒展式構(gòu)造積分構(gòu)造積分構(gòu)造例例5解解給定求解常微分方程初值問題給定求解常微分方程初值問題 的線

17、性多步公式的線性多步公式 00( , )()yf x yy xy 試確定系數(shù)試確定系數(shù) 并推導(dǎo)其局部截?cái)嗾`差主項(xiàng)。并推導(dǎo)其局部截?cái)嗾`差主項(xiàng)。 使它具有盡可能高的精度，使它具有盡可能高的精度，1()()nny xy xh111111()()nnnnnnyyyhfff11, 234(4)5()()()()()()2624nnnnnhhhy xhy xy xyxyxO h1()()nny xy xh111(, ()()()nnnnf xy xy xy xh111(, ()()()nnnnf xy xy xy xh234(4)5()()()()()()2624nnnnnhhhy xhy xyxyxyx

18、O h23(4)4()()()()()26nnnnhhy xhyxyxyxO h23(4)4()()()()()26nnnnhhy xhyxyxyxO h線性多步公式局部截?cái)嗾`差線性多步公式局部截?cái)嗾`差1nR x11()( ()()nnny xy xy x11()( ()()nnny xy xy x111111(, ()(, ()(, ()nnnnnnhf xy xf xy xf xy x1111()()()nnnhy xy xy x()ny x()nhy x234(4)5()()()()()()2624nnnnnhhhy xhy xyxyxyxO h234(4)5 ()()()()()()2

19、624nnnnnhhhy xhy xy xyxyxO h23(4)41()()()()()26nnnnhhhy xhyxyxyxO h23(4)41()()()()()26nnnnhhhy xhyxyxyxO h(1 2 ) ()ny x11(11)()nhy x 2111()()22nh yx3111()()6622nh yx4(4)111()()242466nh yx5()O h此時(shí)此時(shí):令令:111112001022得得:12138118111066221111024246648 所以當(dāng)所以當(dāng):121381181111131()()288nnnnnnyyyhfff為三階多步公式為三階多步

20、公式.局部截?cái)嗾`差主項(xiàng)為局部截?cái)嗾`差主項(xiàng)為:4(4)1()48nh yx六六 特征值特征向量特征值特征向量特特征征值值及及特特征征向向量量解解法法迭代法迭代法變換法變換法重要概念重要概念特征值特征向量特征值特征向量QR分解分解變換變換正交相似正交相似反射反射平面旋轉(zhuǎn)平面旋轉(zhuǎn)冪法冪法反冪法反冪法雅可比法雅可比法QR法法(1)QR算法的基本思想算法的基本思想記記 AA1且有且有A1Q1R1.將等號(hào)右邊兩個(gè)矩陣因子的次序交換，得將等號(hào)右邊兩個(gè)矩陣因子的次序交換，得 A2R1Q1且且11112QAQA即即12 AA不難證明不難證明:kkkkkkQQAQQQAQA1111111即即11AAAkk矩陣序列

21、矩陣序列Ak有相同的特征值有相同的特征值.因?yàn)樯弦驗(yàn)樯螲essenberg矩陣次對(duì)角線以下的元素全為矩陣次對(duì)角線以下的元素全為0, 因此因此, 只要證明只要證明, 當(dāng)當(dāng)k時(shí)時(shí), 由迭由迭 代格式產(chǎn)生的矩代格式產(chǎn)生的矩陣陣Ak的次對(duì)角元趨向于零就可以了的次對(duì)角元趨向于零就可以了. 記記kkQQQ1kkRRR1容易得到容易得到 是是Ak的一個(gè)的一個(gè)QR分解分解kkkRQA如果如果A是一個(gè)滿秩的上是一個(gè)滿秩的上Hessenberg矩陣矩陣, 可以證明可以證明, 經(jīng)過一個(gè)經(jīng)過一個(gè)QR迭代步得到的迭代步得到的A2Q-11A1Q1仍然是上仍然是上Hessenberg矩陣矩陣. 例例4設(shè)矩陣設(shè)矩陣 4 1 01 2 10 1 2A