数值分析-第二章小结

第二章线性方程组的数值解法——学习小结姓名班级学号一、 本章学习体会通过本章的学习，我了解了线性方程组的不同解法，切实体会到了不同的计算方法对计算结果的影响。求解线性方程组的方法可分为两大类：直接方法和迭代方法。直接方法在解一般的线性方程组的时候比较简便，使用此方法经过有限次运算就可得到方程组的解。然而迭代法是要构造一个无限的向量序列，其极限是方程组的解向量，它适用于求解大型稀疏线性方程组。总的来说，直接方法和迭代法各有优点与不足，在解线性方程组的时候，我们要根据具体的线性方程组的特点来选择合适的解法，这样我们才能快速准确的得到方程组的解。因此，我们要熟悉书中介绍的各类线性方程组的解法，同时要善于思考、总结，在使用各种方法求解的同时尽量提出自己独特的见解，通过不断练习计算，使自己的能力得到提高。二、 本章知识梳理线性方程组的求解方法分为直接法和迭代法两种，Gramer（克莱姆）法是直接法的一种，但由于其计算量比较大，在世界工作中其效率比较低、经济效益差，所以此方法我们很少使用，本章主要介绍其他的计算方法。Gauss消去法Gauss（高斯）消去法由消元和回代两个过程组成。消元过程就是对方程组的增广矩阵做有限次的初等行变换，使它的系数矩阵部分变换为上三角阵。所用的初等行变换主要有两种：第一种，交换两行的位置；第二种，用一个数乘某一行加到另一行上。回代过程就是先由方程组的最后一个方程解出七，然后通过逐步回代，依次求出气］，气2，…，气。这种Gauss消去法可分为Gauss消去法和列主元素Gauss消去法两种。2.1.1顺序Gauss消去法在Gauss消去法的消元过程中对方程组的增广矩阵只做前述的第二种初等行变换就形成了顺序Gauss消去法，其算法如下：b⑴=b （i=1,2,…，n）1、消元过程对于k=1,2，…，n-1执行（1） 如果"）=0，则算法失效，停止计算；否则转（2）。（2） 对于i=k=1，k=2，…，n计算%=%吐5腆）=叫产）一叫泌/心。=1以+&"3=杪）_皿航㈤2、回代过程由上述计算方法可统计出顺序Gauss消去法求解n元线性方程组的乘除法运算总次数为1,—（n+3n2-n）。与Gramer法则相比，顺序Gauss消去法的计算重大为减少。33定理2.1顺序Gauss消去法的前n-1个主元素。以（k）（k=1，2，…，n-1）均不为零的充分必要条件是方程组的系数矩阵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执行（1） 选行号ik，使同撰）|=皿**心|叫（2）交换a（k）与a（k） （j=k，k+1，…，n）以及b（k）与b（k）所含的数值。k ikj kL（3） 对于i=k+1，k+2，…，n计算ff刑5二%’峪_mikatk^(/=fc+ 42,....n)2、回代过程吼=（*恐—£如舟玲/诳」峪（fc=7T-tn-2,.,,4）\/定理2.2设方程组的系数矩阵A非奇异，则用列主元素Gauss消去法求解方程组时，各个列主元素a（k）（k=1，2，…，n-1）均不为零。lkk2.2直接三角分解法Doolittle分解法与Crout分解法如果方程组的系数矩阵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=?i- -2,.,,4}2.2.2选主元的Doolittle分解法定理2.4若矩阵AeRnxn非奇异，则存在置换矩阵Q，使得QA可作Doolittle分解，其中L是单位下三角矩阵，U是上三角矩阵。选主元的Doolittle分解法，特别适用于在同一个计算问题中须要求解多个具有相同系数矩阵A而具有不同右端向量的线性方程组。2.3矩阵的条件数与病态线性方程组2.3.1矩阵的条件数与线性方程组的性态定理2.6设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的条件数，记作cond(A)=A|||A-i|矩阵A的条件数与所取的矩阵范数有关，常用的条件数是cond(A)=|A|||A-』，cond(A)=||A||||A-i||矩阵A的条件数有以下性质：(1)对任何人非奇异矩阵(1)对任何人非奇异矩阵A，cond(A)>1o(2)(3)设(2)(3)设A是非奇异矩阵的实对称矩阵，则有设A是非奇异矩阵，k"0是常数，则有cond(kA)=cond(A)。cond(A)=2其中入1和七分别是矩阵A的模为最大和模为最小的特征值。(4)设A是正交矩阵，则有cond(a)=1定义：设线性方程组Ax=b的系数矩阵A非奇异，若cond(A)相对很大，则称Ax=b是病态线性方程组(也称A是病态矩阵)；若cond(A)相对较小，则称Ax=b是良态线性方程组(也称A是良态矩阵)。我们应该注意到：矩阵A的条件数刻画了线性方程组Ax=b的一种性态。A的条件数越大，方程组Ax=b的病态程度越严重。对于严重病态的线性方程组Ax=b，当A和b有微小变化时，即使求解过程是精确进行的，所得的解相对于原方程组的解也会有很大的相对于误差。2.3.2关于病态线性方程组的求解问题可以用下列方法判别线性方程组Ax=b是否病态：

(1)当|detA|相对很小或A的某些行(或列)近似线性相关是2,方程组可能病态。(2)用列主元素Gauss消去法求解方程组时，若出现小列主元a(k)《1，则方程组可能病态。(3)分别用b和b+Ab(||Ab|《1)作方程组的右端向量，求解Ax=b和A~=b+Ab，若x和~相差很大，则Ax=b是病态的。(4)当A的元素的数量级差别很大，且无一定规则时，方程组可能病态。对于病态线性方程组可采用以下的方法求解：米用高精度的算术运算平衡方法残差校正法2.4迭代法2.4.1迭代法的一般形式及其收敛性定义设有向量序列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设有向量序列k)^和常向量x*，如果对某种范数lim]x(k)_x*=0k—3则必有limx(k)=x*k—3定义设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的某种范数||G||<1,则(1)方程组x=Gx+d的解x*存在且唯一;(2)对于迭代公式X(k+1^=Gx(k+1)+d，有limX(k)=X*，Vx(0)eRnks并且下列两式成立HLHIg||XHLHIg||X(1)-X(0)IG||X(k)-X(k-1)Jaxobi迭代法设方程组AX=b设方程组AX=b的系数矩阵A=eRg满足条件a。0ij "ii(i=1,2,…,n)..。把A分裂根据已知条件在迭代法一般形式X(k根据已知条件在迭代法一般形式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,…)关于Jacobi迭代法收敛的条件:Jacobi迭代法收敛的充分必要条件是P（Gj）<1。Jacobi迭代法收敛的充分条件：⑴IGJIK1若矩阵Agn是主对角线按行（或按列）严格占优阵，则A是非奇异矩阵。（2）如果方程组Ax=b的系数矩阵是主对角线按行（或按列）严格占优阵，则用Jacobi迭代法求解必收敛。Gauss-Swidel迭代法定理2.13GS法收敛的充分必要条件是P（G（）<1。定理2.14如果GG<1,则GS法收敛。定理2.15如果方程组的系数矩阵A是主对角线按行（或按列）严格占优阵，则用GS法求解必收敛。2.4.4逐次超松弛迭代法设方程组Ax=b的系数矩阵A满足条件a。0（i=1,2,…,n）.，把A分裂为iiTOC\o"1-5"\h\z1 （1\A=—D+L+1—D+U\o"CurrentDocument"① IS其中实常数«>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如果方程组的系数矩阵A是主对角线按行(或按列)严格占优阵，则用0<«<1的SOR方法求解必收敛。定理2.21如果方程组的系数矩阵A是正定矩阵，则用0<-<2的SOR方法求解必收敛。三、本章思考题在求解线性方程组的过程当中，我们应注意哪些问题?

答：在求解线性方程组的过程中，我们应针对不同方程组的特点选择合适的方法，在保证解的准确性的同时尽量提高其运算速度，简便运算程序，保证运算效率。例如，在解一般比较简单的线性方程组时，我们可以选用直接法，如果要求计算结果的精度与稳定性，我们尽量选用直接法中的列主元素Gauss消去法；如果方程组的系数矩阵是主对角线按行（或按列）严格占优阵，我们可以选用Jacobi迭代法快速准确的解出方程组的解。所以，在求