第三章解線性方程組的直接法

第三章解線性方程組的直接法《數(shù)值分析》主講教師1第一頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.1基礎(chǔ)知識(shí)§3.1.1引言§3.1.2矩陣特征值與譜半徑§3.1.3對(duì)稱正定矩陣§3.1.4正交矩陣與初等矩陣第二頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.1.1引言對(duì)于n個(gè)變量n個(gè)線性方程組求解，其表達(dá)式為：用向量矩陣表示可表示為：第三頁(yè)，共九十三頁(yè)，編輯于2023年，星期四其中第四頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第五頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.1.2矩陣特征向量與譜半徑第六頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第七頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第八頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第九頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第十頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第十一頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.1.3對(duì)稱正定矩陣第十二頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第十三頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.1.4正交矩陣與初等矩陣第十四頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第十五頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第十六頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第十七頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第十八頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.2Gauss消去法§3.2.1Gauss順序消去法§3.2.2消去法與矩陣三角分解§3.2.3列主元消去法第十九頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.2.1Gauss順序消去法第二十頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第二十一頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第二十二頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第二十三頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第二十四頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第二十五頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第二十六頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第二十七頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.2.2消去法與矩陣三角分解定理：第二十八頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.2.3列主元消去法第二十九頁(yè)，共九十三頁(yè)，編輯于2023年，星期四選主元素的矩陣表示也稱初等置換矩陣第三十頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.3直接三角分解法§3.3.1Doolittle分解法§3.3.2Cholesky分解與平方根法§3.3.3三對(duì)角方程組的追趕法第三十一頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.3.1Doolittle分解法第三十二頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第三十三頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第三十四頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第三十五頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第三十六頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.3.2Cholesky分解與平方根法第三十七頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第三十八頁(yè)，共九十三頁(yè)，編輯于2023年，星期四利用Cholesky分解將AX=b轉(zhuǎn)化為，令，則原方程等價(jià)解以下兩個(gè)方程第三十九頁(yè)，共九十三頁(yè)，編輯于2023年，星期四例用平方根法解方程組解驗(yàn)證A正定，由Cholesky分解求得第四十頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.3.3三對(duì)角方程組的追趕法第四十一頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第四十二頁(yè)，共九十三頁(yè)，編輯于2023年，星期四下面舉實(shí)例用追趕法來(lái)解三對(duì)角方程組。第四十三頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第四十四頁(yè)，共九十三頁(yè)，編輯于2023年，星期四追趕法計(jì)算量：5n-4次乘法，o(n),計(jì)算量小；穩(wěn)定性：普半徑小于1，穩(wěn)定。第四十五頁(yè)，共九十三頁(yè)，編輯于2023年，星期四直接解法的Ｍatlab求解1．利用左除運(yùn)算符的直接解法對(duì)于線性方程組Ax=b，可以利用左除運(yùn)算符“\”求解：x=A\b第四十六頁(yè)，共九十三頁(yè)，編輯于2023年，星期四例1用直接解法求解下列線性方程組。命令如下：A=[2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4];b=[13,-9,6,0]';x=A\b第四十七頁(yè)，共九十三頁(yè)，編輯于2023年，星期四2．利用矩陣的分解求解線性方程組矩陣分解是指根據(jù)一定的原理用某種算法將一個(gè)矩陣分解成若干個(gè)矩陣的乘積。常見的矩陣分解有LU分解、QR分解、Cholesky分解，以及Schur分解、Hessenberg分解、奇異分解等。第四十八頁(yè)，共九十三頁(yè)，編輯于2023年，星期四(1)LU分解矩陣的LU分解就是將一個(gè)矩陣表示為一個(gè)交換下三角矩陣和一個(gè)上三角矩陣的乘積形式。線性代數(shù)中已經(jīng)證明，只要方陣A是非奇異的，LU分解總是可以進(jìn)行的。MATLAB提供的lu函數(shù)用于對(duì)矩陣進(jìn)行LU分解，其調(diào)用格式為：[L,U]=lu(X)：產(chǎn)生一個(gè)上三角陣U和一個(gè)變換形式的下三角陣L(行交換)，使之滿足X=LU。注意，這里的矩陣X必須是方陣。[L,U,P]=lu(X)：產(chǎn)生一個(gè)上三角陣U和一個(gè)下三角陣L以及一個(gè)置換矩陣P，使之滿足PX=LU。當(dāng)然矩陣X同樣必須是方陣。實(shí)現(xiàn)LU分解后，線性方程組Ax=b的解x=U\(L\b)或x=U\(L\Pb)，這樣可以大大提高運(yùn)算速度。第四十九頁(yè)，共九十三頁(yè)，編輯于2023年，星期四例2用LU分解求解例題中的線性方程組。命令如下：A=[2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4];b=[13,-9,6,0]';[L,U]=lu(A);x=U\(L\b)或采用LU分解的第2種格式，命令如下：[L,U,P]=lu(A);x=U\(L\P*b)第五十頁(yè)，共九十三頁(yè)，編輯于2023年，星期四(2)QR分解對(duì)矩陣X進(jìn)行QR分解，就是把X分解為一個(gè)正交矩陣Q和一個(gè)上三角矩陣R的乘積形式。QR分解只能對(duì)方陣進(jìn)行。MATLAB的函數(shù)qr可用于對(duì)矩陣進(jìn)行QR分解，其調(diào)用格式為：[Q,R]=qr(X)：產(chǎn)生一個(gè)一個(gè)正交矩陣Q和一個(gè)上三角矩陣R，使之滿足X=QR。[Q,R,E]=qr(X)：產(chǎn)生一個(gè)一個(gè)正交矩陣Q、一個(gè)上三角矩陣R以及一個(gè)置換矩陣E，使之滿足XE=QR。實(shí)現(xiàn)QR分解后，線性方程組Ax=b的解x=R\(Q\b)或x=E(R\(Q\b))。第五十一頁(yè)，共九十三頁(yè)，編輯于2023年，星期四例3用QR分解求解例題中的線性方程組。命令如下：A=[2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4];b=[13,-9,6,0]';[Q,R]=qr(A);x=R\(Q\b)或采用QR分解的第2種格式，命令如下：[Q,R,E]=qr(A);x=E*(R\(Q\b))第五十二頁(yè)，共九十三頁(yè)，編輯于2023年，星期四(3)Cholesky分解如果矩陣X是對(duì)稱正定的，則Cholesky分解將矩陣X分解成一個(gè)下三角矩陣和上三角矩陣的乘積。設(shè)上三角矩陣為R，則下三角矩陣為其轉(zhuǎn)置，即X=R'R。MATLAB函數(shù)chol(X)用于對(duì)矩陣X進(jìn)行Cholesky分解，其調(diào)用格式為：R=chol(X)：產(chǎn)生一個(gè)上三角陣R，使R'R=X。若X為非對(duì)稱正定，則輸出一個(gè)出錯(cuò)信息。[R,p]=chol(X)：這個(gè)命令格式將不輸出出錯(cuò)信息。當(dāng)X為對(duì)稱正定的，則p=0，R與上述格式得到的結(jié)果相同；否則p為一個(gè)正整數(shù)。如果X為滿秩矩陣，則R為一個(gè)階數(shù)為q=p-1的上三角陣，且滿足R'R=X(1:q,1:q)。實(shí)現(xiàn)Cholesky分解后，線性方程組Ax=b變成R‘Rx=b，所以x=R\(R’\b)。第五十三頁(yè)，共九十三頁(yè)，編輯于2023年，星期四例4用Cholesky分解求解例1中的線性方程組。命令如下：A=[2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4];b=[13,-9,6,0]';R=chol(A)???Errorusing==>cholMatrixmustbepositivedefinite命令執(zhí)行時(shí)，出現(xiàn)錯(cuò)誤信息，說(shuō)明A為非正定矩陣。第五十四頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4向量和矩陣范數(shù)§3.4.1向量?jī)?nèi)積與范數(shù)§3.4.2矩陣范數(shù)（迭代解法數(shù)學(xué)基礎(chǔ)）第五十五頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.1內(nèi)積與向量范數(shù)第五十六頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.1內(nèi)積與向量范數(shù)內(nèi)積定義：設(shè)X為一個(gè)線性空間，<.,.>為X上的一個(gè)二元泛函,滿足：（1）（正定性）<x,x>0,當(dāng)且僅當(dāng)x=0時(shí)等號(hào)成立；（2）（對(duì)第一變?cè)€性）對(duì)任意a，bC1,<ax+by,z>=a<x,z>+b<y,z>;(3)(共扼對(duì)稱性)<x,y>=<y,x>*。則稱該二元泛函為線性空間X上的一個(gè)內(nèi)積。第五十七頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.1內(nèi)積與向量范數(shù)第五十八頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.1向量?jī)?nèi)積與范數(shù)第五十九頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.1內(nèi)積與向量范數(shù)例如：對(duì)RN(或CN),有如下的范數(shù)：這說(shuō)明了范數(shù)的多樣性。第六十頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.1內(nèi)積與向量范數(shù)從該定理可知內(nèi)積可導(dǎo)出范數(shù)，第六十一頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.1內(nèi)積與向量范數(shù)此外，內(nèi)積還滿足下述性質(zhì)：第六十二頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.1內(nèi)積與向量范數(shù)第六十三頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)第六十四頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)第六十五頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)第六十六頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)注2通常的范數(shù)未必滿足上述相容性條件，如：注3由每種向量范數(shù)均可按前述定義構(gòu)造出一種矩陣的從屬范數(shù)。第六十七頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)(A的行范數(shù))(A的列范數(shù))(A的2范數(shù))第六十八頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)第六十九頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)第七十頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)證明（1）：（2）參見關(guān)治、陸金甫。第七十一頁(yè)，共九十三頁(yè)，編輯于2023年，星期四問(wèn)題思考第七十二頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)第七十三頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.4.2矩陣范數(shù)第七十四頁(yè)，共九十三頁(yè)，編輯于2023年，星期四相關(guān)的定理*第七十五頁(yè)，共九十三頁(yè)，編輯于2023年，星期四證明：第七十六頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.5誤差分析與病態(tài)方程組§3.5.1矩陣條件數(shù)與擾動(dòng)方程組誤差界§3.5.2條件數(shù)與剩余誤差估計(jì)的關(guān)系§3.5.3病態(tài)方程組的解法第七十七頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.5.1矩陣條件數(shù)與擾動(dòng)方程組誤差界第七十八頁(yè)，共九十三頁(yè)，編輯于2023年，星期四一個(gè)并不顯然的例子第七十九頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第八十頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.5.1矩陣條件數(shù)與擾動(dòng)方程組誤差界病態(tài)方程組的定義：第八十一頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.5.1矩陣條件數(shù)與擾動(dòng)方程組誤差界對(duì)照條件數(shù)觀察此式第八十二頁(yè)，共九十三頁(yè)，編輯于2023年，星期四證明：第八十三頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.5.1矩陣條件數(shù)與擾動(dòng)方程組誤差界第八十四頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.5.2條件數(shù)與剩余誤差估計(jì)的關(guān)系對(duì)上式比照條件數(shù)進(jìn)行分析從而獲得矩陣條件數(shù)的定義！第八十五頁(yè)，共九十三頁(yè)，編輯于2023年，星期四第八十六頁(yè)，共九十三頁(yè)，編輯于2023年，星期四§3.5.2條件數(shù)與剩余誤差估計(jì)的關(guān)系第八十七頁(yè)，共九十三頁(yè)，編輯于2023年，星期四著名的病態(tài)矩陣(Hilbert)第