数值分析课件第二章

1、第二章 2.2 解线性方程组的迭代法 理学院 缪淑贤 11112211 21122222 1122 (1) nn nn nnnnnn a xa xa xb axaxaxb a xaxaxb , 0, X ,. 11 ijn n T AXb A T nn a , , ) , , )(x(b xbb 矩阵表示记为 这里我们假设 A 解线性方程组的两类方法 直接法: 经过有限次运算后可求得方程组精确解 的方法(不计舍入误差!) 迭代法：从解的某个近似值出发，通过构造一个 无穷序列去逼近精确解的方法。 迭代法研究的主要问题 1）迭代格式的构造； 2）迭代的收敛性分析； 3）收敛速度分析； 4）复杂性分

2、析；（计算工作量） 5）初始值选择。 迭代格式的构造 把矩阵A分裂为 则 ,0,AQCQ 11 () () . AxbQC xb IQ C xQ b xBxg 迭代过程 B称为迭代矩阵。 给定初值 就得到向量序列 定义：若 称逐次逼近法收敛， 否则，称逐次逼近法不收敛或发散。 1 ,(2) kk xBxg 0 ,x 01 , n xxx * lim, n n xx 问题： 是否是方程组（1）的解？ 定理1：任意给定初始向量 ，若由迭 代公式（2）产生的迭代序列收敛到 ， 则 是方程组（1）的解。 证： 0 x * x * x * x * 1 limlim(). kk kk xBxgxBxg 逐

3、次逼近法收敛的条件 定理2：对任意初始向量 ，由（2）得到 的迭代序列收敛的充要条件是迭代矩阵 的谱半径 证： 因此 ( )1.B 0 x * 1 *1* 10 ()(). kk k kk xBxg xBxg xxB xxBxx *1 1 lim()0lim0( )1. k k kk xxBB 要检验一个矩阵的谱半径小于1比较困难， 所以我们希望用别的办法判断是否有 定理3：若逐次逼近法的迭代矩阵满足 ， 则逐次逼近法收敛。 Remark:因为矩阵范数 ， ， 都可以 直接用矩阵 的元素计算，因此，用定理3， 容易判别逐次逼近法的收敛性。 1 lim0. k k B 1B 1 B F BB 问

4、题：如何判断可以终止迭代？ 定理4：若迭代矩阵 满足 则 （3） （4） Remark: 1) (4)式给出了一个停止迭代的判别准则。 2) (3）式指出 越小收敛越快。 ， 1B 1 * 110 1 k k B xxxx B * 11 1 kkk B xxxx B 1B 证： * 1221 * 221 * 11 * 11 ()() kkkk kkk kkk kkk xxxxxx xxxx B xxB xx B xxB xx 1110 k kkkk xxBxxBxx Jacobi 迭代 11112213311 21 1 22223322 31 1322 33334433 1 122,11 +

5、nn nn nn nnn nn nnnn a x a xa x a xa xax a xa xa xa xb a xa xa xb a xa xa xb a xb = Dx LxUx Jacobi迭代 (), (A xbD xLUxb若 | D |0 ) 11 (),xDLU xD b ( )(),0, ijijijij Lllaijelsel ()(),0, ijijijij Dddaijelse d ()ADLU分裂 迭代过程： 若记 11 1 (), kk xDLU xD b 1 (1)( )( ) 11 1 ( (), in kkk iijjijji jj i ii xa xa xb

6、a (1)( )( ) 1 1 (). n kkk iiijji j ii xba xx a ( )( )( ) 12 (,) , kkk kn xxxx 算法描述 1 输入 2 if , then 2.1 for 2.1.1 s=0, 2.1.2 for 2.1.3 2.1.4 if then 0 , , ,.A b xM kM 1, 2,in 1, 2,jn 0 () ijj ssax 10 ()()/() iiiii xbsax 01 |()() | ii xx 01 |()() |, ii xx (1)( )( ) 1 1 (). n kkk iiijji j ii xba xx a

7、2.2 k=k+1 2.3 if then 2.3.1 2.3.2 goto 2 else 输出 结束。 else 2.4 输出 迭代次数太大。 3 结束 1, x k 10 xx Gauss-Seidel迭代 假设| 0,D 1 (1)( )( ) 11 1 ( (), in kkk iijjijji jj i ii xa xa xb a Jacobi迭代 1 (1)(1)( ) 11 1 ( (), in kkk iijjijji jj i ii xa xa xb a 1 (1)(1)( )( ) 1 1 (), in kkkk iijjijjii jj i ii xa xa xbx a

8、Axb()ADLU 分裂 算法描叙 1 输入 2 if , then 2.1 for 2.1.1 s=0， 2.1.2 for 2.1.3 0 , , ,.A b xM kM 1, 2,in 1, 2,jn 0 () ijj ssax 0 ()itx 00 ()()/() iiiii xbsax 1 (1)(1)( )( ) 1 1 (), in kkkk iijjijjii jj i ii xa xa xbx a 2.1.4 if then 2.2 k=k+1 2.3 if ,输出结果，结束。 else 2.4 输出迭代次数太大。 3 结束 0 |()|, i xt 0 |()| i xt

9、Remark: 1) Gauss-Seidel迭代法的计算过程比Jacobi 迭代法更简单。计算过程中只需用一个 一维数组存放迭代向量。 2) Gauss-Seidel迭代不一定比Jacobi迭代收 敛快。 例 希望直接对系数矩阵A研究这俩种迭代收敛 条件。 定理5 设A是有正对角元的n阶对称矩阵， 则Jacobi迭代收敛 A和2D-A同为正定 矩阵。 证：记 则 即 ， 从而有相同的谱半径。 1122 (,), nn Ddiag aaa 1 2 111111 (,).Ddiagaaa 1111 1 2222 () J DIDADDID AB 11 22 () J IDADB 由A的对称性，

10、也对称， 因而特征值全为实数，记为 则 的任一特征值为 。 A ， 正定。 故 正定。 11 11 22 () iijjij DADaa a , (1). i in 11 22 IDAD 1 i ()11 1102 Jii B 11 22 2IDAD 1111 2222 2(2)DADIDADD 2DA A正定 正定， 特征 值小于1。 若 2D-A正定, 特 征值小于1, 所以 特征值大于1。 11 22 DAD 11 22 IDAD 1111 2222 (2)()IDDA DIDAD J B 定理6 A按行（列）严格对角占优，则 Jacobi迭代收敛。 引理 A按行（列）严格对角占优 （ ） 证 （提示） 1. J B 1 1. J B 1, max| n ij J jj i ii a B a 定理7 A按行严格对角占优，则Gauss- Seidel迭代收敛。 证 设 是 任一特征值，x 是相应 特征向量。设 若 则 G S B | max |. ij xx 1 1 11 () | |. in j iiijijj jj i i DLUxxDxLxUx x aaax x | 1, 1 11 |. in iiijij j