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

1、.线性方程组的直接法 直接法就是经过有限步算术运算，无需迭代可直接求得方程组精确解的方法。线性方程组迭代法 迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法该方法具有对计算机的存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法迭代法不是用有限步运算求精确解，而是通过迭代产生近似解逼近精确解如Jacobi迭代、Gauss Seidel迭代、SOR迭代法等。1. 线性方程组的直接法 直接法就是经过有限步算术运算，无需迭代可直接求得方程组精确解的方法。 1.1 Cramer法则 Cramer法则用于判断具有n个未知数的n个线性方程的方程组解的

2、情况。当方程组的系数行列式不等于零时，方程组有解且解唯一。如果方程组无解或者有两个不同的解时，则系数行列式必为零。如果齐次线性方程组的系数行列式不等于零，则没有非零解。如果齐次线性方程组有非零解，则系数行列式必为零。 定理1如果方程组中，则有解，且解事唯一的，解为是D中第i列换成向量b所得的行列式。Cramer法则解n元方程组有两个前提条件：1、未知数的个数等于方程的个数。2、系数行列式不等于零 例1 a取何值时，线性方程组有唯一解。解：所以当时，方程组有唯一解。定理2当齐次线性方程组，时该方程组有唯一的零解。定理3 齐次线性方程组有非零解。1.2 Gauss消元法 Gauss消元法是线性代数

3、中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个“行梯阵式”。 1.2.1 用Gauss消元法为线性方程组求解eg：Gauss消元法可用来找出下列方程组的解或其解的限制：这个算法的原理是：首先，要将以下的等式中的消除，然后再将以下的等式中的消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中，就可求出其余的答案了。在刚才的例子中，我们将和相加，就可以将中的消除了。然后再将和相加，就可以将中的消除。方程组则变为：现在将和相加，就可将中的消除，方程组变为：这样就完成了整个算法

4、的初步，一个三角形的格式(指:变量的格式而言,上例中的变量各为3,2,1个)出现了。第二步，就是由尾至头地将已知的答案代入其他等式中的未知数。第一个答案就是。然后直接带入，立即就可得出第二个答案：和最后一个答案。这样，我们利用高斯消元法解决了这个方程组。2. 线性方程组迭代法 迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法该方法具有对计算机的存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法迭代法不是用有限步运算求精确解，而是通过迭代产生近似解逼近精确解如Jacobi迭代、Gauss Seidel迭代、SOR迭代法等。2.1 Jaco

5、bi迭代法 对于线性方程组则，即将A分解为一个严格下三角矩阵、一个对角阵和一个严格上三角矩阵之和，从而可写出Jacobi迭代格式的矩阵表示形式为：，其迭代矩阵)称为雅可比迭代矩阵. 将线性方程组变为一个通解方程组，对其进行迭代式改写，矩阵B为迭代矩阵 由方程组（I）的第i个方程解出，得到一个同解方程组：构造相应的迭代公式取初始向量，利用（III）反复迭代可以得到一个向量序列，利用此迭代格式求解方程组的解法称为Jacobi迭代法。用Jacobi迭代求解下列方程组输入A=4 3 0;3 3 -1;0 -1 4；b=24;30;-24；x, k, index=Jacobi(A, b, 1e-5, 1

6、00)输出：x = -2.9998 11.9987 -3.0001k = 100index = 0所以解为：=-2.9998, =11.9987, =-3.00012.2 Gauss-Seide迭代 若L、 U、 D为上述的L、 U、 D。则GaussSeidel迭代法的矩阵表示为：，现将显示化由得：，令，则得：，此即为GaussSeidel迭代法的矩阵表示形式，G称为迭代阵。 由Jacobi迭代法中，每一次的迭代只用到前一次的迭代值，若每一次迭代充分利用当前最新的迭代值，即在计算第个分量时，用最新分量，代替旧分量，就得到所谓解方程组的Gauss-Seidel迭代法。其迭代格式为 (初始向量)

7、， 或者写为用Gauss-Seide迭代求解下列方程组 输入A=4 3 0;3 3 -1;0 -1 4；b=24;30;-24；x0=0;0;0；v,sN,vChain=gaussSeidel(A,b,x0,0.00001,11)输出：v = 0.6169 11.1962 -4.2056sN = 11vChain = 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.

8、2083 10.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 0 0 0 0 0 0 0 0 0 0 0所以结果为：= 0.6169, =11.1962, =-4.2056 。2.3 SOR迭代在很多情况下，Jacobi和GaussSeidel法收敛速度较慢，SOR法是GaussSeidel法的一种加速方法，需要施加合适的松弛因子。若L、 U、 D为上述的L、 U、 D 。SOR迭代公式为，其中，。用SOR迭代求解下列方程组。取

9、初始点松弛因子，精度要求。输入A=0.76 -0.01 -0.14 -0.16；-0.01 0.88 -0.03 0.06； -0.14 -0.03 1.01 -0.12；-0.16 0.06 -0.12 0.72;B=0.68 1.18 0.12 0.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 迭代法收敛引理：设A为n阶方阵，则的充要条件为（为普半径）。证明：必要

10、性若由矩阵收敛的定义知有因为所以由夹逼定理可得出，又因为所以由可得出充分性：若，取，存在矩阵范数，使得则有：，由算子范数相容性可得：由夹逼定理可得出。定理1： 迭代公式收敛的充分必要条件是迭代矩阵的谱半径 证明：必要性设存在n维向量，使得，则满足由迭代公式得出所以因为为任意n维向量，因此上式成立必须由引理可得出。充分性：若，则不是B的特征值，因而有,于是对任意的n维向量f，方程组有唯一解，记为。即：且，又因为所以，对任意初始向量都有即迭代公式收敛。注解： 代矩阵的谱半径这里的是矩阵的特征值。定理2： 若迭代矩阵的一种范数，则对任意的初始向量和任意。迭代格式均收敛。 迭代法收敛与否只决定于迭代矩

11、阵的普半径，于初始向量及右端项无关。对于同一方程组，由于不同的迭代法迭代矩阵不同，可能出现有的方法收敛，有的发散的情形。注解：三种常用矩阵范数为：，（是的最大特征值）。 由上述两个定理可得：Jacobi迭代收敛的充分必要条件是，收敛的充分条件是任一种范数，GaussSeidel迭代收敛的充分必要条件是，收敛的充分条件是任一种范数。 定理3： 对角占优线性方程组的Jacobi迭代格式和GaussSeidel迭代格式均收敛。注解：n阶方阵A，如果其主对角线元素的绝对值大于同行其他元素绝对值之和，则称A是对角占优的虽然定理1是充分必要条件，可是需要计算迭代矩阵的特征值，我们在线性代数上看到一个大型矩

12、阵的特征值是非常难求的，计算量是很大的。定理2和定理3的计算量相对定理1来说是相当小的，因为它们只是简单的加减乘除；但是他们是充分条件，不满足时需要再改用定理1来判断。所以收敛的判断可先采用定理2和定理3，不行再选择定理1。 预处理是用来加速迭代法收敛的一个重要手段。值得注意的是，经典的求解线性方程组的迭代法也都能够看作是求解采用不同的因子预处理之后得到的线性方程组的迭代法。换句话来说，原线性方程组的松弛迭代法等价于预处理之后的方程组的定点迭代法。谱条件数是反映预处理因子性态是否良好的一个有效指标。在估计特征值和条件数的界的研究领域，虽然已经有了很多的研究成果，但是支持理论还是一个全新的概念。支撑理论是一个用于分析预处理方程组的最大(或最小)特征值和条件数的代数架构，它最初产生于对称正定的线性方程组(7)2.5 迭代法收敛的应用用Jacobi迭代，GaussSe