線性方程組AX=B的數(shù)值解法(j)

第3章線性方程組AX=B的數(shù)值解法1/24/2024編輯ppt引言在自然科學(xué)和工程技術(shù)中很多問題的解決常常歸結(jié)為解線性代數(shù)方程組。例如電學(xué)中的網(wǎng)絡(luò)問題，船體數(shù)學(xué)放樣中建立三次樣條函數(shù)問題，用最小二乘法求實(shí)驗(yàn)數(shù)據(jù)的曲線擬合問題，解非線性方程組問題，用差分法或者有限元法解常微分方程，偏微分方程邊值問題等都導(dǎo)致求解線性方程組，而且后面幾種情況常常歸結(jié)為求解大型線性方程組。線性代數(shù)方面的計算方法就是研究求解線性方程組的一些數(shù)值解法與研究計算矩陣的特征值及特征向量的數(shù)值方法。1/24/2024編輯ppt線性方程組求解問題考慮線性方程組Ax=b其中A是一個(n

×n)的非奇異矩陣,x是要求解的n維未知向量,b是n維常向量1/24/2024編輯ppt線性方程組的解的存在性和唯一性定理3.4設(shè)A是N×N方陣，以下命題等價：給定任意N×1矩陣B，線性方程組AX=B有唯一解矩陣A是非奇異的〔即A-1存在〕 方程組AX=0有唯一解X=0det(A)≠01/24/2024編輯ppt線性方程組的解最常見的求線性方程組Ax=b的解的方法是在方程組兩側(cè)同乘以矩陣A的逆Gram法那么：Ax=b1/24/2024編輯ppt線性方程組的解〔續(xù)1〕求逆運(yùn)算和行列式計算由于運(yùn)算量大，實(shí)際求解過程中根本不使用，僅作為理論上的定性討論克萊姆法那么在理論上有著重大意義，但在實(shí)際應(yīng)用中存在很大的困難，在線性代數(shù)中，為解決這一困難給出了高斯消元法還有三角分解法和迭代求解法1/24/2024編輯ppt解法分類關(guān)于線性方程組的數(shù)值解法一般有兩類直接法：假設(shè)在計算過程中沒有舍入誤差，經(jīng)過有限步算術(shù)運(yùn)算，可求得方程組的精確解的方法迭代法：用某種極限過程去逐步逼近線性方程組精確解的方法迭代法具有占存儲單元少，程序設(shè)計簡單，原始系數(shù)矩陣在迭代過程中不變等優(yōu)點(diǎn)，但存在收斂性及收斂速度等問題1/24/2024編輯ppt3.3上三角線性方程組定義3.2N×N矩陣A=[aij]中的元素滿足對所有i>j，有aij=0，那么稱矩陣A為上三角矩陣；如果A中的元素滿足對所有i<j，有aij=0，那么稱矩陣A為下三角矩陣。定理3.5〔回代〕設(shè)AX=B是上三角線性方程組，如果akk≠0，其中k=1,2,…,N，那么該方程組存在唯一解。1/24/2024編輯ppt3.3上三角線性方程組〔續(xù)1〕定理3.6如果N×N矩陣A=[aij]是上三角矩陣或下三角矩陣，那么條件akk≠0很重要，因?yàn)榛卮惴ㄖ邪瑢kk的除法。如果條件不滿足，那么可能無解或有無窮解聯(lián)系定理3.4，可知要條件akk≠0成立才能保證方程組存在唯一解1/24/2024編輯ppt3.3上三角線性方程組〔續(xù)2〕求解上三角線性方程組的回代算法最后1/24/2024編輯ppt上三角線性方程組的求解根本算法：

1/24/2024編輯ppt上三角線性方程組的求解〔續(xù)1〕1/24/2024編輯ppt3.4高斯消去法和選主元求解有N個方程和N個未知數(shù)的一般方程組AX=B的一般做法：構(gòu)造一個等價的上三角方程組UX=Y，并利用回代法求解如果兩個N×N線性方程組的解相同，那么稱二者等價對一個給定方程組進(jìn)行初等變換，不會改變它的解1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)1〕考慮一個簡單的例子：求解第二個方程，得第二個方程減去第一個方程除以3再乘以4得到的新方程，得到新的方程組：回代到第一個方程，得1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)2〕考慮包含n個未知數(shù)的方程組or作如下行變換之前方程組的解向量x不變對調(diào)方程組的兩行用非零常數(shù)乘以方程組的某一行將方程組的某一行乘以一個非零常數(shù)，再加到另一行上

通過對增廣矩陣[A|B]進(jìn)行如上的行變換求解1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)3〕1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)4〕1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)5〕1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)6〕利用3.3節(jié)的回代法求解上述上三角方程組1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)7〕消去過程1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)8〕回代過程1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)9〕上述消去過程中，如果akk=0，那么不能使用第k行消除第k列的元素，而需要將第k行與對角線下的某行進(jìn)行交換，以得到一個非零主元。如果不能找到非零主元，那么線性方程組的系數(shù)矩陣是奇異的，因此線性方程組不存在唯一解選主元以防止，如果此主元非零，那么不換行；如果此主元為零，那么尋找第p行下滿足的第1行，將此行與第p行互換，使新主元非零。平凡選主元策略1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)10〕選主元以減少誤差：把元素中的最大絕對值移到主對角線上例3.17和3.18偏序選主元策略|akp|=max{|app|,|app+1|,…,|aN-1p|,|aNp|}按比例偏序選主元〔平衡〕策略sr=max{|arp|,|arp+1|,…,|arN|}其中r=p,p+1,…,N1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)11〕病態(tài)問題：矩陣A中元素的微小變化引起解的很大變化

cond(A)=207.0121/24/2024編輯ppt圖形解釋1/24/2024編輯ppt3.4高斯消去法和選主元〔續(xù)12〕一個線性方程組稱為是病態(tài)的，如果其系數(shù)矩陣接近奇異且它的行列式接近0矩陣條件數(shù)

cond(A)=||A||||A-1||1/24/2024編輯ppt3.5三角分解法A=LU:下三角矩陣L的主對角線為1，上三角矩陣U的對角線元素非零定義3.4如果非奇異矩陣A可表示為下三角矩陣L和上三角矩陣U的乘積：A=LU，那么A存在一個三角分解A非奇異蘊(yùn)含著對所有的k有ukk≠0，k=1,2,3,4.1/24/2024編輯ppt矩陣的LU分解是否所有的非奇異矩陣A都能作LU分解呢？一個例子：N階方陣A有唯一LU分解的充要條件是A的各階順序主子式均不為零1/24/2024編輯ppt3.5三角分解法〔續(xù)1〕

利用前代/回代算法求解形如Lx=b或Ux=b的線性方程組是容易的如果對一個給定的矩陣A，能夠找到一個下三角矩陣L和一個上三角矩陣U，使A=LU那么求解線性方程組Ax=b的問題可以分解成兩個簡單的問題：

Ly=b

Ux=y易見：Ax=(LU)x=L(Ux)=Ly=b1/24/2024編輯ppt3.5三角分解法〔續(xù)2〕

假設(shè)已有矩陣A:

對A作LU分解:

檢驗(yàn)分解結(jié)果:1/24/2024編輯ppt3.5三角分解法〔續(xù)3〕

構(gòu)造一系列乘數(shù)矩陣M1,M2,M3,M4,…,MN-1使得:(MN-1…M4M3M2M1)A是上三角矩陣，把它重新記成U.對4×4矩陣A，M1可取:1/24/2024編輯ppt3.5三角分解法〔續(xù)4〕M2可取:M3可取：1/24/2024編輯ppt3.5三角分解法〔續(xù)5〕那么U=(M3M2M1)A是上三角形矩陣每個M矩陣都是下三角形矩陣如M2的逆為:

注意到每個M矩陣的逆只是它自身下三角局部元素取相反數(shù)A=(M3M2M1)-1U

=(M1)-1(M2)-1(M3)-1U定義L=(M1)-1(M2)-1(M3)-1，那么L就是一個對角元素全為1的下三角矩陣，因?yàn)樗械腗矩陣的逆都是對角元素全為1的下三角矩陣1/24/2024編輯ppt3.5三角分解法〔續(xù)6〕計算復(fù)雜性：高斯消去法與三角分解法的三角化過程是一樣的，都需要次乘法和除法次減法求解LUX=B又需要N2次乘法和除法，以及(N2-N)次減法1/24/2024編輯ppt3.5三角分解法〔續(xù)7〕每一個M矩陣中都需要計算1/A(i,i)

當(dāng)?shù)趇個對角元素為0或者很接近0時就沒法計算M，這時A的直接LU分解就沒法繼續(xù)進(jìn)行

可以將第i行與它下面的某一行互換，該行的第i列元素非零

帶選主元過程的LU分解1/24/2024編輯ppt3.5三角分解法〔續(xù)8〕之前我們構(gòu)造了一系列的M矩陣使得是上三角矩陣現(xiàn)在我們構(gòu)造一系列的M矩陣和P矩陣使得是上三角矩陣(MN-1….M4

M3

M2

M1)A(MN-1

PN-1

….M4

P4M3

P3M2

P2M1P1)A1/24/2024編輯ppt3.6求解線性方程組的迭代法考慮線性方程組1/24/2024編輯ppt3.6求解線性方程組的迭代法〔續(xù)1〕高斯消去法–受限于舍入誤差和病態(tài)性迭代法–另一種求解線性方程組的方法給出初始估計值，通過迭代得到更好的解的近似值迭代法對求解大型線性方程組非常有效Jacobi〔雅可比〕和Gauss-Seidel〔高斯-賽德爾〕方法1/24/2024編輯ppt3.6求解線性方程組的迭代法〔續(xù)2〕將方程組改寫成每個方程的左邊只有一個未知數(shù)的形式：給出初始估計值和迭代規(guī)那么1/24/2024編輯pptJacobi迭代法初始估計值迭代一步后的結(jié)果：1/24/2024編輯pptJacobi迭代法〔續(xù)1〕k步迭代后的結(jié)果：1/24/2024編輯pptJacobi迭代法〔續(xù)2〕例：Jacobi迭代公式：1/24/2024編輯pptJacobi迭代法〔續(xù)3〕初始迭代值20步迭代后1/24/2024編輯pptJacobi迭代法〔續(xù)4〕迭代會不會收斂到方程組的解？迭代到何時會終止？終止的判斷條件是什么？兩個必須考慮的問題：1/24/2024編輯ppt3.6求解線性方程組的迭代法〔續(xù)3〕定義3.6設(shè)有N×N維矩陣A，如果其中k＝1,2,…,N那么稱A具有嚴(yán)格對角優(yōu)勢〔嚴(yán)格對角占優(yōu)〕。定理3.15〔雅可比迭代〕設(shè)矩陣A具有嚴(yán)格對角優(yōu)勢，那么AX=B有唯一解X=P。利用雅可比迭代可產(chǎn)生一個向量序列{Pk}，而且對于任意初始向量P0，向量序列都將收斂到P。1/24/2024編輯ppt3.6求解線性方程組的迭代法〔續(xù)4〕向量之間的距離可以用來判斷{Pk}是否收斂到P。因?yàn)閮蓚€向量P=(x1,x2,…,xN)和Q=(y1,y2,…,yN)之間的歐幾里德距離計算復(fù)雜；而1－范數(shù)具有度量的數(shù)學(xué)結(jié)構(gòu)，也適合作為一個一般化的“距離公式〞。而且根據(jù)線性代數(shù)的理論可知，如果兩個向量的||＊||1范數(shù)接近，那么它們的歐幾里德范數(shù)||＊||2也接近。所以定義兩個N維向量的距離為||＊||1范數(shù)，用來確定N維空間中的收斂性1/24/2024編輯ppt3.6求解線性方程組的迭代法〔續(xù)5〕1-范數(shù)：滿足一般向量范數(shù)的性質(zhì)定理3.16設(shè)X和Y是N維向量，c是一個標(biāo)量。那么函數(shù)||X||有如下性質(zhì)：正定性：||X||≥0，||X||=0當(dāng)且僅當(dāng)X=0齊次性：||cX||=|c|·||X||三角不等式：||X+Y||≤||X||+||Y||1/24/2024編輯pptGauss-Seidel迭代法初始估計值迭代一步后的結(jié)果：1/24/2024編輯ppt

每一次迭代新產(chǎn)生的被認(rèn)為是比更好的xj的近似值，所以在計算xj+1時用來替換是合理的Gauss-Seidel迭代法〔續(xù)1〕k步迭代后的結(jié)果：

矩陣A具有嚴(yán)格對角優(yōu)勢時，高斯－賽德爾迭代收斂1/24/2024編輯pptGauss-Seidel迭代法〔續(xù)2〕1步G-S迭代之后：

迭代