北京理工大学数值分析课件3解线性方程组的迭代法

第三章解线性方程组的迭代法迭代法：用某种极限过程去逐步逼近方程组的精确解，优点是需要计算机的存储单元少，程序设计简单，原始系数矩阵在计算机中始终不变，但存在收敛性和收敛速度等问题。它是解大型稀疏系数矩阵方程组的有效方法。）任意选定的初始向量（）迭代公式（)0()()1()(xxGxnnn迭代的向量序列（收敛到方程组的精确解）)(nx作足够多的有限次迭代，得到满足精度要求的近似解要解决的主要问题1.如何构造迭代公式从而产生迭代向量序列2.向量序列是否收敛到精确解的判别3.即使收敛，收敛的速度又如何4.误差估计迭代公式构造的一般思路bAxgMxx,2,1,0,)()1(kgMxxkk要解的方程组同解的方程组迭代公式注：称作一阶线性定常迭代公式，M称作迭代矩阵向量序列与矩阵序列的收敛性:xxxxRxxRxRxkkknkknnk)()()()(lim,}{0lim,}{记为收敛于列中的向量范数，则称序为其中如果：中的向量序列，为定义：设),...,(),,...,,(),...2,1(limlim21)()(2)(1)()()(knknkkkikikkxxxxxxxxnixxxx其中定理：AAAAAAnAnAkkkkk)(k)()()(lim,}{0lim}{记作：收敛于为矩阵范数，则称序列其中如果阶方阵，为阶方阵序列，为定义：设)(),(),...2,1,(limlim:)()()()(ijkijkijkijkkkaAaAnjiaaAA其中定理§1雅可比（Jacobi）迭代法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111nnnnnnnnnnngxmxmxmxgxmxmxmxgxmxmxmx2211222221212112121111nnnnnnnnngggxxxmmmmmmmmmxxx212121222121121121gMxxbAx方程组可同解变形为：若),,2,1(0niaii112112111111221221222222121121nnnnnnnnnnnnnnnnnnnaabxxxaaaaabxxxaaaaaabxxxxaaaa,...2,1,0)()1(kgMxxkkgMxxnnnknnnnnknnnknnnknknnkkknnkkabxaaxaaxaaxabxaaxaaxabxaaxaax)(11)(22)(11)1(222)(222)(12221)1(2111)(111)(21112)1(1迭代法的计算公式：Jacobi即),,2,1(11)(11)()1(nixaxabaxnijkjijijkjijiiiki,...2,1,0)()1(kgMxxkk记),,2,1,,(njijiaabiiijij),,2,1(niabgiiii0003212232111312nnnnnbbbbbbbbbBngggg21)()1(gBxxJacobikk迭代法的矩阵形式：Jacobi迭代矩阵计算公式：),,(,,1111nnaadiagDbDgADIB.3),2,1(,1,5)0(，否则输出失败信息转置、若nixxkkNkii;5.,4)0(否则转输出，停、若xx)(1,...2,131)0()0(11nijjijjijijiiiixaxabaxni、对;,),,...,(,),...,(),(1)0()0(2)0(1)0(21NxxxxbbbbaAnTnij最大容许迭代次数误差、输入迭代）算法Jacobi(1.3;12k、置例1用Jacobi迭代法求解线性方程组4258321072210321321321xxxxxxxxx解：Jacobi迭代计算公式为4.82.02.03.82.01.02.72.01.0)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx,)0,0,0()0(Tx取4258321072210321321321xxxxxxxxx50.114.866.144.170.103.868.172.071.92.768.183.0)2(3)2(2)2(1xxxTx)13,12,11(依次下去收敛于真解Tx)4.8,3.8,2.7()1(x=Jacobi_iter(A,b,20,1e-5,x0)kx1x2x3....1.00007.20008.30008.40002.00009.710010.700011.50003.000010.570011.571012.48204.000010.853511.853412.82825.000010.951011.951012.94146.000010.983411.983412.98047.000010.994411.994412.99338.000010.998111.998112.99789.000010.999411.999412.999210.000010.999811.999812.999711.000010.999911.999912.999912.000011.000012.000013.000013.000011.000012.000013.000014.000011.000012.000013.0000Jacobimethodconvergedx=11.000012.000013.0000,)()1(gBxxkk令写成矩阵形式ADIB1TgBxx)8.4,8.3,2.7()0()1(得4258321072210321321321xxxxxxxxx02.02.02.001.02.01.00bDg1T)8.4,3.8,2.7(Tx)12.9992,11.9994,9994.10()9(Tx)0,0,0()0(取依次下去，Tx)13,12,11(收敛于精确解)1()(gBxxkk§2高斯－赛德尔（Gauss－Seidel）迭代法即),,2,1(11)(11)()1(nixaxabaxnijkjijijkjijiiikinnnknnnnnknnnknnnknknnkkknnkkabxaaxaaxaaxabxaaxaaxabxaaxaax)(11)(22)(11)1(222)(222)(12221)1(2111)(111)(21112)1(1:迭代的计算公式Jacobi即),,2,1(11)(11)1()1(nixaxabaxnijkjijijkjijiiikinnnknnnnnknnnknnnknknnkkknnkkabxaaxaaxaaxabxaaxaaxabxaaxaax)1(11)1(22)1(11)1(222)(222)1(12221)1(2111)(111)(21112)1(1:迭代的计算公式SeidelGauss记0000000000000000000000000000322311312321323121nnnnnnaaaaaaUaaaaaaL),,,(2211nnaaadiagDGauss－Seidel迭代法的矩阵表示：bLDUxLDxkk1)(1)1()()()()()1(1)1(bUxLxDxkkk),,2,1(11)(11)1()1(nixaxabaxnijkjijijkjijiiikibUxxLDkk)()1()(ULDMs1)(:迭代矩阵为例2用Gauss-Seidel迭代法求解线性方程组4258321072210321321321xxxxxxxxx解：G-S迭代计算公式为4.82.02.03.82.01.02.72.01.0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxxTTxx)11.644,02.9,2.7(,)0,0,0()1()0(取4258321072210321321321xxxxxxxxx8205.124.833438.208616.26719.113.83288.204308.14308.102.73288.2902.0)2(3)2(2)2(1xxxTx)13,12,11(依次下去收敛于真解x=Gauss_Seidel_iter(A,b,20,1e-5,x0)kx1x2x3.....1.00007.20009.020011.64402.000010.430811.671912.82053.000010.931311.957212.97774.000010.991311.994712.99725.000010.998911.999312.99966.000010.999911.999913.00007.000011.000012.000013.00008.000011.000012.000013.0000Gauss_seidelmethodconvergedx=11.000012.000013.0000x=Jacobi_iter(A,b,20,1e-5,x0)kx1x2x3....1.00007.20008.30008.40002.00009.710010.700011.50003.000010.570011.571012.48204.000010.853511.853412.82825.000010.951011.951012.94146.000010.983411.983412.98047.000010.994411.994412.99338.000010.998111.998112.99789.000010.999411.999412.999210.000010.999811.999812.999711.000010.999911.999912.999912.000011.000012.000013.000013.000011.000012.000013.000014.000011.000012.000013.0000Jacobimethodconvergedx=11.000012.000013.0000求G-S的迭代矩阵?ULDMS1)(4258321072210321321321xxxxxxxxx000200210511010100101.)(收敛于真解依次下去，kx084.0022.0022.001.002.01.