数值分析第三章-线性方程组的迭代法课件.ppt

1、 我们知道，凡是迭代法都有一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设计简单，适于自动计算，而且较直接法更少的计算量就可获得满意的解。因此，迭代法亦是求解线性方程组，尤其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。第三章 解线性方程组的迭代法3.1 迭代法的基本思想 迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值 ，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。),2,1()0(nixi设 非奇异，则线性方程组 有惟一解 ，经过变换构造出一个等价同解方程组

2、将上式改写成迭代式nnRAnRbbAx bAx1dGxx),1,0()()1(kdGxxkk选定初始向量 ,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法Tnxxxx)0()0(2)0(1)0(,如果 存在极限则称迭代法是收敛的，否则就是发散的。收敛时，在迭代公式中当 时，,则,故 是方程组 的解。对于给定的方程组可以构造各种迭代公式。并非全部收敛 Tknkkkxxxx)()(2)(1)(,Tnxxxx*2*1*,k),1,0()()1(kdGxxkk*)(xxkdGxx*xbAx 例1 用迭代法求解线性方程组 352322121xxxx解 构造方程组的等

3、价方程组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(2)1(1xxxxxxxxxx迭代解离精确解 越来越远 迭代不收敛 1,121xx3.2 雅可比（Jacobi）迭代法雅可比迭代法算法构造 例2 用雅可比迭代法求解方程组 3612363311420238321321321xxxxxxxxx解：从方程组的三个方程中分离出 和 21,xx3x1232133121322081433

4、111633612xxxxxxxxx建立迭代公式(1)()()123(1)()()213(1)()()3121322081433111633612kkkkkkkkkxxxxxxxxx精确解x*=(3,2,1)T取初始向量进行迭代,可以逐步得出一个近似解的序列：（k=1,2,）直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第10次有计算结果表明，此迭代过程收敛于方程组的精确解x*=(3,2,1)T。TTxxxx)0,0,0(),()0(3)0(2)0(1)0(),()(3)(2)(1kkkxxxTTxxxx)9998813.0,999838.

5、1,000032.3(),()10(3)10(2)10(1)10(考察一般的方程组，将n元线性方程组 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111nibxainjjij,2,11写成 若 ,分离出变量 0iia),2,1(niixnixabaxjnijjijiiii,2,1)(11据此建立迭代公式 nixabaxnijjkjijiiiki,2,1)(11)()1(上式称为解方程组的Jacobi迭代公式。雅可比迭代法的矩阵表示 设方程组 的系数矩阵A非奇异，且主对角元素 ，则可将A分裂成 bAx),2,1(0niaii1213111212

6、32223132112100000000nnnnnnnnnnaaaaaaaaAaaaaaaa 记作 A=D+L+U bAx 则 等价于()DLU xb即()DxLU xb 因为 ，则),2,1(0niaii11()xDLU xD b 这样便得到一个迭代公式(1)1()1()kkxDLU xD b 11()BDLUfD b 令则有fBxxkk)()1(（k=0,1,2）称为雅可比迭代公式,B称为雅可比迭代矩阵雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即)(1)(1)(1)(11)(22)(11)1(2)(2)(323)(12122)1(21)(1)

7、(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax(k=0,1,2,)3.2.1 雅可比迭代法的算法实现?max1iiniyx k+1 k yi xi k=M?i=1,2,n 输 出 迭 代 输 出 失 败 标 志 y1,y2,yn 输 入 aij,bi,和 方 程 阶 数n,M 1 k niyaxabiiinijjjiji,2,1/)(1 y n y n 3.3 高斯-塞德尔（Gauss-Seidel）迭代法 3.3.1 高斯-塞德尔迭代法的基本思想 在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每

8、次迭代充分利用当前最新的迭代值，即在求 时用新分量代替旧分量 ,就得到高斯-赛德尔迭代法。其迭代法格式为：)1(kix)1(1)1(2)1(1,kikkxxx)(1)(2)(1,kikkxxx)(1111)()1()1(ijnijkjijkjijiiikixaxabax(i=1,2,n k=0,1,2,)例例3 用用GaussSeidel 迭代格式解方程组迭代格式解方程组 35410218321321321xxxxxxxxx精确要求为精确要求为=0.005=0.005 解解 GaussGaussSeidel Seidel 迭代格式为迭代格式为(1)()()123(1)(1)()213(1)(1

9、)(1)312(1)/8(24)/10(3)/5kkkkkkkkkxxxxxxxxx 取初始迭代向量取初始迭代向量 ,迭代结果为：迭代结果为：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()3,2,1(,005.0)3()4(ixxiix*3.3.2 GaussSeidel 迭代法的矩阵表示 将A分裂成A=D+L+U，则 等价于 (D+L+U)x=b 于是,则高斯塞德尔迭代过程 bAx(1)(1)()k

10、kkDxLxUxb 因为 ,所以 0D0DLD(1)()()kkDL xUxb(1)1()1()()kkxD L UxD L b1111(),()GDLUdDLb 1)(1)1(dxGxkk则高斯-塞德尔迭代形式为：故 令 3.3.3 高斯塞德尔迭代算法实现 高斯-塞德尔迭代算法的计算步骤与流程图与雅可比迭代法大致相同，只是一旦求出变元的某个新值 后,就改用新值 替代老值 ，再进行这一步剩下的计算。ix)1(kix)1(kix)(kix 3.4 超松弛迭代法（SOR方法）使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛，但由于收敛速度缓慢，使计算量变得很大而失去使用价值。因此，迭代过

11、程的加速具有重要意义。逐次超松弛迭代（Successive Over relaxatic Method，简称SOR方法）法，可以看作是带参数的高斯塞德尔迭代法，实质上是高斯-塞德尔迭代的一种加速方法。3.4.1超松弛迭代法的基本思想 超松弛迭代法目的是为了提高迭代法的收敛速度，在高斯塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果 与高斯-塞德尔迭代方法的迭代值 适当加权平均，期望获得更好的近似值 。是解大型稀疏矩阵方程组的有效方法之一，有着广泛的应用。其具体计算公式如下：)(kix)1(kix)1(kix用高斯塞德尔迭代法定义辅助量。),.,2,1(,11)(11)1(nixaxa

12、banijkjijijkjijiii)1(kix把 取为 与 的加权平均，即)1(kix)(kix)1(kix)()1()()1()()1()()1(kikikikikikixxxxxx合并表示为：)()1(1)()1(11)()1(nijkjijkjijijiiikikixaxabaxx式中系数称为松弛因子，当=1时，便为高斯-塞德尔迭代法。为了保证迭代过程收敛，要求0 2。当0 1时，低松弛法；当1 2时称为超松弛法。但通常统称为超松弛法(SOR)。3.4.2超松弛迭代法的矩阵表示设线性方程组 Ax=b 的系数矩阵A非奇异,且主对角元素 ,则将A分裂成A=d+L+U,则超松弛迭代公式用矩阵

13、表示为),2,1(0niaii(1)()1(1)()(1)()kkkkxxDbLxUx(1)()(1)()(1)()kkkkDxDxbLxUx或(1)()()(1)kkDL xDU xb故 显然对任何一个值,(D+L)非奇异,(因为假设 )于是超松弛迭代公式为 niaii,2,1,0(1)1()1()(1)()kkxDLDU xDLb1()(1)LDLDU令1()fDLb则超松弛迭代公式可写成 fxLxkk)()1(例例4 用用SOR法求解线性方程组法求解线性方程组 7910431017210424321321321xxxxxxxxx取取=1.46，要求，要求 6)()1(10kkxx解：SO

14、R迭代公式(1)()()()1123(1)()(1)()2213(1)()(1)(1)3312(1)(2410)4(1)(2103)17(1)(4107)9kkkkkkkkkkkkxxxxxxxxxxxxk=0,1,2,，初值 Tx)0,0,0()0(该方程组的精确解只需迭代20次便可达到精度要求 Tx)1,1,2(*)如果取=1(即高斯塞德尔迭代法)和同一初值 ,要达到同样精度,需要迭代110次Tx)0,0,0()0(3.5 迭代法的收敛性迭代法的收敛性 我们知道我们知道,对于给定的方程组可以构造成对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯简单迭代公式、雅可比迭代公式、高斯

15、-塞德塞德尔迭代公式和超松弛迭代公式，但并非一定尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。收敛。现在分析它们的收敛性。对于方程组对于方程组 经过等价变换构造出的等价方程组经过等价变换构造出的等价方程组 bAx),1,0()()1(kdGxxkk在什么条件下迭代序列在什么条件下迭代序列 收敛？先引入收敛？先引入如下定理如下定理 )(kx基本定理基本定理5 5 迭代公式迭代公式 收敛收敛的的充分必要条件充分必要条件是迭代矩阵是迭代矩阵G的谱半径的谱半径证:必要性 设迭代公式收敛,当k时,则在迭代公式两端同时取极限得记 ,则 收敛于0(零向量),且有 ),1,0()()1(k

16、dGxxkk1)(G*)(xxkdGxx*)()(xxekk)(ke)1(*)1(*)1(*)()()()(kkkkkGexxGdGxdGxxxe)0()2(2)1()(eGeGGeekkkk于是 由于 可以是任意向量,故 收敛于0当且仅当 收敛于零矩阵，即当 时)0(e)(kekGk0kG0)()(kkkGGG于是 所以必有 1)(G充分性充分性:设设 ,则必存在正数则必存在正数,使使则存在某种范数则存在某种范数 ,使使 ,则则 ,所以所以 ,即即 。故。故 收敛于收敛于 0,收敛于收敛于 由此定理可知，不论是雅可比迭代法、高斯由此定理可知，不论是雅可比迭代法、高斯塞德尔迭代法还是超松弛迭代

17、法，它们收敛的塞德尔迭代法还是超松弛迭代法，它们收敛的充要条件是其迭代矩阵的谱半径充要条件是其迭代矩阵的谱半径 。1)(G1)(G1)(GGkkkGGG)(0)(limkkG0limkkG0limkkG)(ke)(kx*x1)(G 事实上事实上,在例在例1中中,迭代矩阵迭代矩阵G=，其特征多项式为其特征多项式为,特征值为特征值为-2，-3，,所以迭代发散所以迭代发散 421165)det(2GI13)(G定理定理6(6(迭代法收敛的充分条件迭代法收敛的充分条件)若迭代矩阵若迭代矩阵G G的一种范数的一种范数 ,则迭代公式则迭代公式收敛收敛,且有误差估计式且有误差估计式,且有误差估计式且有误差估

18、计式 1G),1,0()()1(kdGxxkk)1()()(1kkkxxGGxx)0()1()(1xxGGxxkk及及 证证:矩阵的谱半径不超过矩阵的任一种范数矩阵的谱半径不超过矩阵的任一种范数,已知已知 ,因此因此 ,根据定理根据定理4.94.9可知可知迭代公式收敛迭代公式收敛1G1)(G又因为又因为 ,则则det(I-G)0,I-G为非奇异矩阵为非奇异矩阵,故故xGxd有惟一解有惟一解 ,即即与迭代过程与迭代过程 相比较相比较,有有两边取范数两边取范数 1G*xdGxx*dGxxkk)()1()()1(*)(*kkxxGxx)1(*)(*kkxxGxx)1()()(*kkkxxxxG)1(

19、)()(*kkkxxGxxG)1()()(*)1(kkkxxGxxG)1()()(*1kkkxxGGxx 由迭代格式，有由迭代格式，有)()()()0()1(1)2()1(2)2()1()1()(xxGxxGxxGxxkkkkkkk两边取范数，代入上式，得两边取范数，代入上式，得 )0()1()(*1xxGGxxkk证毕证毕 由定理知，当由定理知，当 时，其值越小，迭代时，其值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代收敛越快，在程序设计中通常用相邻两次迭代 （为给定的精度要求）作为为给定的精度要求）作为控制迭代结束的条件控制迭代结束的条件 1G)1()(kkxx例例5 5 已知线性方

20、程组已知线性方程组 6612363311420238321321321xxxxxxxxx考察用考察用JacobiJacobi迭代和迭代和G-SG-S迭代求解时的收敛性迭代求解时的收敛性解解:雅可比迭代矩阵雅可比迭代矩阵 131211111232122223132333332008841()00111163001212aaaaaaBDLUaaaaaa 1129129,115,85maxB故故JacobiJacobi迭代收敛迭代收敛 将系数矩阵分解将系数矩阵分解 80032114001126300ADLU则高斯则高斯-塞德尔迭代矩阵塞德尔迭代矩阵 1118032()4110163120GDLU 1

21、32000888032113200102211221109112770176441217688 18517641,227,85max1G故高斯故高斯塞德尔迭代收敛。塞德尔迭代收敛。定义定义3.2 3.2 设矩阵设矩阵 每一行对角元素每一行对角元素的绝对值都大于同行其他元素绝对值之和的绝对值都大于同行其他元素绝对值之和 nijaA)(1,1,2,niiijjjiaain则称则称A A为弱对角占优矩阵。若上式中不等号均为弱对角占优矩阵。若上式中不等号均严格成立，则称严格成立，则称A A为严格对角占优矩阵。为严格对角占优矩阵。定理定理8 设设n阶方阵阶方阵 为严格对角占优为严格对角占优阵阵,则则A非

22、奇异非奇异。nnijaA)(定理定理9 9 若矩阵A A按行(或列)严格对角占优,或按行(或列)弱对角占优不可约；则Jacobi迭代、Gauss-Seidel迭代都收敛。111122111221bA例例 6 考察用考察用雅可比迭代法和雅可比迭代法和高斯高斯-塞德尔迭代塞德尔迭代 法解线性方程组法解线性方程组Ax=bAx=b的收敛性，其中的收敛性，其中解：解：先计算迭代矩阵先计算迭代矩阵002211223,2,13BI求特征值求特征值雅可比矩阵雅可比矩阵 (B)=0 1)=21 用高斯用高斯-塞德尔迭代塞德尔迭代法求解时，迭代过程发散法求解时，迭代过程发散11100022022()1100010

23、2302 1000002GDLU 高斯高斯-塞德尔迭代矩阵塞德尔迭代矩阵求特征值求特征值2122023(2)0002IG 当时当时 a a 11时时,Jacobi矩阵矩阵 G GJ J 1,1,对初值对初值x x(0)(0)均收敛均收敛例例7 设设 方程组方程组 写出解方程组的写出解方程组的Jacobi迭代公式和迭代矩阵迭代公式和迭代矩阵 并讨论迭代收敛的条件。并讨论迭代收敛的条件。写出解方程组的写出解方程组的Gauss-Seidel迭代矩阵迭代矩阵,并讨并讨 论迭代收敛的条件。论迭代收敛的条件。解解 Jacobi迭代公式和迭代公式和Jacobi矩阵分别为矩阵分别为 2211212bxaxba

24、xx2)(1)1(21)(2)1(12bxaxbaxxkkkk020aaGJ例例 7设设 方程组方程组 写出解方程组的写出解方程组的Gauss-Seidel迭代矩阵，并讨论迭代矩阵，并讨论 迭代收敛的条件。迭代收敛的条件。解解 Gauss-Seidel矩阵为矩阵为 2211212bxaxbaxx120100()100222SaaGDLUaa当时当时 a a 11时时,Gauss-Seidel,Gauss-Seidel矩阵矩阵 G Gs s 1,1,所以对任意初值所以对任意初值x x(0)(0)均收敛。均收敛。也可用矩阵的谱半径也可用矩阵的谱半径p(GS)1来讨论来讨论解：解：先计算迭代矩阵先计

25、算迭代矩阵例例8 讨论用讨论用雅可比迭代法和雅可比迭代法和高斯高斯-塞德尔迭代塞德尔迭代 法解线性方程组法解线性方程组Ax=bAx=b的收敛性。的收敛性。024211121112321xxx024211121112bA0)1()12(412121212121213BI求特征值求特征值雅可比矩阵雅可比矩阵 (B)=1 用用雅可比迭代法求解时，迭代过程不收敛雅可比迭代法求解时，迭代过程不收敛131211111232122223112333311002211()0022110022aaaaaaBDLUaaaaaa 1=-1，2,3=1/2求特征值求特征值高斯高斯-塞德尔迭代矩阵塞德尔迭代矩阵1121

26、1102211()0481308811221110(51)044813088GDLUIG (G1)=0.3536 1 用用高斯高斯-塞德尔迭代塞德尔迭代法求解时，迭代过程收敛法求解时，迭代过程收敛16753,2i 1=0,求解求解AX=b,AX=b,当当 取何取何值时迭代收敛？值时迭代收敛？解解:所给迭代公式的迭代矩阵为所给迭代公式的迭代矩阵为 例例9 9 给定线性方程组给定线性方程组 AX=bAX=b 用迭代公式用迭代公式 X X(K+1)(K+1)=X=X(K)(K)+(b-A(b-AX X(K)(K)(k=0,1,)(k=0,1,）323,121Ab 1 321 2(1 3)20(1 2

27、)BIAIB 即即 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迭代收敛迭代收敛 本章小结本章小结本章介绍了解线性方程组本章介绍了解线性方程组 迭代法的迭代法的一些基本理论和具体方法。迭代法是一种逐次逼一些基本理论和具体方法。迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按近的方法，即对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序列的极照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。注意到在

28、使用迭代法限为方程组的解。注意到在使用迭代法解方程组时，其迭代矩阵解方程组时，其迭代矩阵B B和迭代向量和迭代向量f f在计算过在计算过程中始终不变程中始终不变,迭代法具有循环的计算公式迭代法具有循环的计算公式,方法方法简单，程序实现方便，它的优点是能充分利用系简单，程序实现方便，它的优点是能充分利用系数的稀疏性数的稀疏性,适宜解大型稀疏系数矩阵的方程组。适宜解大型稀疏系数矩阵的方程组。bAx fBxxkk)()1(迭代法不存在误差累积问题。使用迭代法的迭代法不存在误差累积问题。使用迭代法的关键问题是其收敛性与收敛速度，收敛性与迭代关键问题是其收敛性与收敛速度，收敛性与迭代初值的选取无关，这是

29、比一般非线性方程求根的初值的选取无关，这是比一般非线性方程求根的优越之处。在实际计算中，判断一种迭代格式收优越之处。在实际计算中，判断一种迭代格式收敛性较麻烦，由于求迭代的谱半径时需要求特征敛性较麻烦，由于求迭代的谱半径时需要求特征值，当矩阵的阶数较大时，特征值不易求出，通值，当矩阵的阶数较大时，特征值不易求出，通常采用矩阵的任一种范数都小于常采用矩阵的任一种范数都小于1 1或对角占优来判或对角占优来判断收敛性。有时也可边计算边观察其收敛性。如断收敛性。有时也可边计算边观察其收敛性。如何加快迭代过程的收敛速度是一个很重要的问题何加快迭代过程的收敛速度是一个很重要的问题，实用中更多的采用，实用中更多的采用SORSOR法，选择适当的松驰因子法，选择适当的松驰因子有赖于实际经验。我们应针对不同的实际问题有赖于实际经验。我们应针对不同的实际问题，采用适当的数值算法。，采用适当的数值算法。