數(shù)值分析-第二章小結(jié)

第二章線性方程組的數(shù)值解法——學習小結(jié)姓名班級學號一、 本章學習體會通過本章的學習，我了解了線性方程組的不同解法，切實體會到了不同的計算方法對計算結(jié)果的影響。求解線性方程組的方法可分為兩大類：直接方法和迭代方法。直接方法在解一般的線性方程組的時候比較簡便，使用此方法經(jīng)過有限次運算就可得到方程組的解。然而迭代法是要構(gòu)造一個無限的向量序列，其極限是方程組的解向量，它適用于求解大型稀疏線性方程組?？偟膩碚f，直接方法和迭代法各有優(yōu)點與不足，在解線性方程組的時候，我們要根據(jù)具體的線性方程組的特點來選擇合適的解法，這樣我們才能快速準確的得到方程組的解。因此，我們要熟悉書中介紹的各類線性方程組的解法，同時要善于思考、總結(jié)，在使用各種方法求解的同時盡量提出自己獨特的見解，通過不斷練習計算，使自己的能力得到提高。二、 本章知識梳理線性方程組的求解方法分為直接法和迭代法兩種，Gramer（克萊姆）法是直接法的一種，但由于其計算量比較大，在世界工作中其效率比較低、經(jīng)濟效益差，所以此方法我們很少使用，本章主要介紹其他的計算方法。Gauss消去法Gauss（高斯）消去法由消元和回代兩個過程組成。消元過程就是對方程組的增廣矩陣做有限次的初等行變換，使它的系數(shù)矩陣部分變換為上三角陣。所用的初等行變換主要有兩種：第一種，交換兩行的位置；第二種，用一個數(shù)乘某一行加到另一行上?；卮^程就是先由方程組的最后一個方程解出七，然后通過逐步回代，依次求出氣］，氣2，…，氣。這種Gauss消去法可分為Gauss消去法和列主元素Gauss消去法兩種。2.1.1順序Gauss消去法在Gauss消去法的消元過程中對方程組的增廣矩陣只做前述的第二種初等行變換就形成了順序Gauss消去法，其算法如下：b⑴=b （i=1,2,…，n）1、消元過程對于k=1,2，…，n-1執(zhí)行（1） 如果"）=0，則算法失效，停止計算；否則轉(zhuǎn)（2）。（2） 對于i=k=1，k=2，…，n計算%=%吐5腆）=叫產(chǎn)）一叫泌/心。=1以+&"3=杪）_皿航㈤2、回代過程由上述計算方法可統(tǒng)計出順序Gauss消去法求解n元線性方程組的乘除法運算總次數(shù)為1,—（n+3n2-n）。與Gramer法則相比，順序Gauss消去法的計算重大為減少。33定理2.1順序Gauss消去法的前n-1個主元素。以（k）（k=1，2，…，n-1）均不為零的充分必要條件是方程組的系數(shù)矩陣A的前n-1個順序主子式不為零。2.1.2列主元素Gauss消去法在Gauss消去法的消元過程中，第k次消元之前，先對增廣矩陣作前述的第一種初等行變換（行交換），目的是把。詼以）（i=k，k+1，…，n）中絕對值最大的元素交換到第k行的主對角線位置上，然后再使用前述的第二種初等行變換進行消元，這就形成了列主元素Gauss消去法，其算法如下：b（i）b （i=1,2,…，n）1、消元過程對于k=1，2，…，n-1執(zhí)行（1） 選行號ik，使同撰）|=皿**心|叫（2）交換a（k）與a（k） （j=k，k+1，…，n）以及b（k）與b（k）所含的數(shù)值。k ikj kL（3） 對于i=k+1，k+2，…，n計算ff刑5二%’峪_mikatk^(/=fc+ 42,....n)2、回代過程吼=（*恐—￡如舟玲/誑」峪（fc=7T-tn-2,.,,4）\/定理2.2設(shè)方程組的系數(shù)矩陣A非奇異，則用列主元素Gauss消去法求解方程組時，各個列主元素a（k）（k=1，2，…，n-1）均不為零。lkk2.2直接三角分解法Doolittle分解法與Crout分解法如果方程組的系數(shù)矩陣A能分解成A=LU其中L是下三角矩陣，U是上三角矩陣。這時，方程組就可化為兩個容易求解的三角形方程組Ly=b， Ux=y先由Ly=b解出向量y，再由Ux=y解出向量x，這就是原方程組的解向量。矩陣A分解為LU的形式稱為矩陣A的三角分解。如果分解式中L是單位下三角陣，U是上三角矩陣，則稱為矩陣A的Doolittle（杜立特爾）分解；如果L是下三角矩陣，U是單位上三角陣，則稱為矩陣A的Crout（克勞特）分解。矩陣能作三角分解是有條件的。定理2.3矩陣A=[a"“（n>2）有唯一的Doolittle分解的充分必要條件是A的前n-1個順序主子式Dk。0（k=1，2，…，n-1）。Doolittle分解的計算公式：對于k=1，2，…，n計算k-1t=i求解下三角方程組Ly=b和上三角方程組Ux=y的計算公式為=加C-1Ve=4_y."烘=t=L氣=（比一弋電建J/站?。╥=?i- -2,.,,4}2.2.2選主元的Doolittle分解法定理2.4若矩陣AeRnxn非奇異，則存在置換矩陣Q，使得QA可作Doolittle分解，其中L是單位下三角矩陣，U是上三角矩陣。選主元的Doolittle分解法，特別適用于在同一個計算問題中須要求解多個具有相同系數(shù)矩陣A而具有不同右端向量的線性方程組。2.3矩陣的條件數(shù)與病態(tài)線性方程組2.3.1矩陣的條件數(shù)與線性方程組的性態(tài)定理2.6設(shè)A、△△eRnxn，b、MeRn，a非奇異，b豐0，x是方程組A,x=b的解向量。若|*A||v-^，則有：At（1）方程組

(A+AA)(x+Ax)=b+Ab有唯一解X+△心下列估計式成立:問vAA』凹日〕

WW>J定義：對非奇異矩陣A，稱量||A||A-』為矩陣A的條件數(shù)，記作cond(A)=A|||A-i|矩陣A的條件數(shù)與所取的矩陣范數(shù)有關(guān)，常用的條件數(shù)是cond(A)=|A|||A-』，cond(A)=||A||||A-i||矩陣A的條件數(shù)有以下性質(zhì)：(1)對任何人非奇異矩陣(1)對任何人非奇異矩陣A，cond(A)>1o(2)(3)設(shè)(2)(3)設(shè)A是非奇異矩陣的實對稱矩陣，則有設(shè)A是非奇異矩陣，k"0是常數(shù)，則有cond(kA)=cond(A)。cond(A)=2其中入1和七分別是矩陣A的模為最大和模為最小的特征值。(4)設(shè)A是正交矩陣，則有cond(a)=1定義：設(shè)線性方程組Ax=b的系數(shù)矩陣A非奇異，若cond(A)相對很大，則稱Ax=b是病態(tài)線性方程組(也稱A是病態(tài)矩陣)；若cond(A)相對較小，則稱Ax=b是良態(tài)線性方程組(也稱A是良態(tài)矩陣)。我們應該注意到：矩陣A的條件數(shù)刻畫了線性方程組Ax=b的一種性態(tài)。A的條件數(shù)越大，方程組Ax=b的病態(tài)程度越嚴重。對于嚴重病態(tài)的線性方程組Ax=b，當A和b有微小變化時，即使求解過程是精確進行的，所得的解相對于原方程組的解也會有很大的相對于誤差。2.3.2關(guān)于病態(tài)線性方程組的求解問題可以用下列方法判別線性方程組Ax=b是否病態(tài)：

(1)當|detA|相對很小或A的某些行(或列)近似線性相關(guān)是2,方程組可能病態(tài)。(2)用列主元素Gauss消去法求解方程組時，若出現(xiàn)小列主元a(k)《1，則方程組可能病態(tài)。(3)分別用b和b+Ab(||Ab|《1)作方程組的右端向量，求解Ax=b和A~=b+Ab，若x和~相差很大，則Ax=b是病態(tài)的。(4)當A的元素的數(shù)量級差別很大，且無一定規(guī)則時，方程組可能病態(tài)。對于病態(tài)線性方程組可采用以下的方法求解：米用高精度的算術(shù)運算平衡方法殘差校正法2.4迭代法2.4.1迭代法的一般形式及其收斂性定義設(shè)有向量序列X(k)=(x(k),X(k)，?…,X(k))T (k=0,1,—)如果存在常向量x*=(x*,x2，-,x*)T，使得則稱向量序列^(則稱向量序列^(kJ攵斂于常向量x*，limx(k)=x*(i=1,2,…,n)iks記為limlimx(k)=x*ks定理2.7設(shè)有向量序列k)^和常向量x*，如果對某種范數(shù)lim]x(k)_x*=0k—3則必有l(wèi)imx(k)=x*k—3定義設(shè)nxn矩陣G的特征值是人，人，…人，稱1 2np(G)=max|X|1<i<n'為矩陣G的譜半徑。

其中P(A)圳A定理2.8對任意的向量deRn，迭代法X(k+1)=Gx(k+1)+d (k=0,1,…)收斂的充分必要條件是P(G)<1。定理2.9如果矩陣G的某種范數(shù)||G||<1,則(1)方程組x=Gx+d的解x*存在且唯一;(2)對于迭代公式X(k+1^=Gx(k+1)+d，有l(wèi)imX(k)=X*，Vx(0)eRnks并且下列兩式成立HLHIg||XHLHIg||X(1)-X(0)IG||X(k)-X(k-1)Jaxobi迭代法設(shè)方程組AX=b設(shè)方程組AX=b的系數(shù)矩陣A=eRg滿足條件a。0ij "ii(i=1,2,…,n)..。把A分裂根據(jù)已知條件在迭代法一般形式X(k根據(jù)已知條件在迭代法一般形式X(k+1)=Gx(k+1)+d(k=0,1，…)中，取N=DP=-(L+U)，形成為:A=D+L+U這里a11a221..a」，L=r010」，U=「°a210…a1n-a、n-1,n0a21a,0…a1—nn」n1n,n-11——1D=D-1存在。以下的迭代公式(k=0,1,…)x(k+1)=-D-1(L+D)x(k)(k=0,1,…)其中x(0)eRn任取。由以上迭代公式所表示的迭代法稱為Jacobi(雅可比)迭代法，又稱

簡單迭代法，它的迭代矩陣是G=-D-1（L+D）J迭代法式的分量形式是因D-I=diag(a-1)，故Jacobi迭代法式的分量形式是ii(i(i=1,2,…,n;k=1,2,…)關(guān)于Jacobi迭代法收斂的條件:Jacobi迭代法收斂的充分必要條件是P（Gj）<1。Jacobi迭代法收斂的充分條件：⑴IGJIK1若矩陣Agn是主對角線按行（或按列）嚴格占優(yōu)陣，則A是非奇異矩陣。（2）如果方程組Ax=b的系數(shù)矩陣是主對角線按行（或按列）嚴格占優(yōu)陣，則用Jacobi迭代法求解必收斂。Gauss-Swidel迭代法定理2.13GS法收斂的充分必要條件是P（G（）<1。定理2.14如果GG<1,則GS法收斂。定理2.15如果方程組的系數(shù)矩陣A是主對角線按行（或按列）嚴格占優(yōu)陣，則用GS法求解必收斂。2.4.4逐次超松弛迭代法設(shè)方程組Ax=b的系數(shù)矩陣A滿足條件a。0（i=1,2,…,n）.，把A分裂為iiTOC\o"1-5"\h\z1 （1\A=—D+L+1—D+U\o"CurrentDocument"① IS其中實常數(shù)?>0稱為松弛因子。在迭代法一般形式中，取1 「（一1、 IN=—D+L，P=-1—D+Uo ^oy形成以下的迭代公式

/1…、X(/1…、X(k+1)=—(—D+L)T①r1)1——D+UI1x(k)+(—D+L)-1b①(k=0,1,…)其中x(0)eA〃任取。由以上迭代公式所表示的迭代法稱為逐次超松弛迭代法(SuccessiveOverRelaxationMethod)，簡稱SOR法。當^=1時，上式就是GS法，SOR的迭代矩陣是1 \(1、一G=—(-D+L)-11——D+Us① |_[①J_在實際使用SOR方法時，為避免求1D+L的逆矩陣，把迭代公式作如下的變動：用-1D+L左乘式兩端，并整理，得(一1工一一(-D+L)

-Xk+1=—I1——ID+UIx(k(-D+L)

-I1J—Dxk+—Dxk+1=—Lx(k+1)一-(1\1——D+UI1Jx(k)+b其分量形式是x(k其分量形式是x(k+1)=—?^D—1Lx(k+1)—(1\1——I+D-1Ul①Jx(k)+D—1bbx(k+x(k+1)=—

iNa乙一jx(k+1)—Lj=1aii jx(k—ELx(k)+么iajaj=i+1 ii ii(i=1,2,…,n;k=1,2,…)SOR方法收斂的條件:定理2.17SOR方法收斂的充分必要條件是P(Gg)<1。定理2.18如果||G||<1，則SOR方法收斂。S定理2.19SOR方法收斂的必要條件是0<1<2。定理2.20如果方程組的系數(shù)矩陣A是主對角線按行(或按列)嚴格占優(yōu)陣，則用0<?<1的SOR方法求解必收斂。定理2.21如果方程組的系數(shù)矩陣A是正定矩陣，則用0<-<2的SOR方法求解必收斂。三、本章思考題在求解線性方程組的過程當中，我們應注意哪些問題?

答：在求解線性方程組的過程中，我們應針對不同方程組的特點選擇合適的方法，在保證解的準確性的同時盡量提高其運算速度，簡便運算程序，保證運算效率。例如，在解一般比較簡單的線性方程組時，我們可以選用直接法，如果要求計算結(jié)果的精度與穩(wěn)定性，我們盡量選用直接法中的列主元素Gauss消去法；如果方程組的系數(shù)矩陣是主對角線按行（或按列）嚴格占優(yōu)陣，我們可以選用Jacobi迭代法快速準確的解出方程組的解。所以，在求