[數(shù)學(xué)]計(jì)算方法線性方程組解法ppt課件

1、計(jì)算方法 (力學(xué)系本科生)3.1 問題的提出 第三章 線性方程組解法 n階線性方程組3.1 問題的提出11 11221331121 1222233221 12233.nnnnnnnnnnna xa xa xa xba xa xa xa xba xa xa xa xb3.1 問題的提出線性方程組Ax=b，其中A是n維方陣，x是n維未知數(shù)向量，b是n維常數(shù)向量。1112111212222212.,.nnnnnnnnaaabxaaabxaaabxAbx3.1 問題的提出假設(shè)A是非奇特陣時，方程組有獨(dú)一解，且可以用克萊姆(Grammer)法那么表示:, (1,2,., )iiDxinD其中xi是解向量

2、x*的第i個分量，D=detA, Di是用b替代A的第i列后得到矩陣的行列式。3.1 問題的提出克萊姆方法求解計(jì)算量太大，需求計(jì)算(n+1)個n階行列式，共需求(n+1)!次乘法運(yùn)算。3.1 問題的提出 求解線性方程組的數(shù)值方法有兩大類： 直接法(direct methods)。 經(jīng)過有限次算術(shù)運(yùn)算可求方程組準(zhǔn)確解的方法(實(shí)踐上，由于舍入誤差不可防止，普通得不到準(zhǔn)確解)。適宜于求解低階稠密陣方程組。3.1 問題的提出2) 迭代法(iterative methods)。采用極限過程去逐漸逼近線性方程組準(zhǔn)確解的方法。迭代法需求計(jì)算機(jī)存儲單元較少，對計(jì)算機(jī)要求不高，程序設(shè)計(jì)簡單，但有收斂性和收斂速度

3、方面的問題。迭代法是求解大型稀疏矩陣方程的重要方法。 3.1 問題的提出 我們在本章將要學(xué)習(xí)迭代法有：雅可比(Jacobi)迭代法高斯塞德爾(Gauss-Seidel)迭代法超松弛迭代法(Successive overrelaxation method, SOR)。3.1 問題的提出追逐法(Forward elimination and backward substitution)。 我們在本章將要學(xué)習(xí)直接解法有：高斯消去法(Gauss Elimination)，高斯主元素消去法(Gauss Elemination with pivoting),三角分解法(LU decomposition)，

4、3.1 問題的提出JacobiGauss Seidel迭代法迭代法迭代法超松弛迭代法不選主元高斯消去法選主元（列選，全選）直接法三角分解法追趕法【歷史注記】線性代數(shù)方程組數(shù)值解法有著悠久的歷史。我國古代數(shù)學(xué)著作(公元1世紀(jì))的“方程章中就有了較好的線性方程組數(shù)值解法相當(dāng)于現(xiàn)代對方程組的增廣矩陣進(jìn)展初等變換、消去未知數(shù)的方法。中世紀(jì)的印度數(shù)學(xué)家也可以求解線性方程組。例如12世紀(jì)的婆什迦羅的著作中，也有求解線性方程組的內(nèi)容。3.1 問題的提出在歐洲，16世紀(jì)的比特奧在其1559中采用了與類似的消元法。日本數(shù)學(xué)家關(guān)孝和在其一書(1683)中首先采用了類似于現(xiàn)代行列式法求解了三元線性方程組。稍后，萊布

5、尼茨提出關(guān)于行列式解線性方程組的思想(1693)。1721年馬可勞林用行列式展開式的方法給出了二元、三元、四元線性方程組的解法，3.1 問題的提出但他的符號記法不完善。1750年，克萊姆給出了如今比較通用的線性方程組行列式解法，即克萊姆法那么。1764年，貝祖用行列式建立了線性方程組的普通實(shí)際。但由于當(dāng)時計(jì)算的效率很低，這一實(shí)際幾乎只需實(shí)際的意義，實(shí)踐上只能求出未知數(shù)很少的線性代數(shù)方程組的解。只是在20世紀(jì)中葉電子計(jì)算機(jī)問世并投入運(yùn)用之后，大型線性代數(shù)方程組的數(shù)值求解才成為能夠。3.1 問題的提出如何利用計(jì)算機(jī)更準(zhǔn)確、更有效地求解大型線性方程組，是計(jì)算數(shù)學(xué)中最重要的課題之一。 現(xiàn)代計(jì)算實(shí)際中，

6、常用的線性代數(shù)方程組數(shù)值解法有直接法和迭代法兩大類。直接法是在沒有舍入誤差的假設(shè)下，經(jīng)過有限次運(yùn)算就可得出方程組的準(zhǔn)確解的方法，如各種消元法。迭代法那么采用逐次逼近的方法,即從一個初始值出發(fā)，按照一定的計(jì)算格式(迭代公式)，構(gòu)造一個向量的無窮序列，其極限才3.1 問題的提出是方程組的準(zhǔn)確解，用有限次運(yùn)算得不到準(zhǔn)確解。迭代法是牛頓最先提出來的，1940年經(jīng)司威爾提出的松弛法也是一種迭代法，共軛梯度法那么是另一種迭代法，是弗萊徹等人于20世紀(jì)60年代提出來的。3.1 問題的提出例3.13.1 問題的提出52832026xyxy準(zhǔn)確解為*2,1xy 0.41.60.151.3xyyx 將方程寫為取(

7、0)(0)0 xy(1)(0)(1)(0)0.41.61.60.151.31.3xyyx 3.1 問題的提出反復(fù)以上過程得(2)(1)(2)(1)0.41.62.120.151.31.06xyyx k0123456x(k)01.62.122.0241.99281.998562.000432y(k)0-1.3-1.06-0.982-0.9964-1.00108-1.0002163.1 問題的提出假設(shè)把原方程寫為6.6678.6672.54.0 xyyx 構(gòu)造(1)( )(1)( )6.6678.6672.54.0kkkkxyyx k0123x(k)08.66735.335-109.126y(k)

8、04.0-17.668-84.35852832026xyxy3.1 問題的提出例3.2 12312312382124102132516xxxxxxxxx構(gòu)造(1)( )( )123(1)( )( )213(1)( )( )3120.1250.251.50.40.12.10.60.43.2kkkkkkkkkxxxxxxxxx (0)(0)(0)1230 xxx3.1 問題的提出得 3.1 問題的提出構(gòu)造(1)( )( )123(1)( )( )213(1)( )( )3122.50.255.25(2)1.52.58.0(3)40.56.0(1)kkkkkkkkkxxxxxxxxx (0)(0)(

9、0)1230 xxx12312312382124102132516xxxxxxxxx由原方程3.1 問題的提出得3.1 問題的提出 假設(shè)A非奇特，那么線性方程組Ax=b有獨(dú)一解x*，將上式化為x=Bx+f，給出初始向量x0，那么有： ！xk+1=Bxk+f, k=0,1,2可以構(gòu)成一向量序列xk，假設(shè)向量序列xk收斂于x*，那么x*=Bx*+f, 即x*是方程組的解 。 這種方法稱為迭代法, B稱為迭代矩陣。 3.1 問題的提出 構(gòu)造迭代法的中心問題是建立一個由本次近似值計(jì)算下一次近似值的規(guī)那么。用迭代法求解線性方程組時要處理的問題有： 構(gòu)造一種迭代格式，由xk計(jì)算xk+1 證明向量序列xk的

10、收斂性 給出初始向量x0 假設(shè)序列收斂，證明是原方程組的解 給出估計(jì)誤差和迭代停頓判據(jù)。 3.1 問題的提出v 定義：在n維空間中給定一個向量序列 ， ，假設(shè)對每一個分量 ,當(dāng) 時都有極限xi, 即 , 那么稱向量序列 有極限 ,或稱 收斂于x。 kx 12(,.)kkkkTnxxxxkixk limkiikxx kx122( ,.)Tx xxx kx3.2 雅可比迭代(Jacobi iteration) 第五章 線性方程組解法3.2 雅可比迭代 最簡單的迭代方法是從第i個方程解出未知數(shù)xi，i=1,2,n 1,1()niiijjjj iiixba xa于是雅可比迭代式為 111(),1,2,

11、.,nkkiiijjjj iiixba xina 把系數(shù)矩陣分解為A=U+D+L，其中U為由A上三角部分構(gòu)成的上三角陣，L為由A下三角元素構(gòu)成的下三角陣，D為由A對角線元素構(gòu)成的對角陣。 3.2 雅可比迭代 顯然，一切aii, i=1,2,n不為零上式才有意義，從線性代數(shù)知，對于任何系數(shù)方陣非奇特的方程組，經(jīng)過適當(dāng)交換方程的順序總可以使一切方程的0iia 3.2 雅可比迭代121312320.0.0.0nnaaaaaU21313212000.0nnaaaaaL112233.nnaaaaD于是原方程組為 (U+D+L)x=b3.2 雅可比迭代上式兩邊左乘D-1得 x= D-1 b- D-1(U+

12、L)x=Bx+f其中 B=-D-1(U+L), f=D-1b于是有迭代格式 xk+1=Bxk+f例3.3 用Jacobi迭代格式解下面方程組。3.2 雅可比迭代解：Jacobi迭代格式為 1238111210141153xxx 3.2 雅可比迭代取初始向量x(0)=(0,0,0)T，各次迭代結(jié)果(1)( )( )123(1)( )( )213(1)( )( )312(1)/8(42)/10( 3)/( 5)kkkkkkkkkxxxxxxxxx k0123456x1(k)0.00000.12500.25000.22630.22350.22510.2250 x2(k)0.00000.40000.3

13、1500.30050.30600.30580.3056x3(k)0.0000-0.6000 -0.4950 -0.4870 -0.4946 -0.4941 -0.49483.3 高斯塞德爾迭代(Gauss-Seidel iteration ) 第五章 線性方程組解法 在雅可比迭代中, 計(jì)算第k+1次迭代近似值時用的是上一次即第k次的近似值，從式 3.3 高斯塞德爾迭代11,1(),1,2,.,nkkiiijjjj iiixba xina可以看出，在計(jì)算第i個xik+1分量時，前面i-1個分量x1k+1, x2k+1 xi-1k+1曾經(jīng)從上式中計(jì)算出來了，于是很自然會想到假設(shè)把它們代入用來計(jì)算x

14、ik+1能夠會改良迭代,于是就得到Gauss-Seidel迭代格式： 寫成矩陣方式為： 3.3 高斯塞德爾迭代111111(),1,2.,inkkkiiijjijjjj iiixba xa xina 111()kkkxDbLxUx或1()kkDL xbUx假設(shè)(D+L)-1存在，那么 111()()kkk xDLUxDLbBxf其中3.3 高斯塞德爾迭代11(),() BDLU fDLb【注記】 通常高斯塞得爾方法比雅可比如法有更快的收斂速度，但不是總這樣，對于某些方程組，雅可比迭代收斂，而高斯塞得爾方法發(fā)散。即，并不是任何時候高斯塞得爾方法都比雅可比如法好。 例3.4 用Gauss-Seid

15、el迭代格式解下面方程組，準(zhǔn)確到3位有效數(shù)。3.3 高斯塞德爾迭代1238111210141153xxx 解：Gauss-Seidel迭代格式如下3.3 高斯塞德爾迭代取初始近似值x0=(0,0,0)T，各次迭代結(jié)果112311213111312(1)/8(42)/10( 3)/( 5)kkkkkkkkkxxxxxxxxx k01234xk10.00000.12500.23440.22450.2250 xk20.00000.37500.30310.30590.3056xk30.0000-0.5000-0.4925-0.4939-0.49363.4 逐次超松弛迭代法(SOR) (Successi

16、ve Overrelaxation Method) 第五章 線性方程組解法 逐次超松弛迭代簡稱SOR方法，是高斯塞得爾法的一種加速方法。 3.4 逐次超松弛迭代法高斯塞得爾法迭代格式得到 111111(),1,2,.,inkkkiiijjijjjj iiixba xa xina 把xik+1改良為xik與 的加權(quán)平均，即 1kix11111(1)(),1,2,.,kkkiiiinkkkiiijjijjjj iiixxxxba xa xina3.4 逐次超松弛迭代法 上式中 時, 就是高斯塞得爾方法，為保證迭代過程收斂,要求 102當(dāng) 時叫低階松弛法；當(dāng) 時叫超松弛法。 121 SOR方法收斂時

17、，希望選擇一個最正確的使收斂速度最快。目前還沒有最正確松弛因子 的普通算法實(shí)際，實(shí)踐大都由計(jì)算閱歷經(jīng)過試算確定 的近似值 optopt 超松弛迭代式的矩陣方式 3.4 逐次超松弛迭代法直接由分量方式公式寫 由1111()inkkkkiiiijjijjjj iiixxba xa xa有111()kkkkkxxDbLxUxDx所以111() ()()kkxDLDDU xDLb(證明)3.4 逐次超松弛迭代法111()kkkkkxxDbLxUxDx111() ()()kkxDLDDU xDLb11()kkkkkDxDxbLxUxDx11kkkkkDxLxDxUxDxb1()()kkDL xDUD x

18、b由高斯塞德爾公式推導(dǎo)。 3.4 逐次超松弛迭代法高斯塞德爾迭代公式的矩陣方式是 11kkkDxbLxUx加權(quán)平均11(1)kkkxxx11(1)()kkkkDxDxbLxUx111() (1)()kkxDLDU xDLb(證明)3.4 逐次超松弛迭代法11(1)()kkkkDxDxbLxUx111() (1)()kkxDLDU xDLb11(1)kkkkDxLxDxUxb1() (1)kkDL xDU xb3.5 迭代法的收斂性 (convergence) 第五章 線性方程組解法1( )maxii n Av 矩陣 的特征值 的絕對值最大值稱為矩陣A的譜半徑，即 3.5 迭代法的收斂性n nR

19、A,1,2,.,iin 定理 (迭代法根本定理)：設(shè)有方程組x=Bx+f，對于恣意初始向量x0及恣意f，迭代公式xk+1=Bxk+f收斂的充要條件是 ( )1B3.5 迭代法的收斂性 定理(迭代收斂的充分條件)：設(shè)有迭代式xk+1=Bxk+f，假設(shè) ，那么對于恣意初始向量x0，這個迭代過程收斂于方程組x=Bx+f的獨(dú)一解x*，并且有事后估計(jì) 1qB*111kkkqxxxx以及事前估計(jì) *101kkqqxxxx3.5 迭代法的收斂性v定義：假設(shè)對于方陣 ，有 n nA1,1,2,.,niiijjj iaain那么稱方陣對角占優(yōu)。 1213123879897xxxxxxx 定理：假設(shè)方程組Ax=b

20、的系數(shù)陣對角占優(yōu)，那么方程組有獨(dú)一解且對恣意初始向量x0雅可比迭代和高斯塞德爾迭代都收斂于真解。？、 3.5 迭代法的收斂性【思索題3.1】如何對方程組進(jìn)展調(diào)整，運(yùn)用Gauss-Seidel迭代格式求解時收斂？ 定理：假設(shè)方程組Ax=b的系數(shù)陣對稱正定，那么方程組有獨(dú)一解且對恣意初始向量x0高斯塞德爾迭代收斂于真解。 3.5 迭代法的收斂性 Jacobi迭代格式的收斂性3.5 迭代法的收斂性 Jacobi迭代矩陣1() JDUL 特征方程0IJ1()0IDUL1()0DDUL3.5 迭代法的收斂性由于10D0DUL所以留意到ADUL所以，將A的對角線元素乘以 后取行列式，令其等于零，就是Jac

21、obi迭代矩陣的特征方程。 例3.5 討論用Jacobi迭代格式解方程組的收斂性。3.5 迭代法的收斂性1238111210141153xxx解：Jacobi迭代矩陣的特征方程為81121010115展開得3.5 迭代法的收斂性Jacobi迭代格式收斂。34001230解得12,30.146084,0.073041 0.214487i 123( )max,0.226581B Gauss-Seidel迭代格式的收斂性3.5 迭代法的收斂性 Gauss-Seidel迭代矩陣1() GDLU 特征方程0IG1()0IDLU1()()0DLDLU3.5 迭代法的收斂性由于1()0DL()0DLU所以留

22、意到ADUL所以，將A的對角線以下元素乘以 后取行列式，令其等于零，就是Gauss-Seidel迭代矩陣的特征方程。3.5 迭代法的收斂性【思索題3.2】Gauss-Seidel迭代矩陣1() GDLU至少有1個特征值為零，為什么？ 例3.6 討論用Gauss-Seidel迭代格式解方程組的收斂性。3.5 迭代法的收斂性1238111210141153xxx解： Gauss-Seidel迭代矩陣特征方程為811210105展開得3.5 迭代法的收斂性Gauss-Seidel迭代格式收斂。2(400101)0解得12,30,( 117)/80 123()max,0.0640381G3.5 迭代法

23、的收斂性!作業(yè)：(1) 寫出下面方程組的Jacobi迭代格式和Gauss-Seidel迭代格式的算法! (2) 討論它們的收斂性。123211111111121xxx 3.6高斯消去法(Gauss Elimination)第三章 線性方程組解法 高斯消去法是最古老的數(shù)值方法之一，如今依然是一個很有用的方法，它在計(jì)算機(jī)上容易實(shí)現(xiàn)。 3.6 高斯消去法 其根本思想是在各個方程之間進(jìn)展乘法和加減運(yùn)算，逐漸消去方程中的未知數(shù)。它分為消去和回代兩個過程。 Axb 給定線性方程組3.6 高斯消去法1112111212222212.nnnnnnnnaaaxbaaaxbaaaxb第一步消元，令 ，用 乘第一個

24、方程再加到第i個方程上作為第i個新方程，消去x1的項(xiàng)，變?yōu)?111/,2,3,.,iimaain1 im逐次進(jìn)展同樣過程，最后，經(jīng)過n-1次消元，得到： 3.6 高斯消去法1112111(1)(1)(1)22222(1)(1)(1)2.0.0.nnnnnnnaaaxbaaxbaaxb以上這些步驟叫消元過程。 3.6 高斯消去法1112111(1)(1)(1)22222(1)(1).0.0.00.nnnnnnnnaaaxbaaxbaxb然后，從第n個方程開場，依次解出 xn, xn-1, x1 3.6 高斯消去法(1)(1)/nnnnnnxba(1)(1)(1)1()/niiiiiijjiij

25、ixbaxa 1,.,1in高斯消去法的計(jì)算量3.6 高斯消去法 消去過程的計(jì)算量。第一步計(jì)算乘數(shù)mi1,(i=2,3,n)需求i-1次除法運(yùn)算，計(jì)算aij(2)(i,j=2,3,n)需求(i-1)2次乘法運(yùn)算以及(i-1)2次加減法運(yùn)算。 利用求和公式211(1)/2,(1)(21)/6,1nniiin nin nnn 得到3.6 高斯消去法第k步加減法次數(shù)乘法次數(shù)除法次數(shù)1(n-1)2(n-1)2n-12(n-2)2(n-2)2n-2N-1111合計(jì)n(n-1)(2n-1)/6 n(n-1)(2n-1)/6n(n-1)/2 于是消去過程乘除法次數(shù)為2(1)/3n n 消去過程加減法次數(shù)為(

26、1)(21)/6n nn3.6 高斯消去法計(jì)算b(n-1)的計(jì)算量(1)(2).2 1(1)/2nnn n 乘除法次數(shù)為 加減法次數(shù)為(1)/2n n3.6 高斯消去法回代計(jì)算量 乘除法次數(shù)為 加減法次數(shù)為(1)/2n n1 2.(2)(1)(1)/2nnnn n3.6 高斯消去法總的計(jì)算量332333nnnn 乘除法次數(shù)為 加減法次數(shù)為3353263nnnn 高斯消去法還有沒有方法進(jìn)展，為什么？ 3.6 高斯消去法(1)0,1,2,.,(1)iiiain【思索題3.3】假設(shè)遇到! 作業(yè)：寫出高斯消去法的Fortran程序。3.7高斯主元消去法(Gauss Elimination with p

27、ivoting )第三章 線性方程組解法3.7 高斯主元消去法 從高斯消去法我們曾經(jīng)看出，為使高斯消去法能順利進(jìn)展，必需在每一步消去步都滿足條件 ，但假設(shè)(1)0iiia(1)(1),iiiikiaaki相應(yīng)的系數(shù) (1)(1)/,iikiikiimaaki計(jì)算能夠引起很大的舍入誤差。 為此，需求改良高斯消去法。有兩種改良方法：列選主元，完全選主元。 3.7 高斯主元消去法u列選主元u經(jīng)過交換方程而使得 aki(i-1), k=i,i+1,n,中絕對值最大的一個換到(i, i)位置而成為第i步的消去主元。u完全選主元法就是在系數(shù)矩陣的子塊 1,11,1,.kkknn kn naaaa中找出絕對

28、值最大的元素，作為第k+1次消去過程的主元。 3.7 高斯主元消去法假設(shè) 11maxpqijki nkj naa 那么k+1行與p行交換，第k+1列與第q列交換，右端也同時交換，在做列交換時，要留意未知量也作交換，即把xk+1與xp交換。 3.7 高斯主元消去法 列選主元算法： for k=1,2,n-1 找出滿足 元素的行位置p ,maxp kikk i naa if , error,無獨(dú)一解，stop error if ( )換行 ,p kapk for j=k,k+1,n ak,j與ap,j交換 3.7 高斯主元消去法 bk與bp交換 Endfor Endif 消去計(jì)算： /,1,.,i

29、kikkkmaaikn,1,.,ijijikkjaam ai jkn,1,.,iiikkbbm bikn Endfor3.7 高斯主元消去法回代計(jì)算：/nnnnxba for i=n-1,n-2,2,1 1()/niiijjiij ixba xa Endfor 3.7 高斯主元消去法3.8 三角分解法(LU decomposition )第三章 線性方程組解法高斯消去法 3.7 三角分解法第一次消元過程為 111111/,2,3,., ,0iimaaina用-mi1乘上面第一個方程再加到第i個方程，即可消去第i個方程中的未知量x1。這個過程實(shí)踐上是給系數(shù)矩陣A左乘這樣一個下三角陣L1： 作第二

30、次消元相當(dāng)于給系數(shù)矩陣A(1)左乘了一個下三角陣L2：211311100.010.00100.00.1nmmm L3.7 三角分解法作第k次消元相當(dāng)于系數(shù)矩陣A(k-1)左乘一個下三角陣Lk2322100.0010.001.0.00.1nmmL(1)(1)(1)222222/,2,., ,0iimaain a3.7 三角分解法|11,2,100.010.1.0.0.0.kKkkkkkn kmmmL3.7 三角分解法于是第n-1次消元過程可表示為：( )1221.nnnLLL L AA( )1221.nnnLLL L bb于是1111( )1221.nnnAL LLLA下三角陣乘積也是一個下三角

31、陣。 記111121.nLL LL3.7 三角分解法 L是單位下三角陣(即對角元素全為1的下三角陣)。 211210.01.0.1nnlllL3.7 三角分解法( )nALA叫矩陣A的三角分解，或LU分解。假設(shè)L為單位下三角陣，那么叫Doolittle分解，假設(shè)U為單位上三角陣，那么叫Crout分解。 ALU只需A的各順序主子式不為零，那么A可獨(dú)一分解成一個單位下三角陣L與一個上三角陣U的乘積。3.7 三角分解法 設(shè)Ax=b，A=LU，那么Ax=LUx=b于是令Ux=y，那么Ly=b11121212221210.0.1.00.,.0.100.nnnnnnuuuluulluLU3.7 三角分解法

32、這樣原來方程能化為兩個簡一方程組由 求y11,1,2,.,iiiijjjybl yin然后由 求x1()/niiijjiij ixyu xu 3.7 三角分解法1,2,.,in 如今顯式地給出lij和uij的表達(dá)式 111211112121222212221212.1.10.1nnnnnnnnnnnnaaauuuaaaluuaaallu從第一行可以看出，u1j=a1j, j=1,2,n3.7 三角分解法從第一列可以看出 ai1=li1u11, i=2,3,n, 即li1=ai1/u11, i=2,3,n 。 從第二行可以看出，a2j=l21u1j+u2j , j=2,3,n，那么u2j=a2j

33、-l21u1j, j=2,3,n 從第二列可以看出，ai2=li1u12+li2u22 , i=2,3,n，那么li2=(ai2-li1u12)/u22, i=2,3,n3.7 三角分解法111211112121222212221212.1.10.1nnnnnnnnnnnnaaauuuaaaluuaaallu 普通地，假設(shè)U的前k-1行，L的前k-1行曾經(jīng)求出，那么第k (k=2,3,n)步 11kkjkmmjkjmal uu(行)3.7 三角分解法11,1,.kkjkjkmmjmual ujk kn(列)11kikimmkikkkmal ul u11()/,1,.kikikimmkkkmla

34、l uuikn直到第n步，A全部分解成LU。3.7 三角分解法3.9 追逐法( Forward elimination and backward substitution )第三章 線性方程組解法 在很多實(shí)踐問題中，方程組Ax=b的系數(shù)矩陣A是一個稀疏矩陣。 3.6 追逐法11122221110.0000000.0000000.00.00000000.00000000.000000000iiinnnnnnbcxabcxabcabcabx12.nddd假設(shè)非零元素集中分布在對角線及其相鄰兩個次對角線上，且系數(shù)陣為對角占優(yōu)陣，即有：11,2,3,.1iiinnbcbacinba3.6 追逐法把系數(shù)

35、矩陣三角分解有11222110.010000.0100,.0000010000nnnnqrqrpqrpqLU3.6 追逐法利用LU分解公式，寫出111111,2,3,.,kkkkkkkkkqb rcrcp qaqp cb kn3.6 追逐法得到 11,kkqbrc11,2,3,.,kkkkkkkapqbp cknq于是 ,LydUxy得到 111,2,3,.,kkkkydydp ykn3.6 追逐法1/1(),1,2,.,1nnnkkkkkxyqxyc xknnq3.6 追逐法3.10 其它運(yùn)用第三章 線性方程組解法 計(jì)算行列式值3.6 其他運(yùn)用ALU1122det()det( ).nnu uuAU 求矩陣逆1AAI111212122212.1000.0100.0001nnnnnnxxxxxxxxxA分別由 120.,1,2,.,.10iinixxinix A解出 xij, ij=1,2,n 于是1ijxA3.6 其他運(yùn)用3.11 誤差分析(Error analysis)第三章 線性方程組解法