1、1第第第第第第6 6 6章章章章章章 解线性方程组的迭代法解线性方程组的迭代法解线性方程组的迭代法解线性方程组的迭代法解线性方程组的迭代法解线性方程组的迭代法6.1 迭代法迭代法的基本概念的基本概念6.2 雅可比迭代法与高斯雅可比迭代法与高斯-赛德尔迭代法赛德尔迭代法21 1 引言引言 我们知道，凡是迭代法都有一个收敛问题，有我们知道，凡是迭代法都有一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设计简单，适于自动计算，而且较直接法具有程序设计
2、简单，适于自动计算，而且较直接法更少的计算量就可获得满意的解。因此，迭代法亦更少的计算量就可获得满意的解。因此，迭代法亦是求解线性方程组，尤其是求解具有大型稀疏矩阵是求解线性方程组，尤其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。的线性方程组的重要方法之一。6.1 迭代法的基本概念迭代法的基本概念32 迭代法的基本思想迭代法的基本思想 迭代法的基本思想是将线性方程组转化为便于迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值迭代的等价方程组，对任选一组初始值 ，按某种计算规则，不断地对所得到的值进行修正，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度
3、要求的方程组的近似解。，最终获得满足精度要求的方程组的近似解。 ), 2 , 1()0(nixi迭代法的基本思想迭代法的基本思想设设 非奇异，非奇异， ，则线性方程组，则线性方程组 有惟一解有惟一解 ，经过变换构造出一个等价，经过变换构造出一个等价同解方程组同解方程组nnRAnRbbAx bAx1dGxx4将上式改写成迭代式将上式改写成迭代式选定初始向量选定初始向量 , ,反复不断地反复不断地使用迭代式逐步逼近方程组的精确解使用迭代式逐步逼近方程组的精确解, ,直到满足精直到满足精度要求为止。这种方法称为迭代法度要求为止。这种方法称为迭代法如果如果 存在极限存在极限 则称迭代法是收敛的，否则就
4、则称迭代法是收敛的，否则就是发散的。是发散的。Tnxxxx)0()0(2)0(1)0(,迭代法的基本思想迭代法的基本思想Tknkkkxxxx)()(2)(1)(,Tnxxxx*2*1*,), 1 , 0()() 1(kdGxxkkTknkkkxxxx)()(2)(1)(,5收敛时，在迭代公式收敛时，在迭代公式中当中当 时，时， , 则则, 故故 是方程组是方程组 的解。的解。对于给定的方程组可以构造各种迭代公式。对于给定的方程组可以构造各种迭代公式。并非全部收敛并非全部收敛 *xbAx 迭代法的基本思想迭代法的基本思想k*)(xxkdGxx*), 1 , 0()()1(kdGxxkk6例例1
5、用迭代法求解线性方程组用迭代法求解线性方程组 352322121xxxx解解 构造方程组的等价方程组构造方程组的等价方程组3423212211xxxxxx据此建立迭代公式据此建立迭代公式 3423)(2)(1)1(2)(2)(1)1(1kkkkkkxxxxxx0)0(2)0(1 xx取取 计算得计算得 例题例题7例题例题迭代解离精确解迭代解离精确解 越来越远迭代不收敛越来越远迭代不收敛 1, 121xx,3333,1515, 99, 33, 33) 5 (2) 5 (1) 4(2) 4(1) 3 (2) 3 (1) 2(2) 2(1) 1 (2) 1 (1xxxxxxxxxx81 1 雅可比（
6、雅可比（JacobiJacobi）迭代法）迭代法 1. 1.雅可比迭代法算法构造雅可比迭代法算法构造 6.2 雅可比迭代法与高斯雅可比迭代法与高斯- -赛德尔迭代法赛德尔迭代法例例2 2 用雅可比迭代法求解方程组用雅可比迭代法求解方程组 3612363311420238321321321xxxxxxxxx9例题例题解：从方程组的三个方程中分离出解：从方程组的三个方程中分离出 和和 21,xx3x341213111114254183213312321xxxxxxxxx10例题例题341213111114254183)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxx
7、xxxxxxx建立迭代公式建立迭代公式 取初始向量取初始向量进行迭代进行迭代, 可以逐步得出一个近似解的序列：可以逐步得出一个近似解的序列：TTxxxx)0 ,0 ,0(),()0(3)0(2)0(1)0(),()(3)(2)(1kkkxxx（k=1, 2, ）11直到求得的近似解能达到预先要求的精度，则迭代直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第解。当迭代到第10次有次有计算结果表明，此迭代过程收敛于方程组的精计算结果表明，此迭代过程收敛于方程组的精确解确解x*= (3, 2, 1)T。
8、 TTxxxx)9998813. 0,999838. 1,000032. 3(),()10(3)10(2)10(1)10(例题例题12nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111nibxainjjij, 2 , 11写成写成 例题例题考察一般的方程组，将考察一般的方程组，将n n元线性方程组元线性方程组 13若若 , ,分离出变量分离出变量 0iia), 2 , 1(niixnixabaxjnijjijiiii,2, 1)(11例题例题据此建立迭代公式据此建立迭代公式 nixabaxnijjkjijiiiki, 2 , 1)(11)()
9、1(上式称为解方程组的上式称为解方程组的Jacobi迭代公式。迭代公式。 142. 雅可比迭代法的矩阵表示雅可比迭代法的矩阵表示 设方程组设方程组 的系数矩阵的系数矩阵A A非奇异，且主对非奇异，且主对角元素角元素 ，则可将，则可将A A分裂成分裂成 bAx ), 2 , 1(0niaii000000001223113122211121323121nnnnnnnnnnaaaaaaaaaaaaaaaA记作记作 A = L + D + U 雅可比（雅可比（Jacobi）迭代法）迭代法15则则 等价于等价于bAx bxUDL)(即即bxULDx)(因为因为 ，则则), 2 , 1(0niaiibDx
10、ULDx11)(这样便得到一个迭代公式这样便得到一个迭代公式bDxULDxkk1)(1)1()(bDxDADk1)(1)(bDxADIk1)(1)(雅可比（雅可比（Jacobi）迭代法）迭代法16000)(21222222111111121nnnnnnnnaaaaaaaaaaaaADIB其中其中 雅可比（雅可比（Jacobi）迭代法）迭代法称为雅可比迭代公式称为雅可比迭代公式, B称为雅可比迭代矩阵称为雅可比迭代矩阵则有则有fBxxkk)()1(（k = 0,1,2）令令bDfADIB11)(17雅可比迭代矩阵表示法，主要是用来讨论其收敛雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中
11、，要用雅可比迭代法公式的分量性，实际计算中，要用雅可比迭代法公式的分量形式。即形式。即 雅可比（雅可比（Jacobi）迭代法）迭代法01231261110114828301ADIB在例在例2中中,由迭代公式写出雅可比迭代矩阵为由迭代公式写出雅可比迭代矩阵为 18雅可比（雅可比（Jacobi）迭代法）迭代法)(1)(1)(1)(11)(22)(11) 1(2)(2)(323)(12122) 1(21)(1)(313)(21211) 1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax(k=0,1,2,) 193 高斯高斯-塞德尔（塞德尔（
12、Gauss-Seidel）迭代法迭代法 1. 高斯高斯-塞德尔迭代法的基本思想塞德尔迭代法的基本思想 在在Jacobi迭代法中，每次迭代只用到前一次的迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，迭代值，若每次迭代充分利用当前最新的迭代值，即在求即在求 时用新分量时用新分量代替旧分量代替旧分量 , 就得到高斯就得到高斯-赛德尔迭代赛德尔迭代法。其迭代法格式为：法。其迭代法格式为： )1( kix)1(1)1(2)1(1,kikkxxx)(1)(2)(1,kikkxxx高斯高斯-赛德尔迭代法赛德尔迭代法)(1111)()1()1(ijnijkjijkjijiiiki
13、xaxabax( (i=1,2,=1,2, ,n k=0,1,2,=0,1,2,) )20例例3 用用GaussSeidel 迭代格式解方程组迭代格式解方程组 35410218321321321xxxxxxxxx精确要求为精确要求为=0.005=0.005 解解 GaussSeidel 迭代格式为迭代格式为5/ )3(10/ )42(8/ ) 1()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx例题例题21例题例题取初始迭代向量取初始迭代向量 , ,迭代结果为：迭代结果为：Tx)0 ,0 ,0()0(Tx)5000. 0,3750. 0,1
14、250. 0()1(Tx)4925. 0,3031. 0,2344. 0()2(Tx)4939. 0,3059. 0,2245. 0()3(Tx)4936. 0,3056. 0,2250. 0()4(x* )3 , 2 , 1(,005. 0)3()4(ixxii222. GaussSeidel 迭代法的矩阵表示迭代法的矩阵表示 将将A分裂成分裂成A =L+D+U，则则 等价于等价于 ( L+D+U )x = b ，于是，于是,则高斯则高斯塞德尔迭代过程塞德尔迭代过程 bAx bUxLxDxkkk)()1()1(因为因为 , ,所以所以 0D0DLDbUxxLDkk)()1()(bLDUxLD
15、xkk1)(1) 1()()(bLDdULDG1111)(,)(1)(1)1(dxGxkk则高斯则高斯- -塞德尔迭代形式为：塞德尔迭代形式为： 故故 令令 高斯高斯-赛德尔迭代法赛德尔迭代法23我们知道我们知道, 对于给定的方程组可以构造成简单迭代公对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯式、雅可比迭代公式、高斯-塞德尔迭代公式，但并塞德尔迭代公式，但并非一定收敛。现在分析它们的收敛性。非一定收敛。现在分析它们的收敛性。 对于方程组对于方程组 经过等价变换构造出的等价方经过等价变换构造出的等价方程组程组 bAx ), 1 , 0()()1(kdGxxkk在什么条件下迭代序
16、列在什么条件下迭代序列 收敛？收敛？)(kx迭代法的收敛性迭代法的收敛性24定理定理1 1 迭代公式迭代公式 收敛收敛的充分必要条件是迭代矩阵的充分必要条件是迭代矩阵G的谱半径的谱半径 。), 1 , 0()() 1(kdGxxkk1)(G迭代法的收敛性迭代法的收敛性25由此定理可知，不论是雅可比迭代法、高斯由此定理可知，不论是雅可比迭代法、高斯塞德塞德尔迭代法还是简单迭代法，它们收敛的充要条件是尔迭代法还是简单迭代法，它们收敛的充要条件是其迭代矩阵的谱半径其迭代矩阵的谱半径 。 1)(G 事实上事实上, 在例在例1中中, 迭代矩阵迭代矩阵G= ，其特征多项式为其特征多项式为,特征值为特征值为
17、 -2，-3， , 所以迭代发散所以迭代发散 421165)det(2GI13)(G迭代法的收敛性迭代法的收敛性26定理定理2 (2 (迭代法收敛的充分条件迭代法收敛的充分条件) )若迭代矩阵若迭代矩阵G G的一种范数的一种范数 , ,则迭代公式则迭代公式收敛。收敛。1G), 1 , 0()()1(kdGxxkk迭代法的收敛性迭代法的收敛性27例例5 已知线性方程组已知线性方程组 6612363311420238321321321xxxxxxxxx考察用考察用Jacobi迭代和迭代和G-S迭代求解时的收敛性迭代求解时的收敛性解解: 雅可比迭代矩阵雅可比迭代矩阵 0123126111011482
18、8300003332333122232221111311121aaaaaaaaaaaaADIB例题例题28 将系数矩阵分解将系数矩阵分解 01023003604012118ULDA则高斯则高斯-塞德尔迭代矩阵塞德尔迭代矩阵 例题例题1129129,115,85maxB故故Jacobi迭代收敛迭代收敛 01023012361148)(111ULDG2918517641,227,85max1G故高斯故高斯塞德尔迭代收敛。塞德尔迭代收敛。 例题例题88717627011222308283001023012144117690111221008130 定理定理3 设设n阶方阵阶方阵 为对角占优阵为对角占
19、优阵, 则非奇则非奇异。异。（证明省略）（证明省略）nnijaA)(迭代法的收敛性迭代法的收敛性系数矩阵为对角占优阵的线性方程组称作对角占优方程系数矩阵为对角占优阵的线性方程组称作对角占优方程组。组。 31定理定理4 对角占优线性方程组对角占优线性方程组 的雅可比的雅可比 迭代公式和高斯迭代公式和高斯-赛德尔迭代公式均收敛。赛德尔迭代公式均收敛。bAx 迭代法的收敛性迭代法的收敛性32定理定理5 若方程组若方程组 的系数矩阵的系数矩阵A是对称正定的，是对称正定的， 则则GS迭代法收敛。迭代法收敛。bAx 迭代法的收敛性迭代法的收敛性33例例6 设求解线性方程组设求解线性方程组 的雅可比迭代的雅
20、可比迭代 bAx , 1 , 0,)()1(kfBxxkk求证当求证当 1 1时时, ,相应的高斯相应的高斯- -塞德尔迭代收敛塞德尔迭代收敛 B例题例题34证证: :由于由于B B是雅可比迭代的迭代矩阵是雅可比迭代的迭代矩阵, ,故有故有 00021222222111111121nnnnnnnnaaaaaaaaaaaaADI例题例题35系数矩阵系数矩阵 为对角占优阵为对角占优阵, ,故故G-SG-S迭代收敛迭代收敛 bAx例题例题11nijjiiijaa则则 niaaiinijjij,2, 1,1又又 1, 1,故有故有 B36例例7 设设 ,证明证明, 求解方程组求解方程组 02211aa
21、22221211212111bxaxabxaxa的的Jacobi迭代与迭代与G-S迭代同时收敛或发散迭代同时收敛或发散 例题例题37证证:雅可比迭代矩阵雅可比迭代矩阵 00222111121aaaaADIB例题例题其谱半径其谱半径 22112112)(aaaaB 38G-SG-S迭代矩阵迭代矩阵 其谱半径其谱半径 2211212111121100)(aaaaaaULDG221121121)(aaaaG显然显然, 和和 同时小于、等于或大于同时小于、等于或大于1,因而因而Jacobi迭代法与迭代法与G-S迭代法具有相同的收敛性迭代法具有相同的收敛性 )(B)(1G例题例题39例例9 考察用考察用
22、雅可比迭代法和雅可比迭代法和高斯高斯-塞德尔迭代塞德尔迭代 法解线性方程组法解线性方程组Ax=b的收敛性，其中的收敛性，其中例题例题111122111221bA40解：解： 先计算迭代矩阵先计算迭代矩阵例题例题雅可比矩阵雅可比矩阵0221012200003332333122232221111311121aaaaaaaaaaaaADIB41求特征值求特征值例题例题002211223,2, 13BI ( B ) = 0 1)=21 用高斯用高斯- -塞德尔迭代塞德尔迭代法求解时，迭代过程发散法求解时，迭代过程发散求特征值求特征值0)2(2003202221GI44例例12 讨论用讨论用雅可比迭代法
23、和雅可比迭代法和高斯高斯- -塞德尔迭代塞德尔迭代 法解线性方程组法解线性方程组Ax=bAx=b的收敛性。的收敛性。024211121112321xxx024211121112bA例题例题45解：解： 先计算迭代矩阵先计算迭代矩阵例题例题雅可比矩阵雅可比矩阵0212121021212100003312333122232221111311121aaaaaaaaaaaaADIB460)1()12(412121212121213BI求特征值求特征值例题例题 1 = - 1， 2,3 = 1/2 ( B ) = 1 用用雅可比迭代法求解时，迭代过程不收敛雅可比迭代法求解时，迭代过程不收敛47求特征值求
24、特征值高斯高斯-塞德尔迭代矩阵塞德尔迭代矩阵例题例题838108141021210)(11ULDG48例题例题0) 15(818381041410212121GI 1=0,16753 , 2i (G1) = 0.3536 1 用用高斯高斯- -塞德尔迭代塞德尔迭代法求解时，迭代过程收敛法求解时，迭代过程收敛49求解求解AX=b,当当 取何取何值时迭代收敛？值时迭代收敛？ 例例13 给定线性方程组给定线性方程组 AX= b 用迭代公式用迭代公式 X(K+1)=X(K)+ (b-AX(K) (k=0,1,）例题例题23,2123bA50解解:所给迭代公式的迭代矩阵为所给迭代公式的迭代矩阵为例题例题
25、0)21 (2)31 (21231BIAIB51即即 2-(2-5 ) ) +1- 5 +4+4 2 2=0=0 2-(2-5 ) ) +(1- )(1-4 )=0)=0 -(1- ) ) - (1-4 ) )=0=0 1=1- 2=1-4 例题例题 (B)=max|1- |, |1-4 |1取取0 1/21/2迭代收敛迭代收敛52 本章介绍了解线性方程组本章介绍了解线性方程组 迭代法的一些迭代法的一些基本理论和具体方法。基本理论和具体方法。 本章小结本章小结bAx 迭代法是一种逐次逼近的方法，即对任意给定的初始迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按照某种方法逐步生成近似
26、解序列，使近似解向量，按照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。注意到在使用迭代法解序列的极限为方程组的解。注意到在使用迭代法fBxxkk)()1(53 解方程组时，其迭代矩阵解方程组时，其迭代矩阵B和迭代向量和迭代向量f在计算过程中在计算过程中始终不变始终不变,迭代法具有循环的计算公式迭代法具有循环的计算公式,方法简单，程方法简单，程序实现方便，它的优点是能充分利用系数的稀疏性序实现方便，它的优点是能充分利用系数的稀疏性,适宜解大型稀疏系数矩阵的方程组。迭代法不存在误适宜解大型稀疏系数矩阵的方程组。迭代法不存在误差累积问题。使用迭代法的关键问题是其收敛性与与差累积问题。使用迭代法的关键问题是其收敛性与与收敛速度，收敛性与迭代初值的选取无关，这是比一收敛速度，收敛性与迭代初值的选取无关，这是比一般非线性方程求根的优越之处。般非线性方程求根的优越之处。本章小结本章小结54在实际计算中，判断一种迭代格式收敛性较麻烦，由在实际计算中，判断一种迭代格式收敛性较麻烦，由于求迭代的谱半径时需要求特征值，当矩阵的阶数较于求迭代的谱半径时需要求特征值，当矩阵的阶数较大时，特征值不易求出，通常采用矩阵的任一种范数大时，特征值不易求出，通常采用矩阵的任一种范数都小于都小于1或对角占优来判断收敛性。或对角占优来判断收敛性。本章小结本章小结55
