1、第五章线性方程组迭代解法6.2 基本迭代方法基本迭代方法6.1.2 Jacobi 迭代法和迭代法和 Gauss-Seidel迭代法迭代法6.2.1 迭代公式的构造迭代公式的构造第五章线性方程组迭代解法第六章第六章 线性方程组的迭代解法线性方程组的迭代解法教学目的教学目的 1. 掌握掌握Jacobi迭代法，迭代法，G-S迭代法解大型线性方程组的迭代法解大型线性方程组的方法及其收敛性的判别方法；方法及其收敛性的判别方法；2. 掌握掌握SOR迭代法及收敛的必要条件迭代法及收敛的必要条件(02 )；3. 了解三种迭代法之间的改进关系从而掌握该思想方法；了解三种迭代法之间的改进关系从而掌握该思想方法；4
2、. 理解迭代法基本定理。理解迭代法基本定理。教学重点及难点教学重点及难点 重点是重点是三种迭代法及收敛性的判别方法；三种迭代法及收敛性的判别方法；难点是难点是迭代法基本定理及三种迭代法收敛定理的证明。迭代法基本定理及三种迭代法收敛定理的证明。第五章线性方程组迭代解法 迭代法迭代法是一种不断套用一个迭代公式，逐步逼近方程组的是一种不断套用一个迭代公式，逐步逼近方程组的精确精确迭代法优点：迭代法优点：计算量小计算量小，近似解精度高，近似解精度高。考虑问题：考虑问题：如何构造解如何构造解 的有效迭代法？的有效迭代法？bAx 计算量：计算量： )(3nO直接法：解低阶稠密线性方程组，直接法：解低阶稠密
3、线性方程组，解（真解）的方法。解（真解）的方法。适合解大型稀疏线性方程组适合解大型稀疏线性方程组。 用差分法或有限元法解偏微分方程边值问题时得到的方程组。用差分法或有限元法解偏微分方程边值问题时得到的方程组。 电工学中的电工学中的网络问题；网络问题；大型稀疏线性方程组大型稀疏线性方程组占用内存单元较少占用内存单元较少。设计程序简单（适合计算机计算）。设计程序简单（适合计算机计算）。收敛性与收敛速度怎样？收敛性与收敛速度怎样？第第6章章 线性方程组的迭代解法线性方程组的迭代解法迭代法在计算机内存和运迭代法在计算机内存和运算两方面，通常都可利用算两方面，通常都可利用A A中有大量零元素的特点。中有
4、大量零元素的特点。第五章线性方程组迭代解法6.2.1. 迭代法的基本思想迭代法的基本思想 ), 2 , 1()0(nixi 迭代法的基本思想是将线性方程组迭代法的基本思想是将线性方程组 Ax=b (6.2.1)转化为便于迭代的等价方程组，对任选一组初始值转化为便于迭代的等价方程组，对任选一组初始值 ，按某种计算规则，不断地对所得到的，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。值进行修正，最终获得满足精度要求的方程组的近似解。 第五章线性方程组迭代解法设设 非奇异，非奇异， ，则线性方程组，则线性方程组 有惟一解有惟一解 ，经过变换构造出一个等价同解方程组
5、，经过变换构造出一个等价同解方程组将上式改写成将上式改写成单步定常迭代式单步定常迭代式nnRAnRbbAx bAx1xB xf(1)()(0,1,)kkxBxfk选定初始向量选定初始向量 , ,反复不断地使用迭反复不断地使用迭代式逐步逼近方程组的精确解代式逐步逼近方程组的精确解, ,直到满足精度要求为止。这种直到满足精度要求为止。这种方法称为方法称为单步定常单步定常迭代法（迭代法（B, f都与都与k无关无关）. .Tnxxxx)0()0(2)0(1)0(,第五章线性方程组迭代解法 如果 存在极限则称迭代法是收敛的，否则就是发散的。收敛时，在迭代公式中当 时， ,则 , 故 是方程组 的解。Tk
6、nkkkxxxx)()(2)(1)(,Tnxxxx*2*1*,k(1)( )(0,1,)kkxBxfk*)(xxk*xBxf*xbAx 第五章线性方程组迭代解法由前而可得： ，从而递推得：为讨论 收敛性，引进误差向量：.11xxkk 1kkB 01kkkBB kx亦即B满足什么条件使 （零矩阵） 。 要 收敛于 。则须考察B在什么条件下 ，x kx 0k0kBk第五章线性方程组迭代解法1231234123423410261125210113815xxxxxxxAxbxxxxxxx 简记：例例6.1Tx)1 , 1,2, 1(*解：其精确解为：先将先将Ax=b转化为等价方程组转化为等价方程组12
7、321343124423( 62) / 1 0( 2 53) / 1 1(1 12) / 1 0(1 53) / 8xxxxxxxxB xfxxxxxxx或第五章线性方程组迭代解法Tx)0 , 0 , 0 , 0()0(迭代公式：选取初始向量经10次迭代解：0002.0:)9998.0 ,9998.0,9998.1 ,0001.1 ()10(*)10(xxxT误差为(1)()()123(1)()()()2134(1)()()()3124(1)()()423(62) /10(253) /11(0,1, 2)(112) /10(153) / 8kkkkkkkkkkkkkkxxxxxxxkxxxxx
8、xx对于给定的方程组可以构造各种迭代公式对于给定的方程组可以构造各种迭代公式, ,但并非全部收敛但并非全部收敛 。第五章线性方程组迭代解法例例6.26.2 用迭代法求解线性方程组用迭代法求解线性方程组 352322121xxxx解解 构造方程组的等价方程组构造方程组的等价方程组3423212211xxxxxx据此建立迭代公式据此建立迭代公式 3423)(2)(1)1(2)(2)(1)1(1kkkkkkxxxxxx0)0(2)0(1 xx取取 计算得计算得 ,3333,1515, 99, 33, 33) 5 (2) 5 (1) 4(2) 4(1) 3 (2) 3 (1) 2(2) 2(1) 1
9、(2) 1 (1xxxxxxxxxx迭代解离精确解迭代解离精确解 越来越远迭代不收敛越来越远迭代不收敛 1, 121xx第五章线性方程组迭代解法6.1.2 6.1.2 雅可比（雅可比（JacobiJacobi）迭代法）迭代法1 1雅可比迭代法算法构造雅可比迭代法算法构造 例例6.6. 用雅可比迭代法求解方程组用雅可比迭代法求解方程组 3612363311420238321321321xxxxxxxxx解：解：从方程组的三个方程中分离出从方程组的三个方程中分离出 和和 21,xx3x341213111114254183213312321xxxxxxxxx第五章线性方程组迭代解法建立迭代公式建立迭
10、代公式 341213111114254183)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx第五章线性方程组迭代解法取初始向量取初始向量进行迭代进行迭代, , 可以逐步得出一个近似解的序列：可以逐步得出一个近似解的序列： （k=1, 2, =1, 2, ）直到求得的近似解能达到预先要求的精度，直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组则迭代过程终止，以最后得到的近似解作为线性方程组的解。的解。 当迭代到第当迭代到第1010次有次有计算结果表明，此迭代过程收敛于方程组的精确解计算结果表明，此迭代过程收敛于
11、方程组的精确解x*= (3, 2, 1)(3, 2, 1)T T。 TTxxxx)0 ,0 ,0(),()0(3)0(2)0(1)0(),()(3)(2)(1kkkxxxTTxxxx)9998813. 0,999838. 1,000032. 3(),()10(3)10(2)10(1)10(第五章线性方程组迭代解法考察一般的方程组，将考察一般的方程组，将n元线性方程组元线性方程组 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111nibxainjjij, 2 , 11写成写成 若若 , ,分离出变量分离出变量 0iia), 2 , 1(niix
12、nixabaxjnijjijiiii,2, 1)(11第五章线性方程组迭代解法据此建立迭代公式据此建立迭代公式 nixabaxnijjkjijiiiki, 2 , 1)(11)()1(上式称为解方程组的上式称为解方程组的JacobiJacobi迭代公式迭代公式。 0iia第五章线性方程组迭代解法2 2 雅可比迭代法的矩阵表示雅可比迭代法的矩阵表示 设方程组设方程组 的系数矩阵的系数矩阵A A非奇异，且主对角元非奇异，且主对角元素素 ，则可将，则可将A A分裂成分裂成 bAx ), 2 , 1(0niaii121311121232223132112100000000nnnnnnnnnnaaaaa
13、aaaAaaaaaaa 记作记作 A = -L + D -U A = -L + D -U 第五章线性方程组迭代解法即即()DxLU xb因为因为 ，则，则 ), 2 , 1(0niaii11()xDLU xD b这样便得到一个迭代公式这样便得到一个迭代公式(1)1( )1()kkxDLU xD b1( )1()kDDA xD bbDxADIk1)(1)(11()JJBID AfD b令令则有则有(1)()kkJJxB xf（k = 0,1,2k = 0,1,2）称为称为雅可比迭代公式雅可比迭代公式, B, BJ J称为雅可比迭代矩阵称为雅可比迭代矩阵bAx 则则 等价于等价于()DLU xb第
14、五章线性方程组迭代解法1121111221122221200()0nnJnnnnnnaaaaaaaaBID Aaaaa其中其中 在例在例5.35.3中中, ,由迭代公式写出雅可比迭代矩阵为由迭代公式写出雅可比迭代矩阵为 13208841011116301212JBIDA341213111114254183)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx第五章线性方程组迭代解法雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即计算中，要用雅可比迭代法公式的分
15、量形式。即 )(1)(1)(1)(11)(22)(11) 1(2)(2)(323)(12122) 1(21)(1)(313)(21211) 1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax(k=0,1,2,) 第五章线性方程组迭代解法J 称为称为JacobiJacobi迭迭代法的迭代阵代法的迭代阵Jacobi迭代法迭代法：(0)(1)( )111(0,1, )()kkJJJJxxB xfkBI D A D L UJfD b Tknkikkxxxx),()()()(1)( 若记若记Jacobi迭代法的分量形式：迭代法的分量形式：，bM
16、 f1 1,BIM A (5.1.4)称（称（6.2.2）为解（）为解（6.2.1）的）的Jacobi 迭代法迭代法，简称，简称 J 法法。(6.2.2)第五章线性方程组迭代解法 ni , 2 , 1 ,1111)()()1( nijjkjijiijnijkjijkjijikiiixabxaxabxa当当 时，得到时，得到0 iia由由（6.2.2）有有 ，即，即bxULDxkk )()1()( 求解求解 的的Jacobi迭代法迭代法计算公式计算公式： bAx xabaxxx xnijjkjijiiikiTn)(1),(1)() 1()0()0(1)0( ni, 2 , 1 ( (6.2.3)
17、 )表示迭代次数。表示迭代次数。, 1 , 0 k 注：注：(1)(1)Jacobi迭代法迭代法, ,每迭代一次主要是计算一次矩阵乘向量每迭代一次主要是计算一次矩阵乘向量 。)(kBx （2)2)计算过程中，原始数据计算过程中，原始数据A始终不变。始终不变。(3)(3)计算中需要两组工作单元计算中需要两组工作单元 用来保存用来保存 及及 。 )(),(nynx)(kx)1( kx前一例前一例6.3即为即为Jacobi法求解，在此不再举例。法求解，在此不再举例。第五章线性方程组迭代解法 Algorithm: Jacobi Iterative Method Solve given an initi
18、al approximation .Input: the number of equations and unknowns n; the matrix entries a ; the entries b ; the initial approximation X0 ; tolerance TOL; maximum number of iterations Mmax.Output: approximate solution X or a message of failure.Step 1 Set k = 1;Step 2 While ( k Mmax) do steps 3-6Step 3 Fo
19、r i = 1, , n Set ; /* compute xk */Step 4 If then Output (X ); STOP; /* successful */Step 5 For i = 1, , n Set X 0 = X ; /* update X0 */ Step 6 Set k +;Step 7 Output (Maximum number of iterations exceeded); STOP. /* unsuccessful */Axb0XiinjijjijiiaXabX 1)0(TOLXXXXiini |0|max|0|1What if aii = 0?迭代过程中
20、，迭代过程中，A 的元素的元素不改变，故可以不改变，故可以事先调整事先调整好好 A 使得使得aii 0，否则否则 A不可逆不可逆。必须等必须等X(k)完全计算完全计算好了才能计算好了才能计算X(k+1)，因此，因此需要需要两组向量两组向量存储。存储。A bit wasteful, isnt it?第五章线性方程组迭代解法6.2.36.2.3高斯高斯- -塞德尔塞德尔(Gauss-Seidel(Gauss-Seidel) )迭代法迭代法(G-S)(G-S) )1( kix)1(1)1(2)1(1,kikkxxx)(1)(2)(1,kikkxxx)(1111)()1()1(ijnijkjijkji
21、jiiikixaxabax(i=1,2,n k=0,1,2,)1 1 高斯高斯- -塞德尔迭代法的基本思想塞德尔迭代法的基本思想 在在JacobiJacobi迭代法中，每次迭代只用到前一次的迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，迭代值，若每次迭代充分利用当前最新的迭代值，即在求即在求 时用新分量时用新分量代替旧分量代替旧分量 , , 就得到高斯就得到高斯- -赛德赛德尔迭代法。其迭代法格式为：尔迭代法。其迭代法格式为： 第五章线性方程组迭代解法)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(4
22、24)(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 只存一组向量即可。只存一组向量即可。第五章线性方程组迭代解法例例6.4 6.4 用用GaussGaussSeidel Seidel 迭代格式解方程组迭代格式解方程组 35410218321321321xxxxxxxxx精确要求为精确要求为=0.005 =0.005 解解 GaussGaussSeidel Seidel
23、迭代格式为迭代格式为5/ )3(10/ )42(8/ ) 1()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx取初始迭代向量取初始迭代向量 , ,迭代结果为：迭代结果为：Tx)0 ,0 ,0()0(第五章线性方程组迭代解法Tx)5000. 0,3750. 0,1250. 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(ixxii第五章线性方程组迭代
24、解法2. GaussSeidel 迭代法的矩阵表示迭代法的矩阵表示 将将A分裂成分裂成A =D-L-U，则，则 等价于等价于 (D-L-U )x = b 于是于是,则高斯则高斯塞德尔迭代过程塞德尔迭代过程 bAx (1)(1)( )kkkDxLxUxb因为因为 , ,所以所以 0D0DLD(1)( )()kkDL xUxb(1)1( )1()()kkxD L UxD L b11(), ()GSGSBDLUfDLb(1)()kkGSGSxBxf则高斯则高斯- -塞德尔迭代形式为：塞德尔迭代形式为： 故故 令令 第五章线性方程组迭代解法于是得到于是得到解解 的的G-S迭代法：迭代法： bAx (0
25、)(1)( )11()()kkGSGSGSxxB xfBD LUfD Lb(6.2.3)其中其中BGS 称为称为G- -S迭代迭代法的迭代阵法的迭代阵NMA ULDA 从上面的分析可以看出从上面的分析可以看出, G-S迭代法是改进的迭代法是改进的J迭代法迭代法. 即即 在在J 法中，计算法中，计算 时，分量时，分量 已经算出，因此可考虑已经算出，因此可考虑)1( kix(1)(1)11,kkixx对对J 法进行修改。在每个分量计算出来之后，下一个分量的计算就利用最法进行修改。在每个分量计算出来之后，下一个分量的计算就利用最 新的计算结果。这样，在整个迭代过程中只要使用一组单元存放迭代向新的计算
26、结果。这样，在整个迭代过程中只要使用一组单元存放迭代向量，其分量形式的计算结果为量，其分量形式的计算结果为., 2 , 1,/ )()(1)1(11)1(niaxaxabxiikjnijijkjijiiiki（6.2.10）这就是这就是Gauss-Seidel 迭代法迭代法，简称，简称 GS 法法第五章线性方程组迭代解法(1)由由(6.2.10)可知可知, ,计算计算 第第i个分量时个分量时, ,利用已经计算出的最利用已经计算出的最新新)1( kxG-SG-S法的优点：法的优点：(2)G-S迭代法每迭代一次主要计算一次矩阵乘向量。迭代法每迭代一次主要计算一次矩阵乘向量。计算量小，计算量小，(3
27、)当当J-J-迭代与迭代与G-SG-S迭代都收敛时，迭代都收敛时， G-S迭代的收敛速度快。迭代的收敛速度快。 G-S迭代法可看作迭代法可看作J J迭代法的一种迭代法的一种修正修正或或改进改进。用用G-S迭代法解只需要一组工作单元，用来保存迭代法解只需要一组工作单元，用来保存 或或 分量。分量。)1( kx)(kx分量分量 ，因此，计算，因此，计算 就可冲掉就可冲掉 , ,于是利于是利)1, 2 , 1()1( ijxkj)1( kix)( kixG-S迭代存贮少。迭代存贮少。第五章线性方程组迭代解法例例6. 5用法和法分别求解方程组用法和法分别求解方程组,145141031310213103
28、21xxx其准确解为其准确解为 。Tx) 1 , 1 , 1 (*解解 用用 J 法计算，按法计算，按（6.2.8）有有.10/ )14 3(,10/ )53 2(,10/ )143- ()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx第五章线性方程组迭代解法用用 GS 法计算，按（法计算，按（6.2.9）有）有.10/ )14 3(,10/ )53 2(,10/ )143- ()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx 取取 ，J 法迭代法迭代4次的计算结果是次的计算结果是Tx)0 ,
29、 0 , 0()0(.0356. 0,)9906. 0 ,9645. 0 ,9906. 0(*)4()4(xxxTGS 法迭代法迭代4次的计算结果是次的计算结果是.0085. 0,)0021. 1 ,99578. 0 ,99154. 0(*)4()4(xxxT从计算结果看，本例用从计算结果看，本例用 GS 法显然比用法显然比用 J 法收敛快。法收敛快。第五章线性方程组迭代解法 例例6.6 用用Jacobi迭代迭代法，法，G-S迭代法解下述方程组迭代法解下述方程组 351110288321321321xxxbAxxxxxxx或或Tx)1 , 1 , 1( 精确解精确解 （1） 迭代公式：迭代公式
30、：Jacobi 5/ )3(10/ )211(8/ )8()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx其中，其中， ，计算结果见表，计算结果见表6-1。 ), 1 , 0( ,),()(3)(2)(1)( kxxxxTkkkk表表6-1 000015. 19964. 00045. 102. 16 . 00000015. 100195. 19895. 096. 01 . 100006938. 1998125. 09925. 00625. 1. 10)(3)(2)(1)5()4()3()2()1()0()(kkkkxxxxxxxxxx且有且有 0
31、007. 0)5( xx9895. 09964. 096. 06 . 019925. 0第五章线性方程组迭代解法 5/ )3(10/ )211(8/ )8()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx其中，其中， , ,), 1 . 0( ,),()(3)(2)(1)( kxxxxTkkkk（2 2）G-SG-S迭代公式迭代公式999995. 0. 1998. 098. 0000000625. 199975. 0. 19 . 0099996875. 000025. 199. 0. 10)(3)(2)(1)4()3()2()1()0()(
32、kkkkxxxxxxxxx且有且有5*)4(*)3(102 . 3|00025. 0| xxxx由此例看出，用由此例看出，用 G-S迭代法解此方迭代法解此方程组比用程组比用Jacobi方方法解此法解此Ax=b收敛快收敛快（即在初始向量（即在初始向量 相同，达到同样精相同，达到同样精度，所需迭代次数度，所需迭代次数较少），这个结论较少），这个结论只当只当A满足一定条满足一定条件时才是对的。有件时才是对的。有些方程组些方程组, ,用用J- -迭迭代法收敛，而用代法收敛，而用G-S迭代法却是发散迭代法却是发散的。例如的。例如P P李李259习习题题6 6中中2 2（b）。）。)0(x注：注：9999
33、95. 099975. 000025. 1998. 099996875. 000000625. 1计算结果见计算结果见: :表表6-26-20007. 0)5( xx第五章线性方程组迭代解法 Jacobi 迭代法和迭代法和 Gauss-Seidel 迭代法的分量形式迭代法的分量形式供计算编程用供计算编程用，它们，它们的矩阵形式的矩阵形式供研究迭代序列是否收敛等理论分析供研究迭代序列是否收敛等理论分析用。用。小结：小结：Jacobi 迭代法迭代法Gauss-Seidel 迭代法迭代法矩阵形式矩阵形式 xabaxxx xnijjkjijiiikiTn)(1),(1)() 1()0()0(1)0(
34、ni, 2 , 1 表示迭代次数。表示迭代次数。, 1 , 0 k分量形式分量形式 bDfJULDBkfBxxxkk11)() 1() 0()(), 1 , 0( bLDfGULDBfBxxxkk11)()1()0()()(矩阵形式矩阵形式分量形式分量形式), 2 , 1(ni )(1),(1)(11)1()1()0()0(1)0(nijkjijijkjijiiikiTnxaxabaxxxx第五章线性方程组迭代解法6. 4 超松弛迭代法（超松弛迭代法（SOR方法）方法） 使用迭代法的困难在于难以估计其计算量。使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛，但由于收敛速度缓慢，使有时
35、迭代过程虽然收敛，但由于收敛速度缓慢，使计算量变得很大而失去使用价值。因此，迭代过程计算量变得很大而失去使用价值。因此，迭代过程的加速具有重要意义。逐次超松弛迭代（的加速具有重要意义。逐次超松弛迭代（Successive Over Relaxatic Method，简称，简称SOR方法方法）法，可以看作是带参数的高斯）法，可以看作是带参数的高斯塞德尔迭代法，塞德尔迭代法，实质上是高斯实质上是高斯-塞德尔迭代的一种加速方法。塞德尔迭代的一种加速方法。 第五章线性方程组迭代解法1 1超松弛迭代法的基本思想超松弛迭代法的基本思想 超松弛迭代法目的是为了提高迭代法的收敛速超松弛迭代法目的是为了提高迭代
36、法的收敛速度，在高斯度，在高斯塞德尔迭代公式的基础上作一些修改塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果。这种方法是将前一步的结果 与高斯与高斯- -塞德尔塞德尔迭代方法的迭代值迭代方法的迭代值 适当加权平均，期望获得更适当加权平均，期望获得更好的近似值好的近似值 。是解大型稀疏矩阵方程组的有效。是解大型稀疏矩阵方程组的有效方法之一，有着广泛的应用。方法之一，有着广泛的应用。 其具体计算公式如下：其具体计算公式如下： )(kix) 1(kix)1( kix用高斯用高斯塞德尔迭代法定义辅助量。塞德尔迭代法定义辅助量。 ),.,2 , 1( ,11)(11)1(nixaxabani
37、jkjijijkjijiii) 1(kix第五章线性方程组迭代解法把把 取为取为 与与 的加权平均，即的加权平均，即 )1( kix)(kix)1(kix)()1 ()()1()()1()()1(kikikikikikixxxxxx合并表示为：合并表示为： )()1 (1)()1(11)()1(nijkjijkjijijiiikikixaxabaxx式中系数式中系数称为松弛因子，当称为松弛因子，当=1=1时，便为高斯时，便为高斯- -塞德尔迭代法。为了保证迭代过程收敛，要求塞德尔迭代法。为了保证迭代过程收敛，要求0 20 2。 当当0 10 1时，低松弛法；当时，低松弛法；当1 21 2时称为
38、超松弛法。但通常统称为超松弛法时称为超松弛法。但通常统称为超松弛法(SOR) (SOR) 第五章线性方程组迭代解法2 2 超松弛迭代法的矩阵表示超松弛迭代法的矩阵表示设线性方程组设线性方程组 的系数矩阵的系数矩阵A非奇异非奇异, ,且主对且主对角元素角元素 , ,则将则将A分裂成分裂成A=D-L-U, , 则超松弛迭代公式用矩阵表示为则超松弛迭代公式用矩阵表示为), 2 , 1(0niaiiAxb(1)( )1(1)( )(1)()kkkkxxDbLxUx(1)( )(1)( )(1)()kkkkDxDxbLxUx或或 (1)( )()(1)kkDL xDU xb故故 显然对任何一个显然对任何
39、一个值值,(D+L),(D+L)非奇异非奇异,(,(因为假设因为假设 ) )于是超松弛迭代公式为于是超松弛迭代公式为 niaii, 2 , 1, 0(1)1( )1()(1)()kkxDLDU xDLb第五章线性方程组迭代解法例例* * * 用用SORSOR法求解线性方程组法求解线性方程组 7910431017210424321321321xxxxxxxxx取取=1.46=1.46，要求，要求 6)()1(10kkxx解：解：SORSOR迭代公式迭代公式 )1047(9)1 ()1023(17)1 ()4210(4)1 ()1(2)1(1)(3)1(3)(3)1(1)(2)1(2)(3)(2)
40、(1)1(1kkkkkkkkkkkkxxxxxxxxxxxxk = 0,1,2,k = 0,1,2,， 初值初值 Tx)0,0,0()0(第五章线性方程组迭代解法该方程组的精确解该方程组的精确解只需迭代只需迭代2020次便可达到精度要求次便可达到精度要求. . Tx)1,1 ,2(*)如果取如果取=1(=1(即高斯即高斯塞德尔迭代法塞德尔迭代法) )和同一初值和同一初值 , ,要达到同样精度要达到同样精度, , 需要迭代需要迭代110110次次. .Tx)0 , 0 , 0()0(第五章线性方程组迭代解法6.3 迭代法的收敛性迭代法的收敛性 我们知道我们知道, 对于给定的方程组可以构造成简单迭
41、代公式对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯、雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公塞德尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。式，但并非一定收敛。现在分析它们的收敛性。 对于方程组对于方程组 经过等价变换构造出的等价方程经过等价变换构造出的等价方程组组 bAx (1)()(0,1,)kkxBxfk在什么条件下迭代序列在什么条件下迭代序列 收敛？收敛？)(kx如果，当如果，当 时时 存在极限存在极限 则称迭代法则称迭代法是收敛的，否则就是发散的。是收敛的，否则就是发散的。Tknkkkxxxx)()(2)(1)(,Tnxxxx*2*1*
42、,k(1)( )(0,1,)kkxBxfk第五章线性方程组迭代解法收敛时，在迭代公式收敛时，在迭代公式中当中当 时，时， , ,则则 , , 故故 是方程组是方程组 的解。的解。k(1)( )(0,1,)kkxBxfk*)(xxk*xBxf*xbAx ( )*(1)*(0)()()kkkxxB xxBxx从而从而k由此可见当时，如果，那么，从由此可见当时，如果，那么，从而而0kB *)(xxk(1)( )0kkxx*)(xxk反过来，如果反过来，如果( () )，那么由的任意性，那么由的任意性，k(0)x0.kB第五章线性方程组迭代解法(1)( )kkxBxf0,.kBk 定理定理1 1 对任
43、意的初始向量迭代公式对任意的初始向量迭代公式 收敛收敛的充分必要条件是的充分必要条件是 . .(0)x不过，对过判别是否趋于零，运算量很大实不过，对过判别是否趋于零，运算量很大实际上，利用的约当标准型，可以证明下面的定理际上，利用的约当标准型，可以证明下面的定理kB(1)( )(0,1,)kkxBxfk( )1B定理定理2 迭代公式迭代公式 收敛收敛的充分必要条件是迭代矩阵的充分必要条件是迭代矩阵B的谱半径的谱半径由此定理可知，不论是雅可比迭代法、高斯由此定理可知，不论是雅可比迭代法、高斯塞德尔迭塞德尔迭代法还是超松弛迭代法，它们收敛的代法还是超松弛迭代法，它们收敛的充要条件充要条件是其迭代矩
44、阵是其迭代矩阵的谱半径的谱半径 。 ( )1B第五章线性方程组迭代解法 有时实际判别一个迭代法是否收敛，条件有时实际判别一个迭代法是否收敛，条件 是很难检验的。而是很难检验的。而一些矩阵范数一些矩阵范数 可以用可以用 B 的元素表示，所以用的元素表示，所以用 作为收敛的充分条作为收敛的充分条件较为方便。件较为方便。1)(BB1B定理定理3 3 ( (迭代法收敛的充分条件迭代法收敛的充分条件) )若迭代矩阵若迭代矩阵B B的一种范数的一种范数 , ,则迭代公式则迭代公式收敛收敛, ,且有误差估计式且有误差估计式, ,且有误差估计式且有误差估计式 1B (1)( )(0,1,)kkxBxfk( )
45、( )(1)1kkkBxxxxB( )(1)(0)1kkBxxxxB及及 证证: : 矩阵的谱半径不超过矩阵的任一种范数矩阵的谱半径不超过矩阵的任一种范数, ,已知已知 , ,因因此此 , ,根据定理根据定理2 2可知迭代公式收敛可知迭代公式收敛1B ( )1B第五章线性方程组迭代解法又因为又因为 , 则则det (I-B)0, I-B为非奇异矩阵为非奇异矩阵,故故xBxf 有惟一解有惟一解 , 即即与迭代过程与迭代过程 相比较相比较, 有有两边取范数两边取范数 1B *x*xBxf(1)( )kkxBxf*( )*(1)()kkxxB xx*( )*(1)kkxxBxx*( )( )(1)k
46、kkBxxxx*( )( )(1)kkkBxxBxx*( )( )(1)(1)kkkBxxBxx*( )( )(1)1kkkBxxxxB 第五章线性方程组迭代解法由迭代格式，有由迭代格式，有 ( )(1)(1)(2)2(1)(2)1(1)(0)()()()kkkkkkkxxB xxB xxBxx两边取范数，代入上式，得两边取范数，代入上式，得 *()(1)(0)1kkBxxxxB证毕证毕 由定理知，当由定理知，当 时，其值越小，迭代收敛越快，时，其值越小，迭代收敛越快，在程序设计中在程序设计中通常用相邻两次迭代通常用相邻两次迭代 （为给定的精度要求）作为控制迭代结束的条件为给定的精度要求）作为
47、控制迭代结束的条件. 1B )1()(kkxx第五章线性方程组迭代解法例例6.8 6.8 已知线性方程组已知线性方程组 6612363311420238321321321xxxxxxxxx考察用考察用JacobiJacobi迭代和迭代和G-SG-S迭代求解时的收敛性迭代求解时的收敛性解解: : 雅可比迭代矩阵雅可比迭代矩阵 13121111123212222313233333200884100111163001212JaaaaaaBIDAaaaaaa5599max,18 11 1212JB故故JacobiJacobi迭代收敛迭代收敛 第五章线性方程组迭代解法 将系数矩阵分解将系数矩阵分解 80
48、032114001126300ADLU 则高斯则高斯- -塞德尔迭代矩阵塞德尔迭代矩阵 118032()4110163120GSBDLU887176270112223082830010230121441176901112210081第五章线性方程组迭代解法57415m ax,18221768G SB故高斯故高斯塞德尔迭代收敛。塞德尔迭代收敛。 320883202211277017688GSB第五章线性方程组迭代解法定理定理严格对角占优线性方程组严格对角占优线性方程组 的雅可比的雅可比迭代公式、高斯迭代公式、高斯- -赛德尔迭代公式均收敛。赛德尔迭代公式均收敛。bAx 定理定理5 的系数矩阵的系
49、数矩阵A是对称正定矩阵，则雅可比是对称正定矩阵，则雅可比迭代公式收敛的充要条件是迭代公式收敛的充要条件是2D-A也是也是对称正定矩阵，对称正定矩阵，SQR法收法收敛的充要条件是敛的充要条件是0 2 。bAx 定理定理6 6 设设A A是不可约对角占优矩阵，是不可约对角占优矩阵， 那么那么JacobiJacobi迭代法与迭代法与G GS S迭代法都收敛迭代法都收敛. .定理定理7 7 设设A A是是n n阶正定矩阵，那么，阶正定矩阵，那么，G GS S迭代法收敛迭代法收敛. .下面补充几个常用结论下面补充几个常用结论第五章线性方程组迭代解法注意的问题注意的问题（2）Jacobi迭代法和迭代法和G
50、auss-Seidel迭代法的收敛性迭代法的收敛性没有必然的联系：没有必然的联系： 即当即当Gauss-Seidel法收敛时，法收敛时，Jacobi法可能不收敛；法可能不收敛；而而Jacobi法收敛时，法收敛时， Gauss-Seidel法也可能不收敛。法也可能不收敛。（1）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代法的迭代矩阵不同：迭代矩阵不同：BJ =D-1(L+U), B G-S = (D-L) -1U第五章线性方程组迭代解法举例举例12312312321121xxxxxxxxx用用Jacobi迭代法求解不收敛，但用迭代法求解不收敛，但用 Gauss-Seidel法
