數值代數課件

1、河南師大數學與信息科學學院河南師大數學與信息科學學院復量大學區(qū)將爾雄等編復量大學區(qū)將爾雄等編主講：焦爭鳴，申培萍主講：焦爭鳴，申培萍第一章第一章 緒論緒論第二章求方程根的近似方法第二章求方程根的近似方法第三章線性代的方程組解法第三章線性代的方程組解法第四章矩陣特征值和特征向量計算第四章矩陣特征值和特征向量計算第五章插值法第五章插值法數值代數數值代數1.11.1計算方法的任務與特點計算方法的任務與特點第一章第一章:緒論緒論實際問題數學問題提供計算方法實際問題數學問題提供計算方法程序設計上機計算結果分析程序設計上機計算結果分析數值代數數值代數 基本的數學問題基本的數學問題: :1.大型線性代數方程

2、組大型線性代數方程組Ax=b求解求解; 2.矩陣矩陣A的特征值和特征向量計算的特征值和特征向量計算;3.非線性方程非線性方程 求解求解(求根求根);4.積分積分 計算計算;5.常微分方程初值問題求解常微分方程初值問題求解;6.其它。其它。0)( xfdxxfba )(求精確解求精確解( (值值) )一般非常困難。例如：一般非常困難。例如： 1. 1. 方程組階數方程組階數n n很大，例如很大，例如n=20,n=20,計算機運算速度計算機運算速度 1 1億次億次/ /秒秒, ,用不好的方法用不好的方法, ,大約需算大約需算3030多萬年多萬年; ; 好方法不到一分鐘。另外，有計算結果可靠性好方法

3、不到一分鐘。另外，有計算結果可靠性 問題。問題。2. 2. 特征值定義特征值定義)0(xxAx0 xAx 0)( xIA0| IA3. 3. 形式復雜時求根和求積分很困難。形式復雜時求根和求積分很困難。 4.4.線性微分方程易解，線性微分方程易解， 如如 非線性方程難解，如非線性方程難解，如 )(xf12 yyy1)0()0( yy1sin2 yyyey 1)0()0( yy 希希 望：望： 求近似解，但方法簡單可行，行之有效求近似解，但方法簡單可行，行之有效 （計算量小，誤差小等）。以計算機為工（計算量小，誤差小等）。以計算機為工 具，易在計算機上實現。具，易在計算機上實現。計算機運算計算機

4、運算: 只能進行加，減，乘，除等算術運只能進行加，減，乘，除等算術運 算和一些邏輯運算。算和一些邏輯運算。計算方法：計算方法： 把求解數學問題轉化為按一定次序只把求解數學問題轉化為按一定次序只 進行加，減，乘，除等基本運算進行加，減，乘，除等基本運算 數值方法。數值方法。1.2 1.2 誤差基礎知識誤差基礎知識, .!5!3sin53 xxxx.!5)! 3(sin53xxxx一一 .誤差來源（分類）誤差來源（分類） 1. 模型誤差。模型誤差。 2. 觀測誤差。觀測誤差。 3. 截斷誤差，如截斷誤差，如 右端是截斷誤差。右端是截斷誤差。4. 4. 舍入誤差。計算機字長有限，一般實數不能精確舍入

5、誤差。計算機字長有限，一般實數不能精確存儲，于是產生舍入誤差。例如：在存儲，于是產生舍入誤差。例如：在1010位十進位十進制數限制下：制數限制下： 舍入誤差很小，本課程將研究它在運算過程中舍入誤差很小，本課程將研究它在運算過程中 是否能有效控制。是否能有效控制。3333333333.031 ）本本應應33333333333. 031( 0000004. 1)000002. 1(2 ）本本應應（122104040000000000. 0000004. 1040000040000. 1000004. 1000002. 1( 二誤差基本概念二誤差基本概念1 1絕對誤差。設絕對誤差。設 準確值，準確值

6、， 近似值。近似值。 稱稱 為為 的絕對誤差。的絕對誤差。 為為 的絕對誤差限。的絕對誤差限。 2 2相對誤差。稱相對誤差。稱 為為 的相對誤差。的相對誤差。 實用中，常用實用中，常用 表示表示 的相對誤差。的相對誤差。 稱稱 為為 的相對誤差限。的相對誤差限。x*x*)(xxxe |)(|*xe*x*xxxxree*)(*)( *x*)(xxerxre *)(*x*x3 3有效數字有效數字設設 若若 (1.1)(1.1)則說則說 具有具有n n位有效數字，分別是位有效數字，分別是 若若 ，則稱，則稱 為有效數。為有效數。)21.0(10*pnmaaaax ), 0(1 panmxx 1021

7、*xnaaa,21 pn *x例例1.11.1 設設 =0.0270=0.0270是某數是某數 經經“四舍五入四舍五入”所得，所得，則則 誤差誤差 不超過不超過 末位的半個單位，即：末位的半個單位，即： 又又 , ,故該不等式又可寫為故該不等式又可寫為 由有效數字定義可知由有效數字定義可知, , 有有3 3位有效數字，分別位有效數字，分別 是是2,72,7，0 0。*x*)(xe*x41021* xx)270. 0(10*1 x311021* xx*xx例例1.2 1.2 = 32.93, = 32.89, = 32.93, = 32.89, 故故 有有3 3位有效數字，分別是位有效數字，分別

8、是3,23,2，8 8。由于由于 中的數字中的數字9 9不是有效數字，故不是有效數字，故 不是有不是有效數。效數。 x1102105. 004. 0* xx321021* xx*x*x*x*x三、有效數位與誤差的關系三、有效數位與誤差的關系1. 1. 有效數位有效數位n n越多，則絕對誤差越多，則絕對誤差 越小越小 ( (由定義由定義1.1)1.1)2.2. 定理定理1.1 1.1 若近似數若近似數 具有具有n n位有效數字，則位有效數字，則 (1.2) (1.2) 反之，反之， 若若 則則 至少有至少有n n位有效數字。位有效數字。*)(xenraxe 1*)(10211 nraxe 11*

9、)(10211*x*x 兩邊除以兩邊除以 得得 (1.3)(1.3)和（和（1.41.4）給出了由自變量的誤差引起的函）給出了由自變量的誤差引起的函 數值的誤差的近似式（誤差傳播）。數值的誤差的近似式（誤差傳播）。四、數值運算的誤差估計四、數值運算的誤差估計 1. 1. 一元函數情形一元函數情形 設設 則則 ，由，由TaylorTaylor展開公式展開公式 ),(xfy *)*)(*)()(*)(xxxfxfxfyyye *)(*)(*)(xexfye *)(*)(*)( *)(xrxxfxfyree )(*xfy (1.4)(1.4)*)(*)(*)( *)(*)(*xeeerxfxfxyy

10、yr )(*xfy （1.3）2. 2. 多元函數情形多元函數情形 設設 ，),(21nxxxfy *),*,*,(*21nxxxfy *)(*),*,*,(*)(211inniixexxxfye *)(*),*,*,(*),*,*,(*)(21211irinninirxexxxxfxxxfye 2121),(xxxxf 2121,xxxx)(21)21(*maxirirxexxe 21, xx)2()1()21(*xexexxerrr )(*2)1()2()1()*2*1(*xexexexexxerrrrr 則，則，由多元函數的由多元函數的TaylorTaylor展開公式類似可得展開公式類似

11、可得 （1.51.5） （1.61.6）在（在（1.61.6）式中，分別取）式中，分別取, ,可得可得同號) )（1.71.7） （1.81.8） （1.91.9）(,例例1.31.3：測得某桌面的長測得某桌面的長a a的近似值的近似值a a* *=120cm,=120cm,寬寬b b的的 近似值近似值b b* *=60cm=60cm。若已知。若已知|e(a|e(a* *)|0.2cm, )|0.2cm, |e(b |e(b* *)|0.1cm)|0.1cm。 試求近似面積試求近似面積s s* *=a=a* *b b* * 的絕對誤差限與相對誤差限。的絕對誤差限與相對誤差限。2241 . 01

12、202 . 060|*)(|*|*)(|*|*)(|*)(*)(*)(*)*,(*)(*)*,(*)(cmbeaaebsebeaaebbebbasaeabasse 解解: : 面積面積s=ab,s=ab,在公式（在公式（1.51.5）中）中, ,將將 換為換為 s=ab, s=ab, 則則),(21xxfy 相對誤差限為相對誤差限為%33. 06012024|*)(|*)(| sseser 1.3 1.3 選用算法應遵循的原則選用算法應遵循的原則1.1.盡量簡化計算步驟，減少乘除運算的次數盡量簡化計算步驟，減少乘除運算的次數. . 例如，計算多項式例如，計算多項式 通常運算的乘法次數為通常運算

13、的乘法次數為 若采用遞推算法若采用遞推算法, , 則乘法次數僅為則乘法次數僅為n. n. 又如又如 nnnxaxaaxp .)(102)1(.21 nnn01)()0121( uxp,n-n-kaxuuaunkkknn 100111)111() 1(11000110001 nnnnnn2.2.防止大數防止大數“吃掉吃掉”小數小數 當當|a|b|a|b|時，盡量避免時，盡量避免a+b a+b 。例如，假設計算機。例如，假設計算機 只能存放只能存放1010位尾數的十進制數，則位尾數的十進制數，則3.3.盡量避免相近數相減盡量避免相近數相減 例如，當例如，當x x很大時，應很大時，應 8998104

14、0000000000. 0101 . 01004. 010 111 xxxx)1(1111 xxxx， 2cos1sinsincos1xtgxxxx或或 當當x x接近于接近于0 0時，應時，應 4. 4.避免絕對值很小的數做分母避免絕對值很小的數做分母 當當|b|a|b|a|時，應盡量避免時，應盡量避免 。5. 5. 選用數值穩(wěn)定性好的算法，以控制舍入誤差高速選用數值穩(wěn)定性好的算法，以控制舍入誤差高速 增長增長 例如例如 若若 （誤差（誤差 ）則計算）則計算 時誤差擴大了時誤差擴大了 倍倍, ,而而ba nnnIndxxxI51510 1823. 056ln0 I41021 100I1005

15、)1(511nnInI （n=1,2,n=1,2,） 是穩(wěn)定的。是穩(wěn)定的?；疽螅夯疽螅?.1.熟悉計算方法在解決實際問題中所處的地位，熟熟悉計算方法在解決實際問題中所處的地位，熟悉計算方法是以計算機為工具求近似解的數值方悉計算方法是以計算機為工具求近似解的數值方法；法；2.2.熟悉絕對誤差（限），相對誤差（限）及有效數熟悉絕對誤差（限），相對誤差（限）及有效數字概念；字概念；3.3.熟悉公式（熟悉公式（1.21.2）-（1.91.9）；）；4.4.熟悉選用算法應遵循的原則；熟悉選用算法應遵循的原則；作業(yè)：作業(yè)： 作業(yè)集（作業(yè)集（A A）第一章）第一章1 1，2 2，3 3，4 4，5

16、5，6 6，7 7，8 8數值代數數值代數 f(x)=0 f(x)=0根或根或f(x)f(x)零點，當零點，當f(x)f(x)復雜時，很難求復雜時，很難求 （找近似有效簡單方法）。（找近似有效簡單方法）。 第二章第二章 求方程根的近似方法求方程根的近似方法 2.1 2.1 區(qū)間二分法區(qū)間二分法理理 論論 : f(x) Ca,b,: f(x) Ca,b,單調，單調， f(a)f(b)0 f(a)f(b)0 f(x)=0 f(x)=0在在(a,b)(a,b)有惟一根。有惟一根。根分離：畫草圖，試算根分離：畫草圖，試算. . 多項式方程根的模多項式方程根的模 的上下界。的上下界。 例例2.1 2.1

17、 用二分法求用二分法求 在在(1,2)(1,2)內的根，要求絕對誤差不超過內的根，要求絕對誤差不超過 解解： f(1)=-50 -(1,2)+ f(1.25)0 (1.25,1.375) f(1.313)0 (1.313,1.375) f(1.344)0 (1.344,1.375) f(1.360)0 (1.360,1.368) 010423 xx21021 f(1.5)0 (1,1.5) nx 1.51 x364. 1368. 1360. 1344. 1313. 1375. 125. 18765432 xxxxxxx 364.18* xx若若取取近近似似根根2*1021004. 0)360.

18、 1368. 1(21| xx81,10212|21* nabxxn解解出出對對分分次次數數先先驗驗估估計計：優(yōu)點：條件簡單優(yōu)點：條件簡單. .缺點：收斂慢缺點：收斂慢. . 不易求偶數重根不易求偶數重根. . 如圖如圖，則則 （事后估計事后估計）xy 2.2 2.2 迭代法迭代法連連續(xù)續(xù)），改改寫寫建建立立 fxxxf()( 0)(:. 1 01 ,.)2 , 1 , 0( )(xnxxnn取取定定初初值值 ，則，則若收斂，設極限為若收斂，設極限為則產生數列則產生數列 .,., 121 nnxxxx 一一. 迭代法的建立與收斂性迭代法的建立與收斂性)( )(lim1lim nnnnxx可可作

19、作為為近近似似值值充充分分大大時時之之根根，故故當當是是即即1,0)( nxnxf )2lg(2100210)( xxxxxxx或或形形式式不不唯唯一一，如如：問問題題： 收收斂斂性性不不同同。計計算算結結果果見見表表取取取取4 . 2 3 )2lg(3 2100101 xxxxxnnxnn2.2.收斂定理（定理收斂定理（定理2.22.2）,)(bax 在在設設 為為常常數數）LLxbax(1| )( |,)2( 01101|3 (,2 ,)(1xxLLxxxbaxbaxxnnnn ）（）收收斂斂到到）（；有有唯唯一一根根在在）方方程程則則：（;)(1bxabxa 時時，）當當（. )(,0)

20、( 1)( ,0)( , ,0)()(,0)()( ),()(1) 唯唯一一故故根根遞遞增增，又又使使故故至至少少有有則則設設證證： xgxxggbabbbgaaagxxxg (2) (2) 1nx，故收斂。，故收斂。 )(00112時時當當 nxLxLnn 中中值值定定理理 nnnnnxLxxx)( )()(1 ( )1）式式（由由（）（）式式）由由（）（）中中值值定定理理01121111111111 2 311)1( 1 ()()( 2)( )()(xxLLxxLLxxLxxLxLxxxxxxxxxLxxxxxxnnnnnnnnnnnnnnnnnnnnnnnn (3)(3) 注：注：L L

21、越小，收斂越快。越小，收斂越快。3 3編程停機判斷編程停機判斷)(1nnxx （取定初值（取定初值0 x）計算，當）計算，當 nnxx1時，由（）時，由（） 3 3 式知式知 L11 nx 比較小，此時停機，比較小，此時停機，1n x 二、迭代加速公式（略）二、迭代加速公式（略） 由由 2.32.3Newton Newton 迭代法迭代法一一 Newton Newton 迭代法迭代法 1.1.迭代公式建立迭代公式建立)(xf 在在nx 點點TaylorTaylor展開展開 )( )( )()()(! 2)()( )( )()(2nnnnnnnnxxxfxfxfxxxfxxxfxfxf Tayl

22、orTaylor展開線性化（重要思想）展開線性化（重要思想）0)( xf近似于近似于0)()( )( nnnxxxfxf解出解出 記為記為1nx，則，則) 1 . 2(), 2 , 1 , 0( )( )(1 nxfxfxxnnnn1 nx 將將x2.Newton2.Newton迭代法的幾何意義迭代法的幾何意義 過過) )(,(nnxfx 切線切線 )()( )(nnnxxxfxfy 與與 0 y求交點，解出求交點，解出1 nxx , 則則)( )(1nnnnxfxfxx 3. Newton3. Newton迭代法收斂定理（定理迭代法收斂定理（定理 2.62.6）0)( xf在在 ba,有根有

23、根，且，且)(xf在在 ba,（1 1）)(),( xfxf連續(xù)，且分別不變號；連續(xù)，且分別不變號； bax,0 , ,使使則則 Newton Newton 迭代法（迭代法（2.12.1）產生的數列）產生的數列 1 nx的收斂到根的收斂到根。0)(, 0)(, 0)( 0 xfxfxf 為例證明（其它情況類似）為例證明（其它情況類似） （2 2） 取初值取初值設設0)()(00 xfxf 證：證：以以將將在在)( f nx處處TaylorTaylor展開展開12122)()( 2)()()( 2)()( )(0)(! 2)()( )()( nnnnnnnnnnnnnnnnxxxffxxxffx

24、fxfxxfxxfxff 說明數列說明數列1nx 有下界有下界 又又nnnnnxxfxfxx )( )(1 故故 1 nx單調遞減。單調遞減。 1 nx收斂。設收斂。設xxnn 1lim則由（則由（2.12.1），）， xxfxfxfxx, 0)(,)( )(，例例2.22.2 解：設解：設, 0,2 cxcx則則取取cxxf 2)(，則由（，則由（2.12.1）)(21221nnnnnnxcxxcxxx )0( cc用用 Newton Newton 迭代法求迭代法求基本要求基本要求 熟悉區(qū)間分法；熟悉區(qū)間分法； 熟悉迭代法的建立，會使用收斂定理；熟悉迭代法的建立，會使用收斂定理； 熟悉熟悉N

25、ewtonNewton迭代法及其幾何意義和收斂條件。迭代法及其幾何意義和收斂條件。作業(yè)：作業(yè)： 作業(yè)集（作業(yè)集（B B）第二章）第二章1 1、2 2、3 3、4 4、6 6數值代數數值代數二二. .迭代法的收斂階迭代法的收斂階( (收斂速度收斂速度) ) 1. 1.定義定義: :設設.lim nnx 若有實數若有實數p0,p0,使使)0( |lim1 ccxxpnnn 則稱則稱xn p p階收斂階收斂, ,相應的迭代法稱為相應的迭代法稱為p p階方法階方法. . 特別特別, , p=1p=1時叫線性收斂時叫線性收斂, ,p=2p=2時叫平方收斂時叫平方收斂. . p p越大越好越大越好(why

26、?)(why?)2.2.定理定理2.72.7線線性性收收斂斂；則則（且且）（若若。的的根根收收斂斂到到設設)(, 0)(), 2 , 1 , 0()( (1)111xxxxnnnncxxxn 至至少少二二階階收收斂斂。（即即的的單單根根迭迭代代法法求求則則)0)( 0)( fxfNewton 的的條條件件成成立立）設設定定理理（6 .22 所以，此時所以，此時NewtonNewton法至少二階收斂法至少二階收斂. . 線性收斂線性收斂）證：（證：（)(0)( )( )()(11111nnnnnnnnnxxaxxxxx (2)(2)由由2.62.6的證明有：的證明有：故故,)()( 2)(21n

27、nnnxxffx )( 2)()( 2)(21 ffxffxxnnnn 0)()(00)()(0 ff若若大大于于二二階階收收斂斂若若二二階階收收斂斂3. Newton3. Newton法改進：法改進：則則重重根根有有設設)2(0)( mmxf2.4 2.4 弦截法弦截法(略略) ) )( )(1xxxxnnnnffm 。收斂時至少是二階收斂收斂時至少是二階收斂第三章第三章 線性代數方程組解法線性代數方程組解法解線性方程組解線性方程組 bAx x解解向向量量列列迭迭代代法法：格格式式，無無窮窮序序誤誤差差，有有限限步步，精精確確解解直直接接法法：理理論論，無無舍舍入入一、一、 GaussGau

28、ss消去法消去法設設 有有1,22111,2211)1 .3(1,222221211,11212111 nnnnnnnnininiinnnnnnaxaxaxaaxaxaxaaxaxaxaaxaxaxa行行。行行，加加到到第第第第把把化化為為零零；將將用用 1),2(111111iaaniaaii 以以后后各各步步類類似似?；蚧蝾}題：問問?001111 aa線性代數：方法不好時工作量非常大，線性代數：方法不好時工作量非常大， 工作量小的方法是工作量小的方法是 Gauss Gauss 消去法。消去法。消消 元：元： 3.13.1直接法直接法二二 列主元素消去法列主元素消去法-計算結果可靠計算結果可

29、靠jjrjjrjjiniracaacaraar1113211max)1(1111111 行行：，對對調調使使找找行行號號)1n,1,2,j( ）；（個個元元素素成成為為行行第第第第行行加加到到第第行行第第為為消消消消元元：用用1,2 , 1,3 ,2,1:01111111111 njniaaaaajiiaaaaijijijii到此原方程組化為到此原方程組化為1,22 1,22 1,222221, 11212111 nnnnnnninininnnnnnaxaxaaxaxaaxaxaaxaxaxa 到此原方程組化為到此原方程組化為.2max)2(222222行行，對對調調，使使找找raarinir

30、 ），；，（行行，則則第第行行第第消消為為把把消消元元：用用1,3 , 2,4 , 3 2:), 4 , 3( 02222222222 njniaaaaaiaaniaaijijijii1,33 1,33333 1,223232221,11313212111 nnnnnnnnnnnnnnnaxaxaaxaxaaxaxaxaaxaxaxaxa（3.3) 3.3) 是回代過程。是回代過程。( (上三角方程組上三角方程組) ) （3.2)3.2)1, 1,222221, 11212111 nnnnnnnnnnnaxaaxaxaaxaxaxa(n) (n) 回代求解公式回代求解公式 (n-1) (n-1

31、) 原方程組化為原方程組化為以上為消元過程。以上為消元過程。 （3.3)3.3)1, )1,.,2, 1(1 11,1, nnnnnaxannkxaaaxaaxnkjjkjnkkkknnnnn三、三、 Gauss Gauss 全主元消去法：全主元消去法： 優(yōu)點優(yōu)點-計算結果更可靠；計算結果更可靠； 缺點缺點-挑主元花機時更多，挑主元花機時更多， 次序有變動，程序復雜。次序有變動，程序復雜。說明：說明： (1)(1)也可采用無回代的列主元消去法也可采用無回代的列主元消去法( (叫叫Gauss-Gauss- -Jordan -Jordan消去法消去法) )，但比有回代的列主元消，但比有回代的列主元

32、消 去法的乘除運算次數多。去法的乘除運算次數多。 (2)(2)有回代的列主元消去法所進行的乘除運算有回代的列主元消去法所進行的乘除運算 次數為次數為 ，量很小。，量很小。nnn313123 nxx,1 四、應用四、應用 （1）求行列式）求行列式 （2）求逆矩陣）求逆矩陣 ( (以上過程都應選主元以上過程都應選主元) ) nnmnnnmnnnnbbbbbaaaa.) 1(.) 1(.111111111 )(.)(1 AEEA uALLLLgubALLLLgubAKKkk 121121)|()|()1|()|()|(uLLLLAKK1121)( 記記11)( LLLK，則，則LUA 上上三三角角）

33、（下下三三角角 （三角因子分解）（三角因子分解） Gauss Gauss消元，初等行變換，化原方程組為上三角型。消元，初等行變換，化原方程組為上三角型。五矩陣三角分解法五矩陣三角分解法定義定義3.13.1 LUA 叫叫A的三角（因子）分解，其中的三角（因子）分解，其中 是是L是上三角。是上三角。U下三角下三角, , L為單位下三角陣（對角元全為為單位下三角陣（對角元全為1 1），），U為上三角陣，則稱為上三角陣，則稱LUA 為為DoolittleDoolittle分解分解; ;L若若 是下三角，是下三角，U 是單位上三角，則稱是單位上三角，則稱LUA 定理定理3.1 n3.1 n階陣階陣)2(

34、 nA 有唯一有唯一DoolittleDoolittle分解分解(Crout(Crout）A 的前的前n-1n-1個順序主子式不為個順序主子式不為0.0.（證略）（證略）三角分解不唯一三角分解不唯一, ,為此引入為此引入定義定義3.2 3.2 若若 為為CroutCrout分解。分解。 為什么要討論三角分解？若在消元法進行前能實為什么要討論三角分解？若在消元法進行前能實 現三角分解現三角分解LUA ， 則則 bxLUbAx)(上三角方程組）上三角方程組）下三角方程組）下三角方程組）( ( yUxbLy 容易回代求解容易回代求解回代求解很容易，如回代求解很容易，如 2,1)1,-n(k n),2

35、,3,(k 1 1111111212121222111 kknkjjkjkknnnnkjjkjkkkknnnnnnuxubxuyxylblylbybbbyyyllllll練練習習：基本要求：基本要求： 1. 1. 熟悉收斂階的定義；熟悉收斂階的定義； 2. 2. 熟悉熟悉NewtonNewton法及改進方法的收斂階；法及改進方法的收斂階； 3. 3. 熟悉列主元消去法解線性方程組的計算熟悉列主元消去法解線性方程組的計算 過程；過程； 4. 4. 熟悉矩陣三角分解中熟悉矩陣三角分解中DoolittleDoolittle分解和分解和 CroutCrout分解定義；分解定義； 5. 5. 熟悉利用三

36、角分解來求解線性方程組的熟悉利用三角分解來求解線性方程組的 思路；思路；作業(yè)：作業(yè)：作業(yè)集（作業(yè)集（A A） 第三章第三章 1 1，2 2 nnnnnnaaaaaaaaa212222111211數值代數數值代數1 1直接三角分解法（以直接三角分解法（以DoolittleDoolittle分解為例）設分解為例）設1112121nnlllnnnnuuuuuu22211211 由矩陣乘法由矩陣乘法221212222221211212222121111111111111/ )( n),3,4, 2i22) 1 n),2, j22)1 )2(), 3 , 2( n),2,3,1L12) n),1,2,(

37、j u 1. n),1,2, 1)1 )1(uulalaululiuLLulauauuljuLuniualauliuiLauajjuLuiiiiiijjjjjjiiiijjjj （列列的的第第行行的的第第列列：用用的的第第求求（列列的的第第行行的的第第行行：用用的的第第求求列列（的的第第行行的的第第列列：用用的的第第求求（列列的的第第的的第第一一行行行行：用用的的第第求求 (k) 111121,2,1100)0 ,0,(n),1,kk,(j1kmmjkmkjkjkjkjkmmjkmkjjjkjjjkkkkulauauulauuuullljukLku，列列的的第第行行的的第第行行：用用的的第第求

38、求 kkkmmkimikikikkkikkmmkimikkkkkkkikiuulalaululauuulllkuiLkL 111121,100)00(n),1,k(i2，即，即列列的第的第行行的第的第列：用列：用的第的第求求), 3 , 2(), 1( ), 1,( ), 3 , 2( ), 2 , 1( 1111111111nknkiauulalnkkjaulauniualnjauDoolittleikkkkmmkimikikkjkmmjkmkjkjiijj 分解公式分解公式例例3 31 112/ )126(23/ )06(, 111 1661230 3 22 1 251865364 5 4

39、2 1 2231323 xxxxxx所以所以選主元的三角分解法（略）選主元的三角分解法（略）2 2平方根法平方根法定理定理3.23.2 設設A A對稱正定，則有非奇異下三角陣對稱正定，則有非奇異下三角陣L L，使，使TLLA - - 理論基礎理論基礎 ( (證略）證略）分解方法：設分解方法：設jiijnnnnnnnnnnnnnnaallllllllllllaaaaaaaaa 其其中中 2221211121222111212222111211( choleskey( choleskey分解分解) )22121222222212121222222222111111111111111111 n),3

40、,4,(j j2L )2 22L 1) )2( n),2,(j j1L )2 )( )1 )1(2222lllalaallllLlalallLlalaallLalaljjjjjjjTTjjjjjT 列列第第行行第第列列第第行行第第列列第第行行第第取取正正由由矩矩陣陣乘乘法法及及其其改改進進分分解解。缺缺點點：開開方方運運算算。主主元元。平平方方根根法法穩(wěn)穩(wěn)定定，不不必必先先受受到到控控制制舍舍入入誤誤差差的的放放大大所所以以說說的的最最大大元元的的值值不不會會超超過過程程中中這這說說明明在在分分解解過過故故列列：第第行行、第第、計計算算量量小小優(yōu)優(yōu)點點：）（，可可得得：Tkmkknkkmkkn

41、kkkkmkmkmkkkmjmkmjkkkjmkmkmkkkklalaallakknkjllalllalkLDL,A maxmax21, 11)(21121211112 六、解三對角方程組六、解三對角方程組追趕法追趕法 1111 1, 2 2212111221111222111112112111122211nnnnnnnnnnnniiinnnnnnnnnbacbacbacbniabcabcbffffxxxxbacbacbacb 設設有有分分解解）（，且且按按行行嚴嚴格格對對角角占占優(yōu)優(yōu)：（三三對對角角方方程程組組）給給定定( Crout分解分解 )列得：列得：第第行行第第，）（由矩陣乘法由矩陣

42、乘法1, 1)(1)2(2112221222222222212221111111111 iiiiicbacbacbcb 00 00i i 11111 iiiii ii1 ,1 .,1 .1iiiiiiba , ,ciii 故有故有 ,111111 iiiiiiiiicbacb ), 3 , 2(ni (3.1) fLUxfAx （二二對對角角方方程程組組）二二對對角角方方程程組組） ( yUxfLy )1, 3 , 2( ni解解n)2,3,(i , 1111y iiiiiyffyfLy設設解解得得 yUx 1)1,-n(i ,1 xyxyxiiiinn (3.1) (3.3) (3.1) (

43、3.3) 叫追趕法，工作量小，非常有效。叫追趕法，工作量小，非常有效。(3.2)(3.2)（3.33.3）基本要求基本要求1.1.會矩陣的直接三角分解法的過程（不記公式）；會矩陣的直接三角分解法的過程（不記公式）；2.2.熟悉平方根法的計算過程（不記公式）及其優(yōu)缺熟悉平方根法的計算過程（不記公式）及其優(yōu)缺 點。點。作業(yè)：作業(yè)： 作業(yè)集（作業(yè)集（A A） 第三章第三章 3.3.bAx 一一. .簡單迭代法簡單迭代法 1.1.迭代法建立迭代法建立. . 考慮考慮gBxxbAx ( (矩陣矩陣B B不唯一不唯一) )對應寫出對應寫出 )0()()1()4 . 3( ), 2 , 1 , 0( xkg

44、Bxxkk取取定定初初始始向向量量 3.2 3.2 解線性方程組的迭代法解線性方程組的迭代法數值代數數值代數產生向量序列產生向量序列,)1()()2()1( kkxxxx若收斂若收斂, ,記記xxkk )1(lim則于則于(3.4)(3.4)兩端取極限有：兩端取極限有：, gxBx 上式說明：上式說明： 是解向量是解向量, ,從而當從而當k k充分大時充分大時 )1(kx注意注意: : 迭代陣迭代陣B B不唯一不唯一, ,影響收斂性。影響收斂性。 解向量解向量(1)(1)叫簡單迭代法叫簡單迭代法,B,B叫迭代矩陣。叫迭代矩陣。 2. 2.收斂性收斂性. . 定義定義3.3 3.3 稱稱| )(

45、|max)(1BBini 為矩陣為矩陣B B的譜半徑。的譜半徑。定理定理3.3 3.3 簡單迭代法簡單迭代法（證證略略）（都都收收斂斂對對任任意意初初始始向向量量 1 )0()()1( BxgBxxkk xx都都不不收收斂斂”。時時不不能能說說“對對任任意意）（注注意意)0(1:xB 收收斂斂。則則其其對對任任意意或或若若對對迭迭代代法法)0(11111)()1( 1|max| 1|max|, ),2, 1 ,0( xbBbBkgBxxnjijniniijnjkk 定理定理3.43.4 ),2 , 1( | |,|max |max| )( )4 .3(1|)1()(1k1)(11)()1(1)

46、()1(niBxxxxxxbxxbxxxxbxxgBxxBkikijkjnjnjjkjijninjjkjijikinjjkjijiki 則則記記相相減減有有與與為為例例。將將證證：以以 收斂列解收斂列解 (i=1,2,n)(i=1,2,n)( 0011時時當當 kBBkkk klim|max)1(1xxikini xki)1( xi即即=0,=0, 例例3.2 3.2 設有方程組設有方程組( ( 其中其中 ) Ax=b,) Ax=b,即即 aii0 a11bxaxaxnn111212 bxaxaxann22222121 bxaxaxannnnnn 2211(3.5)(3.5) 作等價變形作等價

47、變形 xaxaxbaxnn1212111110 1 xaxxabaxnn2212122220 1 xaxabaxnnnnnnn0 2111 (3.6)(3.6)-Jacobi-Jacobi迭代法迭代法.01)(1)(212)(1111)1(1knnkkkxaxaxbax .01)(2)(2)(1212)1(222knnkkkxaxxabax 0.1)()(22)(11)1(knknknnnnknxxaxabax 于是有迭代公式于是有迭代公式(k=0,1,2,)(k=0,1,2,)(3.7)(3.7)矩陣形式為：矩陣形式為： nnnkkknnnnnnnnknkkabababxxxaaaaaaaa

48、aaaaxxx2221112212122222211111112)1()1(2)1(1 000.)7 . 3(, 1|1|)2(1)()7 . 3()1(:)0(1)0()()1(收收斂斂對對任任意意迭迭代代法法則則或或若若收收斂斂對對任任意意迭迭代代法法迭迭代代法法收收斂斂性性簡簡記記為為xJacobiBBBxJacobiJacobigxBxJJJkJk (3) (3)設方程組（設方程組（3.53.5）的系數矩陣）的系數矩陣A A按行嚴格對角占優(yōu)即：按行嚴格對角占優(yōu)即： n),1,2,(i , 1 nijjijiiaan),1,2,(j , 1 njiiijjjaa 或按列嚴格對角占優(yōu)，即或

49、按列嚴格對角占優(yōu)，即二、二、 迭代法迭代法 設有簡單迭代法設有簡單迭代法 即即Seidel,)()1(gBxxkk xbxbxbxxbxbxbxxbxbxbxknnnknknknknnkkkknnkkk)()(22)(11)1()(2)(222)(121)1(2)(1)(212)(111)1(1 (3.8)(3.8) )( )7 . 3( )0(證證明明留留作作練練習習收收斂斂對對任任意意迭迭代代法法則則xJacobi 稱如下迭代法稱如下迭代法(3.9)(3.9)xbxbxbxxbxbxbxxbxbxbxknnnknknknknnkkkknnkkk)()1(22)1(11)1()(2)(222

50、)1(121)1(2)(1)(212)(111)1(1 為與為與(3.8)(3.8)對應的對應的 迭代法，其迭代矩陣迭代法，其迭代矩陣 可用可用 “ “代入法代入法”求得。求得。SeidelBs （1 1） 迭代法迭代法(3.9)(3.9)對任意對任意 收斂收斂（2 2）若）若 則則 迭代法迭代法(3.9)(3.9)對對 任意任意 收斂；收斂；（3 3）若簡單迭代法）若簡單迭代法(3.8)(3.8)的迭代矩陣的迭代矩陣 滿滿 足足 或或 ，則相應的，則相應的SeidelSeidel迭代法迭代法 (3.9)(3.9)對任意對任意 收斂（證略）收斂（證略） SeidelSeidelx)0(; 1)

51、( Bs , 111 BBss或或Seidelx)0()(bBijnn 11 B1 Bx)0(迭代法迭代法(3.9)(3.9)的收斂性的收斂性 例例3.3 3.3 迭代方法迭代方法 （3.103.10） )()1(22)1(11)1()(2)(2)1(121222)1(2)(1)(212)(1111)1(10 1 0 10 1knknknnnnknknnkkkknnkkkxxaxabaxxaxxabaxxaxaxbax 稱為與稱為與JacobiJacobi迭代法（迭代法（3.73.7）對應的）對應的SeidelSeidel方法方法, , 其收斂情況如下：其收斂情況如下：(1)(1)使用一般的使

52、用一般的SeidelSeidel方法（方法（3.93.9）的收斂性判別法）的收斂性判別法(2)(2)若系數矩陣若系數矩陣A A對稱正定，則求解方程組（對稱正定，則求解方程組（3.53.5）的）的 與與JacobiJacobi迭代法對應的迭代法對應的SeidelSeidel方法（方法（3.103.10）對任意）對任意 收斂。收斂。 （證略）（證略）)0(x 松弛因子松弛因子, =1 , =1 即即SeidelSeidel方法方法(3.10)(3.10)(3)(3)若系數矩陣若系數矩陣A A按行（或按列）嚴格對角占優(yōu)，則按行（或按列）嚴格對角占優(yōu)，則 求解（求解（3.53.5）的與）的與Jacob

53、iJacobi方法對應的方法對應的ScidelScidel方法方法 （3.103.10）對任意）對任意 收斂收斂. . （練習）（練習）)0(x (3.11) (3.11)是一種加權平均。是一種加權平均。 1)1(111)()1()()1( ijnijkjijkjijiiikikixaxabaxx 三三. .逐次超松弛迭代法逐次超松弛迭代法(SOR(SOR法法) )(3.11) ),2,1(ni SORSOR方法的收斂性如下（不加證明）：方法的收斂性如下（不加證明）：(1)SOR(1)SOR方法對任意方法對任意 都收斂的必要條件是：都收斂的必要條件是： (2)(2)若系數矩陣若系數矩陣A A對

54、稱正定，則對稱正定，則 時時SORSOR方法方法 求解求解 對任意對任意 收斂；收斂；(3)(3)若系數矩陣若系數矩陣A A按行（或按列）嚴格對角占優(yōu)，按行（或按列）嚴格對角占優(yōu)， 則則 時時SORSOR方法對任意方法對任意 收斂。收斂。最佳松弛因子最佳松弛因子 選取問題。選取問題。20 bAx )0(x10 opt 20 )0(x)0(x 例例3.4 3.4 用用SeidelSeidel迭代法求解方程組迭代法求解方程組 1015352111021210321xxxTx)0 , 0 , 0()0( 10max3)()1(31| xxkikii解解：因為系數矩陣嚴格對角占優(yōu)，故因為系數矩陣嚴格對

55、角占優(yōu)，故SeidelSeidel方方 法對任意法對任意 收斂。收斂。取初始向量取初始向量, ,要求要求 時迭代終止。時迭代終止。 Seidel Seidel迭代格式為迭代格式為)0(x 24 . 02 . 0, 2 , 1 , 0 5 . 11 . 02 . 03 . 01 . 02 . 0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1 kkkkkkkkkxxxkxxxxxx計算結果可列表如下計算結果可列表如下TTTTTTT)(3)(2)(1)(2.99998) 1.99998 (0.9999662.99988) 1.99985 (0.9997052.99914) 1.9

56、9894 (0.9978242.99375) 1.99224 (0.9842832.95387) 1.94448 (0.8804022.68400) 1.56000 (0.3000010) 0 0(0),(Tkkkkxxxxk 注意：未必注意：未必SeidelSeidel方法一定比方法一定比JacobiJacobi方法好。方法好。99998. 2 , 99998. 1 , 99996. 0, )321( 10|32163)5()6( xxxx,ixxii為為近近似似解解，即即故故因因為為）（1 1 熟悉簡單迭代法及其收斂條件的使用；熟悉簡單迭代法及其收斂條件的使用；2 2 熟悉熟悉Jacobi

57、Jacobi迭代法及其相應的迭代法及其相應的SeidelSeidel迭代法的迭代法的 計算公式以及它們的收斂條件；計算公式以及它們的收斂條件；3 3 熟悉熟悉SORSOR方法的計算公式及其收斂條件；方法的計算公式及其收斂條件；作業(yè)：作業(yè)：作業(yè)集作業(yè)集(A) (A) 第三章第三章 4 4，5 5，6 6，7 7基本要求：基本要求： 復習：復習： 線代：線代： 1.1.定義：若定義：若 則則 叫叫A A的特征的特征 值，值， 叫其相應的特征向量。叫其相應的特征向量。 說明說明 還是特征向量。還是特征向量。 2.2.求法求法 十分困難十分困難; ;應尋求近似解法應尋求近似解法, ,且簡單、且簡單、

58、可行、有效?？尚小⒂行?。)0( )( xxxA xx 0)( 0| xEAEA 0 )()( xxA又又數值代數數值代數 第四章第四章 矩陣特征值和特征向量計算矩陣特征值和特征向量計算設設A A的特征值的特征值 特征向量特征向量|, 2121nn 且且), 2 , 1( A , , , n21nixxxxxii 4.14.1乘冪法與反冪法乘冪法與反冪法一乘冪法一乘冪法求求A A的主特征值（按模最大者）及的主特征值（按模最大者）及 其相應的特征向量其相應的特征向量 （假定（假定線形無關線形無關）nknnkkkknnnnnnnnxxxuuxxxuuxxxuuxxxuAAA 222111122222

59、1211022221110122110 ,0 則則有有線線性性表表示示初初始始向向量量)1 . 4()(0)( 121111設設 ikniiixxukk的的近近似似特特征征向向量量。就就是是故故充充分分大大時時，）顯顯然然知知由由（，充充分分大大時時，故故個個分分量量，則則的的第第為為記記111111111121111211111, 01 . 4), 2 , 1(lim)2 . 4( xxxxxkjkjkjkjkkjkniiijjkniiijjkjkkjkuknjuukuuuujuu )()()( ,)3(.)3,2, 1()2(0)1(10110常常數數充充分分大大時時若若固固定定一一個個分

60、分量量標標號號計計算算按按cuukjjkuAuujkjkkk 說明說明: : ;,0. 101u也也可可換換另另外外初初始始向向量量概概率率很很小小 ,)(. 21為為零零若若算算法法中中分分母母jku .,1征征向向量量就就是是相相應應的的一一個個近近似似特特而而則則取取ukc )()()()( 0111(111jjjkjkjkuuu 計計算算分分量量則則選選擇擇另另一一個個不不為為零零的的 有算法：有算法：;)()()(,)(,)( ,1|;)(, 1|,)1 . 4(. 3minmaxminmax11(最最小小分分量量的的絕絕對對值值最最大大的的分分量量和和分分別別表表示示向向量量和和這