资源描述
计 算 方 法第八章第八章 线性方程组的解线性方程组的解法法计算方法课程组8.08.0 引引 言言重要性重要性：解线性代数方程组的有效方法在计算数学和：解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作用。如科学计算中具有特殊的地位和作用。如弹性力学、电弹性力学、电路分析、热传导和振动路分析、热传导和振动、以及社会科学及定量分析商、以及社会科学及定量分析商业经济中的各种问题。业经济中的各种问题。求解线性方程组求解线性方程组 的求解方法，其中的求解方法，其中 ，。假设假设 非奇异，则方程组有唯一解非奇异，则方程组有唯一解.8.08.0 引引 言言 分类分类：线性方程组的解法可分为线性方程组的解法可分为直接法直接法和和迭代法迭代法两种方法。两种方法。(a)直直接法接法：对于给定的方程组，在没有舍入误差的假设下，对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解。最基本的直接法是能在预定的运算次数内求得精确解。最基本的直接法是Gauss消去法，重要的直接法全都受到消去法，重要的直接法全都受到Gauss消去法的启发。消去法的启发。计算代价高计算代价高.(b)迭代法：迭代法：基于一定的递推格式，产生逼近方程组精确解的基于一定的递推格式，产生逼近方程组精确解的近似序列近似序列.收敛性是其为迭代法的前提，此外，存在收敛速收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题。度与误差估计问题。简单实用简单实用,诱人诱人。8.1 雅可比雅可比Jacobi迭代法迭代法 (AX=b)一、迭代法的基本思想迭代法的基本思想 二、例题分析例题分析 三、Jacobi迭代公式迭代公式 与解与解f(x)=0 的不动点迭代相类似，将的不动点迭代相类似，将AX=b改写改写为为X=BX+f 的形式，建立雅可比方法的迭代格式：的形式，建立雅可比方法的迭代格式：其中，其中，B称为迭代矩阵。其计算精度可控，特别称为迭代矩阵。其计算精度可控，特别适用于求解系数为大型稀疏矩阵适用于求解系数为大型稀疏矩阵(sparse matrices)的方程组。的方程组。8.1 8.1 雅可比雅可比JacobiJacobi迭代法迭代法 (AX=b)(AX=b)迭代法的基本思想迭代法的基本思想 问题问题:(a)如何建立迭代格式？如何建立迭代格式？(b)向量向量序列序列 x(k)是否收敛以及收敛条件是否收敛以及收敛条件?2 例题分析例题分析:其准确解为其准确解为X*=1.1,1.2,1.3。考虑解方程组考虑解方程组 (1)3.1Jacobi迭代法迭代法2 例题分析例题分析:建立与式建立与式(1)(1)相等价的形式：相等价的形式：(2)其准确解为其准确解为X*=1.1,1.2,1.3。考虑解方程组考虑解方程组 (1)3.1Jacobi迭代法迭代法2 例题分析例题分析:其准确解为其准确解为X*=1.1,1.2,1.3。建立与式建立与式(1)(1)相等价的形式：相等价的形式：考虑解方程组考虑解方程组取迭代初值取迭代初值据此建立迭代公式：据此建立迭代公式：迭代结果如下表迭代结果如下表：迭迭代代次次数数 x1 x2 x30 0 0 01 0.7 2 0.8 3 0.8 42 0.9 7 1 1.0 7 1.1 53 1.0 5 7 1.1 5 7 1 1.2 4 8 24 1.0 8 5 3 5 1.1 8 5 3 4 1.2 8 2 8 25 1.0 9 5 0 9 8 1.1 9 5 0 9 9 1.2 9 4 1 3 86 1.0 9 8 3 3 8 1.1 9 8 3 3 7 1.2 9 8 0 3 97 1.0 9 9 4 4 2 1.1 9 9 4 4 2 1.2 9 9 3 3 58 1.0 9 9 8 1 1 1.1 9 9 8 1 1 1.2 9 9 7 7 79 1.0 9 9 9 3 6 1.1 9 9 9 3 6 1.2 9 9 9 2 41 0 1.0 9 9 9 7 9 1.1 9 9 9 7 9 1.2 9 9 9 7 51 1 1.0 9 9 9 9 3 1.1 9 9 9 9 3 1.2 9 9 9 9 11 2 1.0 9 9 9 9 8 1.1 9 9 9 9 8 1.2 9 9 9 9 71 3 1.0 9 9 9 9 9 1.1 9 9 9 9 9 1.2 9 9 9 9 91 4 1.1 1.2 1.31 5 1.1 1.2 1.3 设方程组设方程组 AX=b,通过分离变量的过程建立通过分离变量的过程建立Jacobi迭代公式，即迭代公式，即 由此我们可以得到由此我们可以得到 Jacobi 迭代公式迭代公式：8.1 Jacobi8.1 Jacobi迭代公式迭代公式 雅可比迭代法的矩阵表示雅可比迭代法的矩阵表示 写成矩阵形式：写成矩阵形式：A=LUDBJacobi 迭代阵迭代阵8.2 8.2 高斯高斯-塞德尔迭代法塞德尔迭代法(AX=b)(AX=b)注意到利用注意到利用JacobiJacobi迭代公式计算迭代公式计算时，已经计算好了时，已经计算好了的值，而的值，而JacobiJacobi迭代公式并不利用这些最新的近似值计算，迭代公式并不利用这些最新的近似值计算，仍用仍用 这启发我们可以对其加以改进这启发我们可以对其加以改进,即在每个分量的计算中尽量即在每个分量的计算中尽量利用最新的迭代值，得到利用最新的迭代值，得到上式称为上式称为 Gauss-Seidel 迭代法迭代法.写成写成矩阵形式：矩阵形式：BGauss-Seidel 迭代阵迭代阵8.2 8.2 高斯高斯-塞德尔迭代法塞德尔迭代法其准确解为其准确解为X*=1.1,1.2,1.3。考虑解方程组考虑解方程组高斯高斯-塞德尔迭代法算例塞德尔迭代法算例高斯高斯-塞德尔迭代格式塞德尔迭代格式迭代次数迭代次数 x1 x2 x3 0 0 0 0 1 0.72 0.902 1.1644 2 1.04308 1.167188 1.282054 3 1.09313 1.195724 1.297771 4 1.099126 1.199467 1.299719 5 1.09989 1.199933 1.299965 6 1.099986 1.199992 1.299996 7 1.099998 1.199999 1.299999 8 1.1 1.2 1.3开始TFTFT 逐次超松弛迭代法逐次超松弛迭代法(Successive Over Relaxation Method，简写为，简写为SOR)可以看作带参数可以看作带参数的高斯的高斯-塞德塞德尔迭代法，是尔迭代法，是 G-S 方法的一种修正或加速，是求解大方法的一种修正或加速，是求解大型稀疏矩阵方程组的有效方法之一。型稀疏矩阵方程组的有效方法之一。8.3 8.3 超松驰迭代法超松驰迭代法SOR方法方法1.SOR基本思想基本思想 设方程组设方程组AX=b,其中，其中，A=(aij)为非奇异阵，为非奇异阵，x=(x1,x2,xn)T,b=(b1,b2,bn)T.假设已算出假设已算出 x(k)，8.3 8.3 超松驰迭代法超松驰迭代法SOR方法方法2.SOR算法的构造算法的构造 称为松弛因子称为松弛因子 利用高斯利用高斯-塞德尔迭代法得塞德尔迭代法得:8.3 8.3 超松驰迭代法超松驰迭代法SOR方法方法2.SOR算法的构造算法的构造(基于基于G-S迭代迭代)解方程组解方程组AX=b的逐次超松弛迭代公式：的逐次超松弛迭代公式：显然，当取显然，当取=1=1时，上式就是高斯时，上式就是高斯-塞德尔迭代公式塞德尔迭代公式.8.3 8.3 超松驰迭代法超松驰迭代法SOR方法方法2.SOR算法的构造算法的构造(基于基于Jacobi迭代迭代)得到解方程组得到解方程组 AX=b 的逐次超松弛迭代公式：的逐次超松弛迭代公式：显然，上式就是显然，上式就是 基于基于Jacobi 迭代的迭代的 SOR 方法方法.下面令下面令 ，希望通过选取合适的希望通过选取合适的 来加速收敛，这就是来加速收敛，这就是松弛法松弛法。3.SOR算法的进一步解释算法的进一步解释 SOR方法方法其中其中ri(k+1)=相当于在相当于在 的基础上的基础上加个余项加个余项生成生成 。0 1(渐次渐次)超松弛法超松弛法利用利用SOR方法方法解方程组解方程组SOR例题分析例题分析:其准确解为其准确解为x*=1,1,2.=1,1,2.建立与式建立与式(1)(1)相等价的形式：相等价的形式：据此建立据此建立G-S迭代公式：迭代公式：取迭代初值取迭代初值:,=1.5,=1.5,迭代结果如下表迭代结果如下表.SORSOR迭代公式为：迭代公式为：GS迭代法须迭代迭代法须迭代85次得到准确值次得到准确值 x*=1,1,2;而而SOR方法只须方法只须55次即得准确值次即得准确值.由此可见，适当地选择松弛由此可见，适当地选择松弛因子因子，SOR法具有法具有明显的明显的加速收敛效果加速收敛效果.逐次超松弛迭代法逐次超松弛迭代法次数次数 x1 x2 x3 1 0.625000 0.062500 1.750000 2 0.390625 0.882813 1.468750 3 1.017578 0.516602 1.808594 4 0.556885 0.880981 1.710449 5 1.023712 0.743423 1.868103 15 0.991521 0.985318 1.987416 25 0.998596 0.998234 1.998355 55 1.00000 1.0000 2.0000 关于关于SOR方法的说明：方法的说明：(1)显然，当显然，当 时，时，SOR方法就是方法就是Gauss-Seidel方法。方法。(2)SOR 方法每一次迭代的主要运算量是计算一次矩阵与向量方法每一次迭代的主要运算量是计算一次矩阵与向量的乘法。的乘法。(3)时称为超松弛方法，时称为超松弛方法，时称为低松弛方法。时称为低松弛方法。(4)计算机实现时可用计算机实现时可用 控制迭代终止，或用控制迭代终止，或用(5)SOR方法可以看成是方法可以看成是Gauss-Seidel方法的一种修正。方法的一种修正。（迭代法基本定理）（迭代法基本定理）设有方程组设有方程组 ，对于任意的初始向，对于任意的初始向量量 ，迭代公式，迭代公式 收敛的充要条件是迭收敛的充要条件是迭代矩阵代矩阵 的谱半径的谱半径 .8.4 8.4 迭代法的收敛性迭代法的收敛性-充要条件充要条件 迭代法的基本定理在理论分析中有重要意义。迭代法的基本定理在理论分析中有重要意义。定理定理2：设设X*是方程组是方程组AX=b的同解方程的同解方程X=BX+F 的准确解的准确解，若迭代公式中迭代矩阵若迭代公式中迭代矩阵B的某种范数的某种范数，(1)(2)则有则有 在具体使用上，由于在具体使用上，由于 ，因此，我们利，因此，我们利用范数可以建立判别迭代法收敛的充分条件。用范数可以建立判别迭代法收敛的充分条件。关于解某些特殊方程组迭代法的收敛性关于解某些特殊方程组迭代法的收敛性定义：定义：(对角占优阵对角占优阵)设设(1)(1)如果如果 元素满足元素满足 称称 为为严格对角占优阵严格对角占优阵(2)(2)如果如果 元素满足元素满足 且上式至少有一个不等式严格成立，且上式至少有一个不等式严格成立，称称 为为弱对角占优阵弱对角占优阵。设设 ，如果：，如果：为严格对角占优，则解为严格对角占优，则解 的的Jacobi迭代法，迭代法，Gauss-Seidel迭代法均收敛。迭代法均收敛。Seidel迭代格式为迭代格式为 从式中解出从式中解出故可得故可得Seidel迭代矩阵为迭代矩阵为从例中可以看出从例中可以看出Jacobi迭代矩阵迭代矩阵Bj的主对角线为零，而的主对角线为零，而Seidel迭代矩阵迭代矩阵Bs的第的第1列都是零，这对一般情况也是成立的。列都是零，这对一般情况也是成立的。举例检验举例检验JacoaiJacoai迭代的收敛性迭代的收敛性首先将原方程组写为迭代形式的方程组，即：首先将原方程组写为迭代形式的方程组，即：求任一行之和的最大值求任一行之和的最大值1,1,即：即：|M|=max5/8,5/11,9/12=9/121i或求任一列之和的最大值或求任一列之和的最大值1,即：即：|M|1=max114/132,60/96,30/88=114/1321结论：该方程组采用结论：该方程组采用Jacobi迭代法计算是收敛的。迭代法计算是收敛的。已知线性方程组为：已知线性方程组为：8.5 迭代法的误差估计迭代法的误差估计定理定理4：设设X*是方程组是方程组AX=b的同解方程的同解方程X=BX+F 的准确解的准确解，若迭代公式中迭代矩阵若迭代公式中迭代矩阵B的某种范数的某种范数，(1)(2)则有则有
展开阅读全文