解线性方程组迭代法

1、解线性方程组迭代法 求解求解 bxA 思思 路路 与解与解 f (x)=0 的不动点迭代相似的不动点迭代相似 ，将，将 等价等价 bxA 改写为改写为 形式，建立迭代形式，建立迭代 。 从初值从初值 出发，得到序列出发，得到序列 。 fxBx fxBx kk )()1( )0( x )(k x 计算精度可控，特别适用于求解系数为大型稀疏计算精度可控，特别适用于求解系数为大型稀疏 矩阵的方程组。矩阵的方程组。 研究研究 内容：内容： 如何建立迭代格式？如何建立迭代格式？ 收敛速度？收敛速度？ 向量序列的收敛条件？向量序列的收敛条件？ 误差估计？误差估计？ 第第4章章 解线性方程组的迭代法解线性方

2、程组的迭代法 解线性方程组迭代法 为了误差的度量为了误差的度量 （正定性（正定性) (齐次性齐次性) 向量范数向量范数 定义定义 4-1 Rn空间的向量范数空间的向量范数 | | 对任意对任意 满足下列条件：满足下列条件： n Ryx , 00|;0|)1( xxx |)2(xx C 对任意对任意 |)3(yxyx （三角不等式（三角不等式) 向量范数的定义向量范数的定义 12 , T n Xx xx 向量向量 的的Lp范数定义为范数定义为 p n i p i xx /1 1 p )|(| 1 向量和矩阵范数向量和矩阵范数 解线性方程组迭代法 n i i xx 1 1 | n i i xx 1

3、 2 2 | |max| 1 i ni xx |limxx p p 1 1 359X 例：计算例：计算 的三种范数的三种范数 1,3, 5,1,2, T Xp 解：解： 1/2 222 2 13535X max 1,3,55X 常用向量范数：常用向量范数： 解线性方程组迭代法 向量序列向量序列 收敛于向量收敛于向量 是指对每一个是指对每一个 1 i n 都都 有有 。 定义定义 4-3 )(k x *x *)( lim i k i k xx 可以理解为可以理解为0|*| )( xx k 若存在常数若存在常数C 0 使得对任意使得对任意 有有 , 则则 称范数称范数 | |A 比范数比范数 |

4、|B 强。强。 定义定义 4-4 n Rx BA xCx| 若范数若范数 | |A 比比| |B 强，同时强，同时| |B 也比也比| |A 强，即存强，即存 在常数在常数 C1、C2 0 使得使得 ，则称，则称 | |A 和和 | |B 等价。等价。 定义定义 4-5 BAB xCxxC| 21 定理定理 Rn 上一切范数都等价。上一切范数都等价。 可以理解为对任何可以理解为对任何 向量范数都成立。向量范数都成立。 解线性方程组迭代法 定义定义 4-5 Rm n空间的矩阵范数空间的矩阵范数 | | 对任意对任意 满足：满足： nm RBA , 00|;0|)1( AAA（正定性（正定性) |

5、) 2(AA C 对任意对任意(齐次性齐次性) |) 3(BABA （三角不等式（三角不等式) (4)* | AB | | A | | B | （相容（相容 当当 m = n 时时) n j ij aA ni 1 |max| 1 （行和范数）（行和范数） n i ij aA nj 1 1 |max| 1 （列和范数）（列和范数） )(| max2 AAA T （谱范数（谱范数 ） 矩阵矩阵 ATA 的最大的最大 特征根特征根 常用矩阵范数：常用矩阵范数： 矩阵范数矩阵范数 解线性方程组迭代法 n i n j ijF aA 11 2 | 向量向量| |2的直接推广的直接推广 对方阵对方阵 以及以

6、及 有有 nn RA n Rx 22 |xAxA F 利用利用Cauchy 不等式不等式 可证。可证。 22 |yxyx 1 max13,279A 解：解： max12,3710A 13121019 27371953 T A A 例：计算例：计算 的三种范数的三种范数 12 37 A 12 ,AAA 2 60.19A 12 60.19,2.81 T A A的特征值 Frobenius 范数范数 解线性方程组迭代法 矩阵矩阵A的谱半径记为的谱半径记为 (A) = ，其中，其中 i 为为 A 的特征根。的特征根。 定义定义 4-9 |max 1 i ni Re Im (A) 定理定理 4-1 对任

7、意算子范数对任意算子范数 | | 有有|)(AA 证明：证明：由算子范数的相容性，得到由算子范数的相容性，得到 |xAxA 将任意一个特征根将任意一个特征根 所对应的特征向量所对应的特征向量 代入代入u |uAuA |uu 谱半径谱半径 解线性方程组迭代法 此时方程的解为：此时方程的解为： 12 10.75,2xx 2 线性方程组的误差分析线性方程组的误差分析 例：计算方程组例：计算方程组 的解为的解为 12 2,1xx 000001.59000001.3512 5935 12 21 21 xx xx 由于某种原因，第二个方程的系数有了一个小小的扰由于某种原因，第二个方程的系数有了一个小小的扰

8、 动（误差），变为：动（误差），变为： 000002.59999999.3412 5935 12 21 21 xx xx 解线性方程组迭代法 求解求解 时，时，A 和和 的误差对解的误差对解 有何影响？有何影响？bxA b x 设设 A 精确，精确， 有误差有误差 ，得到的解为，得到的解为 ，即，即b b xx bbxxA )( bAx 1 | 1 bAx 绝对误差放大因子绝对误差放大因子 |xAxAb 又又 | | | 1 b A x | | | | | 1 b b AA x x 相对误差放大因子相对误差放大因子 解线性方程组迭代法 设设 精确，精确，A有误差有误差 ，得到的解为，得到的解为

9、 ，即，即b A xx bxxAA )( bxxAxxA )()( )( 1 xxAAx | | | | | | 1 1 A A AA AA xx x bxAAxAA )()( xAxAA )( xAxAAIA )( 1 xAAAAIx 111 )( (只要只要 A充分小，使得充分小，使得 )1| 11 AAAA | | |1 | | | |1 | | | 1 1 1 1 A A AA A A AA AA AA x x 是关键是关键 的误差放大因子，称为的误差放大因子，称为 A的条件数，记为的条件数，记为cond (A) , 越越 则则 A 越病态，越病态， 难得准确解。难得准确解。 | 1

10、AA 大大 条件数条件数 AAAA AAI -1 1 -1 1 11 1 解线性方程组迭代法 注注: cond (A) 的具体大小与的具体大小与 | | 的取法有关，但相对的取法有关，但相对 大小一致。大小一致。 cond (A) 取决于取决于A，与解题方法无关。，与解题方法无关。 | | | | |)(1 )( | | b b A A AAAcond Acond x x 常用条件数有：常用条件数有： cond (A)1cond (A) cond (A)2)(/ )( minmax AAAA TT 特别地，若特别地，若 A 对称，则对称，则 |min |max )( 2 Acond 条件数的性

11、质：条件数的性质： A可逆，则可逆，则 cond (A)p 1； A可逆，可逆， R 则则 cond ( A) = cond (A) ； A正交，则正交，则 cond (A)2=1； A可逆，可逆，R正交，则正交，则 cond (RA)2 = cond (AR)2 = cond (A)2 。 解线性方程组迭代法 例：例：Hilbert 阵阵 12 1 1 11 3 1 2 1 1 2 1 1 nnn n n H cond (H2) = 27cond (H3) 748 cond (H6) = 2.9 106cond (Hn) as n 注：一般判断矩阵是否病态，并不计算注：一般判断矩阵是否病态，

12、并不计算A 1，而由经验得出。，而由经验得出。 行列式很大或很小（如某些行、列近似相关）；行列式很大或很小（如某些行、列近似相关）； 元素间相差大数量级，且无规则；元素间相差大数量级，且无规则； 主元消去过程中出现小主元；主元消去过程中出现小主元； 特征值相差大数量级。特征值相差大数量级。 解线性方程组迭代法 精确解为精确解为 . 1 1 x 例：例： 97.1 99.1 , 98.099.0 99.01 bA 计算计算cond (A)2 。 100009900 99009800 A 1 = 解：考察解：考察 A 的特征根的特征根 0)det(AI 000050504. 0 980050504

13、. 1 2 1 2 1 2 )( Acond 39206 1 测试病态程度：测试病态程度： 给一个扰动给一个扰动b 3 4 10106.0 1097.0 b ，其相对误差为，其相对误差为 %01.010513.0 | | 4 2 2 b b 此时精确解为此时精确解为 0203. 1 3 *x 0203.2 2 *xxx 2 2 | | x x 2.0102 200% 所以所以 A是坏条件的是坏条件的 解线性方程组迭代法 设设 的近似解为的近似解为 ，则一般有，则一般有bxA *x 0* xAbr | | | |*| b r x xx cond (A) 误差上限误差上限 改善方法：改善方法： S

14、tep 1:近似解近似解 bxA ; 1 x Step 2:; 11 xAbr Step 3:; 111 drdA Step 4:; 112 dxx 若若 可被精确解出，则有可被精确解出，则有 就是精确解了。就是精确解了。 1 d bAxAbAxx 1 1 1 12 )( 2 x 经验表明：若经验表明：若 A 不是非常病态（例如：不是非常病态（例如： ），）， 则如此迭代可达到机器精度；但若则如此迭代可达到机器精度；但若 A 病态，则此算法也病态，则此算法也 不能改进。不能改进。 1)( Acond 近似解的误差估计及改善：近似解的误差估计及改善： b A x 1 rAxx * 1 解线性方程

15、组迭代法 Jacobi 法法 nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa . . . . 2211 22222121 11212111 1112111 212222 124 n nn nnnnn aaabx aaabx aaabx 3 Jacobi法和法和 Gauss-Seidel法法 解线性方程组迭代法 0 ii a 121111111111 212222222222 1244 01 01 01 n n nnnnnnnnn aaaab axx aaaab axx aaaab axx 12111111111 21222222222 124 1 1 1 n n nn

16、nnnnnnn aaaab ax aaaabax aaaabax 121111111111 212222222222 1244 0 0 0 n n nnnnnnnnn aaaab axx aaaab axx aaaab axx 解线性方程组迭代法 写成矩阵形式：写成矩阵形式： A = L U D bxULxD bxULDbxA )( )( bDxULDx 11 )( Bf Jacobi 迭代阵迭代阵 bDxULDx kk 1)(1)1( )( 因此得到因此得到 nnnnn nn n nn nn bxaxa a x bxaxa a x bxaxa a x 1111 22121 22 2 1121

17、2 11 1 . 1 . . 1 . 1 雅可比迭代公式为：雅可比迭代公式为： 解线性方程组迭代法 123 123 123 25 58 1011 xxx xxx xxx 解：方程组的迭代格式为解：方程组的迭代格式为 123 13 12 1 1 2 1 3 0.50.52.5 0.20.21.6 0.10.11.1 kkk kkk kkk xxx xxx xxx 11 22 33 1 1 1 00.50.52.5 0.200.21.6 0.10.101.1 kk kk kk xx xx xx 或或 例：用雅可比方法解下列方程组例：用雅可比方法解下列方程组x(0)=(1,1,1)T 解线性方程组迭

18、代法 取初始值取初始值x(0)=(1,1,1)T，计算结果如下表，计算结果如下表 k 0111 1-1.51.60.92.5 2-1.252.081.090.48 3-0.9152.0681.0170.335 4-0.95751.98640.98470.0816 5-1.014451.988440.997110.05695 6-1.007222.002311.00260.01387 7-0.9975432.001971.000490.009687 2 k x 3 k x 1 k x 1kk xx 解线性方程组迭代法 )( 1 1 )( 1 )( 414 )( 313 )( 212 11 )1(

19、 1 bxaxaxaxa a x k nn kkkk )( 1 2 )( 2 )( 424 )( 323 )1( 121 22 )1( 2 bxaxaxaxa a x k nn kkkk )( 1 3 )( 3 )( 434 )1( 232 )1( 131 33 )1( 3 bxaxaxaxa a x k nn kkkk )( 1)1( 11 )1( 33 )1( 22 )1( 11 )1( n k nnn k n k n k n nn k n bxaxaxaxa a x 写成矩阵形式：写成矩阵形式： bDxUxLDx kkk 1)()1(1)1( )( bxUxLD kk )()1( )(

20、bLDxULDx kk 1)(1)1( )()( Bf Gauss - Seidel 迭代法迭代法 解线性方程组迭代法 123 123 123 25 58 1011 xxx xxx xxx 解：方程组的迭代格式为解：方程组的迭代格式为 123 13 12 1 11 2 111 3 0.50.52.5 0.20.21.6 0.10.11.1 kkk kkk kkk xxx xxx xxx 例：用高斯例：用高斯-赛德尔法解下列方程组赛德尔法解下列方程组 解线性方程组迭代法 取初始值取初始值x(0)=(1, 1, 1)T，计算结果如下表，计算结果如下表 kx1x2x3|x(k)-x(k+1)| 01

21、11 1-1.52.11.042.5 2-0.931.9940.99360.57 3-1.00621.999961.0006240.0762 4-0.9997082.00006640.999964160.006492 解线性方程组迭代法 取初始值取初始值x(0)=(0, 0, 0)T，计算结果如下表，计算结果如下表 k 0000 1-2.52.11.142.5 2-0.882.0040.98741.62 3-1.00421-99841.00061.1242 4-1.00052.00021.00000.0037 2 k x 3 k x 1 k x 1kk xx 解线性方程组迭代法 的收敛条件的收

22、敛条件fxBx kk )()1( * )1()1( xxe kk )()()( *)()*()( kkk eBxxBfxBfxB )0()( eBe kk |.| ) 0() 1()( eBeBe kkk 充分条件充分条件: |B| 1 kB k as0| 0| )( k e 必要条件必要条件: kk Bke as0 )( ？ 定义定义 4-10 设设：.)(,)( )(nn nn k ijknnij RaAaA AAk k lim 是指是指ij k ij k aa )( lim 对所有对所有 1 i, j n 成立成立 等价于对等价于对 任何算子范数有任何算子范数有 kAA k as0| 4

23、 迭代法的收敛性迭代法的收敛性 解线性方程组迭代法 0|xB k 对对任意非零向量任意非零向量 成立成立x 定理定理 4-10 设设 fxBx 存在唯一解，则从任意存在唯一解，则从任意 出发，出发， )0( x 迭代迭代fxBx kk )()1( 收敛收敛0 k B 证明证明:Bk 0| Bk | 0 0 | | max 0 x xB k x “”：对任意非零向量：对任意非零向量 有有x 0| | | k k B x xB “”：取：取 则则 Ti x)0.1.0( )( 第第 i 位位 0 )( k ij b 0 xB k 对对任意非零向量任意非零向量 成立成立x 从任意从任意 出发，出发，

24、 记记 ，则，则 )0( x * )0()0( xxe 0 )0()( eBe kk as k )( k x 收敛收敛 P62 定义4-8 定理定理 4-11 Bk 0 0 B 1 1 解线性方程组迭代法 （充分条件）若存在一个矩阵范数使得（充分条件）若存在一个矩阵范数使得 | B | = q 1, 则则迭代收敛，且有下列误差估计：迭代收敛，且有下列误差估计： 定理定理 4-13 | 1 |*| )1()()( kkk xx q q xx | 1 |*| )0()1()( xx q q xx k k 证明证明: )*( )*(* )1()()( )1()( kkk kk xxxxB xxBxx

25、 |)|*(|*| )1()()()( kkkk xxxxqxx )(.)( )0()1(1)2()1()1()( xxBxxBxx kkkkk | )0()1(1)1()( xxqxx kkk 解线性方程组迭代法 若事先给定误差控制精度若事先给定误差控制精度 ，可得迭代次数的估计，可得迭代次数的估计 10 1B ln xx k ln B | 1 |*| )0() 1 ()( xx q q xx k k 解线性方程组迭代法 123 123 123 202324 812 231530 xxx xxx xxx 解：方程组的迭代格式为解：方程组的迭代格式为 11 22 33 1 1 1 02/203

26、/2024/20 1/801/812/8 2/153/15030/15 kk kk kk xx xx xx 取取 ，问雅可比迭代法是否收敛？若收敛，问雅可比迭代法是否收敛？若收敛， 需要迭代多少次，才能保证各分量的误差绝对值小于需要迭代多少次，才能保证各分量的误差绝对值小于 1010-6 -6？ ？ T 0 0,0,0 x 例：用雅可比方法解下列方程组例：用雅可比方法解下列方程组 解线性方程组迭代法 02/203/20 B1/801/8 2/153/150 迭代阵迭代阵 111 123 10 6 B1/31, 6/5,3/2,2, 2, 101 1/2 ln 2 13 ln1/3 xxx xx k 所以迭代法收敛。 经第一次迭代得： 则 所以要保证各分量的误差绝对值小于所以要保证各分量的误差绝对值小于1010-6 -6，需要迭代 ，需要迭代1414次次 解线性方程