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

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

×n)的非奇異矩陣,x是要求解的n維未知向量,b是n維常向量2/6/2023華南師范大學數(shù)學科學學院謝驪玲線性方程組的解的存在性和唯一性定理3.4設A是N×N方陣，下列命題等價：給定任意N×1矩陣B，線性方程組AX=B有唯一解矩陣A是非奇異的（即A-1存在） 方程組AX=0有唯一解X=0det(A)≠02/6/2023華南師范大學數(shù)學科學學院謝驪玲線性方程組的解最常見的求線性方程組Ax=b的解的方法是在方程組兩側同乘以矩陣A的逆Gram法則：Ax=b2/6/2023華南師范大學數(shù)學科學學院謝驪玲線性方程組的解（續(xù)1）求逆運算和行列式計算由于運算量大，實際求解過程中基本不使用，僅作為理論上的定性討論克萊姆法則在理論上有著重大意義，但在實際應用中存在很大的困難，在線性代數(shù)中，為解決這一困難給出了高斯消元法還有三角分解法和迭代求解法2/6/2023華南師范大學數(shù)學科學學院謝驪玲解法分類關于線性方程組的數(shù)值解法一般有兩類直接法：若在計算過程中沒有舍入誤差，經(jīng)過有限步算術運算，可求得方程組的精確解的方法迭代法：用某種極限過程去逐步逼近線性方程組精確解的方法迭代法具有占存儲單元少，程序設計簡單，原始系數(shù)矩陣在迭代過程中不變等優(yōu)點，但存在收斂性及收斂速度等問題2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.3上三角線性方程組定義3.2N×N矩陣A=[aij]中的元素滿足對所有i>j，有aij=0，則稱矩陣A為上三角矩陣；如果A中的元素滿足對所有i<j，有aij=0，則稱矩陣A為下三角矩陣。定理3.5（回代）設AX=B是上三角線性方程組，如果akk≠0，其中k=1,2,…,N，則該方程組存在唯一解。2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.3上三角線性方程組（續(xù)1）定理3.6如果N×N矩陣A=[aij]是上三角矩陣或下三角矩陣，則條件akk≠0很重要，因為回代算法中包含對akk的除法。如果條件不滿足，則可能無解或有無窮解聯(lián)系定理3.4，可知要條件akk≠0成立才能保證方程組存在唯一解2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.3上三角線性方程組（續(xù)2）求解上三角線性方程組的回代算法最后2/6/2023華南師范大學數(shù)學科學學院謝驪玲上三角線性方程組的求解基本算法：

2/6/2023華南師范大學數(shù)學科學學院謝驪玲上三角線性方程組的求解（續(xù)1）2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元求解有N個方程和N個未知數(shù)的一般方程組AX=B的一般做法：構造一個等價的上三角方程組UX=Y，并利用回代法求解如果兩個N×N線性方程組的解相同，則稱二者等價對一個給定方程組進行初等變換，不會改變它的解2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)1）考慮一個簡單的例子：求解第二個方程，得第二個方程減去第一個方程除以3再乘以4得到的新方程，得到新的方程組：回代到第一個方程，得2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)2）考慮包含n個未知數(shù)的方程組or作如下行變換之后方程組的解向量x不變對調方程組的兩行用非零常數(shù)乘以方程組的某一行將方程組的某一行乘以一個非零常數(shù)，再加到另一行上

通過對增廣矩陣[A|B]進行如上的行變換求解2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)3）2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)4）2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)5）2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)6）利用3.3節(jié)的回代法求解上述上三角方程組2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)7）消去過程2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)8）回代過程2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)9）上述消去過程中，如果akk=0，則不能使用第k行消除第k列的元素，而需要將第k行與對角線下的某行進行交換，以得到一個非零主元。如果不能找到非零主元，則線性方程組的系數(shù)矩陣是奇異的，因此線性方程組不存在唯一解選主元以避免，如果此主元非零，則不換行；如果此主元為零，則尋找第p行下滿足的第1行，將此行與第p行互換，使新主元非零。平凡選主元策略2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.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,…,N2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)11）病態(tài)問題：矩陣A中元素的微小變化引起解的很大變化cond(A)=207.0122/6/2023華南師范大學數(shù)學科學學院謝驪玲圖形解釋2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.4高斯消去法和選主元（續(xù)12）一個線性方程組稱為是病態(tài)的，如果其系數(shù)矩陣接近奇異且它的行列式接近0矩陣條件數(shù)

cond(A)=||A||||A-1||2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.5三角分解法A=LU:下三角矩陣L的主對角線為1，上三角矩陣U的對角線元素非零定義3.4如果非奇異矩陣A可表示為下三角矩陣L和上三角矩陣U的乘積：A=LU，則A存在一個三角分解A非奇異蘊含著對所有的k有ukk≠0，k=1,2,3,4.2/6/2023華南師范大學數(shù)學科學學院謝驪玲矩陣的LU分解是否所有的非奇異矩陣A都能作LU分解呢？一個例子：N階方陣A有唯一LU分解的充要條件是A的各階順序主子式均不為零2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.5三角分解法（續(xù)1）

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

Ly=b

Ux=y易見：Ax=(LU)x=L(Ux)=Ly=b2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.5三角分解法（續(xù)2）

假設已有矩陣A:

對A作LU分解:

檢驗分解結果:2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.5三角分解法（續(xù)3）

構造一系列乘數(shù)矩陣M1,M2,M3,M4,…,MN-1使得:(MN-1…M4M3M2M1)A是上三角矩陣，把它重新記成U.對4×4矩陣A，M1可取:2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.5三角分解法（續(xù)4）M2可取:M3可取：2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.5三角分解法（續(xù)5）

則U=(M3M2M1)A是上三角形矩陣每個M矩陣都是下三角形矩陣

如M2的逆為:

注意到每個M矩陣的逆只是它自身下三角部分元素取相反數(shù)

A=(M3M2M1)-1

U

=(M1)-1(M2)-1(M3)-1

U

定義L=(M1)-1(M2)-1(M3)-1，則L就是一個對角元素全為1的下三角矩陣，因為所有的M矩陣的逆都是對角元素全為1的下三角矩陣2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.5三角分解法（續(xù)6）計算復雜性：高斯消去法與三角分解法的三角化過程是一樣的，都需要次乘法和除法次減法求解LUX=B又需要N2次乘法和除法，以及(N2-N)次減法2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.5三角分解法（續(xù)7）每一個M矩陣中都需要計算1/A(i,i)

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

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

帶選主元過程的LU分解2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.5三角分解法（續(xù)8）之前我們構造了一系列的M矩陣使得

是上三角矩陣現(xiàn)在我們構造一系列的M矩陣和P矩陣使得是上三角矩陣(MN-1….M4

M3

M2

M1)A(MN-1

PN-1

….M4

P4M3

P3M2

P2M1P1)A2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.6求解線性方程組的迭代法考慮線性方程組2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.6求解線性方程組的迭代法（續(xù)1）

高斯消去法

–受限于舍入誤差和病態(tài)性

迭代法

–另一種求解線性方程組的方法

給出初始估計值，通過迭代得到更好的解的近似值迭代法對求解大型線性方程組非常有效

Jacobi（雅可比）和Gauss-Seidel（高斯-賽德爾）方法2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.6求解線性方程組的迭代法（續(xù)2）將方程組改寫成每個方程的左邊只有一個未知數(shù)的形式：給出初始估計值和迭代規(guī)則2/6/2023華南師范大學數(shù)學科學學院謝驪玲Jacobi迭代法初始估計值迭代一步后的結果：2/6/2023華南師范大學數(shù)學科學學院謝驪玲Jacobi迭代法（續(xù)1）k步迭代后的結果：2/6/2023華南師范大學數(shù)學科學學院謝驪玲Jacobi迭代法（續(xù)2）例：Jacobi迭代公式：2/6/2023華南師范大學數(shù)學科學學院謝驪玲Jacobi迭代法（續(xù)3）初始迭代值20步迭代后2/6/2023華南師范大學數(shù)學科學學院謝驪玲Jacobi迭代法（續(xù)4）迭代會不會收斂到方程組的解？迭代到何時會終止？終止的判斷條件是什么？兩個必須考慮的問題：2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.6求解線性方程組的迭代法（續(xù)3）定義3.6設有N×N維矩陣A，如果其中k＝1,2,…,N則稱A具有嚴格對角優(yōu)勢（嚴格對角占優(yōu)）。定理3.15（雅可比迭代）設矩陣A具有嚴格對角優(yōu)勢，則AX=B有唯一解X=P。利用雅可比迭代可產(chǎn)生一個向量序列{Pk}，而且對于任意初始向量P0，向量序列都將收斂到P。2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.6求解線性方程組的迭代法（續(xù)4）向量之間的距離可以用來判斷{Pk}是否收斂到P。因為兩個向量P=(x1,x2,…,xN)和Q=(y1,y2,…,yN)之間的歐幾里德距離計算復雜；而1－范數(shù)具有度量的數(shù)學結構，也適合作為一個一般化的“距離公式”。而且根據(jù)線性代數(shù)的理論可知，如果兩個向量的||＊||1范數(shù)接近，則它們的歐幾里德范數(shù)||＊||2也接近。所以定義兩個N維向量的距離為||＊||1范數(shù)，用來確定N維空間中的收斂性2/6/2023華南師范大學數(shù)學科學學院謝驪玲3.6求解線性方程組的迭代法（續(xù)5）1-范數(shù)：滿足一般向量范數(shù)的性質定理3.16設X和Y是N維向量，c是一個標量。則函數(shù)||X||有如下性質：正定性：||X||≥0，||X||=0當且僅當X=0齊次性：||cX||=|c|·