数值分析第三章解线性方程组的迭代法

1、1第三章第三章 解线性方程组的迭代法解线性方程组的迭代法 Jacobi迭代法迭代法 Gauss-Seidel迭代法迭代法 迭代法的收敛条件迭代法的收敛条件(充要条件充要条件, 充分条件充分条件)bAx 求求 迭代法概述迭代法概述23.1 迭代法概述迭代法概述 gMxxbAx 等价线性方程组等价线性方程组取初始向量取初始向量 x(0) Rn, 构造如下构造如下单步定常线性单步定常线性迭代迭代公式公式), 2, 1, 0()()1( kgMxxkk以此来产生近似向量序列以此来产生近似向量序列 x(1), x(2), .当当k充分大时充分大时, .*)(xxk 基本思想基本思想等价变形等价变形如何做

2、如何做收敛性条件收敛性条件M: 迭代矩阵迭代矩阵30|lim)( xxkk0|lim)( AAkkxxkk )(limAAkk )(lim定义定义 对于对于Rn中的向量序列中的向量序列 x(k), 如果如果则称则称向量序列向量序列x(k)收敛于收敛于 Rn中的向量中的向量 x.定义定义对于对于n阶方阵序列阶方阵序列 A(k), 如果如果则称则称方阵序列方阵序列A(k)收敛于收敛于n阶方阵阶方阵A. 上面两式通常表示成上面两式通常表示成 向量序列与矩阵序列的收敛概念向量序列与矩阵序列的收敛概念4）（njxxjkjk,.,2 , 1,lim)( ),.,2 , 1,lim)(njiaaijkijk

3、 （定理定理 Rn中的向量序列中的向量序列x(k)收敛于收敛于Rn中的向中的向量量x的充分必要条件是的充分必要条件是其中其中xj(k)和和 xj分别表示分别表示 x(k)和和 x中的第中的第 j个分量个分量.定理定理 n阶方阵序列阶方阵序列A(k)收敛于收敛于n阶方阵阶方阵A的充的充分必要条件是分必要条件是 向量序列与矩阵序列收敛的充分必要条件向量序列与矩阵序列收敛的充分必要条件 向量序列和矩阵序列的收敛可归结为对应分向量序列和矩阵序列的收敛可归结为对应分量或对应元素序列的收敛性量或对应元素序列的收敛性.5 若由迭代公式若由迭代公式gMxxkk )()1(产生的向量序列产生的向量序列 x(k)

4、 收敛于向量收敛于向量 x, 则则gMxxgMxxkkkk )()1(limlim即向量即向量 x 是是 方程方程 Ax=b 的解的解. 单步定常线性迭代法产生的向量序列若收敛则单步定常线性迭代法产生的向量序列若收敛则必收敛到原线性方程组的解必收敛到原线性方程组的解.6 4444343242141343433323213124243232221211414313212111bxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxa n=4的的Jacobi迭代法迭代法把方程组改写成如下等价形式把方程组改写成如下等价形式 4434324214144334342321313322424

5、323121221141431321211/ )(/ )(/ )(/ )(axaxaxabxaxaxaxabxaxaxaxabxaxaxaxabxbAx gMxx 3.2 几种基本的迭代法几种基本的迭代法7 44)(343)(242)(1414)1(433)(434)(232)(1313)1(322)(424)(323)(1212)1(211)(414)(313)(2121)1(1/ )(/ )(/ )(/ )(axaxaxabxaxaxaxabxaxaxaxabxaxaxaxabxkkkkkkkkkkkkkkkk n=4的的Jacobi迭代法计算公式迭代法计算公式, 2 , 1 , 0 k已

6、知已知 用上述迭代公式可算得用上述迭代公式可算得 )0(4)0(3)0(2)0(1)0(xxxxx )(4)(3)(2)(1)(kkkkkxxxxx, 2 , 1 k8 n=4的的Jacobi迭代法迭代法矩阵表示矩阵表示 0 00 0444344424441333433323331222422232221111411131112 aaaaaaaaaaaaaaaaaaaaaaaaM )()1(gMxxkk 444333222111ababababg9 Jacobi迭代法迭代法,1)1(1)1(11ininiiiiiiiiiibxaxaxaxaxa ,1)1(1)1(11ininiiiiiiiii

7、ibxaxaxaxaxa ,1)1(1)1(11iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k)(k)(k+1), 2 , 1(ni Tknkkkxxxx)()(2)(1)(, 10 设设D为由为由A的对角线元素构成的对角矩阵的对角线元素构成的对角矩阵Jacobi迭代公式迭代公式bDxADIxbxADDxbAx11)()( bDxADIxkk1)(1)1()( Jacobi迭代法的矩阵表示迭代法的矩阵表示 迭代矩阵迭代矩阵ADIM1 11例例 用用Jacobi迭代法求解线性方程组迭代法求解线性方程组 4258321072210321321321xx

8、xxxxxxx解解 将方程组改写成如下等价形式将方程组改写成如下等价形式 4 . 82 . 02 . 03 . 82 . 01 . 02 . 72 . 01 . 0213312321xxxxxxxxx12Jacobi迭代法计算公式为迭代法计算公式为 4 . 82 . 02 . 03 . 82 . 01 . 02 . 72 . 01 . 0)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx假设初始向量取假设初始向量取 x(0)=(0, 0, 0)T.第一次迭代第一次迭代Tx)4 . 8, 3 . 8, 2 . 7()1( 第二次迭代第二次迭代71.

9、92 . 74 . 82 . 03 . 81 . 0)2(1 x7 .103 . 84 . 82 . 02 . 71 . 0)2(2 x50.114 . 83 . 82 . 02 . 72 . 0)2(3 x13 实际计算时，迭代法中止条件实际计算时，迭代法中止条件 |max|max)()1(11kikiniinixxx其中其中 为给定的要求精度为给定的要求精度.14 n=4的的Gauss-Seidel迭代法迭代法把方程组改写成如下等价形式把方程组改写成如下等价形式 4434324214144334342321313322424323121221141431321211/ )(/ )(/ )(

10、/ )(axaxaxabxaxaxaxabxaxaxaxabxaxaxaxabxbAx )(k)(k)(k)(k)(k)(k)1( k)1( k)1( k)1( k)1( k)1( k)1( k)1( k)1( k)1( k1511)(414)(313)(2121)1(1/ )(axaxaxabxkkkk 22)(424)(323)1(1212)1(2/ )(axaxaxabxkkkk 33)(434)1(232)1(1313)1(3/ )(axaxaxabxkkkk 44)1(343)1(242)1(1414)1(4/ )(axaxaxabxkkkk n=4的的Gauss-Seidel迭代法

11、迭代法16 Gauss-Seidel迭代法迭代法,1)1(1)1(11ininiiiiiiiiiibxaxaxaxaxa ,1)1(1)1(11ininiiiiiiiiiibxaxaxaxaxa ,1)1(1)1(11iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k+1)(k+1)(k+1), 2 , 1(ni 17在迭代的每一步设定计算顺序在迭代的每一步设定计算顺序并且，在计算迭代值并且，在计算迭代值 充分利用它前面的新信息充分利用它前面的新信息这样设计出来的迭代公式这样设计出来的迭代公式称为称为高斯高斯塞德尔迭代公式塞德尔迭代公式.)1()1(2

12、)1(1 knkkxxx)1( kix)1(1)1(2)1(1, kikkxxxni, 2 , 1 ,11)(11)1()1( nijkjijijkjijiiikixaxabax Gauss-Seidel迭代法迭代法18 Gauss-Seidel迭代法的矩阵表示迭代法的矩阵表示 设将系数矩阵设将系数矩阵A 分裂为分裂为,UDLA 其中其中D为对角阵为对角阵, L 和和U分别为严格下三角和严格上三分别为严格下三角和严格上三角阵角阵.bLDUxLDxkk1)(1)1()()( gMxbLDUxLDxbUxxLD b U)xDL(Ax 11)()()(U LDM1)( 迭代矩阵迭代矩阵GaussSe

13、idel迭代公式迭代公式19例例 用用Gauss-Seidel迭代法求解线性方程组迭代法求解线性方程组 4258321072210321321321xxxxxxxxx解解 将方程组改写成如下等价形式将方程组改写成如下等价形式 4 . 82 . 02 . 03 . 82 . 01 . 02 . 72 . 01 . 0213312321xxxxxxxxx20Gauss-Seidel迭代法计算公式为迭代法计算公式为 4 . 82 . 02 . 03 . 82 . 01 . 02 . 72 . 01 . 0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxx

14、xxx假设初始向量取假设初始向量取 x(0)=(0, 0, 0)T.第一次迭代第一次迭代2 . 7)1(1 x02. 93 . 82 . 71 . 0)1(2 x644.114 . 802. 92 . 02 . 72 . 0)2(3 x21第二次迭代第二次迭代4308.102 . 7644.112 . 002. 91 . 0)2(1 x6719.113 . 8644.112 . 04308.101 . 0)2(2 x8205.124 . 86719.112 . 04308.102 . 0)2(3 xGauss-Seidel迭代法计算公式为迭代法计算公式为 4 . 82 . 02 . 03 .

15、82 . 01 . 02 . 72 . 01 . 0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx假设初始向量取假设初始向量取 x(0)=(0, 0, 0)T.22 Jacobi迭代法：迭代法： )1()1(2)1(1)(knkkkxxxx已知已知x(k+1)分量的计算可以分量的计算可以同同时时进行进行, 无先后次序无先后次序 Gauss-Seidel迭代法：迭代法：)1()1()1(2)1(1)( kxknkkkxxxx已知已知x(k+1)分量的计算有分量的计算有先后次序先后次序, 必须先计算必须先计算x(k+1)前前面的分量然后再计算

16、下一分量面的分量然后再计算下一分量.23 Jacobi迭代法与迭代法与Gauss-Seidel迭代法的计算效果迭代法的计算效果哪一种更好哪一种更好? 前例计算结果表明前例计算结果表明, 用用Gauss-Seidel迭代法比用迭代法比用Jacobi迭代法效果好迭代法效果好. 但对一般情形但对一般情形, 有些问题有些问题Gauss-Seidel迭代法确迭代法确实比实比Jacobi迭代法收敛得快迭代法收敛得快, 但也有但也有Gauss-Seidel迭迭代法比代法比Jacobi迭代法收敛得慢迭代法收敛得慢, 甚至还有甚至还有Jacobi迭迭代法收敛代法收敛, 但但Gauss-Seidel迭代法发散的情

17、形迭代法发散的情形.243.3 迭代法的收敛条件迭代法的收敛条件|max)(1iniA 定义定义(谱半径谱半径) 设设n阶方阵阶方阵A的特征值为的特征值为 i (i=1,2,n), 则称则称为矩阵为矩阵A的的谱半径谱半径. Ak 的特征值为的特征值为knkk ,21故故 kkinikinikAA)(|max|max)(11 25|)(AA iiiuAu 矩阵范数和谱半径有如下关系矩阵范数和谱半径有如下关系设设A的任一特征值为的任一特征值为 i , 对应的特征向量为对应的特征向量为ui , 则则|iiiiiiuAAuuu |Ai 由由 的任意性可知结论成立的任意性可知结论成立. 矩阵矩阵A的谱半

18、径不超过它的任何一种由向量范数的谱半径不超过它的任何一种由向量范数诱导出的范数，即诱导出的范数，即|A|是是A的特征值的上界的特征值的上界.证证故故从而从而26)()(|)1max2AAAAATT )(|)22AAA 为为对对称称矩矩阵阵，则则若若 设设A为为n阶方阵阶方阵, 则则 由于由于2-范数具有上面的关系式范数具有上面的关系式, 所以称所以称 |A|2 为为谱范数谱范数.27,.,.,2kAAAI0lim kkA1)( A 定理定理 设设A是任意是任意n阶方阵阶方阵, 由由A的各次幂所组成的的各次幂所组成的矩阵序列矩阵序列收敛于零矩阵收敛于零矩阵, 即即的充分必要条件是的充分必要条件是

19、28定理定理 对任何初始向量对任何初始向量 x(0)和右端项和右端项g, 由迭代公式由迭代公式 x(k+1) =Mx(k)+g (k=0, 1, 2, )产生的向量序列产生的向量序列x(k)收敛的充分必要条件是收敛的充分必要条件是 (M)1其中其中 (M)是是迭代迭代矩阵矩阵M的谱半径的谱半径. 迭代法收敛的充分必要条件迭代法收敛的充分必要条件 迭代法的收敛性只与迭代法的收敛性只与迭代矩阵的谱半径迭代矩阵的谱半径有关有关, 而而迭代矩阵是由迭代矩阵是由A演变来的演变来的, 因此迭代法是否收敛只与因此迭代法是否收敛只与系数矩阵系数矩阵A以及演变的方式有关以及演变的方式有关, 与常数项和初始向与常

20、数项和初始向量的选择无关量的选择无关.29证明证明 必要性必要性. 设序列设序列x(k)收敛于收敛于 x*, 则有则有 迭代法收敛的充分必要条件迭代法收敛的充分必要条件 )0()()1(,xgMxxkk任意任意收敛收敛. 1)( M *)0()2(2)1()1()(xxMxxMxxMgMxgMxxxkkkkk 故故gMxx *0lim, 0*)(lim)( kkkkMxx必必须须由于由于x(0)为任意为任意n维向量维向量,即即. 1)( M 30 迭代法收敛的充分必要条件迭代法收敛的充分必要条件 )0()()1(,xgMxxkk任意任意收敛收敛. 1)( M 充分性充分性. 若若 (M)1,

21、则则 =1不是不是M的特征值的特征值, 故故0)det( MI方程方程 (IM)x=g有唯一解有唯一解, 记为记为x*, 即即gMxx *又又 *)0()(xxMxxkk 且且0lim kkM. 0*)(lim*)(lim)0()( xxMxxkkkk故对任意初始向量故对任意初始向量x(0), 均有均有证明证明31推论推论1 若迭代矩阵若迭代矩阵M满足满足|M|1, 则下列迭代公则下列迭代公式对任意初始向量式对任意初始向量x(0)收敛收敛 gMxxkk )()1(32例例 解方程组解方程组 3222122321321321xxxxxxxxx讨论讨论Jacobi迭代法与迭代法与Gauss-Sei

22、del迭代法的收敛性迭代法的收敛性.解解迭代法是否收敛等价于迭代矩阵的谱半径是否小迭代法是否收敛等价于迭代矩阵的谱半径是否小于于1，故先求迭代矩阵，故先求迭代矩阵33 Jacobi迭代法的迭代矩阵为迭代法的迭代矩阵为 0221012201ADIB其特征方程为其特征方程为 221122| BI03 特征值特征值, 0321 谱半径谱半径10)( M 故故Jacobi迭代法迭代法收敛收敛.34 Gauss-Seidel迭代法的迭代矩阵为迭代法的迭代矩阵为ULDM1)( ,122011001)( LD,120011001)(1 LD 000100220120011001)(1ULDM,2003202

23、20 35其特征方程为其特征方程为20032022| MI0)2(2 特征值特征值, 2, 0321 谱半径谱半径12)( M 故故Gauss-Seidel迭代法迭代法发散发散.36 一般来说一般来说, 计算矩阵的谱半径比较困难计算矩阵的谱半径比较困难, 故用迭故用迭代法收敛的充分必要条件来判断迭代法是否收敛往代法收敛的充分必要条件来判断迭代法是否收敛往往不太容易往不太容易, 以下介绍用其他方法判别迭代法收敛以下介绍用其他方法判别迭代法收敛的的充分条件充分条件.37定义定义(严格对角占优阵严格对角占优阵) 称称n 阶方阵阶方阵 是是严格对角占优严格对角占优的，如果其主对角线元素的绝对值大的，如

24、果其主对角线元素的绝对值大于同行其它元素绝对值之和：于同行其它元素绝对值之和：nijaA)( ni, 2 , 1 |, 1iinijjijaa 若线性方程组的系数矩阵为严格对角占优阵，则称若线性方程组的系数矩阵为严格对角占优阵，则称这个线性方程组为这个线性方程组为严格对角占优方程组严格对角占优方程组. 932331261521013218A 93233126152613218B 38 迭代法收敛的充分条件迭代法收敛的充分条件定理定理 若若A为为严格对角占优阵严格对角占优阵, 则求解则求解Ax=b 的的Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.定理定理 若若A

25、为为对称正定阵对称正定阵, 则则求解求解Ax=b的的Gauss-Seidel迭代法收敛迭代法收敛.39例例 方程组方程组Ax=b的系数矩阵为的系数矩阵为 51121012110A严格对角占优阵严格对角占优阵.故故Jacobi迭代法与迭代法与Gauss-Sidel迭代法均收敛迭代法均收敛.40例例 方程组方程组Ax=b的系数矩阵为的系数矩阵为 49103A非对角占优阵非对角占优阵交换交换两个方程的次序，得原方程组的同解方程组两个方程的次序，得原方程组的同解方程组 122110349bbxx 它是一个严格对角占优方程组，对此方程组它是一个严格对角占优方程组，对此方程组Jacobi迭代法和迭代法和G

26、auss-Seidel迭代法均收敛迭代法均收敛. 当所给的方程组不满足迭代法的收敛条件时当所给的方程组不满足迭代法的收敛条件时, 适适当调整方程组中方程的次序当调整方程组中方程的次序, 有时可得到满足迭代法有时可得到满足迭代法收敛条件的同解方程组收敛条件的同解方程组.41例例 方程组方程组Ax=b的系数矩阵为的系数矩阵为 210121012A但但A为对称正定矩阵为对称正定矩阵, Gauss-Seidel迭代迭代法收敛法收敛.要判别要判别Jacobi迭代法是否收敛迭代法是否收敛, 需要计算其迭代需要计算其迭代矩阵的谱半径矩阵的谱半径. 非严格对角占优非严格对角占优42例例 设有方程组设有方程组Ax=b, 其中其中 121212112121211A讨论用两种迭代法求解的收敛性讨论用两种迭代法