NC-2-1.ppt

1、1,第2章 線性方程組的解法,計算方法/數(shù)值計算,胡小兵 E-mail: 重慶大學數(shù)學與統(tǒng)計學院,2,主要內(nèi)容,線性方程組的直接解法； 向量與矩陣的范數(shù)、條件數(shù)的概念; 線性方程組的迭代解法.,3,在自然科學和工程技術中，很多問題歸結(jié)為解線性方程組。,線性方程組,有的問題的數(shù)學模型中雖不直接表現(xiàn)為含線性方程組，但它的數(shù)值解法中將問題“離散化”或“線性化”為線性方程組。因此線性方程組的求解是數(shù)值分析課程中最基本的內(nèi)容之一。,4,線性方程組,(2.1),(2.2),若|A| 0, (2.2)的解存在且唯一。,5,線性方程組的解法,直接法：經(jīng)過有限次的算術運算，可以求得(2.1)的精確解（假定計算過

2、程沒有舍入誤差）。如克萊姆算法。但該法對高階方程組計算量太大。實用的直接法中具有代表性的算法是高斯消元法。,迭代法：它將(2.1)變形為某種迭代公式，給出初始解x0，用迭代公式得到近似解的序列xk, k=0, 1, 2, 在一定的條件下xkx* (精確解)。,注意：迭代法需考慮收斂條件和收斂速度問題。,6,高斯(Gauss)消元法,高斯消元法是將線性方程組通過初等變換化為上三角形方程組，再回代得其解。是一種直接方法。,第一步，將(2.3)乘-2加到(2.4)；(2.3)乘-1加到(2.5), 得到：,7,高斯消元法,第二步,將(2.6)乘-2/3加到(2.7),得到:,回代：解(2.8)得x3

3、, 將x3代入(2.6)得x2, 將x2, x3代入(2.3)得 x1, 得到解 x*=(2, 1, -1)T,8,高斯消元法,容易看出，第一步和第二步相當于增廣矩陣:b在作行變換，用ri表示增廣陣A:b的第 i 行:,9,高斯消元法-思路,思路：逐次消去未知數(shù)的系數(shù)，將Ax=b化為等價的三角形方程組，然后回代解之。,10,高斯消元法-思路,設第 k-1（k=1,2,n-1） 步消元后的系數(shù)矩陣記為：,第 k 次消元，化為0,i=k+1,k+2,n 第 i 行消元系數(shù),11,高斯消元法步驟,1. 消元,令,對k =1到n-1, 若 , 進行:,12,高斯消元法步驟,2. 回代,若 , 則:,(

4、i=n-1,n-2,1) (2.10),消元過程要求： 回代過程則進一步要求：,13,高斯(Gauss)消元法,定理2.1 Ax=b能用高斯消元法解的充要條件是A的各階順序主子式不為零。,A的各階順序主子式：,14,Gauss消元法問題,問題1：消元時可能出現(xiàn) 的情況，高斯消元法失效。,問題2：即使 ，但 ，此時用它作除數(shù),也會導致其它元素數(shù)量級嚴重增加，帶來舍入誤差的擴散，使解嚴重失真。,15,解決思路,怎么辦？,列主元高斯消元法,基本思想：每次從所在列對角線及以下元素中選擇絕對值最大的元素作為主元進行消元運算。,16,列主元Gauss消元法,設已用列主元消元法完成Ax=b的第k-1次消元(

5、1kn-1), 此時方程組Ax=bA(k)x=b(k)，有如下形式:,(2.12),17,列主元Gauss消元法, 在方框內(nèi)的一列內(nèi)選出絕對值最大者，即確定ik：,若 ，則必有方框內(nèi)的元素全為零，此時易證A=A(k)=0，即方程組Ax=b無確定解,進行第 k 次消元前，先進行、兩個步驟:,18,列主元Gauss消元法,然后，用高斯消元法進行消元：從k=1到k=n-1,就完成了消元過程，只要A0，列主元高斯消元法必可進行下去。,19,高斯-若當消元法,(2.13）,是高斯消元法的一種變形。同時消去對角元上方和下方的元素，而且將對角元化為1。設已完成k-1步,于是Ax=b化為等價方程組A(k)x=

6、b(k)，增廣陣為：,20,高斯-若當消元法,1.按列選主元，確定ik使,2.換行，交換增廣陣第 k 行和第 ik 行,(j=k, k+1,n),在第 k 步計算時，考慮將第 k 行上下的第 k 列元素都化為零, 且akk化為1。對k=1,2,n,21,高斯-若當消元法,3 計算乘數(shù) mik= - aikakk (i=1,2,n, ik) mkk=1akk (2.14),4 消元 aij=aij+mikakj (i=1,2,n,且ik,j=k+1,n) bi=bi+mikbk (i=1,2,n,且ik) (2.15),5 主行計算 akj=akjmkk (j=k,k+1,n) bk=bkmkk

7、 (2.16),22,高斯-若當消元法,顯然xi=bi（i=1,2,n）就是Ax=b的解。,當k = n時,23,高斯-若當消元法,高斯-若當消元法解方程組并不比高斯消元法優(yōu)越,但用于矩陣求逆是適宜的,實際上它是初等變換方法求逆的一種規(guī)范化算法:,例3 已知 ，求,24,高斯-若當消元法,25,高斯-若當消元法,26,高斯-若當消元法,所以,Gauss-Jordan法的Matlab程序見課本P13頁。,27,矩陣三角分解,三角分解：設 ，若存在下三角矩陣L和一個上三角陣U使得 A=LU，則稱LU為矩陣A的三角分解.,L - 下三角矩陣 U - 上三角矩陣,28,矩陣的Doolittle分解,D

8、oolittle分解：限定L是單位下三角矩陣（對角線為1的下三角矩陣）。,矩陣L與U滿足一定條件，才能保證分解的唯一性。,29,矩陣三角分解條件,定理2.2 若矩陣A的各階順序主子式非零，則A可進行Doolittle分解和Crout分解，且這種分解是唯一的。,利用LU分解解線性方程組:,LUx = b,令 Ux = y, 則 Ly = b,Ax = b,兩個等價的三角形方程組容易求解,30,Doolittle分解,方法1：用不帶行交換Gauss消元法。其中L的下三角元素就是由消元運算的乘數(shù)因子組成，U是消元運算結(jié)束后的上三角矩陣。,分解方法：,方法2：用矩陣乘法原理推出計算公式。,31,Doo

9、little分解-思路,比較等式兩邊的第一行得：,u1j = a1j,比較等式兩邊的第一列得：,比較等式兩邊的第二行得：,比較等式兩邊的第二列得：,( j = 1, n ),( i = 2, n ),( j = 2, n ),( i = 3, n ),繼續(xù)下去,32,利用矩陣乘法做Doolittle分解,1、計算U 的第一行： ；,2、計算L 的第 一列： ；,3、對k = 2,3,n 進行以下的計算：,（2.14）,（2.15）,33,回代求解線性方程組,4、解,（2.16）,5、解,（2.17）,34,例子,例2.3 用LU分解方法求解方程組,解: 由公式(2.14)(2.15),35,例

10、子,于是化為兩個方程組,用(2.16)式解第一個方程組 ，代入第二個方程組，用(2.17)式解之得,36,矩陣的Crout分解,Crout分解：限定U為單位上三角矩陣（對角線為1的上三角矩陣）。,37,2、計算U 的第一行： ；,3、對 k=2,3,n 進行以下的計算：,Crout分解,1、計算L 的第 一列， ；,38,Crout分解,4、解,5、解,39,平方根法,定理2.3 設矩陣A對稱正定，則存在三角分解A=LLT，L是非奇異下三角矩陣，且當限定的對角元為正時，這種分解是唯一的。,稱為對稱正定矩陣的Cholesky分解。,L,LT,40,平方根法 -計算公式,1、計算L的第一列：,2、對 k = 2, 3, n 進行以下的計算：,41,平方根法 - 計算公式,3、解,4、解,42,追趕法,在三次樣條插值，常微分方程的邊值問題等都歸結(jié)為求解系數(shù)矩陣為對角占優(yōu)的三對角方程組 Ax = f，即:,其中|i-j|1時，aij=0，且滿足如下的對角占優(yōu)條件: (1) |b1|c1|0, |bn|an|0 (2) |bi|ai|+|ci|, aici0, i=2,3,n-1.,43,追趕法,對A作