1、第五章线性方程组迭代解法5.2.2 Jacobi 迭代法和迭代法和 Gauss-Seidel 迭代法的收敛性迭代法的收敛性5.2.1 一般迭代法的收敛性一般迭代法的收敛性5.25.2 迭代法的收敛性迭代法的收敛性第五章线性方程组迭代解法 设设 是方程组（是方程组（5.1.2）的解，即）的解，即 。该式与（。该式与（5.1.3）式相）式相减，并记误差向量减，并记误差向量 ，则有，则有*xfBxx*)()(xxekk.,1,0,)()1(kBeekk由此可推出由此可推出 ,)0()(eBekk（5.2.1）其中其中 与与 k 无关。所以，迭代法（无关。所以，迭代法（5.1.3）收敛就意味着对任）收
2、敛就意味着对任意初始向量意初始向量 ，都有，都有*)0()0(xxenRx)0(0limlim)0()(eBeKkkk 下面给出迭代法收敛的充分必要条件。下面给出迭代法收敛的充分必要条件。5.2.1 一般迭代法的收敛性一般迭代法的收敛性第五章线性方程组迭代解法证证 根据距阵根据距阵 Jordan 标准型的结论，对距阵标准型的结论，对距阵 B，存在非奇异距阵，存在非奇异距阵 P，使，使得得),(211rJJJdiagJBPP其中其中.11ininiiiiJ显然，显然，,11PPJBPJPBKK).,(21krkkKJJJdiagJ因此，因此，的充分必要条件是的充分必要条件是0limkkB.,2,
3、1,0limriJkik)(nnRB 定理定理 5.1 设距阵设距阵 ，则，则 的充分必要条件是的充分必要条件是 B 的的谱半径谱半径 。0limkkB1)(B第五章线性方程组迭代解法记记 ，则有，则有iiEIJ,00101000100iinnkiE其中第其中第1行的第行的第 k+1 个元素为个元素为1。于是有。于是有jinijjkijkjijkikjikkiikiECECEIJ100)(第五章线性方程组迭代解法,1111iinnkikikinikinikkikikCk其中，其中，。)!(!/!,0jkjkCIEjki 由于由于 所以所以 的充分必要条件的充分必要条件是是 。定理得证。定理得证
4、。),0,1(0limskksk0limkikJ),2,1(1rii 定理定理 5.2 对于任意的初始向量对于任意的初始向量 和右端向量和右端向量 f ，解方程组（，解方程组（5.1.2）的迭代法（的迭代法（5.1.3）收敛的充分必要条件是）收敛的充分必要条件是 。)0(x1)(B 证证 先证充分性。设先证充分性。设 ，则矩阵，则矩阵 非奇异，方程组非奇异，方程组（5.1.2）有惟一解）有惟一解 ，从而的（，从而的（5.2.1）。由定理）。由定理 5.1 知知 ，因此，因此，即，即 。*x1)(BBI 0limkkB0lim)(kke*)(limxxkk第五章线性方程组迭代解法 再证必要性。设
5、对任意初始向量再证必要性。设对任意初始向量 和右端顶和右端顶 f，均有，均有 ，则得则得 。因此，对任意。因此，对任意 都有都有 ，由此推出，由此推出 ，即得，即得 。定理得证。定理得证。)0(x*)(limxxkk)(,*)0(*)(*xxBxxfBxxkk)0(x0)(lim*)0(xxBkk0limkkB1)(B 例例 5.2 判断用判断用 J 法和法和 GS 法解方程组法解方程组 的收敛性，其中的收敛性，其中bAx.107571045410)2(,1785191091)1(AA 解解 （1）按（）按（5.1.6）和（）和（5.1.11）有）有.6756390858101090 ,078
6、5091090GSJBB第五章线性方程组迭代解法 的特征值为：的特征值为：的特征值为：的特征值为：因此，两种迭代法均发散。因此，两种迭代法均发散。JB.2825.8,9306.31412.4,9306.31412.4321ii.12825.8)(JBGSB.6054.594,6054.0,0321.16054.594)(GSB（2）按（按（5.1.6）和（）和（5.1.11）求得）求得.6.0088.005.016.005.04.00,07.05.07.004.05.04.00GSJBBJB 的特征值为：的特征值为：的特征值为：的特征值为：因因此，此，J 法发散，而法发散，而 GS 法收敛。法
7、收敛。.10770.1)(.0770.1,7108.0,3653.0321JBGSB.14463.0)(.4463.0,3137.0,0321GSB 有时实际判别一个迭代法是否收敛，条件有时实际判别一个迭代法是否收敛，条件 是很难检验的。而是很难检验的。而一些矩阵范数一些矩阵范数 可以用可以用 B 的元素表示，所以用的元素表示，所以用 作为收敛的充分条作为收敛的充分条件较为方便。件较为方便。1)(BB1B第五章线性方程组迭代解法 定理定理 5.3 对某种算子范数，若对某种算子范数，若 则迭代法（则迭代法（5.1.3）式产生的向）式产生的向量序列量序列 收敛于（收敛于（5.1.2）的精确解）的精
8、确解 ，且有误差估计式，且有误差估计式1B)(kx*x.1)0()1(*)(xxBBxxkk,1)1()(*)(kkkxxBBxx（5.2.2）（5.2.3）证证 由由 知迭代法是收敛的，且知迭代法是收敛的，且 。由（。由（5.1.3）和）和 易得易得 ，于是有于是有 1B*)(limxxkkfBxx*)(*)(*)1(xxBxxkk)()1()()()1(kkkkxxBxx.,)1()()()1(*)(*)1(kkkkkkxxBxxxxBxx第五章线性方程组迭代解法由此可得由此可得.*)()1()(*)1()1()(*)(xxBxxBxxxxxxkkkkkkk因因 ，由上式即得（，由上式即得
9、（5.2.2），反复运用），反复运用01 B,)()()2()1()2()1()1()(kkkkkkxxBxxBxx即可得（即可得（5.2.3），定理得证。），定理得证。式（式（5.2.2）说明，若）说明，若 但不接近但不接近 1，则当相邻两次迭代向量，则当相邻两次迭代向量 和和 很接近时，很接近时，与精确解很靠近。因此，在实际计算中，用与精确解很靠近。因此，在实际计算中，用 作为迭代终止条件是合理的。作为迭代终止条件是合理的。1B)1(kx)(kx)(kx)()1(kkxx 对给定的精度要求，由（对给定的精度要求，由（5.2.3）可以得到需要迭代的次数，并且，由）可以得到需要迭代的次数，并且
10、，由第五章线性方程组迭代解法（5.2.3）可见，）可见，越小，序列越小，序列 收敛越快。由于收敛越快。由于 依赖于所选依赖于所选择的范数，而且择的范数，而且 ，我们以，我们以 给出收敛速度的概念。给出收敛速度的概念。B)(kxBBB)()(B 定义定义 5.2 称称 为迭代法（为迭代法（5.1.3）的）的渐进收敛速度渐进收敛速度。)(ln)(BBR由此定义可以看出，由此定义可以看出，越小，越小，R（B）就越大。）就越大。1)(B例例 5.3 证明用证明用 J 法和法和 GS 法解下列方程组法解下列方程组.132,5.0102,12210321321321xxxxxxxxx必收敛，并比较满足必收
11、敛，并比较满足 的迭代次数。的迭代次数。5)1()(10kkxx 解解 按（按（5.1.6）和（）和（5.1.11）有）有.241402160303001501,03/23/11.002.02.02.00GSJBB第五章线性方程组迭代解法由于由于 ，所以，所以，J 法和法和 GS 法必收敛，法必收敛，并且，并且，GS 法比法比 J 法收敛快。法收敛快。12/1,115/1311GSJBB11JGSBB 取取 ，J 法的计算结果如表法的计算结果如表 5 1，GS 法的计算结果如表法的计算结果如表5-2。对。对 J 法有法有 ，对，对 GS 法有法有 实际计算结果也表明实际计算结果也表明 GS 法
12、比法比 J 法收敛快。法收敛快。Tx)0,0,0()0(5)14()15(10 xx5)8()9(104.0 xx k 表表 5-1)(1kx)(2kx)(3kx 0 0 0 0 1 0.100000 0.050000 0.333333 2 0.176667 0.103333 0.400000 13 0.231069 0.147041 0.508362 14 0.231081 0.147050 0.508383 15 0.231087 0.147055 0.508393 第五章线性方程组迭代解法 表 5-2 k)(1kx)(2kx)(3kx 0 0 0 0 1 0.100000 0.07000
13、0 0.413333 2 0.196667 0.130667 0.486000 7 0.231071 0.147048 0.508389 8 0.231087 0.147056 0.508399 9 0.231091 0.147058 0.5084025.2.2 Jacobi 迭代法和迭代法和 Gauss-Seidel 迭代法的收敛性迭代法的收敛性 显然可以利用定理显然可以利用定理5.2和定理和定理5.3判别判别 J 法和法和 GS 法的收敛性，但其中只法的收敛性，但其中只有定理有定理5.3对对 J 法使用比较方便。对于大型方程组，要求出迭代矩阵法使用比较方便。对于大型方程组，要求出迭代矩阵
14、和和GSB第五章线性方程组迭代解法谱半径谱半径 以及以及 都是不容易的。下面给出一些容易验证收敛性的都是不容易的。下面给出一些容易验证收敛性的充分条件，先讨论对角占优矩阵的性质。充分条件，先讨论对角占优矩阵的性质。)(JB)(GSB定义定义 5.3 若若 满足满足nnijRaA)(,2,1,1niaanijjijii则称则称 A 为为严格对角占优矩阵严格对角占优矩阵。若满足。若满足,2,1,1niaanijjijii且其中至少有一个严格不等式成立，则称且其中至少有一个严格不等式成立，则称 A 为为弱对角占优矩阵弱对角占优矩阵。定义定义 5.4 设设 ，若存在一个排列阵，若存在一个排列阵 P，使
15、得，使得nnRA,0221211AAAAPPT（5.2.4）第五章线性方程组迭代解法其中其中 和和 均为方阵，则称均为方阵，则称 A 为为可约的可约的。如果不存在排列阵。如果不存在排列阵 P 使使（5.2.4）成立，则称）成立，则称 A 为为不可约的不可约的。11A12A如下矩阵如下矩阵 A 是可约的，是可约的，B 是不可约的：是不可约的：.4114114114,3020412330102135BA因为，对于矩阵因为，对于矩阵 A 有有.3200310042132315,101101APPPT第五章线性方程组迭代解法而对于矩阵而对于矩阵 B，不存在一个排列阵使（，不存在一个排列阵使（5.2.4
16、）成立。）成立。定理定理 5.4 若若 严格对角占优，则严格对角占优，则 且且 A 非奇异。非奇异。)(ijaA,2,1,0niaii 证证 由严格占优矩阵的定义可知由严格占优矩阵的定义可知 若若 A 奇异，则奇异，则有有 使使 Ax=0。设。设 则则 Ax=0的第的第k个方个方程有程有,2,1,0niaii,0),(21Tnxxxx,0 xxk,1jnkjjkjkkkxaxa由此得到由此得到,1,1nkjjkjkjnkjjkjkkaxxaa这与严格对角占优矛盾，定理得证。这与严格对角占优矛盾，定理得证。第五章线性方程组迭代解法 定理定理 5.5 若若 为不可约弱对角占优阵，则为不可约弱对角占
17、优阵，则且且 A 非奇异。非奇异。)(ijaA,2,1,0niaii 证证 若有某个若有某个 ，由，由 A 的弱对角占优性质可知的弱对角占优性质可知 A 的第的第k行元素均行元素均为零。交换为零。交换 A 的第的第k行和第行和第n行，并交换行，并交换 A 的第的第k列和第列和第n列，就得到列，就得到（5.2.4）的形式，这与）的形式，这与 A 的不可约性质矛盾，故的不可约性质矛盾，故0kka.,2,1,0niaii 如果如果 A 是奇异的，则存在是奇异的，则存在 使使 Ax=0，下面分两，下面分两种情况考虑。种情况考虑。,0),(21Tnxxxx 若若 由由 Ax=0的第的第k个方程有个方程有
18、,021nxxx.,2,1,1nkaankjjkjkk这与这与 A 的弱对角占优性相矛盾。的弱对角占优性相矛盾。第五章线性方程组迭代解法 若若 不全相等，记不全相等，记 显然显然 J 非空，非空，J 的补集也非空。若有的补集也非空。若有 和和 ，使得，使得 ，则由，则由得知得知),2,1(nixi,2,1,:nixxkJikJk Jm0kma1/kmxx.,1,1nkjjkjkjnkjjkjkkaxxaa这与这与 A 的弱对角占优性相矛盾，因此的弱对角占优性相矛盾，因此.,0JmJkakm这又导致与这又导致与 A 的不可约性相矛盾。的不可约性相矛盾。故在以上两种情况下，齐次方程组故在以上两种情
19、况下，齐次方程组 Ax=0 只有零解，所以只有零解，所以 A 非奇异，非奇异，定理得证。定理得证。第五章线性方程组迭代解法 以上两个定理说明，若以上两个定理说明，若A为严格对角占优或不可约弱对角占优阵，则为严格对角占优或不可约弱对角占优阵，则 J 法和法和GS法都可以计算。在这种情况下迭代法的收敛性有如下定理。法都可以计算。在这种情况下迭代法的收敛性有如下定理。定理定理5.6 若若A为严格对角占优矩阵，或不可约的弱对角占优矩阵，则解为严格对角占优矩阵，或不可约的弱对角占优矩阵，则解方程组方程组 的的 J 法和法和GS法均收敛。法均收敛。bAx 设设 ，这里只给出，这里只给出A为严格对角占优阵时
20、的证明。为严格对角占优阵时的证明。ULDA 对对 J法，迭代矩阵法，迭代矩阵 ，易得，易得)(1ULDBJijjiiijniJaaB,11max。由由A的严格对角占优性，得到的严格对角占优性，得到 ，所以，所以 J 法收敛。法收敛。1JB 对对GS法，迭代矩阵法，迭代矩阵 ，这里，这里 。ULDBGS1)(0)det(111niiiaLD由于由于)(det()det(1LDIBIGS)(det()det(1ULDLD我们只需要证明我们只需要证明 的根的根 ，满足，满足 。0)(det(ULD1证证第五章线性方程组迭代解法用反证法，假设用反证法，假设 ，则由，则由A的严格对角占优性有的严格对角占
21、优性有1nijjijiiaa,1nijijijijaa111，ni,2,1。这说明矩阵这说明矩阵nnnnnnaaaaaaaaaULD212222111211)(第五章线性方程组迭代解法 由定理由定理5.6的证明可见，矩阵的证明可见，矩阵A严格对角占优等价于严格对角占优等价于 。因此，。因此，由定理由定理5.6又可知，若又可知，若 ，则相应的，则相应的GS法也收敛。法也收敛。1JB1JB 由例由例5.1所给的系数矩阵是严格对角占优的，由例所给的系数矩阵是严格对角占优的，由例5.3所给的系数矩阵是不所给的系数矩阵是不可约弱对角占优的，所以，用可约弱对角占优的，所以，用J法和法和GS法解对应的方程组都收敛。法解对应的方程组都收敛。是严格对角占优矩阵，因此是严格对角占优矩阵，因此 。这说明只有。这说明只有当当 时，才能使时，才能使 。从而有。从而有 ，GS法收敛，定理得证。法收敛，定理得证。0)(det(ULD10detULD1)(GSB
