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

1计算方法第八章线性方程组的解法计算方法课程组2§8.0引言重要性：解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作用。如弹性力学、电路分析、热传导和振动、以及社会科学及定量分析商业经济中的各种问题。求解线性方程组的求解方法，其中，。AxbnnAR,nxbR假设非奇异，则方程组有唯一解.****12(,,,)TnxxxxA3§8.0引言分类：线性方程组的解法可分为直接法和迭代法两种方法。(a)直接法：对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解。最基本的直接法是Gauss消去法，重要的直接法全都受到Gauss消去法的启发。计算代价高.(b)迭代法：基于一定的递推格式，产生逼近方程组精确解的近似序列.收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题。简单实用,诱人。4§8.1雅可比Jacobi迭代法(AX=b)一、迭代法的基本思想二、例题分析三、Jacobi迭代公式5与解f(x)=0的不动点迭代相类似，将AX=b改写为X=BX+f的形式，建立雅可比方法的迭代格式：其中，B称为迭代矩阵。其计算精度可控，特别适用于求解系数为大型稀疏矩阵(sparsematrices)的方程组。§8.1雅可比Jacobi迭代法(AX=b)迭代法的基本思想(1)()kkxBxf6问题:(a)如何建立迭代格式？(b)向量序列{x(k)}是否收敛以及收敛条件?(1)()kkxBxfAXb72例题分析:其准确解为X*={1.1,1.2,1.3}。考虑解方程组...xxxxxxxxx1231231231027210283542(1)3.1Jacobi迭代法82例题分析:建立与式(1)相等价的形式：.........xxxxxxxxx123213312010207201020830202084(2)其准确解为X*={1.1,1.2,1.3}。考虑解方程组...xxxxxxxxx1231231231027210283542(1)3.1Jacobi迭代法92例题分析:其准确解为X*={1.1,1.2,1.3}。建立与式(1)相等价的形式：.........xxxxxxxxx123213312010207201020830202084考虑解方程组...xxxxxxxxx1231231231027210283542()()()xxx0001230取迭代初值据此建立迭代公式：(+1)()()123(+1)()()213(+1)()()312=0.1+0.2+0.72=0.1+0.2+0.83=0.2+0.2+0.84kkkkkkkkkxxxxxxxxx10迭代结果如下表：迭代次数x1x2x3000010.720.830.8420.9711.071.1531.0571.15711.248241.085351.185341.2828251.0950981.1950991.29413861.0983381.1983371.29803971.0994421.1994421.29933581.0998111.1998111.29977791.0999361.1999361.299924101.0999791.1999791.299975111.0999931.1999931.299991121.0999981.1999981.299997131.0999991.1999991.299999141.11.21.3151.11.21.31111,0(1,2,,)1()(1,2,,)nijjiiiiniiijjjiijiaxbainxbaxina(1)11()(1,2,,)nkkiiijijiijixbaxina设方程组AX=b,通过分离变量的过程建立Jacobi迭代公式，即由此我们可以得到Jacobi迭代公式：§8.1Jacobi迭代公式12(1)1()1()kkxDLUxDb雅可比迭代法的矩阵表示nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.....................22112222212111212111nnnnnnnnnnnnbxaxaaxbxaxaaxbxaxaax11112212122211212111...1...............1...10iia写成矩阵形式：A=LUD()()AxbDLUxbDxLUxb11()xDLUxDbBfJacobi迭代阵13§8.2高斯-塞德尔迭代法(AX=b)(1)kixkkkixxx(1)(1)(1)121,,,()()()121,,,kkkixxx注意到利用Jacobi迭代公式计算时，已经计算好了的值，而Jacobi迭代公式并不利用这些最新的近似值计算，仍用1(1)(1)111()(1,2,,)inkkkiiijjijjjjiiixbaxaxina这启发我们可以对其加以改进,即在每个分量的计算中尽量利用最新的迭代值，得到上式称为Gauss-Seidel迭代法.14)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk)(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk)(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk)(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax…………写成矩阵形式：(1)1(1)()1()kkkxDLxUxDb(1)()()kkDLxUxb(1)1()1()()kkxDLUxDLbBfGauss-Seidel迭代阵§8.2高斯-塞德尔迭代法15其准确解为X*={1.1,1.2,1.3}。.........kkkkkkkkkxxxxxxxxx123213312111111010207201020830202084考虑解方程组...xxxxxxxxx1231231231027210283542高斯-塞德尔迭代法算例高斯-塞德尔迭代格式16迭代次数x1x2x3000010.720.9021.164421.043081.1671881.28205431.093131.1957241.29777141.0991261.1994671.29971951.099891.1999331.29996561.0999861.1999921.29999671.0999981.1999991.29999981.11.21.317开始Niyxii10,01i0TiiiiaTbx/)(Ni1iiixyjjxyNj,1Niix打印结果1ii(0)()1,2.1,21,2,.0,0,1,23.0,1,2114.1ijiiiijiiikiijjiiiNAaBbXxYyabbainajnbinnxxyinxkninjnbaxijxai线形方程组组数系数矩阵常数矩阵迭代过程中的解－上一轮迭代的解将的值赋给计算步骤：１输入原始数据２输入初使迭代值迭代计算如，则精度判断15.1,2iiiiinxyjnyxxin如则转第三步再计算打印计算结果的值TFTFT,,,,,1ijiabNijN输入1,ijjjNijTTax如18逐次超松弛迭代法(SuccessiveOverRelaxationMethod，简写为SOR)可以看作带参数ω的高斯-塞德尔迭代法，是G-S方法的一种修正或加速，是求解大型稀疏矩阵方程组的有效方法之一。§8.3超松驰迭代法SOR方法1.SOR基本思想19设方程组AX=b,其中，A=(aij)为非奇异阵，x=(x1,x2,…,xn)T,b=(b1,b2,…,bn)T.假设已算出x(k)，§8.3超松驰迭代法SOR方法2.SOR算法的构造),,2,1()(1111)1()1(nixaxabaxnijkjijijkjijiiiki(1)(1)()(1)()()(1)()kkkiiikkkiiixxxxxxω称为松弛因子利用高斯-塞德尔迭代法得:20§8.3超松驰迭代法SOR方法2.SOR算法的构造(基于G-S迭代)解方程组AX=b的逐次超松弛迭代公式：),,2,1()()(11)1()()1(nixaxabaxxxxnijkjijijkjijiiiiikiki显然，当取ω=1时，上式就是高斯-塞德尔迭代公式.21§8.3超松驰迭代法SOR方法2.SOR算法的构造(基于Jacobi迭代)得到解方程组AX=b的逐次超松弛迭代公式：(1)()()1()(1,2,,)kkiiinkiiijjjiixxxxbaxina显然，上式就是基于Jacobi迭代的SOR方法.22下面令，希望通过选取合适的来加速收敛，这就是松弛法。inkkiijjijjjbaxax-1(+1)()=1j=i--3.SOR算法的进一步解释SOR方法inkkkiiijjijjjiiixbaxaxa-1(+1)(+1)()j=1=+11=--kkiiiirxa(+1)()=+其中ri(k+1)=相当于在的基础上加个余项生成。)(kix)1(kix01低松弛法=1Gauss-Seidel法21(渐次)超松弛法1kkkiiiiirxxaw(+1)()()=+23利用SOR方法解方程组SOR例题分析:其准确解为x*={1,1,2}.xxxxxxxxx1231231234-2-=0-2+4-2=-2(1)--2+3=3xxxxxxxxx123213312=0.5+0.25=0.5+0.5-0.5(2)12=++133建立与式(1)相等价的形式：24据此建立G-S迭代公式：(k+1)(k)k123(k+1)(k+1)(k)213(k+1)(k+1)(k+1)312=0.5+0.25=0.5+0.5-0.5(3)12=++133xxxxxxxxx取迭代初值:(0)(0)(0)123===1xxx,ω=1.5,迭代结果如下表.SOR迭代公式为：(k+1)(k)(k)(k)1123(k+1)(k)(k+1)(k)2213(k+1)(k)(k+1)(k+1)3312=(1-)+(0.5+0.25)x=(1-)+(0.5+0.5-0.5)(4)12=(1-)+(++1)33xwxwxxwxwxxxwxwxx25GS迭代法须迭代85次得到准确值x*={1,1,2};而SOR方法只须55次即得准确值.由此可见，适当地选择松弛因子ω，SOR法具有明显的加速收敛效果.逐次超松弛迭代法次数x1x2x310.6250000.0625001.75000020.3906250.8828131.46875031.0175780.5166021.80859440.5568850.8809811.71044951.0237120.7434231.868103…………150.9915210.9853181.987416…………250.9985960.9982341.99