1、1 引言與預(yù)備知識,第5章 解線性代數(shù)方程組的直接法,一、引言,線性方程組的來源,線性方程組的分類：直接法，迭代法。,線性方程組的兩類解法： 1、直接法：就是經(jīng)過有限步算數(shù)運算，可求得線性方程組精確解的方法（若計算過程中沒有舍入誤差）。低階稠密的線性方程組用直接法(如高斯消去法和三角分解法)。 2、迭代法：就是用某種極限過程去逐步逼近線性方程組精確解的方法。大型稀疏矩陣方程組(n很大,且零元素很多.如偏微方程數(shù)值解產(chǎn)生的線性方程組,n104)一般用迭代法。,二、向量和矩陣,三、特殊矩陣,設(shè)A=（aij） Rnn . 對角矩陣 如果當(dāng)ij時，aij=0. 三對角矩陣 如果當(dāng)|i-j|1時，aij

2、=0. 上三角矩陣 如果當(dāng)i j時，aij=0. 上海森伯(Hessenberg)陣 如果當(dāng)i j+1時，aij=0. 對稱矩陣 如果AT = A 埃爾米特矩陣 設(shè)ACnn ,如果AH=A（AH=AT ，即為A的共軛轉(zhuǎn)置） 對稱正定矩陣 如果AT =A，對任意非零向量Rn, (A,)=T A 0. 正交矩陣 如果A-1=AT . 酉矩陣 設(shè)ACnn ,如果A-1=AH .,-,10) 初等置換陣 由單位矩陣I交換第i行與第j行（或交換第i列與第j列），得到的矩陣記為Iij,且 IijA=A（為交換A第i行與第j行得到的矩陣）； AIij=B（為交換A第i列與第j列得到的矩陣）。 11) 置換陣

3、 由初等置換陣的乘積得到的矩陣.,定理1 設(shè)ARnn, 則下述命題等價: 對任何b Rn ，方程組A=b有唯一解. 齊次方程組A=0只有唯一解=0. det(A) 0. A-1存在 A的秩rank(A)=n,定理2 若ARnn 為對稱正定矩陣，則 (1) A為非奇異矩陣，且A-1亦是對稱正定矩陣. (2) 記Ak為A的順序主子陣，則Ak（k=1,2,n）亦是對稱正定矩陣，其中,（3）A的特征值i0（i=1,2, ,n ）. （4）A的順序主子式都大于零，即det(Ak) 0(k=1,2,n),定理3 若ARnn 為對稱矩陣.如果det(Ak) 0(k=1,2,n),或A得特征值i0（i=1,2

4、, ,n ）.則A為對稱正定矩陣。 有重特征值的矩陣不一定相似于對角矩陣，那么一般n階矩陣A在相似變換下能簡化到什么形狀？,定理4(若爾當(dāng)（Jordan）標(biāo)準(zhǔn)型） 設(shè)A為n階矩陣，則存在一個非奇異矩陣P使得,為若爾當(dāng)塊. 1）當(dāng)A的若爾當(dāng)標(biāo)準(zhǔn)形中所有若爾當(dāng)塊Ji均為一階時，此標(biāo)準(zhǔn)型變成對角矩陣； 2）如果A的特征值各不相同，則其若爾當(dāng)標(biāo)準(zhǔn)型必為對角矩陣diag（1 2 n）.,2 高斯消去法,一、高斯消去法,設(shè)有線性方程組：AX=b （2.1）,首先舉一個例子來說明消去法的基本思路 例2 用消去法解線性方程組,解 第1步.將方程（2.2）乘上-2加到方程（2.4）式中的未知數(shù)X1，得到 4X2

5、X3=11. (2.5) 第2步. 將方程（2.3）加到方程（2.5）上去，消去（2.5）中的未知數(shù)X2。得到與原方程組等價的三角形線性方程組,顯然，線性方程組（2.6）是容易求解的，解為,這里（-2）r1+r3r3,r2+r3r3,其中用ri表示矩陣的第i行,由此看出，用消去法解線性方程組的基本思想是用逐次消去 未知數(shù)的方法把原線性方程組AX=b化為與其等價的三角形線性 方程組，從而求解三角形線性方程組可用回代的方法求解。 下面我們討論求解一般線性方程組的高斯消去法。 將方程組AX=b 記為A（1）X=b（1） .其中 A（1） =（aij (1)）=(aij), b(1)=b.,（1）消元

6、過程,簡記為 A（2）X=b（2） ， 其中A（2），b（2）的元素計算公式為,第1步：設(shè),首先計算乘數(shù),用mi1乘（2.1）的第1個方程組，加到第i個中，消去方程組（2.1）的從第2個方程到第n個方程中的未知數(shù)X1，得到與方程組（2.1）等價的線性方程組,第k步：若,用,乘第k行,加到第i行中，得到,簡記為,A（k）X=b（k） ，,同理可得,繼續(xù)上述過程，且設(shè)akk(k) 0(k=1,2,n-1),直到完成第n-1步消元計算，最后得到,由方程組（2.1）約化為方程組（2.10）的過程稱為消元過程,若ARnn是非奇異矩陣，,則由（2.10）得到,這個過程稱為回代過程.,（2）回代過程,說明:

7、 若線性方程組的系數(shù)矩陣非奇異，則它總可以通過帶行交換的高斯消去法進(jìn)行求解。,定理5 設(shè)A=b,其中ARnn . (1)如果,則可以通過高斯消去法將Ax=b約化為,(2)如果系數(shù)矩陣A非奇異，總可以通過帶行交換的高斯消去法進(jìn)行求解。,但是，高斯消去法對于某些簡單的矩陣可能會失敗,比如:,由此需要對前述的算法進(jìn)行修改，首先研究原來矩陣A在什么條件下才能保證,等價的三角線性方程組（2.10）求解.,下面的定理給出了這個條件。,證明 首先利用歸納法證明定理6的充分性.顯然,當(dāng)k=1時,定理6成立,現(xiàn)設(shè)定理6充分性對k-1是成立的,求證定理6充分性對k亦成立.設(shè)Di0（i=1,2,k）,于是由歸納法假

8、設(shè)aii(i) 0(i=1,2,k-1),可用高斯消去法將A（1）約化到A（k）,即,(2.13),由設(shè)Di0 （i=1,2,k）,利用（2.13）式，則有akk(k) 0 ,由定理6充分性對k亦成立. 顯然,由假設(shè)aii(i) 0 (i=1,2,k),利用(2.13)式亦可推出Di0(i=1,2,k).,二、矩陣的三角分解,下面建立高斯消去法與矩陣的因式分解的關(guān)系.設(shè)方程組Ax=b的系數(shù)矩陣A的各順序主子式均不為0.由于對A施行行的初等變換相當(dāng)于用初等矩陣左乘A.,從而我們可以知道，高斯消去法實質(zhì)是將A分解為兩個三角矩陣的相乘的因式分解，于是有如下重要定理。,3 高斯主元素消去法,例4 采用

9、3位十進(jìn)制，用消元法求解,解法1：,解法2：,全主元消去法;列主元消去法.,一、列主元消去法,設(shè)有線性方程組：AX=b,第一步:先在A的第一列選取絕對值最大的元素作主元素,然后交換其增廣矩陣的第1行和第i1行(當(dāng)i11時),再進(jìn)行第1次消元.得到,重復(fù)上述過程，設(shè)已完成第k-1步的選主元素，交換兩行及消元計算， 約化為,其中A（k）的元素仍記為aij，b(k)的元素仍記為b.,第k步選主元素(在A（k）右下角方陣的第1列內(nèi)選),即確定ik，使,然后交換第k行和第ik （k=1,2,n-1）行(當(dāng)ikk時),再進(jìn)行第k次消 元.,最后將原線性方程組化為,回代求解,算法(列主元消去法). 設(shè)AX=

10、b，本算法用A得具有行交換的列主元素消去法，消元結(jié)果沖掉A，乘數(shù)mij沖掉aij，計算解X沖掉常數(shù)項b，行列式存放在det中. 1.det1 2.對于k=1,2,n-1 (1) 按列選主元 (2)如果aik,k=0,則計算停止（det（A）=0） (3)如果ik=k則轉(zhuǎn)（4） 換行：akjaik.j(j=k,k+1,n) , bk bik , det -det (4)消元計算 對于i=k+1,n aik mik=aik/akk 對于j=k+1,n aij aij-mik*akj bi bi-mik*bk,(5)detakk*det 3.如果ann=0，則計算停止（det（A）=0） 4.回代求

11、解 (1)bn bn/ann (2)對于i=n-1,2,1,5.detann*det,下面用矩陣描述列主元消去法,二、高斯若當(dāng)消去法,算法(高斯若當(dāng)消元法).,例4 采用高斯若當(dāng)消去法求矩陣,的逆A-1 .,4 矩陣的三角分解法,設(shè)有線性方程組：AX=b,一、直接三角分解法,1、不選主元三角分解算法 當(dāng)A非奇異時，由不需選主元的順序高斯消去法知,就有,不選主元的三角分解算法：,于是，可以通過求解兩個三角形方程組,得到原方程組的解,求解方程組計算公式:,說明: 上面方法稱為杜利特爾（Doolittle）分解方法,練習(xí),利用LU(Doolittle)分解法求解方程組,克勞特分解方法 設(shè)A為nn階非

12、奇異矩陣,且各階主子矩陣為非奇異,則矩 陣A的克勞特(Crout)分解為 A=LU 其中,這樣,L、U中的元素都已求出。計算L的各列與U的各行的次序如圖所示 。,圖,對方程組Ax=b的系數(shù)矩陣A作出LU分解后,方程組便化為 LUx=b 則求解上列方程組就化為依次解方程組 Ly=b Ux=y 由于L為下三角矩陣,U為單位上三角矩陣,故上述方程組的求解極為方便。他們的計算公式分別為,用克勞特分解求解線性方程組Ax=b的計算過程為: LU分解過程:對于k=1,2,n依次計算,例4 用克勞特分解方法求解下列方程組,解 令,利用矩陣乘法可得到,這樣原方程組就化為依次求下列兩個三角形方程組,代入第二個方程

13、組可求得原方程組的解為,2、選主元直接三角分解法,從直接三角分解公式可看出當(dāng) 時計算將中斷，或者當(dāng) 絕對值很小時，按分解公式計算可能引起舍入誤差的累積。但如果當(dāng)A非奇異，我們可以通過交換A的行實現(xiàn)矩陣PA的LU分解.因此可采用與列主元消去法類似的方法，將直接三角分解法修改為（部分）選主元的三角分解法。,5 向量和矩陣的范數(shù),為了研究線性方程組的近似解的誤差估計和迭代法的收斂性, 我 們需要對Rn中的向量(或Rnn中的矩陣)的“大小”引進(jìn)某種度量向 量(或矩陣)的范數(shù).,首先考慮Rn中向量的長度, 然后可定義向量(或矩陣)的范數(shù).,定義1 設(shè)=( 1, 2, , n)T， =( 1, 2, ,

14、n)T Rn . 將實數(shù)(, )= T = 1 1+ 2 2+ + n n（或復(fù) 數(shù)(, )= H = ）,稱為向量, 的數(shù)量積.并將非負(fù)實,數(shù)| |2 = (, )1/2 = 稱 為向量的歐氏范數(shù).,(1) 正定性：,等號當(dāng)且僅當(dāng),時成立；,(2) 齊次性：,(3) 三角不等式：,則稱,為向量,的范數(shù)或模.,由(3)得,(4),幾種常用范數(shù),(無窮范數(shù)),(1-范數(shù)),(2-范數(shù)),(p-范數(shù)),可以驗證它們都是范數(shù). 易見前三種范數(shù)是p-范數(shù)的特殊情況,例6 計算向量,的幾種常用范數(shù),證明 設(shè),只需證明當(dāng)xy時N（x） N（y）即成.事實上,證明 只要就s=證明上式成立即可，即證明存在常數(shù)

15、c1,c20,使,考慮函數(shù) f(x)=xt0, xRn .,記S=x|x1,xRn,則S是一個有界閉集。由于f(x)為S上的連續(xù)函數(shù)，所以f(x)于S上達(dá)到最大最小值，即存在x,x” S使得,設(shè)x Rn 且x0,則,顯然c1,c20,上式為,定義4(矩陣的范數(shù)),(1) 正定性：,等號當(dāng)且僅當(dāng),時成立；,(2) 齊次性：,(3) 三角不等式：,則稱,為 矩陣,的范數(shù)或模。,顯然這種矩陣的范數(shù)Av依賴于向量范數(shù)xv的具體含義。也就是說，當(dāng)給出一種具體的向量范數(shù)xv時，相應(yīng)地就得到了一種矩陣范數(shù)Av,誘導(dǎo)出的常用范數(shù)有：,它們滿足如下相容關(guān)系：,例7 計算矩陣,的幾種常用范數(shù),證明 用反證法。若d

16、et（IB）=0,則（IB）X=0有非零解， 即存在X00使BX0=X0,故B1，與假設(shè)矛盾，又由,(IB)（I B）-1 =I，有,（I B）-1=I+B （I B）-1 ，,從而,（I B）-1 I+B （I B）-1 （I B）-1 ,6 誤差分析,一、矩陣的條件數(shù),考慮線性方程組 AX=b 系數(shù)矩陣A和右端b的小擾動所產(chǎn)生的相對誤差.,例8 方程組,準(zhǔn)確解為,常數(shù)項微小變化后,準(zhǔn)確解,定義7 如果矩陣A或常數(shù)項b的微小變化,引起線性方程組AX=b的解的巨大變化,則稱此方程組為病態(tài)方程組矩陣A稱為病態(tài)矩陣,否則稱方程組為良態(tài)方程組,矩陣A為良態(tài)矩陣.,條件數(shù)刻畫了線性方程組AX=b的解對數(shù)據(jù)誤差的靈敏程度，它只與此方程組的系數(shù)有關(guān)，反映了方程組固有的本性。故可用條件數(shù)來描述方程組的性態(tài).,例9 求Hilbert矩陣H3的條件數(shù).,注：一般判斷矩陣是否病態(tài)，并不計算A1，而由經(jīng)驗得出。 行列式很大或很?。ㄈ缒承┬?、列近似相關(guān)）； 元素間相差大數(shù)量級，且