1、第二章 線性代數(shù)方程組的解法,2.1 解線性方程組的直接法,2.2 解線性方程組的迭代法,2.0 概述,2.2 迭代法的收斂性,一、研究數(shù)值解法的必要性,求：,的解 的值，根據(jù)克萊姆(Gramer)法則可 表示為兩個(gè)行列式之比：,2.0 概述,如： ,若用每秒完成萬(wàn)億次（1012）浮點(diǎn)乘法運(yùn)算的計(jì)算機(jī)（幾年前國(guó)內(nèi)運(yùn)算速度最快），按每天工作24小時(shí),完成這些計(jì)算約需30年。若使用一般的個(gè)人電腦，每秒不外完成十億次（109）浮點(diǎn)乘法運(yùn)算，則完成這些計(jì)算約需3萬(wàn)年。(天河千萬(wàn)億次),計(jì)算一個(gè) 階行列式需要做 個(gè)乘法，求解上述方程共做 次乘除法。,二、線性代數(shù)方程組的常用解法,1、直接法： 只包含有限

2、次四則運(yùn)算。若在計(jì)算過(guò)程中都不發(fā)生舍入誤差的假定下，計(jì)算結(jié)果就是原方程組的精確解。,2、迭代法： 把方程組的解向量看作是某種極限過(guò)程的極限，而且實(shí)現(xiàn)這一極限過(guò)程每一步的結(jié)果是把前一步所得的結(jié)果施行相同的演算步驟得到的。,Remark：由于運(yùn)算過(guò)程中舍入誤差的存在，實(shí)際上直接方法得到的解也是方程組的近始解。,2.1解線性方程組的直接法,設(shè)有線性方程組,為非奇異矩陣。,或?qū)憺榫仃囆问?，其中,一、Gauss消去法,具體過(guò)程：,其中,將 改為,Step1：,若 令 ,用 乘 第一個(gè)方程加到第 個(gè)方程 ，并保留第一式，則得,其中,記為,記為,其中,設(shè)為,第k-1步消元完成后，有,按上述做法，做完n-1

3、步消元，原方程可化為同解的上三角方程組：,其中,(i,j=k+1,n),（i=k+1,n）,上面的方程記為,記為,最后，若 ，逐步回代可得到原方程組的解：,（i=n-1,n-2,2，1）,上面的求解過(guò)程稱為Gauss順序消去法。它通過(guò)一系列消元過(guò)程與最后的一步回代過(guò)程來(lái)得到方程組的解。,Remark1：在Gauss順序消去法的消去過(guò)程中，可以將右端列向量視為方程組A的第n1列，直接對(duì)矩陣A（指現(xiàn)在的n行，n1列的增廣矩陣）進(jìn)行行初等變換，將其變換為上三角形矩陣，從而回代求解得到方程組的解。,Remark2：可以統(tǒng)計(jì)出，如果A為n階方陣，則Gauss順序消去法消去過(guò)程所需的乘除運(yùn)算次數(shù)為,回代過(guò)

4、程所需的乘除運(yùn)算次數(shù)為,故總的乘除運(yùn)算次數(shù)為,取n20，則N3060，與Gramer法則相比，是天壤之別。,Remark3：在消去過(guò)程中，也可以采用Gauss-Jordan消去法，將方程組化為對(duì)角形方程組，進(jìn)而化為單位陣，則右端列向量就化為方程組的解向量。該方法不需回代過(guò)程，但總的計(jì)算量為n3/2+n2-n/2，比Gauss順序消去法有所增加。,Remark4：在消去過(guò)程中，消去過(guò)程能夠進(jìn)行的前提條件是 。當(dāng)detA= 時(shí)方程組存在唯一解，但未必能滿足 的條件。要使Gauss順序消去法能夠求得方程組的解，應(yīng)滿足如下的定理：,定理：用高斯順序消去法能夠求解方程組 的解的充要條件為A的各階順序主子

5、式均不為零。,算法見(jiàn)教材第27頁(yè)：,（1）消元過(guò)程.對(duì)k=1,2，n-1進(jìn)行如下運(yùn)算： 對(duì)i=k+1.k+2,n; 對(duì)j=k+1,n+1, (2) 回代過(guò)程.按下述公式,由于舍入誤差的原因，Gauss順序消去法不是一個(gè)實(shí)用的方法，實(shí)用中應(yīng)該采用選主元的Gauss消去法。,在計(jì)算過(guò)程中舍入誤差增大迅速，造成計(jì)算解與真解相差甚遠(yuǎn)，這一方法就是不穩(wěn)定的方法，反之，在計(jì)算過(guò)程中的舍入誤差增大能得到控制，該方法就是穩(wěn)定的。小主元是不穩(wěn)定的根源，這就需要采用“選主元素”技術(shù)，即選取絕對(duì)值最大的元素作為主元。,二、主元素消去法,B=,1)列主元消去法,一種常用的方法是列主元消去法。設(shè)增廣矩陣為,再考慮 右下

6、角矩陣，選取絕對(duì)值最大的元素作為主元素,經(jīng)過(guò)行的對(duì)換把主元素移到 ，,再按消元公式計(jì)算 （i,j=3,n）。,直至將方程組化成上三角方程組，再進(jìn)行回代就可求得解。,算法見(jiàn)教材第27頁(yè)：,（1）消元過(guò)程.對(duì)k=1,2，n-1進(jìn)行如下運(yùn)算： 選主元：找行號(hào)ikk,n 使 若為零，終止. 交換A(k),b(k)中的第k,ik兩行; 對(duì)i=k+1.k+2,n;令 對(duì)j=k+1,n+1, (2) 回代過(guò)程.按下述公式,2)全主元消去法,B=,Remark,Reamrk1：全主元消去法每一步所選取的主元的絕對(duì)值不低于列主元消去法的同一步所選主元的絕對(duì)值，因而計(jì)算結(jié)果更加可靠。,Reamrk2：全主元消去法

7、每一步選主元要花費(fèi)更多的機(jī)時(shí)，并且對(duì)增廣矩陣做了列交換，從而未知量的次序發(fā)生了變化，對(duì)編程帶來(lái)了困難。而列主元消去法的計(jì)算結(jié)果已比較可靠，故實(shí)用中常用列主元消去法。,Reamrk3：選主元的消去法與Gauss順序消去法的乘除法的計(jì)算量是一樣的，均為n3/3+n2-n/3。,三、選主元素消去法的應(yīng)用,1.求解方程組系,設(shè)系數(shù)矩陣A可逆，求解方程組系A(chǔ)Xbi(i=1,2,m)。,將方程組系的系數(shù)矩陣與右端向量寫(xiě)成增廣矩陣,A|b1,b2,bm,按列選主元素后再用Gauss-Jordan消去法將左邊的矩陣A化為單位矩陣，則得到,右端的列向量就是方程組系的解向量。,2.求逆矩陣,在1中令mn，且右端列

8、向量組成單位陣，則當(dāng)A化為單位陣時(shí)，右端矩陣即為A的逆矩陣。這是實(shí)用中求逆矩陣的可靠方法。,3.求行列式,若要求矩陣A的行列式，可用主元素消去法將其化為上三角陣，對(duì)角元素設(shè)為b11，b22，bnn，于是A的行列式為：,det(A)=(-1)m b11b22bnn,其中m為行列交換的次數(shù)。這是實(shí)用中求行列式的可靠方法。,四、矩陣三角分解法,1.Gauss順序消去法的矩陣形式,設(shè)方程組A = 中A的各階順序主子式均不為零，令,則n-1步消元過(guò)程為,將上述n-1步消元過(guò)程合并，得，,即,（1）,令L=,則 L=,其中，L為單位下三角矩陣，它的對(duì)角元素皆為1。 (三角分解與高斯消去法的關(guān)系),即,AX

9、=b即為L(zhǎng)UX=b 令Y=UX，方程變?yōu)長(zhǎng)Y=b. 可先解LY=b，求出Y，再解UX=Y即可,2 .矩陣的三角分解及條件,定義1.設(shè)A為n階矩陣（n 2）,稱A=LU為矩陣的三角分解，其中L是下三角矩陣，U是上三角矩陣。,Remark：三角分解不唯一，可以有不同的形式 。為確保唯一性，引入以下定義。,定義2.如果L是單位下三角矩陣，U是上三角矩陣，則稱三角分解A=LU為Doolittle分解；如果L是下三角矩陣，U是單位上三角矩陣，則稱A=LU為Crout分解。前面高斯順序消去法對(duì)應(yīng)了A=LU的Doolittle分解。（P32定義1）,定理1：設(shè)A為n階可逆矩陣，則A有唯一Doolittle(

10、or Crout)分解的充要條件為：A的前n-1階順序主子式不為零。,Remark：實(shí)際中對(duì)A進(jìn)行三角分解，不是利用初等變換矩陣，而是直接使用矩陣乘法得到。（若不加說(shuō)明，后面我們講到的三角分解一律指Doolittle型分解。）,的求解過(guò)程為:,可推導(dǎo)求解單位下三角形方程組 的遞歸公式為 :,求解上三角形方程組 的遞歸公式為：,3.直接三角分解法,設(shè)A=LU 即,Step1：,比較第一行元素：,Step2：,比較第二行元素：,算出：,比較第二列的元素：,得出：,一般地，設(shè)U的前k-1行以及L的前k-1列已求出，則,比較第k行元素,Stepk：,可以算出：,算出:,這組公式可用下圖記憶（緊湊格式）

11、:,P33,的求解過(guò)程為:,可推導(dǎo)求解單位下三角形方程組 的遞歸公式為 :,求解上三角形方程組 的遞歸公式為:,(P34):,對(duì)比計(jì)算 和 公式，,發(fā)現(xiàn)計(jì)算 的規(guī)律與計(jì)算 的規(guī)律類(lèi)似,因此計(jì)算 的求方程組的過(guò)程可用三角分解的緊湊格式取代。事實(shí)上,這只要把 做為A的第n1列進(jìn)行直接三角分解即可。,Reamrk：上述直接三角分解法所對(duì)應(yīng)的是Gauss順序消去法，二者的乘除運(yùn)算次數(shù)是相當(dāng)?shù)摹?shí)際中對(duì)階數(shù)較高的線性方程組，應(yīng)采用選主元的三角分解法求解，以保證計(jì)算結(jié)果的可靠性。,例求解,三角分解法的運(yùn)算量與高斯消去法大體相當(dāng)，但對(duì)于系數(shù)矩陣A不變而常數(shù)列b變化的的一類(lèi)方程組來(lái)說(shuō)，節(jié)省運(yùn)算量 因?yàn)锳=LU

12、不用再分解，對(duì)于不同的b 直接解LY=b和UX=Y即可,列主元三角分解法主要思想,4.平方根法（Cholesky分解）,設(shè)A為n階 對(duì)稱正定矩陣，L是非奇異下三角矩陣，稱 為矩陣A的Cholesky分解。,n階 對(duì)稱正定矩陣A，一定存在如下的分解式 ，其中L為單位下三角陣，D是對(duì)角元全為正的對(duì)角陣，且這種分解式唯一; ，其中L為下三角陣，當(dāng)限定L的對(duì)角元為正時(shí)， （Cholesky分解）的分解式唯一。,定義：,定理：,平方根法的計(jì)算公式 （為簡(jiǎn)單起見(jiàn)設(shè) ，L為下三角矩陣）,令,我們可以通過(guò)矩陣乘法比較來(lái)求L的下三角部分元素。具體計(jì)算公式如下:,P28,Remark1:由于在上式分解過(guò)程中有n次

13、開(kāi)方運(yùn)算，故Choledsky分解法也稱為平方根法。,Remark3:可以證明，若用Gauss順序消去法求解對(duì)稱正 定的方程組Axb，則有,用Gauss順序消去法求解對(duì)稱正定方程組也不用選主元。,Remark4:從運(yùn)算量的角度看，平方根法是有利的?？梢越y(tǒng)計(jì)出，用平方根法求解Axb所需乘除法的運(yùn)算次數(shù)為：,令有n次開(kāi)方運(yùn)算。 n次開(kāi)方運(yùn)算一般使用迭代法，所需乘除法的運(yùn)算次數(shù)大約為n的常數(shù)倍。故平方根法總的乘除法運(yùn)算次數(shù)大約為,Remark5：為避免開(kāi)方運(yùn)算，也可對(duì)A做 分解。(其中L為單位下三角陣,D為對(duì)角陣),平方根法舉例,求解,解,先解,4.改進(jìn)的平方根法,n階 對(duì)稱矩陣A，一定存在如下的分

14、解式 A=LDLT，其中L為單位下三角陣，D是對(duì)角元全為正的對(duì)角陣，且這種分解式唯一,改進(jìn)的平方根法的計(jì)算公式,與P41不同,對(duì)k=2,3,n,分別計(jì)算,改進(jìn)的平方根法舉例,求解,解,先解,五、解三對(duì)角方程組的追趕法,1.矩陣對(duì)角占優(yōu)的概念,設(shè),類(lèi)似地，也有按列對(duì)角占優(yōu)和按列嚴(yán)格對(duì)角占優(yōu)的概念。,若對(duì)于 ，均有 ,則對(duì)稱矩陣A按行嚴(yán)格對(duì)角占優(yōu)。,2.追趕法解三對(duì)角方程組,設(shè),并滿足嚴(yán)格對(duì)角占優(yōu)條件,當(dāng)A嚴(yán)格對(duì)角占優(yōu)時(shí)，可以證明各階順序主子式非零。,即,等價(jià)于,令 即,由 得,由 得,Remark：只要三對(duì)角矩陣按行嚴(yán)格對(duì)角占優(yōu)，則追趕法定能進(jìn)行下去，且計(jì)算過(guò)程是穩(wěn)定的（不必選主元素），其乘除法

15、運(yùn)算次數(shù)為5n4。上述方法稱為解三對(duì)角方程組的追趕法，又稱為T(mén)homas方法。,追趕法舉例,求解,解,2.2 解線性方程組的迭代法,為非奇異矩陣。,線性方程組的矩陣形式AX=b,若能等價(jià)的寫(xiě)成 X=MX+d,其中,例如，AX=B兩邊都加X(jué)得,X+AX=X+b即X=X-AX+b=IX-AX+b 合并右邊前兩項(xiàng)得X=(I-A)X+b 這里,與原方程等價(jià),則當(dāng)X(0)=X(1)時(shí), X(1)就是原方程的解. 若X(0)X(1) ，但當(dāng)二者差別非常小時(shí)，例如當(dāng) 可認(rèn)為X(0)X(1)可將X(1)作為近似解.否則,若X(0)滿足X(0)=MX(0)+d,則X(0)就是原方程X=MX+d的解.若記,則當(dāng)X

16、(2)=X(1)時(shí), X(2)就是原方程的解. 若X(2)X(1) ，但當(dāng)二者差別非常小時(shí)，例如當(dāng) 可認(rèn)為X(2)X(1)可將X(2)作為近似.否則,則X*正是方程組X=MX+d的精確解 稱X(k+1)=MX(k)+d為迭代公式， 稱M為迭代矩陣.對(duì)應(yīng)的方法為一種迭代法.,一.雅可比（Jacobi）迭代法,(1)迭代格式,設(shè)有n 階方程組,其中系數(shù)矩陣非奇異，且 ，i=1,2，n,將上式變形為,建立迭代格式,上面的迭代式稱為雅可比（Jacobi）迭代格式。,用矩陣形式來(lái)表示方程組的迭代格式,設(shè)det(A) ，且,則,記A=D+L+U,雅可比迭代式成為：,令,則得,舉例用矩陣形式和分量形式！,稱

17、B為雅可比迭代矩陣,雅可比,高斯-塞德?tīng)?迭代格式,二、高斯-塞德?tīng)枺℅auss-Seidel）迭代法,G-S迭代式成為：,則,令,則得,記A=D+L+U,舉例用矩陣形式和分量形式！,稱G為高斯-賽德?tīng)柕仃?三、逐次超松弛迭代法 （SOR法-Successive Over Relaxation）,1.迭代公式,將G-S迭代格式,改寫(xiě)為：,并記,一般地，殘量(余量) 。,這就是逐次超松馳迭代法（SOR方法)， 稱為松馳 因子。,SOR方法的計(jì)算公式也常寫(xiě)為：,Remark：可見(jiàn)，SOR方法的得到的 可以看成是G-S方法的結(jié)果與 的加權(quán)平均。,將殘量乘以一個(gè)修正量加到 上，作為新的結(jié)果,P56

18、例1,2.3迭代法的收斂性,一、向量的范數(shù)和矩陣的范數(shù) 定義1 （向量范數(shù)）對(duì)任意n維向量XRn,若按一定規(guī)則對(duì)應(yīng)一實(shí)數(shù)|X| ，并滿足以下條件： 正定條件.即對(duì)任意XRn, |X|0，只有當(dāng)X=0時(shí)， |X|=0 齊次性.對(duì)任意實(shí)數(shù)k， |kX|= |k| |X| （可擴(kuò)展到復(fù)數(shù)） 三角不等式.對(duì)任意X，YRn, |X+Y| |X|+ |Y| 則稱| 為向量范數(shù). 例如設(shè),分別稱為X的1范數(shù)， 2范數(shù)， 范數(shù)，,定義2 （矩陣范數(shù)）若對(duì)任意nn矩陣A，按一定規(guī)則對(duì)應(yīng)一實(shí)數(shù)|A| ，并滿足以下條件： 對(duì)任意nn矩陣A， |A|0，只有當(dāng)A=0時(shí)， |A|=0 對(duì)任意實(shí)數(shù)k， |kA|= |k|

19、 |A| 對(duì)任意nn矩陣A，B, |A+B| |A|+ |B| 對(duì)任意nn矩陣A，B, |AB| |A| |B| 則稱| 為矩陣范數(shù).,分別稱為X的1范數(shù)（列范數(shù)）， 2范（譜范數(shù)）數(shù)， 范數(shù)（行范數(shù)），F(xiàn)robenius范數(shù) P60例2（糾錯(cuò)）,定義3(P59) 若有向量范數(shù)|u和矩陣范數(shù)|v,使得對(duì)任意nn矩陣A和n維向量X都有 |AX|u |A|v |X|u 則稱向量范數(shù)|u與矩陣范數(shù)|v是相容的.注意特別當(dāng)u=v=1,2,，向量范數(shù)|u與矩陣范數(shù)|v是相容的.,二、迭代法的收斂性,當(dāng) k 時(shí)，,與下式等價(jià),或,與下式等價(jià),當(dāng) k 時(shí)，,或,定義4 向量序列的極限,迭代矩陣的譜半徑,(1

20、)收斂的充要條件,定理1（P62）迭代法 ， ，對(duì) 任意初始向量 都收斂的充要條件是：,注意 雅可比好和G-S迭代法對(duì)應(yīng)的M為B,G,定義 5（P61）設(shè)nn矩陣A的所有特征值為1， 2， n，稱下式為矩陣A的譜范數(shù),雅可比、高斯-塞德?tīng)柕ㄅe例：,P76：第9,10題, 是判定收斂的根本法則(充分必要！)。,時(shí)，有可能存在某個(gè)初始向量 使簡(jiǎn) 單迭代法收斂。（該向量不好找）,Remark：,(2)收斂的充分條件,證明：,設(shè)是M的任一特征值，X是A的關(guān)于的特征向量，則有X=MX，根據(jù)范數(shù)相容性，有,由于X0得,根據(jù)的任意性知,根據(jù)定理1得證,定理3（P63） 若nn矩陣A=aij nn是嚴(yán)格對(duì)角占優(yōu)矩陣，則A為非奇異矩陣. 證：用反正法.若|A|=0，則齊次線性方程組AX=0有非零解，設(shè)有一非零解為X,說(shuō)明|A|0，A是非奇異的,定理4（P64）若線性方程組AX=b的系數(shù)矩陣是嚴(yán)格對(duì)角占優(yōu)矩陣，則解此線性方程組的雅可比迭代法收斂.解此線性方程組的高斯-塞德?tīng)柕ㄊ諗?,證（1）設(shè)A=aijnn，則有,所以雅可比迭代法收斂.,由嚴(yán)格對(duì)角占優(yōu)矩陣的定義有（按行）,i=1,2,，n,證（2）：用反正法.設(shè)G=-(L+D)-1 U是高斯-塞德