线性方程组的直接法和迭代法

线性方程组的直接法直接法就是经过有限步算术运算，无需迭代可直接求得方程组精确解的方法。线性方程组迭代法迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法．该方法具有对计算机的存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法．迭代法不是用有限步运算求精确解，而是通过迭代产生近似解逼近精确解．如Jacobi迭代、Gauss—Seidel迭代、SOR迭代法等。1.线性方程组的直接法直接法就是经过有限步算术运算，无需迭代可直接求得方程组精确解的方法。1.1Cramer法则Cramer法则用于判断具有n个未知数的n个线性方程的方程组解的情况。当方程组的系数行列式不等于零时，方程组有解且解唯一。如果方程组无解或者有两个不同的解时，则系数行列式必为零。如果齐次线性方程组的系数行列式不等于零，则没有非零解。如果齐次线性方程组有非零解，则系数行列式必为零。定理1如果方程组Axb中0DA，则Axb有解，且解事唯一的，解为1212,,...,nnDDDxxxDDDiD是D中第i列换成向量b所得的行列式。Cramer法则解n元方程组有两个前提条件：1、未知数的个数等于方程的个数。2、系数行列式不等于零例1a取何值时，线性方程组12312312311xxxaaxxxxxax有唯一解。解：211111111011(1)11001Aaaaaaa所以当1a时，方程组有唯一解。定理2当齐次线性方程组0Ax，0A时该方程组有唯一的零解。定理3齐次线性方程组0Ax有非零解0A。1.2Gauss消元法Gauss消元法是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个“行梯阵式”。1.2.1用Gauss消元法为线性方程组求解eg：Gauss消元法可用来找出下列方程组的解或其解的限制：123283211223xyzLxyzLxyzL这个算法的原理是：首先，要将1L以下的等式中的x消除，然后再将2L以下的等式中的y消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中，就可求出其余的答案了。在刚才的例子中，我们将132L和2L相加，就可以将2L中的x消除了。然后再将1L和3L相加，就可以将3L中的x消除。方程组则变为：281112225xyzyzyz现在将24L和3L相加，就可将3L中的y消除，方程组变为：28111221xyzyzz这样就完成了整个算法的初步，一个三角形的格式(指:变量的格式而言,上例中的变量各为3,2,1个)出现了。第二步，就是由尾至头地将已知的答案代入其他等式中的未知数。第一个答案就是1z。然后直接带入，立即就可得出第二个答案：3y和最后一个答案2x。这样，我们利用高斯消元法解决了这个方程组。2.线性方程组迭代法迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法．该方法具有对计算机的存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法．迭代法不是用有限步运算求精确解，而是通过迭代产生近似解逼近精确解．如Jacobi迭代、Gauss—Seidel迭代、SOR迭代法等。2.1Jacobi迭代法2131321,11,2,1,2,1000...............00nnnnnnaaaLaaaaa1122331,1,...nnnnaaaDaa12131.11,232,12,343,0...0...0......00nnnnnaaaaaaaaaU对于线性方程组Axb则ALDU，即将A分解为一个严格下三角矩阵、一个对角阵和一个严格上三角矩阵之和，从而可写出Jacobi迭代格式的矩阵表示形式为：(1)1()(1)()kkxDLUxDb，其迭代矩阵1()JDLU)称为雅可比迭代矩阵.将线性方程组Axb变为一个通解方程组xBxf，对其进行迭代式改写，(1)(),0,1,2....kkxBxfk矩阵B为迭代矩阵11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbIaxaxaxb由方程组（I）的第i个方程解出1(1,2,)xin，得到一个同解方程组：112213311112212233222212211()1nnnnnnnnnnnnnnxaxaxaxbaxaxaxaxbaIIxaxaxaxba构造相应的迭代公式(1)()()()11221331111(1)()()()22122332222(1)()()()12211()1kkkknnkkkknnkkkknnnnnnnnnnxaxaxaxbaxaxaxaxbaIIIxaxaxaxba取初始向量(0)(0)(0)(0)12,,Tnxxxx，利用（III）反复迭代可以得到一个向量序列()kx，利用此迭代格式求解方程组的解法称为Jacobi迭代法。用Jacobi迭代求解下列方程组121232343243330424xxxxxxx输入A=[430;33-1;0-14]；b=[24;30;-24]；[x,k,index]=Jacobi(A,b,1e-5,100)输出：x=-2.999811.9987-3.0001k=100index=0所以解为：1x=-2.9998,2x=11.9987,3x=-3.00012.2Gauss-Seide迭代若L、U、D为上述的L、U、D。则Gauss—Seidel迭代法的矩阵表示为：(1)1(1)()()kkkxDLxUxb，现将(1)kx显示化由(1)()()kkDLxUxb得：(1)1()1()()kkxDLUxDLb，令1()GDL，1()gDLb，则得：(1)()kkxGxg，此即为Gauss—Seidel迭代法的矩阵表示形式，G称为迭代阵。由Jacobi迭代法中，每一次的迭代只用到前一次的迭代值，若每一次迭代充分利用当前最新的迭代值，即在计算第i个分量)1(kix时，用最新分量)1(1kx，)1(2kx)1(1-kix代替旧分量)(1kx，)(2kx)(1-kix，就得到所谓解方程组的Gauss-Seidel迭代法。其迭代格式为Tnxxxx)()0()0(2)0(1)0(，，，(初始向量)，)(11111)()1()1(ijiijkjijkjijiiiiixaxabax)210i210(nk，，，；，，，或者写为)(1)210i210(1111)()1()1()()1(ijiijkjijkjijiiiiiikikixaxabaxnkkxxx，，，；，，，(1)()()()11221331111(1)(1)()()22112332222(1)(1)(1)(1)()()1122,11,11(1)(1)1221111kkkknnkkkknnkkkkkkiiiiiiiiiinniiikknnnnnnxaxaxaxbaxaxaxaxbaxaxaxaxaxaxbaxaxaxa(1)(1)()kknnnnIVaxb用Gauss-Seide迭代求解下列方程组121232343243330424xxxxxxx输入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.2056sN=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所以结果为：1x=0.6169,2x=11.1962,3x=-4.2056。2.3SOR迭代在很多情况下，Jacobi和Gauss—Seidel法收敛速度较慢，SOR法是Gauss—Seidel法的一种加速方法，需要施加合适的松弛因子。若L、U、D为上述的L、U、D。SOR迭代公式为(1)()kkwXLXf，其中1()((1))wLDLDU，1(),[1,2]fDLb。用SOR迭代求解下列方程组。12341234123412340.760.010.140.160.680.010.880.030.061.180.140.031.010.120.120.160.060.120.720.74xxxxxxxxxxxxxxxx取初始点(0)(0,0,0,0)Tx松弛因子1.05，精度要求610。输入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,x0,w)输出x=1.27151.28440.48581.2843n=7有上述结果得出：经过7次迭代后，该方程组的解为x1=1.2715,x2=1.2844,x3=0.4858,x4=1.28432.4迭代法收敛引理：设A为n阶方阵，则lim0kxA的充要条件为()1A（()A为普半径）。证明：必要性若lim0kxA由矩阵收敛的定义知lim0kxA有因为()AA所以0()AA由夹逼定理可得出lim[()]0kxA，又因为()[()]kkAA所以由lim[()]0kxA可得出()1A充分性：若()1A，取1()02A，存在矩阵范数，使得1()()12AAA则有：lim0kxA，由算子范数相容性可得：10kkkAAAA由夹逼定理可得出lim0kxA。定理1：迭代公式(1)(),0,1,2....kkxBxfk收敛的充分必要条件是迭代矩阵B的谱半径()1B证明：必要性设存在n维向量x，使得limkxxx，则x满足kxBxf由迭代公式得出(1)(1)2(2)(0)kkkkkxxBxfBxfBxxBxxBxx所以(0)limlim0kkxxBxxxx因为(0)x为任意n维向量，因此上式成立必须lim0kxB由引理可得出()1B。充分性：若()1B，则1不是B的特征值，因而有0IB,于是对任意的n维向量f，方程组()I