线性方程组的直接法和迭代法.docx
《线性方程组的直接法和迭代法.docx》由会员分享，可在线阅读，更多相关《线性方程组的直接法和迭代法.docx（14页珍藏版）》请在冰点文库上搜索。
线性方程组的直接法和迭代法
线性方程组的直接法
直接法就是经il有限步算术运算，无需迭代可直接求得方程组精确解的方法。
线性方程组迭代法
迭代法就是用某种极限11程去逐步JlifiSIl方程组精确解的方法•该方法具有对廿算机的存贮单元需求少，程序设廿简单、原始系数拒阵在it算过程中不变等优点，是求辭大里棉疏矩阵方程组的重要方法•迭代法不是用有限步运算求精确齡,而是通过迭代产Sififfl解JI近精确解.如JacobiH代、Gauss—Seidel迭代、SOR迭代法等。
1.线性方程组的直接法
直接法就是经11有限步算术运算，无需迭代可直接求得方程组精确解的方法。
1.1Cramer法则
Cramer法则用于判飾具有n个未知数的n个线性方程的方程组解的悄况。
当方程组的系数行列式不等干零时，方程组有解II解唯一。
如果方程组无齡或者有两个不同的解时,则系数行列式必为零。
如果齐次线性方程组的系数行列式不等于零，则没有非零解。
如果齐次线性方程组有非零解，则系数行列式必为零。
定理1如果方程组Ax=b中D=|A|H0，则Ax=b有解,目解事唯一的，解为X'=¥'x2=*'.%=*，Di是D巾第i列换成向量b所得的行列式。
Cramer法则解n元方程组有两个前提条件:
1、未知数的个数等干方程的个数。
2、系数行列式不等于零
时，线性方程组
xx+x2+x3=aaxx4-x2+=1有唯一解。
Xx+兀2+ax3=1
11
解：
|^|=a1
11
11
\-a\-a=_（（/_1），
0G—l
所以当dHl时，方程组有唯一解。
定理2当齐次线性方程级Ar=O,|4卜°时该方程组有唯一的零解。
定理3齐次线性方程组曲=0有非零解<=>H=0o
1.2Gauss消元法
Gauss消元法是线性代数中的一个算法，可用来为线11方程组求解，求出矩晖的扶，以及求岀可逆方阵的逆葩阵。
当用于一个拒阵时，高斯消元法会产生岀一个“行梯晖式”。
1.2.1用Gauss消元法为线性方程组求解
eg:
Gauss消元法可用来找岀下列方程组的解或其解的限H:
2兀+y_z=8（厶）
V-3x-y+2z=-11（厶）
一2x+y+2z=-3（厶）
这个算法的原理是：
首先，要将厶妙、下的等式中的兀消除，然后再将厶以下的等式中的y消除。
这样可使整f方程组变成一个三角形似的恪式。
之后再将已得岀的苔案一个个地代人已被简化的等式巾的未知数中，就可求岀其余的答案了。
在啊才的例子中，我们将扌厶和厶相加，就可以将厶中的％消除了。
然后再将厶和厶相加，就可以將厶中的X消除。
方程组则变为：
2x+y—z=8
111
_y+_z=1
2'2
2y+z=5
现在将一4乙和厶相加，就可将厶中的y消除，方程组变为:
2x+y—z=8
11[
2-2
-z=1
送样就完成了整个算法的初步，一个三角形的恪式（指:
变量的松武而言，上例中的变量各为3,2,1个）岀现了。
第二步，就是由尾至头地将已知的答案代人其他等式中的未ano第一个答案就是z=—1。
然后直接带人，立即就可得岀第二个答案：
y=3和最后一个答案兀二2。
逆样，找们利用高斯消元法解决了这个方程组。
2.线性方程组迭代法
迭代法就是用某种板限11程去逐步JlifiSIl方程组帝确解的方法•该方法具有对廿算机的存贮单元需求少，程序设it简单、原始系数矩阵在廿算过程中不变等优点，是求解大塑柿磴矩阵方程组的重要方法.迭代法不是用有限步运算求精确解,而是通过选代产生近做解ii近精确解.如Jacobi迭代、Gauss—Seidel迭代、S0R选代法等。
2.1Jacobi迭代法
C/210
6/31G320
L=
aw
an
<733
D=
对干线11方程组Ax=b9\A=L-^-D+U将A分解为一个严恪下三角葩晖、一个对角晖和一个严恪上三角矩阵之和，从而可写岀Jacobi&代榕式的拒阵表示形式为：
（厶其选代矩阵J=-D~\L+U）｝^为雅可比选代矩阵.
将线11方程组Ax=b变为一个通解方程组x=Bx+/,対其进行迭代式改写，J"=B卅*f伙=0丄2.…矩阵b为迭代矩晖
4內+兔2兀2+・・・+°1“£=S
。
2內+°22%2+…+如£=E（/）
[an^+an2x2+-^+annxn=bn
由方程组（I）的第i个方程解出和=1,2,…力,得到一个同解方程组:
购造相应的迭代公式
——气兀巴+勺）
Bill始向量兀⑹=（兀匸，40），-）\利用（III））5«选代可以得到一个向量
序列，利用此迭代恪式求解方程组的解法称为Jacobi&代法。
用Jacobig代求解下列方程组
4%j+3x2二24
<3坷+3x2-x3=30
—勺+4七=_24
输人
A=[430;33-1;0-14]；
b=[24;30;-24]；
[x,k,index]=Jacobi（A,b,1e-5,100）
-2.9998
11.9987
-3.0001
k=
100
index=
0
所以解为：
=-2.9998,x2=11.9987,x3=-3.0001
2.2Gauss-Seideg代
若L、U、D为上述的L、U、Do»lGauss-Seidel迭代法的葩阵表示为:
gl）_丫伙+1）片伙）J&+1）
A3ux十叫现将兀显示化由
{D+L）x（k+i）=-Ux（k）+b得.?
A+,）=-（D+L）_1Ux（ky4-（D+L）_,b令
G=—（D+°[+则得：
xZ=G”+g,此即为
Gauss—Seidel迭代法的矩阵表示形式,G称为迭代阵。
由Jacobig代法中，每一次的迭代只用到前一次的迭代值,若每一次迭代
伙+1）
充分利用当前最新的迭代值，Hl在计算第2个分量亠时，用最新分量
伙+1）伙+1）伙+1）伙）
",兀2…S代替IH分量①
伙）r伙）
兀2…S,就得到
所谓解方程组的Gauss-Seidel选代法。
其迭代格式为
Y（0）_“（0）JO）r（0）xT
X—（E,x2，…，X”）（初始向量）,严=]（切-丈诃屮-头用）aii；=1；=/+!
伙=0丄2,…；i=0丄2,•••?
?
）
或者写为
i=0,12…n）
乂广+“=码⑷+心,（k=k=0丄2,…；
W=丄0—壬門兀5—士仙乂产）
aii7=1./="+1
仏+1）
~ai2X2k）~ai3X3k）
（/V）
cV（*+l）z/V（灯
一0口+1兀+1
V（*+D-1（nv（*+l）z/v（*+l）
召——石（77
需屮=丄（〜曲心_%兀2（屮%
勺后冋）+仇）
用Gauss-Seide迭代求解下列方程组
4兀]+3x2=24
<3X]+3x2-x3=30
_兀2+4七——24
输人
A=[430;33-1;0-14]；
b=[24;30;-24]；
x0=[0;0;0]；
[v,sN,vChain]=gaussSeidel（A,b,xO,0.00001,11）
输岀：
V=
0.6169
11.1962
-4.2056
sN=
11
vChain=
6.0000
10.0000
-6.0000
-1.5000
2.0000
-3.5000
4.5000
10.3333
-5.5000
-1.7500
3.6667
-3.4167
3.2500
10.6111
-5.0833
-1.9583
5.0556
-3.3472
2.208310.8426-4.7361
-2.1319
6.2130-3.2894
1.3403
11.0355-4.4468
-2.2766
7.1775-3.2411
0.6169
11.1962-4.2056
0
00
0
00
0
00
0
00
所以结果为:
兀1=0.6169,J1.1962,®=_4.2056。
2.3SOR迭代
在很多悄况下，JacobifUGauss—Seidel法收敛速度较慢，SOR法是Gauss—Seidel法的一种加速方法,需要施加合适的松弛因子°
若L、U、D为上述的L、U、DoSOR2代公式为Xa+,）=Lu.Xa）+/,其中
Lw={D-coL）~[{（\-co）D+（oU）,f=co（D-0厶尸b,ew[1,2]。
用SOR迭代求辭下列方程组。
O.76Xj-O.Olx2-0.14兀3-0.16兀4=0.68
一0.01X]+O.88x2-O.O3x3+0.06x4=1.18
-0.14%,-0.03x2+1.O1x3-0.12兀4=0.12
-0.16xj+0.06兀2-0.1+072兀4=0.74
Bill始点兀⑼=（0,0,0,0）丁松弛因子血=1.05,精度要求E=10"。
输人
A=[0.76-0.01-0.14-0.16；-0.010.88-0.030.06；
-0.14-0.031.01-0.12；-0.160.06-0.120.72];
B=[0.681.180.120.72];
X0=[0;0;0;0];
W=1.05
[x,n]=SOR（A,b,xO,w）
输岀
x=
1.2715
1.2844
0.4858
1.2843
n=
7
有上述结果借岀：
经117次迭代后，该方程组的解为
x1=1.2715,x2=1.2844,x3=0.485&x4=1.2843
2.4迭代法收敛
引理：
设A为n阶方阵，则lim屮二°的充要条件为p（A）<1（/?
（A）
A
普半径）o
证明：
必要性若lim"=0
由科收敛的定义知哩IMI=°有因为0（4）ATOC
hm[p（A）]k=0可得出q（4）<1
x—>x
充分性：
若Q（A）<1,取£=1二甞）>0,存在葩阵范数||||,使得
||州A）《I则有:
Um||A|f=0,
由算子范数相容性可得：
0<|才|<||A|f_1||A||<-•<||A『由夹逼定理可得岀limA"=°。
定理X迭代公式x（k+}}=Bx（k）+f,k=0X2.…收敛的充分必要条件是选代
矩阵B的谱半gp（B）<1
证明:
必要性
设存在n维向量八使肌型x—门则F满足宀BP+/
由迭代公式得出
H-r
=Bx（k-[）+f-Bx^-f
二
*）=lim（H-x*）=0
=B2（xa_2）-r）=Bk（x（0）-x）glimF（严-兀
A—XX）、因为兀®为任意n维向量,因此上式成立必须!
竺=°由引理可得出P（B）<10
充分恢若O（B）vl,则2=1不是B的特征值，因而有|/一B|hO,于是对任童的n绒向量f,方程组（I~B）x=f有唯一解，记为x\&：
x=Bx+f目吨丹=°,Q因为
=B2（x（k-2）-x）
=Bk（x（0}-x）
所以，对任意初始向量X（（））都有lim（x*-Z）=limB*（x（0）-Z）=0
XTOC'ZA->X'7
即迭代公式=Bx（k）+/,^=0,1,2.…收敛。
注解：
代矩阵〃的谱半gp（B）=max九（3）这里的人（B）是矩阵B的特征值。
定理2：
若迭代矩晖的一种范数则对任恿的初始向量兀⑴）和任J°
迭代法收敛与否只决定于迭代葩阵的普半径，于初始向量及右端顶无关。
对干同一方程组，由干不同的选代法选代葩阵不同，可能岀现有的方法收敛，有的发散的悄形。
II州。
o=m严习匈||A||i=maxXN注解：
三种常用矩阵范数为：
冃,7日岡卜=妬（儿是心的最大特征值）o
由上述两个定理可得：
Jacobi&代收敛的充分必要条件是P（B）<1,收敛的充分条件是任一种范数Gauss-Seidel&代收敛的充分助要条件是
收敛的充分条件是任-种范数回'I
定理3：
对角占优线性方程组^=b的Jacobi选代怡式兀""和
Gauss—Seidel迭代怡式均"）=Gr）+*收敛。
注解：
n阶方阵A,如果其主对角线元素的绝对值大干同行其他元素绝对值之和,则称A是对角占优的.
虽然定BM是充分必要条件，可是需要廿算选代矩阵〃的特征值，我们在线性代数上看到一个大里矩阵的特征值是非常难求it算量是很大的。
定理2和定理3的廿算量相对定理1来说是相当小的,因为它们只是简单的加减乘除；但是他们是充分条件，不满足时需要再改用定理1来I'lBfio所以收敛的判Bi可先呆用定理2和定理3,不行再选择定理1。
预处理是用来加速迭代法收敛的一个重要手段。
值得注恿的是，经典的求解线性方程组的迭代法也都能够看作是求解呆用不同的因子预处理之后得到的线性方程组的迭代法。
换句话来说，原线性方程组的松弛迭代法等价干预处理之后的方程组的定点迭代法。
谱条件数是反映预处理因子性态是否良好的一个有效指标。
在估廿特征値和条件数的界的研究领域，虽然已经有了很多的研究成果，但是支持理论还是一个全新的IB念。
支是一个用于分折预处理方程组的最大（或最小）特征值和条件数的代数架构，它最初产生于对称正定的线性方程组⑺2.5迭代法收敛的应用
用Jacobi迭代,Gauss—Seidel迭代两种方法求解下列方程组是否收敛。
X]+2x2-2x3=1
VX]+兀2+兀3=2
2x,+2x1+兀=3解：
因为选代法收敛与否只决定于选代葩阵的普半径。
所以求普半径是否小于
1.
_12-2'
_100_
A=
111
D=
010
221
001_
000
02-2
L=
100
U=
e
001
220
000
Jacobi选代拒阵B
=-D~l
（L+t/）
0-22
B=-D~\L+U）=-10-1
-2-20
22—2
其讪程困胡"2
22
所以人=人=入=0,所以q（B）=0v1所以Jacobi迭代法收敛。
Gauss一Seidel迭代矩阵B=-（D+L）~}
0-2
2
B=-（D+1尸=
0
2
-3
0
0
2
2
2
-2
其特征方程W~B\=
0
2-2
3
=A（A-2）2=0
0
0
Z-2
所以特征值为人=0,入=入=2所以x?
（B）=2>1所以Gauss-Seidel选代法发散。
上述例子说明对于同一方程组，由于不同的迭代法选代拒阵不同，可能出现有的方法收敛，有的发散的悄形。
升级会员 