1、第2章 解線性方程組的直接法,本章討論n元線性方程組,（2.1）,的直接解法。方程組(2.1)的矩陣形式為,Ax=b,其中,若矩陣A非奇異,即det(A)0,則方程組(2.1)有唯一解。,所謂直接解法是指，若不考慮計(jì)算過程中的舍入誤差，,經(jīng)過有限次算術(shù)運(yùn)算就能求出線性方程組的精確解的方法。,但由于實(shí)際計(jì)算中舍入誤差的存在，用直接解法一般也只,能求出方程組的近似解。,Cramer法則是一種不實(shí)用的直接法，下面介紹幾種實(shí),用的直接法。,1 Gauss消去法,Gauss消元法是一種規(guī)則化的加減消元法，其基本思,想是通過逐次消元計(jì)算，把一般線性方程組的求解轉(zhuǎn)化為,等價(jià)的上三角形方程組的求解。,1.1

2、順序Gauss消去法,為了清楚起見,先看一個(gè)簡單的例子.,考慮線性方程組,消去后兩個(gè)方程中的x1得,再消去最后一個(gè)方程的x2得,消元結(jié)束,經(jīng)過回代得解:,上述求解的消元過程可用矩陣表示為:,(A,b)=,這是Gauss消去法的計(jì)算形式,新的增廣矩陣對(duì)應(yīng)的線性,方程組就是上三角形方程組,可進(jìn)行回代求解。,現(xiàn)在介紹求解線性方程組（2.1)的順序Gauss消去法:,記,則,線性方程組(2.1)的增廣矩陣為,第一步.設(shè) ,依次用,乘矩陣的第1行加到第i行,得到矩陣:,其中,第二步.設(shè) ,依次用,乘矩陣的第2行加到第i行,得到矩陣:,其中,如此繼續(xù)消元下去,第n-1步結(jié)束后得到矩陣:,這就完成了消元過程

3、。,對(duì)應(yīng)的方程組變成：,對(duì)此方程組進(jìn)行回代，就可求出方程組的解。,順序Gauss消去法求解n元線性方程組的乘除運(yùn)算量是： n2-1,+(n-1)2-1,+22-1,+1+2+n,n=20時(shí),順序Gauss消去法只需3060次乘除法運(yùn)算.,順序Gauss消去法通常也簡稱為Gauss消去法.,順序Gauss消去法中的,稱為主元素.,主元素都不為零矩陣A的各階順序主子式都不為零.,1.2 主元Gauss消去法,(用十進(jìn)制四位浮點(diǎn)計(jì)算):,(用Cramer法則可得精確解x1*=1.00010 ,x2*=0.99990),解 用順序Gauss消去法, 消元得,回代得解:x2=1.00 ,x1=0.00,

4、若將方程組改寫成:,例1 解線性方程組,用順序Gauss消去法, 消元得,回代得解:x2=1.00 ,x1=1.00,為了提高計(jì)算的數(shù)值穩(wěn)定性,在消元過程中采用選擇主元的方法.常采用的是列主元消去法和全主元消去法.,給定線性方程組Ax=b, 記A(1)=A,b(1)=b,列主元Gauss消去法的具體過程如下:,首先在增廣矩陣B(1)=(A(1),b(1)的第一列元素中,取,然后進(jìn)行第一步消元得增廣矩陣B(2)=(A(2),b(2).,再在矩陣B(2)=(A(2),b(2)的第二列元素中,取,然后進(jìn)行第二步消元得增廣矩陣B(3)=(A(3),b(3).,按此方法繼續(xù)進(jìn)行下去, 經(jīng)過n-1步選主元

5、和消元運(yùn)算,得到增廣矩陣B(n)=(A(n),b(n).則方程組A(n)x=b(n)是與原方程組等價(jià)的上三角形方程組,可進(jìn)行回代求解.,易證,只要|A|0,列主元Gauss消去法就可順利進(jìn)行.,采用十進(jìn)制四位浮點(diǎn)計(jì)算,分別用順序Gauss消去法和列主元Gauss消去法求解線性方程組:,例2,方程組具有四位有效數(shù)字的精確解為 x1*=17.46, x2*=-45.76, x3*=5.546,解 1. 用順序Gauss消去法求解,消元過程為,回代得: x3=5.546, x2=100.0, x1=-104.0,2. 用列主元Gauss消去法求解,消元過程為,回代得: x3=5.545, x2=-4

6、5.77, x1=17.46,可見，列主元Gauss消去法是在每一步消元前,在主元所在的一列選取絕對(duì)值最大的元素作為主元素.,而全主元Gauss消去法是在每一步消元前,在所有元素中選取絕對(duì)值最大的元素作為主元素.但由于運(yùn)算量大增,實(shí)際應(yīng)用中并不經(jīng)常使用.,2 直接三角分解法,2.1 Gauss消去法的矩陣表示,對(duì)矩陣,若,令,記,則有,A(2)=,記,令,若,則有,A(3)=,如此進(jìn)行下去, 第n-1步得到:,A(n)=,其中,也就是:,A(n)=Ln-1A(n-1),其中,=Ln-1Ln-2A(n-2),= Ln-1Ln-2L2L1A(1),所以有:,A=A(1)= L1-1L2-1Ln-1

7、-1A(n)=LU,而且有,其中L=L1-1L2-1Ln-1-1, U=A(n) .,L稱為單位下三角矩陣; U是上三角矩陣.,式 A=LU稱為矩陣A的三角分解.,2.2 Doolittle分解法,設(shè)n階方陣A的各階順序主子式不為零,則存在唯一單位下三角矩陣L和上三角矩陣U使A=LU .,證明 只證唯一性, 設(shè)有兩種分解 A=LU,則有,=E,所以得,于是 Ax=b LUx=b,令 Ux=y 得,定理2.1,下面介紹矩陣三角分解的Doolittle分解方法,則得,對(duì)k=2,3,n,計(jì)算,設(shè),akj=lk1u1j+lk2u2j+lkk-1uk-1j+ukj,aik=li1u1k+li2u2k+l

8、ikukk,對(duì)k=2,3,n,計(jì)算,由,可得,這就是求解方程組Ax=b的Doolittle三角分解方法。,利用三角分解方法解線性方程組,解 因?yàn)?所以,例3,先解,得,再解,得,解線性方程組Ax=b的Doolittle三角分解法的計(jì)算量約為1/3n3,與Gauss消去法基本相同.其優(yōu)點(diǎn)在于求一系列同系數(shù)的線性方程組Ax=bk ,(k=1,2,m)時(shí),可大大節(jié)省運(yùn)算量.,例如,求上例中矩陣A的逆矩陣.可分別取常向量 b1=(1,0,0)T, b2=(0,1,0)T, b3=(0,0,1)T,由,所以,為了提高數(shù)值穩(wěn)定性, 可考慮列主元三角分解法, 設(shè)已完成A=LU的k-1步分解計(jì)算, 矩陣分解成

9、,設(shè),令 rkri,相當(dāng)于取,為第k步分解的主元素.,但要注意方程組的常數(shù)項(xiàng)也要相應(yīng)變換.,例如,用列主元三角分解解例3中方程組.則有,設(shè)A為對(duì)稱正定矩陣, 則有唯一分解A=LU, 且ukk0.,則有 A=LDM,又因?yàn)?(LDM)T=MTDLT=LDM 所以 M=LT,=LDLT,則有,2.3 平 方 根 法,分解A=GGT稱為對(duì)稱正定矩陣的Cholesky分解.,Ax=b 轉(zhuǎn)換為 Gy=b , GTx=y,若記G=(gij), 則有: 對(duì)k=1,2,n,實(shí)際計(jì)算時(shí),可采用緊湊格式,_平方根法.,解三角方程 Gy=b , GTx=y 可得,解,例4 解線性方程組,平方根法是求對(duì)稱正定系數(shù)線性

10、方程組的三角分解法,對(duì)稱正定矩陣的Cholesky分解的計(jì)算量和存貯量均約為一般矩陣的LU分解的一半. 且Cholesky分解具有數(shù)值穩(wěn)定性.,追趕法是求三對(duì)角線性方程組的三角分解法.即方程,三對(duì)角矩陣A的各階順序主子式都不為零的一個(gè)充分條件是:,|a1|c1|0 ; |an|dn|0 ; |ai|ci|+|di| , cidi 0 ,i=2,3,n-1.,在此條件下, A=LDM=TM , 稱之為矩陣A的Crout分解.,對(duì)三對(duì)角矩陣A進(jìn)行Crout分解,有,2.4 追 趕 法,其中,解三角方程 Ty=b , Mx=y 可得,稱之為解三對(duì)角方程組的追趕法.,解,例5 解線性方程組,當(dāng)滿足條件

11、 |a1|c1|0 ; |an|dn|0 ; |ai|ci|+|di| , cidi 0 ,i=2,3,n-1. 時(shí), 追趕法是數(shù)值穩(wěn)定的, 追趕法具有計(jì)算程序簡單, 存貯 量少,計(jì)算量小的優(yōu)點(diǎn).,3 向量和矩陣的范數(shù),3.1 向量的范數(shù),定義2.1 設(shè)是向量空間Rn上的實(shí)值函數(shù), 且滿足條件:,(1)非負(fù)性: 對(duì)任何向量xRn ,x0 ,且x=0當(dāng) 且僅當(dāng)x=0,(2)齊次性: 對(duì)任何向量x Rn 和實(shí)數(shù) , x=| |x,(3)三角不等式: 對(duì)任何向量x ,yRn x+yx+y,則稱為空間Rn上的范數(shù),x為向量x的范數(shù).,記x=(x1,x2,xn)T, 常用的向量范數(shù)有:,向量的1-范數(shù):

12、x1=|x1|+|x2|+|xn|,向量的2-范數(shù):x2=,向量的-范數(shù):x=,例6 設(shè)向量x=(2,-4,3,1)T, 求向量范數(shù)xp ,p=1,2, .,解 由定義x1=10 , x2=,x=4 .,雖然不同范數(shù)的值可能不同，但它們間存在等價(jià)關(guān)系.,定理2.2 (范數(shù)的等價(jià)性),對(duì)于 Rn 上的任何兩種范數(shù) 和 ,存在正常數(shù)m,M,使得 m x x M x , xRn,常用的三種向量范數(shù)滿足如下等價(jià)關(guān)系 x x1 nx , xRn,定義2.2 設(shè)向量序列,k=1, 2,向量,如果,則稱向量序列x(k)收斂于向量x*, 記作,易見,3.2 矩陣的范數(shù),定義2.3 設(shè)是以n階方陣為變量的實(shí)值函

13、數(shù),且滿足條件:,(1)非負(fù)性: A0 ,且A=0當(dāng)且僅當(dāng)A=0,(2)齊次性: A=| |A, R,(3)三角不等式:A+BA+B,(4)三角不等式:ABAB,則稱A為矩陣A的范數(shù).,記A=(aij) , 常用的矩陣范數(shù)有:,矩陣的1-范數(shù):A1,也稱矩陣的列范數(shù).,矩陣的2-范數(shù):A2,也稱為譜范數(shù).,矩陣的-范數(shù):A,也稱為行范數(shù).,矩陣的F-范數(shù):AF,例7 設(shè)矩陣,求矩陣A的范數(shù)Ap ,p=1,2, ,F.,解 A1=4 , A=5 , AF,設(shè)是一種向量范數(shù), 則定義,稱之為由向量范數(shù)派生的矩陣算子范數(shù).,矩陣的算子范數(shù)滿足,AxAx, xRn,把滿足上式的矩陣范數(shù)稱為與向量范數(shù)相

14、容的矩陣范數(shù).,對(duì)于p=1,2,矩陣范數(shù)Ap是由向量范數(shù)xp派生的矩陣算子范數(shù),所以Ap是與xp相容的矩陣范數(shù).但AF不是一種算子范數(shù),卻與x2是相容的.,設(shè)是一種算子范數(shù), 則,矩陣的范數(shù)與矩陣的特征值之間也有密切的聯(lián)系.,設(shè)是矩陣A的特征值,x是對(duì)應(yīng)的特征向量,則有,Ax= x,利用向量和矩陣范數(shù)的相容性, 則得,|x=x=AxAx,于是 |A,設(shè)n階矩陣A的n個(gè)特征值為1, 2, , n, 則稱,為矩陣A的譜半徑.,對(duì)矩陣的任何一種相容范數(shù)都有, (A)A,另外, 0, 一種相容范數(shù), 使 A (A)+,任何兩種矩陣范數(shù)也具有等價(jià)性 m A A M A , ARnn,矩陣序列的收斂性也定

15、義為,4 線性方程組固有性態(tài)與誤差分析,4.1 線性方程組的固有性態(tài),考慮線性方程組,其精確解為 x*=(-9800b1+9900b2 , 9900b1-10000b2)T,若把線性方程組變?yōu)?解為x=(-9800b1+9900b2-19700 , 9900b1-10000b2+19900)T,可見 x-x*=(-19700 , 19900)T,解的誤差可能放大到常數(shù)項(xiàng)的誤差的近2萬倍。,若把線性方程組變?yōu)?則線性方程組可能無解.,這種由于原始數(shù)據(jù)微小變化而導(dǎo)致解嚴(yán)重失真的線性方程組稱為病態(tài)方程組, 相應(yīng)的系數(shù)矩陣稱為病態(tài)矩陣.,設(shè)線性方程組 Ax=b,系數(shù)矩陣是精確的, 常數(shù)項(xiàng)有誤差b, 此

16、時(shí)記解為x+x ,則 A(x+x) =b+b,于是 Ax =b,所以 x = A-1b A-1 b,又由于 b= Ax A x,因此 x b AA-1bx,即,再設(shè)b是精確的, A有誤差A(yù), 此時(shí)記解為x+x ,則 (A+A)(x+x) =b,則有 Ax +A(x+x) =0,所以 x =-A-1A(x+x),于是 x A-1Ax+x,也就是,記 Cond(A)=AA-1, 稱為方程組Ax=b或矩陣A的條件數(shù).,經(jīng)常使用的條件數(shù)有 Condp(A)=ApA-1p p=1，2，。,當(dāng)A為對(duì)稱矩陣時(shí)，有 Cond2(A)=|1|/|n| 其中1，n分別是A的按絕對(duì)值最大和最小的特征值。,例如，對(duì)前

17、面方程組的系數(shù)矩陣A有,Cond1(A)= Cond(A)= 39601， Cond2(A)39206,由于計(jì)算條件數(shù)運(yùn)算量較大, 實(shí)際計(jì)算中若遇到下述情況之一,方程組就有可能是病態(tài)的:,(1) 矩陣元素間數(shù)量級(jí)差很大 ,且無一定規(guī)律;,(2) 矩陣的行列式值相對(duì)來說很小 ;,(3) 列主元消去法求解過程中出現(xiàn)量級(jí)很小的主元素;,(4) 數(shù)值求解過程中 , 計(jì)算解x的剩余向量r=b-Ax已經(jīng)很小, 但x仍不符合要求.,4.2 預(yù)條件和迭代改善,1. 線性方程組的預(yù)條件處理,對(duì)病態(tài)方程組Ax=b ,考慮線性方程組,其中,稱之為預(yù)條件方程組, 顯然與原方程組等價(jià).可逆矩陣C稱為預(yù)條件矩陣.矩陣C應(yīng)滿足條件,(1)條件數(shù),(2)方程組Cz=d容易求解。,比Cond(A)明顯小.,對(duì)于一般的矩陣A沒有十分有效的方法去選擇預(yù)條件矩陣. 當(dāng)A是對(duì)稱正定矩陣時(shí),可取C .,2. 線性方程組的迭代改善,設(shè)已求得方程組Ax=b的近似解x(1), 計(jì)算剩余向量,r(1)=b-Ax(1),再求解余量方程組Ax=r(1), 得到解,則x(1)的迭代改善解為