第4章 解线性方程组迭代法2017_2

1、14 松弛法(1)( )(1)121(1)( )( )111(1)( )11 (,), 1 ()Tkkkninkkkiijjijjiijj iinkkiijjijjjj iiiGaussSeidelxxxxxxxGaussSeidelxb xb xgxba xa xxa 可认为是对迭代法加速。记其中由迭代公式得到。于是有( )( )(1)( )(1,2, )kikkkinxGaussSeidelkxxxx 可以把看作迭代的修正项，即第 次近似解以此项修正后得到新的近似解 2(1)( )(1)1(1)( )11 (1)() (kkkkiiiinkkkiiijjijjjj iiixxxxxxxxb

2、a xa xai 松弛法是将乘上一个参数因子作为修正项而得到新的近似解，具体公式为即1,2, ) 111nAxbGaussSeidel按上式计算的近似解序列的方法称为松弛法，称为松弛因子。当时称为低松弛；是迭代；时称为超松弛法。3(1)( )( )1(1)1( )1( )( )1(1)1( )11111 () (1)1()(kkkkkkkkkxxxxD LxD UxD bxxD LxD UxD bID LID LDL松弛法迭代公式的矩阵表示：因det（） ，故（） 与存在。(1)111)111(1 () (1)() () (1) () ) kkxDLDU xD DD LDLDDLbMDLDU有

3、松弛法的迭代矩阵为松弛因子的选取对收敛速度影响极大，但目前尚无可供实用的计算最佳松弛因子的方法。通常是根据系数矩阵的性质及实际经验，通过试算来确（）定松弛因子。4(0)1212323(1)(1)1(1)( )11(11 1.4,(1,1,1) ,21 2021.8 +() (1)()Tkkkkiiiiinkkkiiijjijjjj iiikxxxxxxxxxxxxxba xa xax 例：取用超松弛法解方程组解：由)( )( )12(1)( )(1)( )2213(1)( )(1)332(0)(9)0.40.7(1)0.40.7()(0,1,2,)0.40.7(1.8)(1,1,1)(1.20

4、0,1.3996,1.6001) (1.2,1.4,1.6)kkkkkkkkkTTTxxxxxxkxxxxxx 将代入上式开始迭代，精确解5松弛法计算过程如下：1(0)(0)(0)(0)12(0)(0)11111121(0)(0)111.()(,)(,)2.13. (1)() / (1)() / ijnnnjjjiniiiijjijjiijjiAabbbnxxxxNkxxba xaxxba xa xa 输入，维数 ， ，参数，最大容许迭代次数。置。计算，1(0)1(0)(0) (2,1) (1)() /4.55.1(1,2, )3nnnnnjjnnjiiinxxba xaxxxkNkkxxin

5、，。若，输出 ，停机；否则转 。若，置，转 ；否则，输出失败信息，停机。65 迭代法的收敛条件一、矩阵的谱半径11212 (1,2, ) ( )max(,) (,)(1,2,), (iii nnkkkknAninAAAAAAAAk 迭代法的收敛与迭代矩阵的特征值有关。定义：设 为 阶方阵，为 的特征值，称绝对值最大的特征值的绝对值为矩阵 的谱半径，记为称为矩阵 的谱。由特征值的定义知，矩阵的谱是因而22) ( )( ()()kkAuuA uA AuAuAuAAu）7二、迭代法的收敛条件(0)( )(4.2) ( )1.kx Bx fxgxB设线性方程组 =+ 有唯一解,则对任意初始向量和右端项

6、 ，由迭代格式产生的向量序列收敛的充要条件是 定理4.3 （ ： 充要条件）*1*101()().kkkkkxBxfxxB xxBxxxBxf证:*11lim()0lim0( )1.kkkkxxBB因此8注注: :因为因为 都可以直接用矩阵都可以直接用矩阵的元素计算，因此的元素计算，因此, ,用推论用推论1 1容易判别迭代法容易判别迭代法的收敛性的收敛性. .1,FBBB(0)( ) 1 (4.2)kxfBx对任意初始向量和右端项 ，若，由迭代格式产生的向量序列收敛.1() 推论 充分条件注注: :要检验一个矩阵的谱半径小于要检验一个矩阵的谱半径小于1 1，比较困难，所，比较困难，所 以，我们

7、希望用别的办法判断收敛性以，我们希望用别的办法判断收敛性. . 9 02.松弛法收敛的必要条件是 2() 推论必要条件由定理由定理4.3, , 有有定理定理4.4 Jacobi 迭代法收敛的迭代法收敛的充要条件充要条件是是 (B) 1.由推论由推论1, 得到得到定理定理4.5 若若 | B | 1，则，则 Jacobi 迭代法收敛迭代法收敛. (充分条件充分条件)Jacobi迭代法收敛的条件迭代法收敛的条件定理定理4.6 GS 迭代法收敛的迭代法收敛的充要条件充要条件是是 (B) 1.定理定理4.7 若若 | B | 1，则，则 GS 迭代法收敛。迭代法收敛。Gauss - Seidel迭代法

8、收敛的条件迭代法收敛的条件12 021 12,1上例说明了确实只是松弛法收敛的必要条件，而非充要条件，因为Gauss-Seidel迭代即为的情形。判断定理虽然给出了判别迭代收敛的充要条件，但要求逆矩阵和特征值。推论 与 仅分别给出了收敛的充分与必要条件，许多情形下不能起作用由推论 无法判别收敛性。 对一些特殊的系数矩阵可给出几个常用的判别收敛条件。131 ()(1,2, )nijiiijjj inAaaainiAiA定义：若 阶方阵满足且至少有一个 值，使上式中不等号严格成立，则称 为弱对角占优阵。若对所有，上式不等号均严格成立，则称为严格对角占优阵。131112112222 ,0110210

9、 110011012011P ITAAAAAAAAAP AP 定义：如果矩阵 不能通过行的互换和相应的列互换成为形式其中，为方阵，则称 为不可约。 例：141.JacobiGauss-SeidelA若 为严格对角占优阵或不可约弱对角占优阵，则迭代法和迭代法均收敛。2.01,A若 为严格对角占优阵，则松弛法收敛。3.02A若 为对称正定阵，则松弛法收敛的充要条件为。1012210 1 102121115012A BABAB 若线性方程组的系数矩阵分别为 , ：则， 为严格对角占优阵，故Jacobi与Gauss-Seidel迭代均收敛。 为非严格对角占优阵，但为对称正定阵， =1.4故松弛法收敛。

10、 ,Axb设有线性方程组下列结论成立：例例10 判别判别,下列方程组使用下列方程组使用 J-迭代法迭代法,G-S迭代法求迭代法求解是否收敛解是否收敛?12412341231234102 52 92403 48 1 2 61xxxxxxxxxxxxxx解解 此方程组是严格按行对角占优的此方程组是严格按行对角占优的, 所以使用所以使用J-法收敛，法收敛，G-S迭代法收敛迭代法收敛.16-111/ 21/ 2,1/ 211/ 21/ 21/ 213(02)101/ 21/ 2 -1/ 201/ 21/ 21/ 20Axb AAAABI D A 例11：讨论用三种迭代法求解的收敛性。解：因 为对称且其

11、各阶主子式皆大于零，故 为对称正定矩阵.由判别条件 ，Gauss-Seidel迭代法与松弛法均收敛.不是弱对角占优阵，故不能用条件 判断。Jacobi迭代法的迭代矩阵为173212311221131 224411221 () (1)021,1, ()12 IBBJa co b i 其 特 征 方 程得因 而迭 代 法 不 收 敛 。Jacobi迭代法收敛的条件续迭代法收敛的条件续定理定理4.8若方程组若方程组 Ax=b 的系数阵的系数阵 A 是主对角严格占是主对角严格占优阵或不可约弱对角占优阵，则用优阵或不可约弱对角占优阵，则用 Jacobi 迭代法求迭代法求解必收敛。解必收敛。定理定理4.9

12、 若方程组若方程组 Ax=b 的系数阵的系数阵 A 是主对角严格占是主对角严格占优阵或不可约弱对角占优阵，则用优阵或不可约弱对角占优阵，则用 GS 迭代法求解迭代法求解必收敛。必收敛。定理定理4.10 若方程组若方程组 Ax=b 的系数阵的系数阵 A 是正定矩阵，是正定矩阵，则用则用 GS 迭代法求解必收敛。迭代法求解必收敛。Gauss - Seidel迭代法收敛的条件续迭代法收敛的条件续20 310 , 9410100033 , 91500423015( ),()22AxbAJacobiGaussSeidelBMBM改变方程组中方程的次序，即将系数矩阵作行交换，会改变迭代法的收敛性。例12：

13、与迭代的迭代矩阵分别为谱半径分别是。均不收敛。21 ,31094 94310AxbA xbAAAA xbJacobiGaussSeidel若交换方程的次序，得的同解方程组为严格对角占优阵，因而对方程组用与迭代求解均收敛。22 310 , 9410100033 , 91500423015( ),()22AxbAJacobiGaussSeidelBMBM改变方程组中方程的次序，即将系数矩阵作行交换，会改变迭代法的收敛性。例12：与迭代的迭代矩阵分别为谱半径分别是。均不收敛。23 ,31094 94310AxbA xbAAAA xbJacobiGaussSeidel若交换方程的次序，得的同解方程组为严格对角占优阵，因而对方程组用与迭代求解均收敛。