《計(jì)算方法》課件第3章

第3章線性方程組的數(shù)值解法3.1引言3.2高斯(Gauss)消去法及其改進(jìn)3.3直接分解法3.4解線性方程組的迭代法3.5向量范數(shù)、矩陣范數(shù)及迭代法的收斂性 3.1引言

在自然科學(xué)和工程技術(shù)中很多問題的解決常常歸結(jié)為解線性方程組，例如電學(xué)中的網(wǎng)絡(luò)問題、用最小二乘法進(jìn)行實(shí)驗(yàn)數(shù)據(jù)的曲線擬合問題、無線傳感器節(jié)點(diǎn)定位問題、解非線性方程組問題、用差分法或者有限元方法解常微分方程和偏微分方程邊值問題等,都需要求解線性代數(shù)方程組。因此線性方程組的數(shù)值解法是一個應(yīng)用非常廣泛的研究課題。設(shè)線性方程組為(3.1)其中aij，bi(i，j=1，2，…，n)為常數(shù),則方程組(3.1)可寫成矩陣形式：其中,(3.2)

當(dāng)det(A)=D≠0時，由線性代數(shù)中的克萊姆(Cramer)法則，方程組Ax=b的解存在，且有唯一解，其解為(3.3)其中Di為系數(shù)矩陣A的第i列元素以b代替后的矩陣行列式的值?？巳R姆法則在矩陣的研究中具有重要的理論價值，但是在實(shí)際計(jì)算中，其計(jì)算量非常大。按照克萊姆法則求解方程組，需要計(jì)算n+1個n階行列式。每個n階行列式按照直接展開式計(jì)算需要(n-1)×n!次乘法和n次除法。當(dāng)n較大時，這個數(shù)字十分驚人，即使目前最快的計(jì)算機(jī)也難以滿足實(shí)際需求。因此，需要找到實(shí)用且可行的方法求解方程組。

線性方程組的解法可以歸納為直接法和迭代法。理論上講，直接法經(jīng)過有限次四則運(yùn)算，假設(shè)運(yùn)算過程中沒有誤差產(chǎn)生，則最后得到的就是精確解，但是計(jì)算機(jī)在運(yùn)算過程中必然會產(chǎn)生誤差，因此，直接法也不一定能夠得到絕對的精確解。迭代法將線性方程組的求解過程看做是不斷向真實(shí)解逼近的向量序列，在迭代過程中得到的向量值是解的近似值，當(dāng)達(dá)到需要的精度時,迭代過程停止，獲得最終解。 3.2高斯(Gauss)消去法及其改進(jìn)

3.2.1三角形方程組及其求解

下列形狀的方程組容易求解。

(1)對于對角形方程組：(3.4)設(shè)aii≠0，對每個方程可以得到(3.5)

(2)對于下三角方程組:(3.6)若設(shè)lii≠0，按照方程組的順序，從第1個方程至第n個方程，逐個解出xi(i=1，2，…，n),即(3.7)

(3)對于上三角方程組:(3.8)(3.9)3.2.2高斯消去法

首先舉一個簡單的例子來說明高斯消去法的基本思想。

例3－1用高斯消去法解方程組：解將方程①乘以“-2”后加到方程②，可得從而解得x2=3，代入①求得x1=8。上述求解過程相當(dāng)于對方程組的增廣矩陣作初等行變換,即

通過上述變換，將原方程組化為等價的上三角方程組，先解出x2，再回代得到x1

。由此可以看出,高斯消去法的基本步驟由兩部分組成：第一部分是從上至下依次將變量的系數(shù)消去，形成上三角矩陣；第二部分是通過從下至上的求解過程依次求解出x

n，xn－1，…，x1。一般地，對線性方程組，設(shè)其系數(shù)矩陣A滿足det(A)≠0，高斯消去法分為以下幾步：

(1)第1步消元。對線性方程組的增廣矩陣(3.10)從第2行開始作初等行變換,將x1的系數(shù)消去，使系數(shù)變?yōu)?，即得(3.11)其中：(3.12)

(2)第k步消元(1≤k≤n－1)。設(shè)已經(jīng)完成k－1次消元，得到等價方程組A(k)x=b(k)，即(3.13)假設(shè)此時，需要將的系數(shù)消去變?yōu)?，即(3.14)其中：(3.16)(3.15)

(3)當(dāng)k=n－1時，消去過程結(jié)束，原方程組化為等價的上三角方程組,即(3.17)

(4)回代求解，通過回代計(jì)算可以得到方程組的解,即(3.18)3.2.3列主元高斯消去法

在前面介紹的消去法中，未知量按照在方程組中的順序消去，又稱為自然消去法，在每一步消元過程中需要假設(shè)，否則無法繼續(xù)進(jìn)行，而實(shí)際上只要det(A)≠0，方程組Ax=b就有解。同時，若很小，運(yùn)算過程中將其作為分母就會導(dǎo)致產(chǎn)生嚴(yán)重誤差，得不到正確結(jié)果。

例3－2解如下方程組(取5位有效數(shù)字)：解采用高斯消去法，方程組轉(zhuǎn)化為求解得到x2=0.6667，x1=0。經(jīng)檢驗(yàn)知，該結(jié)果不正確。如果交換兩個方程的順序，得到等價方程組：經(jīng)過高斯消去法，方程組化為

(3)回代計(jì)算,即例3－3用列主元高斯消去法解方程組：解選擇當(dāng)前列中絕對值最大元素，并進(jìn)行行交換,即將該列對角線下的元素消去，變?yōu)?,即進(jìn)行下一次操作： 3.3直接分解法

設(shè)則有設(shè)且則設(shè)，3.3.2杜立特爾(Doolittle)分解

如果將矩陣A分解為A=LU，其中L為下三角矩陣，U為上三角矩陣，則方程Ax=b轉(zhuǎn)化為LUx=b，設(shè)y=Ux，原方程化為Ly=b，y=Ux，系數(shù)矩陣分別為下三角矩陣和上三角矩陣，則方程很容易求解。稱將矩陣A分解為下三角和上三角矩陣的乘積為杜立特爾分解。

下面考慮對A直接進(jìn)行LU分解的步驟，設(shè)det(A)≠0，分解的最后結(jié)果如下:(3.19)步驟如下：②對主對角線下面列元素來說，有(3.21)①對主對角線(含)上面行元素來說，有(3.20)從而解得未知參數(shù)為(3.22)計(jì)算出三角矩陣L和U后即可通過解兩個方程組，求得所需的x。

①下三角方程組：Ly=b，(3.23)②上三角方程組：(3.24)

例3－4已知Ax=b，做A的LU分解，并解方程組，其中,解根據(jù)算法可得對Ly=b進(jìn)行回代求解可得y=[281824]T，再對Ux=y進(jìn)行回代，得x=［－11－11]T。 3.4解線性方程組的迭代法

3.4.1雅可比(Jacobi)迭代法

若方程組Ax=b可寫成等價形式:則給定一個初始向量x(0)，可以得到迭代公式(k=0，1，…)(3.25)若上式確定的向量序列{x(k)}收斂于確定的向量x*，則顯然是方程組Ax=b的解。下面以三元方程組為代表進(jìn)行說明，解方程組Ax=b，其中,將方程組化為如下的形式(3.26)將aiixi移到等號的左側(cè)，變?yōu)楦鶕?jù)這個等式可以設(shè)計(jì)出迭代公式:即(3.27)稱該求解方法為雅可比迭代法。雅可比迭代法的求解公式可以表示為(3.28)更改為稱該求解方法為高斯－賽德爾迭代法。高斯－賽德爾迭代法的求解公式可以表示為3.4.3迭代法的精度判斷

通常用迭代偏差來刻畫迭代的精度，當(dāng)e小于給定值時，計(jì)算結(jié)束。

例3－5試用雅可比迭代法和高斯－賽德爾迭代法解下列線性方程組，使迭代誤差小于10－4。

解選取初值x(0)=(0，0，0)T，并寫出雅可比迭代公式,即反復(fù)迭代，計(jì)算結(jié)果見表3.1。表3.1例3－5的雅可比迭代法計(jì)算結(jié)果

從表3.1可以看出當(dāng)?shù)螖?shù)k=10時，滿足誤差要求，方程組的解為x1=1.09998，x2=1.19998，x3=1.29997。

選取初值x(0)=(0，0，0)T，并寫出高斯－賽德爾迭代公式,即反復(fù)迭代，計(jì)算結(jié)果見表3.2。從表3.2可以看出當(dāng)?shù)螖?shù)k=6時，滿足誤差要求，方程組的解為x1=1.09999，x2=1.19999，x3=1.3。表3.2例3－5的高斯－賽德爾迭代法計(jì)算結(jié)果3.4.4迭代法的矩陣表示

方程組Ax=b是隱式的計(jì)算形式，則給定一個初始向量x(0)，可以得到迭代公式若式(3.30)確定的向量序列{x(k)}收斂于確定的向量x*，則顯然是方程組Ax=b的解。式(3.30)中的B稱為迭代矩陣，如何構(gòu)造合適的迭代矩陣B，使求解過程快速收斂，是需要研究的重要問題。

1.雅可比迭代法的矩陣表示

設(shè)方程組的系數(shù)矩陣A可以分解為對角矩陣D、嚴(yán)格下三角矩陣L和嚴(yán)格上三角矩陣U，即

A=D+L+U

則所給方程組Ax=b化為由此得到雅可比迭代公式的矩陣表示為(3.31)即雅可比迭代法公式(3.25)中的(3.32)也可以采用如下方法推導(dǎo)：與上面的結(jié)果完全一致。

2.高斯－賽德爾迭代法的矩陣表示

由(D+L+U)x=b可得從而得出如下迭代公式：對式(3.33)進(jìn)行整理，有進(jìn)而得這就是高斯－賽德爾迭代法的矩陣表達(dá)式。(3.33)(3.34)3.5向量范數(shù)、矩陣范數(shù)及迭代法的收斂性

3.5.1向量范數(shù)

向量范數(shù)可以看做是描述向量“大小”的一種度量。范數(shù)最簡單的例子是絕對值函數(shù)。絕對值函數(shù)有三個性質(zhì)：范數(shù)的另一個簡單例子是三維歐氏空間的長度，設(shè)x=(x1，x2，x3)，則x的歐氏范數(shù)定義為可以證明，歐氏范數(shù)也滿足上面所提到的三個性質(zhì)。

定義3.1設(shè)V是數(shù)域F上的向量空間，對V中任一向量σ，都有唯一實(shí)數(shù)與之對應(yīng)，滿足如下三個條件：Rn上的常見范數(shù)有以下幾種：

(1)1－范數(shù):(3.35)(2)2－范數(shù)，也稱為歐氏范數(shù):(3.36)(3)∞－范數(shù):(3.37)不難驗(yàn)證，上述三種范數(shù)都滿足定義3.1中的條件。上述形式的統(tǒng)一表達(dá)式為(3.38)

例3－6設(shè)x=[243]，求。

解根據(jù)定義可算得

定義3.3矩陣A的特征值中，絕對值最大的稱為A的譜半徑，記為(3.39)對于n階方陣A，常見的范數(shù)有以下幾種：(1)1－范數(shù):(3.40)該范數(shù)是列絕對值之和的最大值，因此又稱為“列和范數(shù)”。

(2)2－范數(shù):(3.41)該范數(shù)是ATA的譜半徑的開方。(3)∞－范數(shù):(3.42)該范數(shù)是行絕對值之和的最大值，也稱為“行和范數(shù)”。不難驗(yàn)證，上述三種范數(shù)都滿足定義的條件。

由于在大多數(shù)與估計(jì)有關(guān)的問題中，矩陣和向量會同時參與討論，因此希望不等式(3.43)成立,以方便運(yùn)算，但是對任意的向量范數(shù)與矩陣范數(shù)卻未必如此。因此，把滿足式(3.43)關(guān)系的向量范數(shù)和矩陣范數(shù)稱為相容的。當(dāng)向量范數(shù)和矩陣范數(shù)相容時，常常不作特殊說明。以下常見的范數(shù)滿足相容關(guān)系：解根據(jù)定義可算得求其最大特征值:所以

定理3.1矩陣A的任一特征值的絕對值不超過A的范數(shù)‖A‖。

證明設(shè)λ為矩陣A的任一特征值，e為相應(yīng)的特征向量，且不為0，則λe=Ae，對該等式兩邊取范數(shù)可得根據(jù)向量范數(shù)和矩陣范數(shù)的相容性有所以從而定理得證。根據(jù)定理3.1,由于矩陣A的譜半徑 ,故可得ρ(A)≤||A||。3.5.3迭代法的收斂性

定理3.2對任意初始向量x(0)及常向量g，迭代法收斂的充分必要條件是迭代矩陣B的譜半徑ρ(B)<1。

定理3.2在理論上具有重要價值，但實(shí)際應(yīng)用起來不太方便。當(dāng)n較大時，不容易計(jì)算譜半徑，但由于ρ(B)<||