第二章 线性方程组的数值解法2

§2线性方程组的迭代解法设有n元线性方程组其中系数矩阵的对角元素。nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111A),,2,1(0niaiibAX§2线性方程组的迭代解法记则方程组可用矩阵形式表示为nnaaa2211D0000321323121nnnaaaaaaL0000,122311312nnnnaaaaaaUbXULD)(§2线性方程组的迭代解法雅可比（Jacobi）迭代法矩阵形式为其中，)(1...................................................................)(1)(1)(11,)(22)(11)1(2)(2)(323)(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax,2,1,0,)()1(kkkdBXX)(1ULDBbDd1§2线性方程组的迭代解法高斯-赛德尔（Gauss-Seidel）迭代法矩阵形式为其中，特点：单次迭代计算量与雅可比迭代法相同，但是计算速度加快且存储量小，看作是雅可比迭代法的一种修正。)(1...................................................................)(1)(1)1(11,)1(22)1(11)1(2)(2)(323)1(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax1)()1(dGXXkkULDG1)(bLDd11)(§2线性方程组的迭代解法k)(1kx)(2kx)(3kx)(4kx)()1(1maxkikinixx000001-0.4-0.65-1.2752.32.320.395-1.551875-1.20031252.778750.90187530.7818125-1.8374453-1.08051172.92216740.3868125130.9999908-1.9999932-1.00000352.99999680.0000160140.9999966-1.9999975-1.00000132.99999880.0000058§2线性方程组的迭代解法逐次超松弛（SOR）迭代法松弛迭代法是高斯-赛德尔迭代法的一种加速方法，其基本思想是将高斯-赛德尔迭代法得到的第次近似解向量与第次近似解向量做加权平均，当权因子选取适当时，加速效果显著。迭代公式为式中为松弛因子。1k)1(kXk)(kX)(1~1)(11)1()1(nijkjijijkjijiiikixaxabax),2,1,0;,,2,1(),~()()1()()1(knixxxxkikikiki§2线性方程组的迭代解法注意：使上式收敛速度最快的称为最优松弛因子。目前尚无简易通用的确定最优松弛因子的有效办法，在实际中往往通过试算来确定。经验告诉我们，当小于最优松弛因子时，迭代序列单调收敛；而大于最优松弛因子时，往往发生摆动。)(kX)(kX§2线性方程组的迭代解法设线性方程组，其迭代公式为，由于不等于方程组的精确解，因此令称为剩余向量。于是迭代公式改写为为了加快收敛速度，剩余向量乘上一个适当的因子，得到加速迭代公式，分量形式为bAXdBXX)()1(kk)(kX0AXb)(k)()(kkAXbr),2,1,0()()()()()()()1(kkkkkkkrXAXbXbXAIX)(kr)()()()1(kkkAXbXX,2,1,0;,,2,1),(1)()()1(knixabxxnjkjijikiki§2线性方程组的迭代解法依照上述加速收敛思想，对高斯-赛德尔迭代法加以修正，得到逐次超松弛迭代法，简称SOR法。其迭代公式如下：任给当时，上式称为低松弛迭代法（SUR法），常用于使不收敛的迭代过程收敛；当时，上式称为超松弛迭代法（SOR法），常用于加速收敛的迭代过程；当时即为高斯-赛德尔迭代法。),,2,1()0(nixi)(11)()1()()1(ijnijkjijkjijiiikikixaxabaxx),2,1,0;,,2,1(kni1011§2线性方程组的迭代解法例：超松弛迭代法解方程组，解：超松弛迭代法的迭代公式为15.1)72312(7)426(4)3826(8)252(5)(4)1(3)1(2)1(1)(4)1(4)(4)(3)1(2)1(1)(3)1(3)(4)(3)(2)1(1)(2)1(2)(4)(3)(2)(1)(1)1(1kkkkkkkkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxxxxxxxx§2线性方程组的迭代解法k)(1kx)(2kx)(3kx)(4kx)()1(1maxkikinixx000001-0.4600000-0.7302500-1.43735632.72804032.728040320.7012641-1.9244233-0.98555132.94971201.194173331.0076221-1.9939216-0.98901553.00218920.306358141.0009921-2.0037201-0.99985283.00161970.010837351.0014857-2.0005888-0.99972203.00020000.003131361.0000685-2.0000576-1.00004643.00002490.001417371.0000037-1.9999965-1.00000112.99999550.000064880.9999963-1.9999974-1.00000112.99999910.0000074迭代8次后满足迭代终止条件，得到方程组的近似解为T)9999991.2,0000011.1,9999974.1,9999963.0()8(X§3迭代法的收敛性定义（向量范数）：对任意n维向量，若按一定规则对应一非负实数，它满足以下条件：（1）正定条件：，当且仅当时，；（2）齐次性：，为任意实数；（3）三角不等式：，对任意；则称为向量的范数或模。nRXX0X0X0XXXkkkYXYXnRYX,XX§3迭代法的收敛性设，常用的向量范数有：分别称为向量1范数、向量2范数、无穷范数。TnxxxX),,,(21nxxx211X222212nxxxXinixmax1X§3迭代法的收敛性定义（严格对角占优阵）：设，如果满足条件即矩阵的每一行对角元素的绝对值都严格大于同行的其它元素的绝对值之和，则称为严格对角占优阵。定义（谱半径）：设n阶矩阵的特征值为，称为矩阵的谱半径。nnija)(AAniaanijiijii,,2,1,1AAnnRA),,2,1(niiiniAmax1)(A§3迭代法的收敛性定理1：对任意的初始向量及任意的右端向量，迭代法收敛的充分必要条件是谱半径。定理4：若的系数矩阵为严格对角占优阵，则解此方程组的雅可比迭代法和高斯-赛德尔迭代法都收敛。定理5：若的系数矩阵为对称正定矩阵，则解此线性方程组的高斯-赛德尔迭代法收敛。)0(XddMXX)()1(kk1)(MbAXnnRAbAXA§3迭代法的收敛性定理6：若解的SOR法收敛，则。定理7：若的系数矩阵为对称正定矩阵，且，则解此方程组的SOR法收敛。),,2,1,0(niaiibAX20bAXA20§3迭代法的收敛性例：讨论用雅可比迭代法和高斯-赛德尔迭代法解方程组的收敛性，其中解：，所以方程组有唯一解。雅可比迭代法的迭代矩阵为bAX122111221A531b01detAAIU)(LDB1022101220§3迭代法的收敛性经过计算得到其三个特征值都为0，因此，所以雅可比迭代法收敛。高斯-赛德尔迭代法的迭代矩阵为经过计算得到其三个特征值为0，2，2，因此，所以高斯-赛德尔迭代法不收敛。10)(BULDG1)(0001002201220110011000100220120011001200320220