《线性方程组的直接法和迭代法》由会员分享,可在线阅读,更多相关《线性方程组的直接法和迭代法(18页珍藏版)》请在金锄头文库上搜索。
1、线性方程组的直接法直接法就是经过有限步算术运算,无需迭代可直接求得方程组准确解的方法。线性方程组迭代法迭代法就是用某种极限过程去逐步逼近线性方程组准确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求准确解,而是通过迭代产生近似解逼近准确解.如Jacobi迭代、Gauss-Seide迭彳t、SOR迭代法等。1 .线性方程组的直接法直接法就是经过有限步算术运算,无需迭代可直接求得方程组准确解的方法。1.1 Cramer法那么Cramer法那么用于判断具有n个未知数的n个线性方程的方程组解的情
2、况。当方程组的系数行列式不等于零时,方程组有解且解唯一。如果方程组无解或者有两个不同的解时,那么系数行列式必为零。如果齐次线性方程组的系数行列式不等于零,那么没有非零解。如果齐次线性方程组有非零解,那么系数行列式必为零。定理1如果方程组Axb中D|a|0,那么Axb有解,且解事唯一D1D2Dn的,解为为-DL,X2-D2,.Xn=,Di是D中第i列换成向量b所得的行列式。Cramer法那么解n元方程组有两个前提条件:1、未知数的个数等于方程的个数。2、系数行列式不等于零例1a取何值时,线性方程组x1x2ax1 x2xix2x3x3ax 31有唯一解解:Aa1101a1a(a1)211a00a1
3、所以当a1时,方程组有唯一解。定理2当齐次线性方程组Ax0,|A0时该方程组有唯一的零解。定理3齐次线性方程组Ax0有非零解|A0o1.2 Gauss消元法Gaus肖元法是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个“行梯阵式。2 .2.1用Gauss消元法为线性方程组求解eg:Gauss消元法可用来找出以下方程组的解或其解的限制:2xyz8L3xy2z11L22xy2z3L3这个算法的原理是:首先,要将L以下的等式中的x消除,然后再将L2以下的等式中的y消除。这样可使整个方程组变成一个三角形似的格式。之后再将已
4、得出的答案一个个地代入已被简化的等式中的未知数中,就可求出其余的答案了在刚刚的例子中,我们将2:和L2相加,就可以将L2中的x消除了然后再将L1和L3相加,就可以将L3中的X消除。方程组那么变为:2xyz811dyz1222yz5现在将4L2和L3相加,就可将L3中的y消除,方程组变为:2xyz81 1dyz12 2z1这样就完成了整个算法的初步,一个三角形的格式(指:变量的格式而言,上例中的变量各为3,2,1个)出现了。第二步,就是由尾至头地将的答案代入其他等式中的未知数。第一个答案就是z1。然后直接带入,立即就可得出第二个答案:y3和最后一个答案x2。这样,我们利用高斯消元法解决了这个方程
5、组。2.线性方程组迭代法迭代法就是用某种极限过程去逐步逼近线性方程组准确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求准确解,而是通过迭代产生近似解逼近准确解.如Jacobi迭代、Gauss-Seidel迭代、SOR迭代法等。2.1 Jacobi迭代法0a210a31a320Lan1,1an1,2.0an,1an,2an,n10a11a22a33Dan1,n1an,na1,na2, na3,n0a12a13.a1.n10a23.a2,n10a34.U对于线性方程组Ax b 那么 AL
6、D U ,即将 A 分解为一个严格下三角矩阵、 一个对角阵和一个严格上三角矩阵之和,从而可写出Jacobi迭代格x(k1)D1(LU)x(k)D(1)b式的矩阵表示形式为:xD(LU)xDb,其迭代矩阵1JD(LU)称为雅可比迭代矩阵.将线性方程组Axb变为一个通解方程组xBxf,对其进展迭代式(k1)(k)改写,xBxf,k0,1,2矩阵B为迭代矩阵aiiXiai2X2ainXnbia21X1a22X2a2nXnb2aniXian2X2annXnbn由方程组I的第i个方程解出Xi(i1,2,-n),得到一个同解方程组:XiX2Xnaiianna12X2a13X3ainXnbia2iX2a23
7、X3a2nXn(II)aniXnan2X2annXnbn构造相应的迭代公式(k1)Xi(k)a12X2(k)a13X(k)ainXnbi(kX2i)aii1(k)a21X2(k)a23X3(k)a2nXna22b2(III)(kXn1)ann(k)aniXn(k)an2X2(k)annXnbn取初始向量x(0)x(o),x2o),端T,利用III反复迭代可以得到一个向量(k)序列X),利用此迭代格式求解方程组的解法称为Jacobi迭代法。用Jacobi迭代求解以下方程组4x13x2243x13x2x330x24x324输入A=430;33-1;0-14;b=24;30;-24;x,k,inde
8、x=Jacobi(A,b,1e-5,100)输出:x=-2.999811.9987-3.0001k=100index=0所以解为:x1=-2.9998,x2=11.9987,x3=-3.00012.2 Gauss-Seidel假设L、U、D为上述的L、U、D。那么Gauss-Seidel迭代法的矩阵(k 1) 表示为:(DL)x(k 1)D1(Lx(k1)Ux(k)b)(k1)D(LxUxb),现将x显示化由Ux(k)b得.x(k1)(DL)1Ux(DL)1b令G(DL)1,g(DL)1b,那么得:x(k1)Gx(k)g,此即为Gauss-Seide迭代法的矩阵表示形式,G称为迭代阵。由Jac
9、obi迭代法中,每一次的迭代只用到前一次的迭代值,假设每一次迭代充分利用当前最新的迭代值,即在计算第 i个分量(k 1)Xi时,用最新分量X1(k 1)(k 1)x2Xi-1(k 1)(k)代替旧分量X1(k)X2xi-1(k)所谓解方程组的Gauss-Seidete代法。其迭代格式为,xn0)T1i 1Xi(i1)LbiaijX(k1)aiij 1(初始向量),i 1(k)az )j i 1(k0,1,2,; i0,1,2, n)或者写为Xi(k1)Xi(k)Xi(k0,12Xi(i1)0,12n)aii(biaijxjk1)aijx(k)x1(k1)1a11(k)(k)(k)a12X2a1
10、3X3a1nXnb1(kXi1)aii(kxn1)(k1)1X2a22(k1)a21x1-(k)a23X3(k)a2nXnb2(IV)(k1)ai1x1(k1)42X2ai,i1Xi(k11)(k)ai,i1Xi1(k)ainXnbi(k1)an1Xn(k1)an2X2一(kannxn1)bnann用Gauss-Seid迭代求解以下方程组4x13x2243x13x2x330x24x324输入A=430;33-1;0-14;b=24;30;-24;x0=0;0;0;v,sN,vChain=gaussSeidel(A,b,x0,0.00001,11)输出:v=0.616911.1962-4.205
11、6sN=11vChain=6.000010.0000-6.0000-1.50002.0000-3.50004.500010.3333-5.5000-1.75003.6667-3.41673.250010.6111-5.0833-1.95835.0556-3.34722.208310.8426-4.7361-2.13196.2130-3.28941.340311.0355-4.4468-2.27667.1775-3.24110.616911.1962-4.2056000000000000所以结果为:x1=0.6169,x2=11.1962,x3=-4.20562.3 SOR迭代SOR 法是在很多
12、情况下,Jacobi和GaussSeidel法收敛速度较慢,Gauss- Seide法的种力口速方法,需要施加适宜的松弛因子o假设 L 、 U、 D 为上述的 L、U、 DSOR迭代公式为X (k 1)LwX(k)f ,其中1Lw (D L) 1(1 )D U)(D L) 1b, 1,2 。用SOR1代求解以下方程组。0.76x10.01x10.01x20.88x20.14x30.03x30.16x40.06x40.681.180.14x10.16x10.03x20.06x21.01x30.12x30.12x40.72x40.120.741.05 ,精度要求10取初始点x(0)(0,0,0,0
13、)T松弛因子输入A=0.76-0.01-0.14-0.1;6-0.010.88-0.030.0;6-0.14-0.031.01-0.1;2-0.160.06-0.120.72;B=0.681.180.120.72;X0=0;0;0;0;W=1.05x,n=SOR(A,b,x0,w)输出x=1.27151.28440.48581.2843n=7有上述结果得出:经过7次迭代后,该方程组的解为x1=1.2715,x2=1.2844,x3=0.4858,x4=1.28432.4迭代法收敛k引理:设A为n阶方阵,那么limA0的充要条件为(A)1(A)x为普半径。证明:必要性假设limAk0x由矩阵收敛的定义知!im|Ak|0有因为(A)|A|所以0(A)|A|由夹逼定理可得出lim(A)k0,又因为(Ak)(A)k所以由xlim(A)k0可得出(A)1x