电力系统迭代法_高斯迭代法_迭代法的收敛性.ppt

计算方法,第八章线性方程组的解法,计算方法课程组,8.0引言,重要性：解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作用。如弹性力学、电路分析、热传导和振动、以及社会科学及定量分析商业经济中的各种问题。,求解线性方程组的求解方法，其中，。,假设非奇异，则方程组有唯一解.,8.0引言,分类：线性方程组的解法可分为直接法和迭代法两种方法。直接法：对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解。最基本的直接法是Gauss消去法，重要的直接法全都受到Gauss消去法的启发。计算代价高.迭代法：基于一定的递推格式，产生逼近方程组精确解的近似序列.收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题。简单实用,诱人。,8.1雅可比Jacobi迭代法(AX=b),一、迭代法的基本思想,二、例题分析,三、Jacobi迭代公式,与解f(x)=0的不动点迭代相类似，将AX=b改写为X=BX+f的形式，建立雅可比方法的迭代格式：其中，B称为迭代矩阵。其计算精度可控，特别适用于求解系数为大型稀疏矩阵(sparsematrices)的方程组。,8.1雅可比Jacobi迭代法(AX=b),迭代法的基本思想,问题:(a)如何建立迭代格式？(b)向量序列x(k)是否收敛以及收敛条件?,2例题分析:,其准确解为X*=1.1,1.2,1.3。,考虑解方程组,(1),3.1Jacobi迭代法,2例题分析:,建立与式(1)相等价的形式：,(2),其准确解为X*=1.1,1.2,1.3。,考虑解方程组,(1),3.1Jacobi迭代法,2例题分析:,其准确解为X*=1.1,1.2,1.3。,建立与式(1)相等价的形式：,考虑解方程组,取迭代初值,据此建立迭代公式：,迭代结果如下表：,设方程组AX=b,通过分离变量的过程建立Jacobi迭代公式，即,由此我们可以得到Jacobi迭代公式：,8.1Jacobi迭代公式,雅可比迭代法的矩阵表示,写成矩阵形式：,L,U,D,Jacobi迭代阵,8.2高斯-塞德尔迭代法(AX=b),注意到利用Jacobi迭代公式计算,时，已经计算好了,的值，而Jacobi迭代公式并不利用这些最新的近似值计算，仍用,写成矩阵形式：,Gauss-Seidel迭代阵,8.2高斯-塞德尔迭代法,其准确解为X*=1.1,1.2,1.3。,考虑解方程组,高斯-塞德尔迭代法算例,高斯-塞德尔迭代格式,开始,T,F,T,F,T,逐次超松弛迭代法(SuccessiveOverRelaxationMethod，简写为SOR)可以看作带参数的高斯-塞德尔迭代法，是G-S方法的一种修正或加速，是求解大型稀疏矩阵方程组的有效方法之一。,8.3超松驰迭代法SOR方法,1.SOR基本思想,设方程组AX=b,其中，A=(aij)为非奇异阵，x=(x1,x2,xn)T,b=(b1,b2,bn)T.假设已算出x(k)，,8.3超松驰迭代法SOR方法,2.SOR算法的构造,称为松弛因子,利用高斯-塞德尔迭代法得:,8.3超松驰迭代法SOR方法,2.SOR算法的构造(基于G-S迭代),解方程组AX=b的逐次超松弛迭代公式：,显然，当取=1时，上式就是高斯-塞德尔迭代公式.,8.3超松驰迭代法SOR方法,2.SOR算法的构造(基于Jacobi迭代),得到解方程组AX=b的逐次超松弛迭代公式：,显然，上式就是基于Jacobi迭代的SOR方法.,下面令，希望通过选取合适的来加速收敛，这就是松弛法。,3.SOR算法的进一步解释,SOR方法,其中ri(k+1)=,相当于在的基础上加个余项生成。,利用SOR方法解方程组,SOR例题分析:,其准确解为x*=1,1,2.,建立与式(1)相等价的形式：,据此建立G-S迭代公式：,取迭代初值:,=1.5,迭代结果如下表.,SOR迭代公式为：,GS迭代法须迭代85次得到准确值x*=1,1,2;而SOR方法只须55次即得准确值.,由此可见，适当地选择松弛因子，SOR法具有明显的加速收敛效果.,关于SOR方法的说明：显然，当时，SOR方法就是Gauss-Seidel方法。SOR方法每一次迭代的主要运算量是计算一次矩阵与向量的乘法。时称为超松弛方法，时称为低松弛方法。计算机实现时可用控制迭代终止，或用SOR方法可以看成是Gauss-Seidel方法的一种修正。,（迭代法基本定理）设有方程组，对于任意的初始向量，迭代公式收敛的充要条件是迭代矩阵的谱半径.,8.4迭代法的收敛性-充要条件,迭代法的基本定理在理论分析中有重要意义。,定理2：设X*是方程组AX=b的同解方程X=BX+F的准确解，若迭代公式中迭代矩阵B的某种范数，,(1),(2),则有,在具体使用上，由于，因此，我们利用范数可以建立判别迭代法收敛的充分条件。,关于解某些特殊方程组迭代法的收敛性定义：(对角占优阵)设(1)如果元素满足称为严格对角占优阵(2)如果元素满足且上式至少有一个不等式严格成立，称为弱对角占优阵。,设，如果：为严格对角占优，则解的Jacobi迭代法，Gauss-Seidel迭代法均收敛。,Seidel迭代格式为,从式中解出,故可得Seidel迭代矩阵为,从例中可以看出Jacobi迭代矩阵Bj的主对角线为零，而Seidel迭代矩阵Bs的第1列都是零，这对一般情况也是成立的。,举例检验Jacoai迭代的收敛性,首先将原方程组写为迭代形式的方程组，即：,求任一行之和的最大值1,即：|M|=max5/8,5/11,9/12=9/121,i,或求任一列之和的最大值1,即：|M|1=max114/132,60/96,