第八章 线性方程组迭代法

1、引言引言n直接法是通过有限步运算后得到线性方程组的解直接法是通过有限步运算后得到线性方程组的解, ,对于阶数不高的方程组，直接法非常有效，对于对于阶数不高的方程组，直接法非常有效，对于阶数高，而系数矩阵稀疏的线性方程组却存在着阶数高，而系数矩阵稀疏的线性方程组却存在着困难，在这类矩阵中，非零元素较少，若用直接困难，在这类矩阵中，非零元素较少，若用直接法求解，就要存贮大量零元素。为减少运算量、法求解，就要存贮大量零元素。为减少运算量、节约内存，使用节约内存，使用迭代法迭代法更有利。更有利。n线性方程组的迭代法主要有线性方程组的迭代法主要有JacobiJacobi迭代法、迭代法、SeidelSei

2、del迭代法和超松弛迭代法和超松弛( (SOR)SOR)迭代法迭代法. .迭代法的基本思想迭代法的基本思想gBxxbAx ( (矩阵矩阵B B不唯一不唯一) )对应写出对应写出 )0()()1( ), 2 , 1 , 0( xkgBxxkk取定初始向量产生向量序列产生向量序列,)1()()2()1( kkxxxx若收敛若收敛, ,记记xxkk )1(lim两端取极限有：两端取极限有：, gxBx 注意注意: : 迭代阵迭代阵B B不唯一不唯一, ,影响收敛性。影响收敛性。B B叫迭代矩阵。叫迭代矩阵。 x上式说明：上式说明： 是解向量是解向量 , ,从而当从而当k k充分大时充分大时 )1(k

3、x 解向量解向量xx 例：若给出解例：若给出解 的迭代公式为的迭代公式为bAx 1 , 0),()()()1(kbxAxxkkk则其迭代矩阵为（则其迭代矩阵为（ ）AI例：用迭代法解线性方程组例：用迭代法解线性方程组352322121xxxx解：构造方程组的等价方程组解：构造方程组的等价方程组3423212211xxxxxx据此建立迭代公式据此建立迭代公式3423)(2)(1)1(2)(2)(1)1(1kkkkkkxxxxxx取取 ，计算得，计算得0)0(2)0(1 xx33)1(2)1(1xx33)2(2)2(1xx99)3(2)3(1xx1515)4(2)4(1xx3333)5(2)5(1

4、xx可见该迭代不收敛可见该迭代不收敛因此，迭代法的关键包括以下因此，迭代法的关键包括以下两方面：两方面：（1 1）如何构造迭代格式）如何构造迭代格式（2 2）由迭代格式产生的向量）由迭代格式产生的向量序列的收敛性如何序列的收敛性如何nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111雅克比（雅克比（Jacobi）迭代法）迭代法设有设有n阶方程组阶方程组若系数矩阵非奇异，且若系数矩阵非奇异，且 (i = 1, 2, n)，将方程组改写成将方程组改写成0iia11,22112323121222213132121111111nnnnnnnnnnnnn

5、xaxaxabaxxaxaxabaxxaxaxabax然后写成迭代格式然后写成迭代格式)(11,)(22)(11)1()(2)(323)(121222)1(2)(1)(313)(212111)1(1111knnnknknnnnknknnkkkknnkkkxaxaxabaxxaxaxabaxxaxaxabax上式也可以简单地写为上式也可以简单地写为), 2, 1(1)(1)1(nixabaxkjnijjijiiiki写成写成矩阵形式矩阵形式：A =LUDBgJacobi 迭代阵迭代阵bDxULDxkk1)(1)1()( bxULxDbxULDbxA )()(bDxULDx11)( )(11)(1

6、)(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 只存一组向量即可。只存一组向量即可。写成写成矩阵形式矩阵形式：bDxUxLDxkkk1)()1(1)1()( bxUxLDkk )()1()(bLDxULDxkk1)(1)1()()( BgGauss-Seidel 迭代

7、阵迭代阵高斯高斯赛得尔赛得尔(Gauss-Seidel)迭代法迭代法解：解： jacobijacobi迭代法的迭代公式为迭代法的迭代公式为1 , 04/ )122(11/ )334(8/ )2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kxxxxxxxxxkkkkkkkkk前前3 3个迭代值为个迭代值为例：分别用例：分别用jacobijacobi迭代法和迭代法和G-SG-S迭代法解线性方程组迭代法解线性方程组12423311420238321321321xxxxxxxxx以以 为初始向量，计算前为初始向量，计算前3 3个迭代值，并与精确解个迭代值，并与精确解 作比较。作

8、比较。Tx)0 , 0 , 0()0(T) 1 , 2 , 3(Tx)0000. 3 ,0000. 3 ,5000. 2()1(Tx)0000. 1 ,3636. 2 ,8750. 2()2(Tx)97159. 0 ,0455. 2 ,1364. 3()3(G-SG-S迭代法的迭代公式为迭代法的迭代公式为1 , 04/ )122(11/ )334(8/ )2023()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kxxxxxxxxxkkkkkkkkk前前3 3个迭代值为个迭代值为Tx)2273. 1 ,0909. 2 ,5000. 2()1(Tx)0043. 1 ,0289.

9、 2 ,9772. 2()2(Tx)9959. 0 ,9968. 1 ,0098. 3()3(方法优缺点讨论方法优缺点讨论由以上例题的求解过程可明显看出由以上例题的求解过程可明显看出GSGS迭代法迭代法的收敛速度比简单迭代法快，但对于任意给定的收敛速度比简单迭代法快，但对于任意给定的一个方程组分别用简单迭代法和的一个方程组分别用简单迭代法和GSGS迭代法求迭代法求解时，两种迭代法可能都收敛，也可能都不收解时，两种迭代法可能都收敛，也可能都不收敛也有可能是敛也有可能是GSGS迭代法收敛而迭代法收敛而J J迭代法不收敛迭代法不收敛但亦有相反情况，即简单迭代法收敛而但亦有相反情况，即简单迭代法收敛而

10、GSGS迭迭代法不收敛而且交换方程组中的方程和未知代法不收敛而且交换方程组中的方程和未知数的次序都会影响数的次序都会影响GSGS迭代法的计算结果，但这迭代法的计算结果，但这种交换对简单迭代法是没有影响的。种交换对简单迭代法是没有影响的。 例：设方程组为例：设方程组为3103220241225321321321xxxxxxxxx试分别写出其试分别写出其JacobiJacobi迭代格式和迭代格式和SeidelSeidel迭代格式以及相应的迭代矩阵。迭代格式以及相应的迭代矩阵。 解：解：JacobiJacobi迭代格式为迭代格式为103)(2103)(151)(2)(1101)1(3)(321)(1

11、41)(3)(141)1(2512)(351)(252)(3)(251)1(1)323(5220()212(kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx故故JacobiJacobi迭代矩阵为迭代矩阵为 0001035121415152SeidelSeidel迭代格式为迭代格式为103)1(2103)1(151)1(3)(321)1(141)1(2512)(351)(252)1(15kkkkkkkkkxxxxxxxxx即即1021)(381)(2201)1(3522)(32011)(2101)1(2512)(351)(252)1(1.kkkkkkkkkxxxxxxxxx故可得故可

12、得SeidelSeidel迭代矩阵为迭代矩阵为 8120120111015152000 从例中可以看出从例中可以看出JacobiJacobi迭代矩阵迭代矩阵BjBj的主对角线为零，而的主对角线为零，而SeidelSeidel迭代矩迭代矩阵阵BsBs的第的第1 1列都是零，这对一般情况也是成立的。列都是零，这对一般情况也是成立的。超松驰法超松驰法)(1)1(11)1(1kjnijijkjijijiiikixaxabax), 2, 1()1 (1)()1(nixxxkikiki)(1)1(11)()1()1 (kjnijijkjijijiiikikixaxabaxx迭代迭代加速加速是松驰因子是松驰

13、因子 20迭代法的收敛条件迭代法的收敛条件定理定理1：对任意初始向量对任意初始向量X(0)及常向量及常向量F，迭代格式迭代格式FBXXkk )1(定理定理2：若迭代矩阵若迭代矩阵的的某种范数某种范数 则上式则上式1B收敛的充分必要条件是迭代矩阵收敛的充分必要条件是迭代矩阵B B的谱半径的谱半径 (B) 1。确定的迭代法对任意初值确定的迭代法对任意初值X(0)均收敛于方程组均收敛于方程组X = BX + F的唯一解的唯一解x*。 定义定义：如果矩阵的每一行中如果矩阵的每一行中，不在主对角线上的所有不在主对角线上的所有 元素绝对值之和小于主对角线上元素的绝对值元素绝对值之和小于主对角线上元素的绝对

14、值， 即即niaaiinijjij, 2, 11则称矩阵则称矩阵A按行严格对角占优按行严格对角占优，类似地类似地，也有按列也有按列严格对角占优。严格对角占优。定理定理3：若线性方程组若线性方程组AX = b的系数矩阵的系数矩阵A按行严格对角按行严格对角 占优占优，则雅克比迭代法和高斯则雅克比迭代法和高斯赛得尔迭代法赛得尔迭代法 对任意给定初值均收敛对任意给定初值均收敛。 例：设方程组为例：设方程组为23 . 0122121xxxx试讨论用试讨论用JacobiJacobi迭代法和迭代法和SeidelSeidel迭代法求解此方程组的收敛性。迭代法求解此方程组的收敛性。 解：解：JacobiJacobi迭代格式为迭代格式为23 . 012)(1)1(2)(2)1(1kkkkxxxx故故JacobiJacobi迭代矩阵为迭代矩阵为 03 . 020其特征值为其特征值为 6 . 0故其谱半径为故其谱半径为 16 . 0故故JacobiJacobi迭代法收敛迭代法收敛SeidelSeidel迭代格式为迭代格式为2) 12(3 . 012)(2)1(2)(2)1(1kkkkxxxx故故G-S