地球物理計算方法第一章

第一章

線性方程組的數(shù)值解法2/47本章內(nèi)容§1.1

引言§1.2

高斯消去法§1.3

選主元素的高斯消去法§1.4

矩陣的三角分解§1.5解三對角線方程組的追趕法§1.6解對稱正定矩陣方程組的平方根法§1.7向量和矩陣的范數(shù)§1.8解線性方程組的迭代法§1.9病態(tài)方程組和迭代改善法3/47本章要求1.理解高斯消去法的基本原理，熟練掌握高斯主元消去法；2.理解矩陣的三角分解；3.掌握解三對角線方程組的追趕法，掌握平方根法；4.了解矩陣范數(shù)、條件數(shù)。5.熟悉簡單迭代法及其收斂條件的使用;6.熟悉Jacobi迭代法及其相應(yīng)的Seidel迭代法的計算公式以及它們的收斂條件;7.熟悉SOR方法的計算公式及其收斂條件。4/47§1.1引言本節(jié)內(nèi)容一.線性方程組解法二.直接法與迭代法比較5/47§1.1引言一.線性方程組解法工程中幾乎有一半的問題涉及到線性方程組的求解設(shè)n階線性方程組6/47§1.1引言A

稱為方程組的系數(shù)矩陣，當是n階非奇異矩陣時，既A0，此時方程組有唯一解。

X陣是解向量，B陣是常向量。在線性代數(shù)中學(xué)過用克萊姆法則求解，它是一種直接法(屬于解析法)，但隨著n計算工作量7/47§1.1引言自學(xué)并理解8/47§1.1引言二.直接法與迭代法比較各有優(yōu)缺點解方程組的數(shù)值解法：直接法與迭代法優(yōu)缺點比較直接法：經(jīng)有限次計算得準確解(在無舍入誤差下),實際上舍入誤差客觀存在,得到的依然還是近似解。由于受到計算機存儲容量的限制，一般來說，僅適于系數(shù)矩陣階數(shù)不太高的問題，其工作量(計算量)較小、精度較高，但程序設(shè)計復(fù)雜。迭代法將問題構(gòu)成一個無窮序列，逼近準確解。主要用于某些系數(shù)矩陣階數(shù)較高的問題，一般來說，程序較為簡單、易于編程，但存在收斂性及收斂速度的問題，只對具有某些性質(zhì)的系數(shù)矩陣的方程組才適用。工作量有時較大。9/47§1.1引言實際計算時，應(yīng)根據(jù)問題的特點和要求來決定方法的取舍。本章介紹的求解線性代數(shù)方程組的直接法有Gauss(高斯)消元法和LU分解等；迭代法有Jacobi(雅可比)迭代和Gauss-Seidel(高斯-賽德爾)迭代。10/47§1.2高斯消去法本節(jié)內(nèi)容一.引言二.例子三.順序Gauss消去法四.Gauss消去法計算量返回章節(jié)目錄順序高斯消去法11/47一.引言是一個古老的求解線性方程組的方法。改進和變形得到高斯選主元素消去法（第3節(jié)）、三角分解法（第4節(jié)）n元線性方程組的直接解法?！?.2高斯消去法（式1）12/47方程組(1)的矩陣形式為Ax=b

其中§1.2高斯消去法13/47線性代數(shù)：方法不好時工作量非常大，工作量小的方法是Gauss消去法。

Cramer法則是一種不實用的直接法，本章介紹幾種實用的直接法。

Gauss消去法是一種規(guī)則化的加減消元法，其基本思想是通過逐次消元計算，把一般線性方程組的求解轉(zhuǎn)化為等價的上三角形方程組的求解?！?.2高斯消去法14/47二.例子為清楚起見，先看一簡單例子。考慮線性方程組1.消去后兩個方程中的x1得：2.再消去最后一個方程的x2得：3.消元結(jié)束,經(jīng)過回代得解:§1.2高斯消去法15/47上述求解的消元過程可用矩陣表示為:

這是高斯消去法的計算形式,新的增廣矩陣對應(yīng)的線性方程組就是上三角形方程組,可進行回代求解§1.2高斯消去法16/47三.

求解線性方程組(1)的順序Gauss消去法記則,線性方程組(1)的增廣矩陣為§1.2高斯消去法17/47§1.2高斯消去法

18/47§1.2高斯消去法

19/47§1.2高斯消去法

20/47（式2）§1.2高斯消去法

（式3）21/47§1.2高斯消去法22/47結(jié)論：

（1）高斯消去法分消元、回代兩過程。

（2）從矩陣分解角度看：

消去是解一個下三角方程組，

回代是解一個上三角方程組。

（3）消去法順利進行必須滿足

akk

(k)0,(k=1,2,…,n)，若出現(xiàn)akk

(k)=0，則可交換行列后再進行消元。§1.2高斯消去法23/47§1.2高斯消去法四.Gauss消去法計算量(n-k)(n-k)224/47§1.2高斯消去法25/47§1.2高斯消去法乘除法耗時大大多于加減法耗時，故高斯消元法的計算量為O(n3)。n=20時,順序Gauss消去法只需3060次乘除法運算。順序Gauss消去法通常也簡稱為Gauss消去法。26/47§1.2高斯消去法27/47§1.3

選主元素的高斯消去法本節(jié)內(nèi)容一.問題提出二.選主元素消去法三.高斯列主元消去法N-S圖四.高斯-約當消去法返回章節(jié)目錄28/47一.問題提出§1.3

選主元素的高斯消去法29/47§1.3

選主元素的高斯消去法例1：單精度解方程組精確解為和8個8個用Gauss消去法計算：8個小主元

/*Smallpivotelement*/

可能導(dǎo)致計算失敗。30/47§1.3

選主元素的高斯消去法

例2：解線性方程組（用4位十進制浮點計算）用Cramer法則可得精度較高的解（精確解）

x1*=1.00010，x2*=0.9999031/47

解用順序Gauss消去法,消元得回代得解：x1=0.00，x2=1.00與精確解相比，該結(jié)果相當糟糕原因是：在求行乘數(shù)時用了很小的數(shù)0.0001作除數(shù)主元9999§1.3

選主元素的高斯消去法32/47用順序Gauss消去法,消元得回代得解：x1=1.00，x2=1.00若將方程組改寫成（將1,2行交換）:這是一個相當不錯的結(jié)果0.9999§1.3

選主元素的高斯消去法33/47例3：解線性方程組(用8位十進制尾數(shù)的浮點數(shù)計算)解：這個方程組和例2一樣，若用Gauss消去法計算會有小數(shù)作除數(shù)的現(xiàn)象，若采用換行的技巧，則可避免§1.3

選主元素的高斯消去法34/47絕對值最大,不需換行§1.3

選主元素的高斯消去法35/47§1.3

選主元素的高斯消去法36/47§1.3

選主元素的高斯消去法二.選主元素消去法37/47§1.3

選主元素的高斯消去法38/47

給定線性方程組Ax=b，記A(1)=A，b(1)=b，列主元Gauss消去法的具體過程如下：首先在增廣矩陣B(1)=(A(1),b(1))的第一列元素中，取然后進行第一步消元得增廣矩陣B(2)=(A(2),b(2))。再在矩陣B(2)=(A(2),b(2))的第二列元素中，取然后進行第二步消元得增廣矩陣B(3)=(A(3),b(3))。按此方法繼續(xù)進行下去,經(jīng)過n-1步選主元和消元運算,得到增廣矩陣B(n)=(A(n),b(n)).則方程組A(n)x=b(n)是與原方程組等價的上三角形方程組,可進行回代求解.

易證，只要|A|0,列主元Gauss消去法就可順利進行?！?.3

選主元素的高斯消去法39/47

方程組具有四位有效數(shù)字的精確解為

x1*=17.46，x2*=-45.76，x3*=5.546例4采用4位十進制浮點計算,分別用順序Gauss消去法和列主元Gauss消去法求解線性方程組:§1.3

選主元素的高斯消去法40/47

解1.用順序Gauss消去法求解，消元過程為回代得：x3=5.546，x2=100.0，x1=-104.0§1.3

選主元素的高斯消去法41/472.用列主元Gauss消去法求解，消元過程為§1.3

選主元素的高斯消去法42/47回代得：x3=5.545，x2=-45.77，x1=17.46§1.3

選主元素的高斯消去法43/47

列主元Gauss消去法是在每一步消元前，在主元所在的一列選取絕對值最大的元素作為主元素。而全主元Gauss消去法是在每一步消元前，在所有元素中選取絕對值最大的元素作為主元素。但由于運算量大增，實際應(yīng)用中并不經(jīng)常使用?！?.3

選主元素的高斯消去法44/47三.高斯列主元消去法N-S圖消元次數(shù)K=1k<=n?選列主元amk|amk|<epsNrmrk進行第k步消元輸出方程組的解X建立增廣矩陣A(n,n+1)m=kYNYk=k+1回代求解停止§1.3

選主元素的高斯消去法45/47四.高斯-約當消去法（Gauss-Jordan）這是一種無回代的方法，使計算工作量減小，在第k次消元時不僅把akk(k)

化成1，不僅將aik（i=k+1，……，n）化成0，而且也將aik（i=1，2，……，k-1）也化為0，最后消元過程結(jié)束時的系數(shù)矩陣為得消元公式

akj

(k)=akj(k-1)/akk(k-1)

（j=1,2,…,n+1）

aij

(k)=aij

(k)-aik(k-1)akj(k)

（ik,i=1,2,…,n，j=1,2,…,n+1）自學(xué)了解§1.3

選主元素的高斯消去法46/47§1.4

矩陣的三角分解本節(jié)內(nèi)容一.Gauss消去法的矩陣表示二.Doolittle分解法返回章節(jié)目錄47/47§1.4

矩陣的三角分解一.Gauss消去法的矩陣表示對矩陣48/47§1.4

矩陣的三角分解49/47§1.4

矩陣的三角分解50/47§1.4

矩陣的三角分解51/47也就是：

A(n)=Ln-1A(n-1)=Ln-1Ln-2A(n-2)=…=Ln-1Ln-2…L2L1A(1)

其中：所以有：A=A(1)=L1-1L2-1…Ln-1-1A(n)=LU

其中：L=L1-1L2-1…Ln-1-1,U=A(n)§1.4

矩陣的三角分解52/47L稱為單位下三角矩陣;U是上三角矩陣.式A=LU稱為矩陣A的三角分解。§1.4

矩陣的三角分解53/47二、Doolittle分解法定理2：設(shè)n階方陣A的各階順序主子式不為零,則存在唯一單位下三角矩陣L和上三角矩陣U使A=LU。證明只證唯一性,設(shè)有兩種分解則有所以得于是Ax=bLUx=b

令Ux=y得§1.4

矩陣的三角分解54/47K=1§1.4

矩陣的三角分解55/47對K=2,3,…,n計算（1）求U的第i行元素§1.4

矩陣的三角分解56/47對K=2,3,…,n計算（2）求L的第i列元素§1.4

矩陣的三角分解57/47§1.4

矩陣的三角分解58/47§1.4

矩陣的三角分解59/47這就是求解方程組Ax=b的Doolittle三角分解方法。§1.4

矩陣的三角分解60/47例利用三角分解方法解線性方程組

解因為§1.4

矩陣的三角分解61/47§1.4

矩陣的三角分解先解,得再解,得62/47

解線性方程組Ax=b

的Doolittle

三角分解法的計算量約為1/3n3,與Gauss消去法基本相同。其優(yōu)點在于求一系列同系數(shù)的線性方程組Ax=bk,(k=1,2,…,m)時,可大大節(jié)省運算量。例如,求上例中矩陣A的逆矩陣?？煞謩e取常向量

b1=(1,0,0)T,b2=(0,1,0)T,b3=(0,0,1)T

§1.4

矩陣的三角分解63/47§1.4

矩陣的三角分解64/47

為了提高數(shù)值穩(wěn)定性,可考慮列主元三角分解法,設(shè)已完成A=LU的k-1步分解計算,矩陣分解成§1.4

矩陣的三角分解65/47§1.4

矩陣的三角分解66/47§6.4

矩陣的三角分解例如，用列主元三角分解解上例中方程組。則有67/47§1.5

解三對角線方程組的追趕法本節(jié)內(nèi)容一.三對角線矩陣二.Crount分解三.例返回章節(jié)目錄68/47一.

有一類方程組，在插值問題和邊值問題中有著重要的作用，即三對角線方程組，其形式為：§1.5

解三對角線方程組的追趕法對角元前次對角線后次對角線69/47§1.5

解三對角線方程組的追趕法70/47§1.5

解三對角線方程組的追趕法前面已經(jīng)講過71/47二對角矩陣§1.5

解三對角線方程組的追趕法注意：和教材上字母不同72/47§1.5

解三對角線方程組的追趕法73/47§1.5

解三對角線方程組的追趕法74/47追，相當于消元過程§1.5

解三對角線方程組的追趕法75/47式1—式3叫追趕法，也稱Thomas法。工作量小，非常有效。趕，相當于回代過程§1.5

解三對角線方程組的追趕法76/47§5.7

解三對角線方程組的追趕法77/47§5.7

解三對角線方程組的追趕法78/47當滿足條件

|a1|>|c1|>0；

|an|>|dn|>0；

|ai||ci|+|di|，cidi0，i=2,3,…,n-1。時，追趕法是數(shù)值穩(wěn)定的追趕法具有：計算程序簡單，存貯量少，計算量小的優(yōu)點?！?.5

解三對角線方程組的追趕法79/47§1.6解對稱正定矩陣方程組的平方根法本節(jié)內(nèi)容一.對稱正定矩陣二.平方根法——喬來斯金分解三.LDLT分解返回章節(jié)目錄80/47§1.6解對稱正定矩陣方程組的平方根法81/47§1.6解對稱正定矩陣方程組的平方根法

對稱正定陣的幾個重要性質(zhì)(2)A的順序主子陣Ak

亦對稱正定(3)A的特征值i>0

(1)A1

亦對稱正定，且aii>0(4)A的全部順序主子式

det(Ak)>082/47§1.6解對稱正定矩陣方程組的平方根法

83/47§1.6解對稱正定矩陣方程組的平方根法84/47§1.6解對稱正定矩陣方程組的平方根法85/47§1.6解對稱正定矩陣方程組的平方根法86/47§1.6解對稱正定矩陣方程組的平方根法87/47§1.6解對稱正定矩陣方程組的平方根法88/47§6.6解對稱正定矩陣方程組的平方根法√44/2=289/47§6.6解對稱正定矩陣方程組的平方根法

平方根法是求對稱正定系數(shù)線性方程組的三角分解法，對稱正定矩陣的Cholesky

分解的計算量和存貯量均約為一般矩陣的LU

分解的一半。且Cholesky

分解具有數(shù)值穩(wěn)定性。90/47§1.6解對稱正定矩陣方程組的平方根法

91/47§1.6解對稱正定矩陣方程組的平方根法92/47§1.7向量和矩陣的范數(shù)本節(jié)內(nèi)容一.向量范數(shù)二.矩陣范數(shù)三.矩陣A的譜半徑返回章節(jié)目錄93/47§1.7向量和矩陣的范數(shù)

94/47§1.7向量和矩陣的范數(shù)95/47§1.7向量和矩陣的范數(shù)96/47§1.7向量和矩陣的范數(shù)97/47§1.7向量和矩陣的范數(shù)98/47§1.7向量和矩陣的范數(shù)

99/47§1.7向量和矩陣的范數(shù)100/47§1.7向量和矩陣的范數(shù)101/47§1.7向量和矩陣的范數(shù)102/47§6.7向量和矩陣的范數(shù)103/47§1.7向量和矩陣的范數(shù)104/47§1.7向量和矩陣的范數(shù)105/47§1.8解線性方程組的迭代法本節(jié)內(nèi)容一.簡單迭代法二.雅可比(Jacobi)迭代法三.塞德爾(Seidel)迭代法四.

逐次超松弛(SOR)迭代法五.

例子返回章節(jié)目錄解大型稀疏線性方程組106/47§1.8解線性方程組的迭代法一.簡單迭代法

107/47§1.8解線性方程組的迭代法一階定常迭代法108/47

特征值譜半徑§1.8解線性方程組的迭代法

109/47§6.8解線性方程組的迭代法有興趣同學(xué)自學(xué)110/47二.雅可比(Jacobi)迭代法1.迭代法§1.8解線性方程組的迭代法111/47§1.8解線性方程組的迭代法112/47§1.8解線性方程組的迭代法113/47§1.8解線性方程組的迭代法114/47§1.8解線性方程組的迭代法115/47§1.8解線性方程組的迭代法2.收斂性范數(shù)116/47§1.8解線性方程組的迭代法117/47§1.8解線性方程組的迭代法三.塞德爾(Seidel)迭代法1.迭代法1118/47§1.8解線性方程組的迭代法119/47§1.8解線性方程組的迭代法2.收斂性1120/47§1.8解線性方程組的迭代法3.迭代法2121/47§1.8解線性方程組的迭代法122/47§1.8解線性方程組的迭代法4.收斂性2123/47四.

逐次超松弛(SOR)迭代法1.迭代法§1.8解線性方程組的迭代法124/47§1.8解線性方程組的迭代法2.收斂性125/47§1.8解線性方程組的迭代法五.

例子例1126/47§1.8解線性方程組的迭代法127/47§6.8解線性方程組的迭代法可見，迭代序列逐次收斂于方程組的解，而且迭代7次得到精確到小數(shù)點后兩位的近似解。kx1(k)x2(k)x3(k)‖x(k)-x*‖0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636計算結(jié)果列表如下:128/47G-S迭代法的計算公式為:§1.8解線性方程組的迭代法129/47同樣取初始向量x(0)=(0,0,0)T，計算結(jié)果為：

由計算結(jié)果可見，G-S迭代法收斂較快.取精確到小數(shù)點后兩位的近似解，G-S迭代法只需迭代3次，而J迭代法需要迭代7次。kx1(k)x2(k)x3(k)‖x(k)-x*‖012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956§1.8解線性方程組的迭代法130/47若使‖x(k)–x*‖<,只需,即可以事先估計達到某一精度需要迭代多少步?！?.8解線性方程組的迭代法131/47例2用J迭代法求例1中方程組的解，取x(0)=(0,0,0)T，若使誤差x(k)-x*<10-5，問需要迭代多少次？解由例1知，x(1)=(1.4,0.5,1.4)T，于是有，x(1)-x(0)=1.4，B=0.5。k應(yīng)滿足故取k=19，即需要迭代1