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

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

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

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

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

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

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

Ly=b

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

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

對(duì)A作LU分解:

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

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

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

如M2的逆為:

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

A=(M3M2M1)-1

U

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

U

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

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

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

帶選主元過(guò)程的LU分解2/6/2023華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲3.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)A2/6/2023華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲3.6求解線性方程組的迭代法考慮線性方程組2/6/2023華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院謝驪玲3.6求解線性方程組的迭代法（續(xù)1）

高斯消去法

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

迭代法

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

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

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