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

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

WW>J定義：對(duì)非奇異矩陣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)對(duì)任何人非奇異矩陣(1)對(duì)任何人非奇異矩陣A，cond(A)>1o(2)(3)設(shè)(2)(3)設(shè)A是非奇異矩陣的實(shí)對(duì)稱矩陣，則有設(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)相對(duì)很大，則稱Ax=b是病態(tài)線性方程組(也稱A是病態(tài)矩陣)；若cond(A)相對(duì)較小，則稱Ax=b是良態(tài)線性方程組(也稱A是良態(tài)矩陣)。我們應(yīng)該注意到：矩陣A的條件數(shù)刻畫了線性方程組Ax=b的一種性態(tài)。A的條件數(shù)越大，方程組Ax=b的病態(tài)程度越嚴(yán)重。對(duì)于嚴(yán)重病態(tài)的線性方程組Ax=b，當(dāng)A和b有微小變化時(shí)，即使求解過程是精確進(jìn)行的，所得的解相對(duì)于原方程組的解也會(huì)有很大的相對(duì)于誤差。2.3.2關(guān)于病態(tài)線性方程組的求解問題可以用下列方法判別線性方程組Ax=b是否病態(tài)：

(1)當(dāng)|detA|相對(duì)很小或A的某些行(或列)近似線性相關(guān)是2,方程組可能病態(tài)。(2)用列主元素Gauss消去法求解方程組時(shí)，若出現(xiàn)小列主元a(k)《1，則方程組可能病態(tài)。(3)分別用b和b+Ab(||Ab|《1)作方程組的右端向量，求解Ax=b和A~=b+Ab，若x和~相差很大，則Ax=b是病態(tài)的。(4)當(dāng)A的元素的數(shù)量級(jí)差別很大，且無一定規(guī)則時(shí)，方程組可能病態(tài)。對(duì)于病態(tài)線性方程組可采用以下的方法求解：米用高精度的算術(shù)運(yùn)算平衡方法殘差校正法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*，如果對(duì)某種范數(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對(duì)任意的向量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)對(duì)于迭代公式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是主對(duì)角線按行（或按列）嚴(yán)格占優(yōu)陣，則A是非奇異矩陣。（2）如果方程組Ax=b的系數(shù)矩陣是主對(duì)角線按行（或按列）嚴(yán)格占優(yōu)陣，則用Jacobi迭代法求解必收斂。Gauss-Swidel迭代法定理2.13GS法收斂的充分必要條件是P（G（）<1。定理2.14如果GG<1,則GS法收斂。定理2.15如果方程組的系數(shù)矩陣A是主對(duì)角線按行（或按列）嚴(yán)格占優(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í)常數(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法。當(dāng)^=1時(shí)，上式就是GS法，SOR的迭代矩陣是1 \(1、一G=—(-D+L)-11——D+Us① |_[①J_在實(shí)際使用SOR方法時(shí)，為避免求1D+L的逆矩陣，把迭代公式作如下的變動(dòng)：用-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是主對(duì)角線按行(或按列)嚴(yán)格占優(yōu)陣，則用0<?<1的SOR方法求解必收斂。定理2.21如果方程組的系數(shù)矩陣A是正定矩陣，則用0<-<2的SOR方法求解必收斂。三、本章思考題在求解線性方程組的過程當(dāng)中，我們應(yīng)注意哪些問題?

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