1、計算方法復習計算方法復習典型概念例題典型概念例題Final Exam Review零零 緒論緒論誤誤差差及及算算法法誤差誤差算法算法分類分類度量度量傳播傳播舍入舍入截斷截斷絕對絕對相對相對有效數字有效數字一元函數一元函數n元函數元函數一一 插值與逼近插值與逼近插值法插值法工具工具多項式插值多項式插值分段多項式分段多項式插值插值差商差商差分差分插值基函數插值基函數存在唯一性存在唯一性誤差估計誤差估計插值公式插值公式Hermite插值插值分段線性分段線性分段三次分段三次Hermite插值插值三次樣條插值三次樣條插值函數逼近函數逼近預備知識預備知識函數逼近方法函數逼近方法范數范數內積內積正交多項式正

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

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

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

5、6I 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復化復化 Simpson 公式公式 將區間將區間0,10,1劃分為劃分為8 8等分等分, ,應用應用復化梯形法復化梯形法求得求得 x f (x)0 11/8 0.99739782

6、/8 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試用數據表計算積分試用數據表計算積分xxxfsin)(10sin)(dxxxfI對于函數對于函數解解應用應用復化復化Simpson法法計算計算,得得比較上面兩個結果比較上面兩個結果T8和和S4,它們都需要提供它們都需要提供9個點個點上的函數值工作量基本相同上的函數值工作量基本相同,然而精度卻差別很然而精度卻差別

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

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

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

10、i 迭代法的迭代格式迭代法的迭代格式 (2)確定確定a的取值范圍，使方程組對的取值范圍，使方程組對應的應的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

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

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

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

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

15、個根x*將方程化為等價方程：將方程化為等價方程：x2lnxxxgln2)(5 . 0|1| )(|xxgx (2, 4)例例5解解因此，因此， x0 (2, ), xk+12lnxk產生的序列產生的序列 xk 收斂于收斂于x*取初值取初值x x0 03.0,3.0,計算結果如下：計算結果如下： 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.14619162

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

17、的線性多步公式的線性多步公式 00( , )()yf x yy xy 試確定系數試確定系數 并推導其局部截斷誤差主項。并推導其局部截斷誤差主項。 使它具有盡可能高的精度，使它具有盡可能高的精度，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 xy xy

18、xyxO h23(4)4()()()()()26nnnnhhy xhyxyxyxO h23(4)4()()()()()26nnnnhhy xhyxyxyxO h線性多步公式局部截斷誤差線性多步公式局部截斷誤差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 xy xyxyxO h234(4)5 ()()()()(

19、)()2624nnnnnhhhy 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此時此時:令令:111112001022得得:12138118111066221111024246648 所以當所以當:121381181111131()()288nnnnnnyyyhfff為三階多步公式為

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

21、矩陣序列矩陣序列Ak有相同的特征值有相同的特征值.因為上因為上Hessenberg矩陣次對角線以下的元素全為矩陣次對角線以下的元素全為0, 因此因此, 只要證明只要證明, 當當k時時, 由迭由迭 代格式產生的矩代格式產生的矩陣陣Ak的次對角元趨向于零就可以了的次對角元趨向于零就可以了. 記記kkQQQ1kkRRR1容易得到容易得到 是是Ak的一個的一個QR分解分解kkkRQA如果如果A是一個滿秩的上是一個滿秩的上Hessenberg矩陣矩陣, 可以證明可以證明, 經過一個經過一個QR迭代步得到的迭代步得到的A2Q-11A1Q1仍然是上仍然是上Hessenberg矩陣矩陣. 例例4設矩陣設矩陣 4 1 01 2 10 1 2A