線性方程組的求解

線性方程組的求解第一頁(yè)，共七十六頁(yè)，編輯于2023年，星期三§1引言一般的線性方程組本章：即有唯一第二頁(yè)，共七十六頁(yè)，編輯于2023年，星期三的求法求法直接求法（解析法）間接方法（數(shù)值方法、迭代方法）1.Grammer法則：2.Gauss消元法及其改進(jìn)3.三角分解法（L-U方法）適用：當(dāng)A為低階稠密陣（n<150）.1.一般迭代法2.Jacobi法3.Seidel法4.SOR法適用：當(dāng)A為高階稀疏矩陣（n>150)第三頁(yè)，共七十六頁(yè)，編輯于2023年，星期三二、預(yù)備知識(shí)1.幾個(gè)概念：1°單位上(下)三角陣：主對(duì)角元素均為1的上（下）三角陣相關(guān)結(jié)論：其逆仍為單位上（下）三角陣

其積仍為單位上（下）三角陣2°置換陣（排列陣）：?jiǎn)挝魂嚱?jīng)過(guò)一次兩行（兩列）的互換形成矩陣為初等置換陣。初等置換陣的乘積即為置換陣初等置換陣一定為對(duì)稱陣,3°三對(duì)角陣:對(duì)方陣當(dāng)稱A為三角陣.

4°可約與不可約矩陣：對(duì)n階矩陣A，若存在置換陣P使其中，為r階子塊，為n-r階子塊，則稱A為可約矩陣，否則不可約。第四頁(yè)，共七十六頁(yè)，編輯于2023年，星期三5°對(duì)角占優(yōu)矩陣：對(duì)n階矩陣A，若或

成立，則稱A為嚴(yán)格行或列對(duì)角占優(yōu)矩陣。

若或且上述不等式

至少有一個(gè)嚴(yán)格成立，稱A為弱對(duì)角行（列）占優(yōu)矩陣。

相關(guān)結(jié)論：若A為嚴(yán)格行或列對(duì)角占優(yōu)矩陣（或A為不可約行或列弱對(duì)角占優(yōu)矩陣），則A可逆。論證：不妨設(shè)A為嚴(yán)格行對(duì)角占優(yōu)矩陣反證：A不可逆，即AX=0有非零解設(shè)，對(duì)AX=0的第K個(gè)方程

第五頁(yè)，共七十六頁(yè)，編輯于2023年，星期三6°矩陣的譜半徑：

對(duì)n階矩陣A,設(shè)為A的全部特征值,稱為A的譜半徑。

第六頁(yè)，共七十六頁(yè)，編輯于2023年，星期三2.再論范數(shù)1°2°3°

主要討論1°

相關(guān)結(jié)論：中的所有范數(shù)均等價(jià),即任意取中的兩個(gè)范數(shù)，則

一定存在兩個(gè)正數(shù)C1以及C2使2°上的范數(shù)（乘積用的最多）

定義：中的范數(shù)常用第七頁(yè)，共七十六頁(yè)，編輯于2023年，星期三例：但在中常用的是所謂的“算子范數(shù)”,稱

為A的算子范數(shù)。易知：稱為矩陣范數(shù)和向量范數(shù)相容。注意：向量范數(shù)與矩陣算子范數(shù)相容。常用的算子范數(shù)為：

行范數(shù)：

列范數(shù)：

第八頁(yè)，共七十六頁(yè)，編輯于2023年，星期三相關(guān)結(jié)論：1)對(duì)任意n階矩陣A，，（可以是算子范數(shù)，也可以是一般范數(shù)）

論證：設(shè)為A的特征值，為對(duì)應(yīng)的特征向量

兩邊取算子范數(shù)：

第九頁(yè)，共七十六頁(yè)，編輯于2023年，星期三若為一般矩陣范數(shù)，設(shè)

,λ對(duì)應(yīng)的特征向量為ξ，ξ≠0Aξ=λξ,令矩陣,使B≠0,其中它一定存在。2)對(duì)任意n階矩陣A，總存在一個(gè)算子范數(shù)3)對(duì)n階矩陣A，若A的算子范數(shù)‖A‖<1,則E±A可逆,且論證：反證：若E±A不可逆，即（E±A）X=0有非零解ξ≠0即（E±A）ξ=0,即有‖A‖≥1,矛盾。

4）上的范數(shù)均等價(jià),即對(duì)上的兩個(gè)范數(shù)及,存在常數(shù)C1>0,C2>0.使第十頁(yè)，共七十六頁(yè)，編輯于2023年，星期三3.向量列及矩陣列的收斂定義1：給定的向量列及向量

若

結(jié)論：

論證：提示取范數(shù)為定義2：

結(jié)論：‖·‖為任意范數(shù)

特別當(dāng)n=1，A=a，

第十一頁(yè)，共七十六頁(yè)，編輯于2023年，星期三§2Gauss消元法一、基本思想回憶：方程組的初等變換：1)互換兩個(gè)方程2)某個(gè)方程的非零倍數(shù)3)某個(gè)方程的非零倍數(shù)加到另一個(gè)方程上

對(duì)應(yīng)線性方程組Ax=b，用矩陣的語(yǔ)言描述：即為增廣矩陣（A,b）的初等行變換對(duì)列初等變換，除列交換之外，其余兩種變換雖可作，但得到的新方程組與原來(lái)的方程組不等價(jià)

特別注意的是：列交換時(shí)須記錄！

顯然：方程組經(jīng)過(guò)初等變換變成等價(jià)的方程組。第十二頁(yè)，共七十六頁(yè)，編輯于2023年，星期三下面討論Gauss消元法：對(duì)給定的方程組：Ax=b。經(jīng)過(guò)一系列的方程組的初等變換，將Ax=b轉(zhuǎn)化為Ux=g（U為上三角矩陣，稱Ux=g為上三角方程組）或Lx=f（L為下三角矩陣，稱Lx=f為下三角方程組）然后回代即可求解，此即為Gauss消元法的基本思想。解釋“回代”對(duì)Ux=g，即

從倒數(shù)第一個(gè)方程求解，依次求得：類似地Lx=f：

第十三頁(yè)，共七十六頁(yè)，編輯于2023年，星期三二、計(jì)算過(guò)程

消元過(guò)程一般化為上三角方程組計(jì)算過(guò)程

回代過(guò)程以上三角方程組為例，說(shuō)明如下：對(duì)已知，即為：設(shè)doing第十四頁(yè)，共七十六頁(yè)，編輯于2023年，星期三設(shè)：

doing：繼續(xù)以上過(guò)程，注意設(shè)得到上三角方程，，可以推出，無(wú)需假設(shè)然后回代即可求解。第十五頁(yè)，共七十六頁(yè)，編輯于2023年，星期三注Notes：①稱為消元的主元素。如何保證

有兩種途徑：1）若A可逆，總可以通過(guò)行交換使得（k，k）位置上的元素非零2）Th.1:為A的第k階順序主子式.

A可逆只能保證第n階順序主子式不為0，不能保證其他階為0.②消元過(guò)程的矩陣分析：第十六頁(yè)，共七十六頁(yè)，編輯于2023年，星期三以此類推：

均為單位下三角矩陣歸納有：(單位下三角矩陣的逆為單位下三角矩陣，乘積也為單位下三角矩陣)由此引進(jìn)如下更一般的三角分解的概念：定義：對(duì)n階矩陣A，若存在下三角陣L及上三角陣U，使A=L?U，則稱L?U為A的三角分解。

當(dāng)L為單位下三角矩陣時(shí)，稱L-U為Doolittel分解（D分解）

當(dāng)U為單位上三角矩陣時(shí)，稱L-U為Grout分解（G分解）第十七頁(yè)，共七十六頁(yè)，編輯于2023年，星期三Th.2：對(duì)n階矩陣A，當(dāng)A的順序主子式≠0（k=1,2，…，n-1），則A一定

存在D分解且D分解唯一。于是有:Gauss消元順利進(jìn)行另，為使主元，只要A可逆，交換AX=b的兩兩個(gè)方程組，可使位置上的元素非零，此時(shí)Gauss消元法可描述為，存在置換陣P使P?A=L?U。第十八頁(yè)，共七十六頁(yè)，編輯于2023年，星期三③Gauss消元法的改進(jìn)Gauss消元法的缺陷：Gauss消元法的改進(jìn)：切入點(diǎn)：主元素

方法：選主元+消元+回代第十九頁(yè)，共七十六頁(yè)，編輯于2023年，星期三具體步驟：第二十頁(yè)，共七十六頁(yè)，編輯于2023年，星期三（b）列主元素消元法常用

第二十一頁(yè)，共七十六頁(yè)，編輯于2023年，星期三消元④計(jì)算量

回代消元：步數(shù)12……n-1

除法n-1n-2……1

乘法n(n-1)(n-1)(n-2)……2×1

第二十二頁(yè)，共七十六頁(yè)，編輯于2023年，星期三

§3三角求解求法一、基本思想第二十三頁(yè)，共七十六頁(yè)，編輯于2023年，星期三第二十四頁(yè)，共七十六頁(yè)，編輯于2023年，星期三LU解法計(jì)算量與Gauss消元法計(jì)算量相同第二十五頁(yè)，共七十六頁(yè)，編輯于2023年，星期三二、特殊的LU解法對(duì)已知Ax=b，若A為某些特殊矩陣，LU解法亦有一些特殊變形，討論以下兩種情況。第二十六頁(yè)，共七十六頁(yè)，編輯于2023年，星期三第二十七頁(yè)，共七十六頁(yè)，編輯于2023年，星期三第二十八頁(yè)，共七十六頁(yè)，編輯于2023年，星期三

§4、誤差分析第二十九頁(yè)，共七十六頁(yè)，編輯于2023年，星期三一、解對(duì)系數(shù)的敏感性關(guān)于Ax=b的求解，以上所述均為精確解，故誤差分析只針對(duì)舍入誤差，而舍入誤差實(shí)質(zhì)上是一種絕對(duì)誤差。

對(duì)Ax=b，可能產(chǎn)生舍入誤差的來(lái)源是：A或b的微小變化（A及b會(huì)產(chǎn)生舍入誤差）。問(wèn)題：A或b的擾動(dòng)對(duì)Ax=b的解是否有影響？第三十頁(yè)，共七十六頁(yè)，編輯于2023年，星期三例題解得x1=2，x2=0。

擾動(dòng)b

解得x1=1，x2=1。第三十一頁(yè)，共七十六頁(yè)，編輯于2023年，星期三值得指出：

①A、b的擾動(dòng)是一種客觀存在；②A、b的擾動(dòng)對(duì)Ax=b的解有時(shí)會(huì)產(chǎn)生破壞作用。

此即為解對(duì)系數(shù)的敏感性，顯然，解對(duì)A、b的敏感性越大，對(duì)解的破壞性越大。反之亦然。

定義：對(duì)給定的線性方程組Ax=b，若A、b的微小擾動(dòng)對(duì)Ax=b的解產(chǎn)生很大的變化，稱為病態(tài)方程組，A為病態(tài)矩陣；反之，稱Ax=b為良性方程組，A稱為良態(tài)矩陣。第三十二頁(yè)，共七十六頁(yè)，編輯于2023年，星期三二、病態(tài)性分析給定Ax=b（|A|≠0），則Ax*=b，x*唯一存在。分三種情形：1.b擾動(dòng)，A不擾動(dòng)2.A擾動(dòng)，b不擾動(dòng)3.A以及b同時(shí)擾動(dòng)第三十三頁(yè)，共七十六頁(yè)，編輯于2023年，星期三1.b擾動(dòng)，A不擾動(dòng)b→b+δb，則此時(shí)x*→x*+δxA（x*+δx）=b+δb∴

Aδx=δb

∴

δx=A-1δb∴‖δx‖≤‖A-1‖·‖δb‖

又‖b‖=‖Ax*‖≤

‖A‖·‖x*‖1/

‖x*‖≤

‖A‖/‖b‖∴≤

‖A-1‖‖A‖‖δb‖·1/‖b‖易知‖A-1‖‖A‖越大,對(duì)解得變化影響越大。反之亦然。第三十四頁(yè)，共七十六頁(yè)，編輯于2023年，星期三2.A擾動(dòng)，b不擾動(dòng)A→A+δA，則此時(shí)x*→x*+δx

（A+δA）（x*+δx）=b

展開(kāi)得（A+δA）·δx=-δAx*

又A+δA=A（E+A-1δA）另設(shè)||A-1δA||≤||A-1||·||δA||＜1有E+A-1δA可逆，則‖(E+A-1δA)-1‖≤1/(1-‖A-1δA‖)≤1/(1-‖A-1‖‖δA‖)

第三十五頁(yè)，共七十六頁(yè)，編輯于2023年，星期三進(jìn)一步有：

δx=-(A+δA)-1δA·x*=-(E+A-1δA)-1A-1δAx*

‖δx‖≤‖(E+A-1δA)-1‖‖A-1‖‖δA‖‖x*‖≤1/(1-‖A-1‖‖δA‖)·‖A-1‖‖δA‖‖x*‖∴‖δx‖/‖x*‖≤‖A-1‖‖δA‖/(1-‖A-1‖‖δA‖)

≤

{‖A-1‖‖A‖‖δA‖/‖A‖}/{1-‖A-1‖‖A‖‖δA‖/‖A‖)}易知‖A-1‖‖A‖越大，對(duì)系數(shù)的擾動(dòng)起的擴(kuò)張作用越大，從而解的變化越大。反之亦然。第三十六頁(yè)，共七十六頁(yè)，編輯于2023年，星期三3.A以及b同時(shí)擾動(dòng)b→b+δb，A→A+δA，x*→x*+δx則（A+δA）（x*+δx）=b+δb同2.知得：同樣可看出‖A-1‖‖A‖對(duì)解的影響一樣的。由此引出下面的條件數(shù)的概念第三十七頁(yè)，共七十六頁(yè)，編輯于2023年，星期三條件數(shù)定義：對(duì)任意的n階可逆矩陣A，稱Cond(A)=

‖A-1‖‖A‖

為A的條件數(shù)。易知，Cond(A)越大，Ax=b病態(tài)程度越大。①常用的條件數(shù)Cond(A)∞=

‖A-1‖∞‖A‖∞Cond(A)2=

‖A-1‖2‖A‖2第三十八頁(yè)，共七十六頁(yè)，編輯于2023年，星期三②條件數(shù)性質(zhì)1.Cond(A)≥1Cond(A)=

‖A-1‖‖A‖≥

‖A-1A‖=12.對(duì)常數(shù)c≠0，Cond(cA)=Cond(A)3.若R為正交矩陣，則Cond(R)2=1

4.對(duì)任意的n階可逆陣A及正交陣R，有Cond(A)2=Cond(RA)2=Cond(AR)25.對(duì)任意的n階矩陣A、B有Cond(AB)≤Cond(A)·Cond(B)第三十九頁(yè)，共七十六頁(yè)，編輯于2023年，星期三三、病態(tài)性診斷及處理已知對(duì)任意的n階矩陣A,Cond(A)=

‖A-1‖

‖A‖但實(shí)際上的計(jì)算很困難例：書中P170，希爾伯特矩陣HnCond(H3)∞=748第四十頁(yè)，共七十六頁(yè)，編輯于2023年，星期三診斷及處理方法診斷1.出現(xiàn)小主元2.系數(shù)陣的行列式很小或某些行近似相關(guān)3.系數(shù)陣元素的大小分布差異性大處理方法1.高精度算法（雙倍字節(jié)）2.預(yù)處理3.迭代處理第四十一頁(yè)，共七十六頁(yè)，編輯于2023年，星期三四、事后估計(jì)設(shè)給定Ax=b，并設(shè)x^為精確解x*的近似值，則有‖x*-x^‖/‖x*‖≤Cond(A)·‖r‖/‖b‖其中r為剩余向量r=Ax*-Ax^=b-Ax^A(x*-x^)=r∴x*-x^=A-1r

第四十二頁(yè)，共七十六頁(yè)，編輯于2023年，星期三§5.5迭代求解法第四十三頁(yè)，共七十六頁(yè)，編輯于2023年，星期三一、基本思想給定Ax=b，|A|≠0，Ax*=b等價(jià)變形x=Bx+f變形的可行性是顯然的！a11x1+a12x2+…+a1nxn=b1x1=(1-a11)x1-a12x2-…-a1nxn+b1第四十四頁(yè)，共七十六頁(yè)，編輯于2023年，星期三任取x*的一個(gè)近似值X(0)=(x1(0),x2(0),…,xn(0))T視Bx+f為校正器！迭代x(1)=Bx(0)+fx(2)=Bx(1)+f…x(k+1)=Bx(k)+f生成向量列﹛x(k)﹜,若﹛x(k)﹜收斂，則其極限x*。第四十五頁(yè)，共七十六頁(yè)，編輯于2023年，星期三證明：x(k+1)=Bx(k)+f∴l(xiāng)imx(k+1)=Blimx(k)+f,k→∞

ξ=Bξ+f

故x=Bx+f的解

又因?yàn)榻馕ㄒ弧唳?x*

第四十六頁(yè)，共七十六頁(yè)，編輯于2023年，星期三

在﹛x(k)﹜收斂時(shí)，取充分大的自然數(shù)N，視x(N)≈x*,這種求解方法叫迭代法。命名：稱x=Bx+f為迭代方程組

稱B為迭代矩陣

稱x(k+1)=Bx(k)+f(校正過(guò)程)為迭代格式

稱﹛x(k)﹜為迭代列第四十七頁(yè)，共七十六頁(yè)，編輯于2023年，星期三NOTES：1.對(duì)給定的Ax=b，其等價(jià)迭代方程組不唯一!2.不同的初值x(0)或迭代矩陣B不同，得到不同的迭代列(有無(wú)窮多個(gè)迭代列)，但若收斂，其極限均

為x*。3.如何使得﹛x(k)﹜收斂？第四十八頁(yè)，共七十六頁(yè)，編輯于2023年，星期三

分析：因x(k)–x*=Bx(k-1)+f-(Bx*+f)=B(x(k-1)–x*)=B2(x(k-2)–x*)=…=Bk(x(0)–x*)

故有﹛x(k)﹜收斂x(k)–x*→0（向量），k→∞Bk(x(0)–x*)→0（向量），k→∞Bk→0（矩陣），k→∞

ρ(B)<1(譜半徑小于1)

第四十九頁(yè)，共七十六頁(yè)，編輯于2023年，星期三二、幾種常用的迭代格式（自始至終）1。Jacobi格式（J-格式,三種形式,分量式,分量濃縮式,矩陣式）①格式設(shè)計(jì)。已知Ax=b（|A|≠0）

即a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…an1x1+an2x2+…+annxn=bn

第五十頁(yè)，共七十六頁(yè)，編輯于2023年，星期三假設(shè)aii≠0,標(biāo)準(zhǔn)等價(jià)方程組x1=(-a12x2-a13x3-…-a1nxn+b1)/a11x2=(-a21x1-a23x3-…-a2nxn+b2)/a22

…xn=(-an1x1-an2x2-…-an,n-1xn-1+bn)/ann矩陣形式：X=BJX

+fJ

其中BJ=0-a12/a11-a13/a11…-a1n/a11-a21/a220-a23/a22…-a2n/a22-a31/a33-a32/a330…-a3n/a33…-an1/ann-an2/ann-an3/ann…0第五十一頁(yè)，共七十六頁(yè)，編輯于2023年，星期三fJ=(b1/a11,b2/a22,…,bn/ann)TJ格式：X(k+1)=BJx(k)+fJ

x1(k+1)=(-a12x2(k)-a13x3(K)-…-a1nxn(k)+b1)/a11x2(k+1)=(-a21x1(k)-a23x3(K)-…a2nxn(k)+b2)/a22