数值计算方法第讲迭代法的收敛性和稳定性

1、插 值 法主讲教师：刘春凤8/eol/jpk/course/welcome.jsp?courseId=1220线性方程组的迭代解法主讲教师：龚佃选第第 六章六章一阶定常迭代法的基本定理关于解某些特殊方程组迭代法的收敛性迭代法的收敛性与稳定性 一阶定常迭代法的基本定理常用结论 设 为 阶方阵的特征值， 的谱半径定义为： (1,2, )iin n1( )maxii nA AA的谱定义为：12.n， ，kkAA)()( AA )( xxAxAxkk iiiiiiuuAuAu 事实上：对 的 及特征向量Ai iuAi 1( )maxii nAA i 由 的任意性：1

2、( )max.ii nAA 当 对称时，A2( ).AA 矩阵的谱半径由 的任意性i 迭代法的收敛性与稳定性 一阶定常迭代法的基本定理.fBxxbAx 设线性方程组,(3.1)Axb 其中 为非奇异矩阵，记 为()n nijAaR *x(3.1)精确解，且设有等价的方程组于是(3.2)xBxf )3 . 3(.)()1(fBxxkk 设有解 的一阶定常迭代法Axb 迭代法的收敛性与稳定性 一阶定常迭代法的基本定理有意义的问题是：迭代矩阵 满足什么条件时，由迭代法产生的向量序列 收敛到 .B( )kx*x误差向量的递推公式误差向量的递推公式)., 2 , 1 , 0(,)0()()()1( kB

3、Bkkkk )., 2 , 1 , 0()()( kxxkk 引进误差向量由(3.3)式减(3.2)得到 研究迭代法(3.3)收敛性问题就是要研究迭代矩阵 满足什么条件时，有B).)(0 kBk零零矩矩阵阵迭代法的收敛性与稳定性 一阶定常迭代法的基本定理定 义设有矩阵序列 及 ，如果( )()kn nkijAaR ()n nkijAaR 2n个数列极限存在且有( )lim( ,1,2, )kijijkaai jn ，则 称收敛于kAAlim().k 记为其中|为矩阵的任意一种, 0limlim AAAAkkkk算子范数.limnkkAAxR 都有lim.kkA xAx 定理定理1定理定理2迭代

4、法的收敛性与稳定性 一阶定常迭代法的基本定理例例 3设有矩阵序列 ，其中 而kAkkAB ,0,02,011222 kkkkkBBB 且设 ，考查矩阵序列极限.1 显然, 当 时, 则有1 .0000limlim kkkkBA迭代法的收敛性与稳定性 一阶定常迭代法的基本定理设 ，则 （零矩阵）的充要条件： ()ijn nAa lim0kkA 1.A 必要性0lim0lim kkkkAAkkkAAA )()(0 lim ( )0kkA ( )1A 充分性若 ，则对( )1A 1( )12A 必存在一种范数 ，使得.12)(1)( AAA 0lim kkAkkAA 而limlim0kkkkAA ，

5、于是lim0kkA 定理定理3即迭代法的收敛性与稳定性 一阶定常迭代法的基本定理迭代法基本原理设有方程组 及一阶定常迭代法xBxf(1)( )kkxBxf )1.B （对任意选取初始向量 ，迭代法收敛的充要条件是(0)x定理定理40.)0()1()( kkkkBBxx）（xxkk )(lim0lim kk 0lim kkB1)( B )()0()0(xx 迭代法的收敛性与稳定性 一阶定常迭代法的基本定理 定理3和定理4的结论和起来即为(1)迭代法 收敛(1)( )kkxBxf lim0kB(2)迭代法 收敛(1)( )kkxBxf ( )1.B 推论推论设 ，其中 为非奇异矩阵且 为非奇异矩阵

6、Axb ADLUD则有 (1) Jacobi迭代法收敛 ，其中( )1J 1().JDLU (2) G-S迭代法收敛 ，其中( )1G 1().GDLU (3) SOR迭代法收敛 ，其中()1L 1() (1).LDLDU 迭代法的收敛性与稳定性 一阶定常迭代法的基本定理例例 4考察用Jacobi方法解方程组 的收敛性.12312312383220,41133,631236.xxxxxxxxx 因为方程组的矩阵 及迭代矩阵 为AJ.012/312/611/1011/48/28/30)(,123611142381 ULDJA得迭代矩阵 的特征方程为J, 0039772727. 003409090

7、9. 0)det(317638833 JI解得,3445. 01841. 0,3445. 01841. 0,3082. 0321ii 迭代法的收敛性与稳定性 一阶定常迭代法的基本定理例例 4考察用Jacobi方法解方程组 的收敛性.12312312383220,41133,631236.xxxxxxxxx . 13592. 0, 13082. 0321 解得,3445. 01841. 0,3445. 01841. 0,3082. 0321ii 即 所以用Jacobi方法解方程组是收敛的.( )1J 迭代法的收敛性与稳定性 一阶定常迭代法的基本定理例例 5考察用迭代法解方程组的收敛性. 其中.5

8、5,0320,)()1( fBfBxxkk方程组的迭代矩阵B的特征方程为22det()63IB 这说明用迭代法解此方程组不收敛. 矩阵B的特征值为 ，即1,26 ( )1.B 迭代法的基本定理在理论上是重要的，根据谱半径的性质 ，下面利用矩阵 的范数建立判别迭代法收敛的充分条件.( )BB B迭代法的收敛性与稳定性 一阶定常迭代法的基本定理(迭代法收敛的充分条件) 定理定理5及一阶定常迭代法设有方程组,()n nijxBxf BbR (1)( )kkxBxf 如果有 的某种算子范数 ，则B1Bq 迭代法收敛，即对任取 有(0)x.xBxf ( )limkkxx 且.)2()0()(xxqxxk

9、k .1)3()1()()( kkkxxqqxx.1)4()0()1()(xxqqxxkk (1)迭代法的收敛性与稳定性 一阶定常迭代法的基本定理(1) 由基本定理4结论(1)是显然的.(2) 显然有关系式 及反复利用(b)即得(2). *(1)*( )()kkxxB xx (1)( )( )(1)()kkkkxxB xx于是有(1)( )( )(1)( )kkkkaxxq xx*(1)*( )( )kkbxxq xx (3) 考查(1)( )*( )*(1)()kkkkxxxxxx*( )*(1)kkxxxx *( )(1)kqxx即得 .111)1()()()1()( kkkkkxxqqx

10、xqxx迭代法的收敛性与稳定性 一阶定常迭代法的基本定理 (4) 利用(3)的结果反复利用(a)，则得到(4). 即 .11)0()1()1()()(xxqqxxqqxxkkkk 迭代法的收敛性与稳定性 关于解某些特殊方程组迭代法的收敛性 在科学及工程计算中，要求解方程组 ，其矩阵 常常具有某些特性. 例如， 具有对角占优性质或 为不可约阵，或 是对称正定阵，下面讨论用基本迭代法解这些方程组的收敛性.Axb AAAA定 义(1) 如果A的元素满足)., 2 , 1(1niaanijjijii 称A为严格(按行)对角占优阵.对角占优阵设()ijn nAa (2) 如果A的元素满足)., 2 ,

11、1(1niaanijjijii 且上式至少有一个不等式成立，称A为弱(按行)对角占优阵.迭代法的收敛性与稳定性 关于解某些特殊方程组迭代法的收敛性定 义可约与不可约矩阵可约与不可约矩阵设(),2ijn nAan ，如果存在置换阵P使1112220TAAP APA 其中 为 阶方阵， 为 阶方阵 ，则称 为可约矩阵. 否则，如果不存在这样置换阵 使上式成立，则称 为不可约矩阵.11Ar22Anr (1)rnAPA 为可约矩阵意即 可经过若干行列重排化为上式或 可化为两个低阶方程组求解(如果 经过两行交换的同时进行相应两列的交换，称对 进行一次行列重排).AAAxb AA迭代法的收敛性与稳定性 关

12、于解某些特殊方程组迭代法的收敛性 2121,ddbPdyyxPyTT 事实上，由 可化为Axb ()TTTP AP P xP b ，且记其中,iiyd为 维向量。r于是，求解 化为求解Axb .,22221212111dyAdyAyA由上式第2个方程组求出 ,再代入第1个方程组求出 .2y1y 显然，如果 所有元素都非零，则 为不可约阵.AA (对角占优定理) 如果A=(aij)nn为严格对角占优矩阵或A为不可约弱对角占优矩阵，则A为非奇异矩阵.迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性定理定理6 6111|,nnnkkkkjjkjjkkjjjjj kj kj ka xa xax

13、xa只就A为严格对角占优矩阵证明此定理. 采用反证法，如果det(A)=0，则Ax=0有非零解，记为 ，则12(,)Tnxxxx 1max0kix nxx 由齐次方程组第k个方程, 01 njjijxa则有即,1 nkjjkjkkaa这与假设矛盾，故det(A)0.迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性设方程组Ax=b，如果(1) A为严格对角占优阵，则解Ax=b的Jacobi迭代法, Gauss-Seidel 迭代法均收敛.(2) A为弱对角占优阵，且A为不可约矩阵, 则解Ax=b的Jacobi迭代法, Gauss-Seidel 迭代法均收敛.定理定理7 7只证(1)，(2

14、)作为练习因为A是严格对角占优阵，所以0(1, )iiainJacobi迭代阵)(1ULDJ 0002122222211111112nnnnnnnnaaaaaaaaaaaa则|J| 1，所以 Jacobi 迭代法收敛.迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性)(det)det(1ULDIGI . 0)(det)det(1 ULDLD )(. 0)(det ULD 下面证明GaussSeidel 迭代法收敛.下面证明|1. 若不然, 即|1, 则. ),2, 1(|111 ijnijijijijijiiniaaaa 由于. 0)det(1 LD所以由 ，得1()GD L U 迭代

15、法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性. ), 2 , 1(|111 ijnijijijijijiiniaaaa 即矩阵 ULD)( 是严格对角占优矩阵，故可逆，这与(*) 式矛盾，所以|1, 从而 (G)1，即GaussSeidel迭代法收敛.212222111211 nnnnnnaaaaaaaaa 迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性若A为正定矩阵，则方程组 Ax=b的Gauss-Seidel 迭代法收敛. .),(),(),(yLyyDyyyLT 则内积从而 因为A正定，所以D正定，故定理定理1(),()TTD LL yyL yD L y (, )()

16、, )TL y yDL y y 因为 ，设为G 的特征值，y为对应的特征(复)向量，即1,()TTA D L L GD L L (, )0Dy y 迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性).(),(),(),(ibayLyLyyyyLT 所以|1, 从而(G)1, 故Gauss-Seidel迭代法收敛.1)(|22222 baba .)(),(),(),(ibaibayLyyDyyyLT 下面研究对于解方程组Ax=b的SOR方法中松弛因子在什么范围内取值，SOR方法才可能收敛. 令 ，则由复向量内积的性质有(, )Ly yaib迭代法的收敛性与稳定性关于解某些特殊方程组迭代法

17、的收敛性(SOR方法收敛的必要条件) 设解方程组 Ax=b的SOR迭代法收敛，则02.定理定理8 8 由于SOR迭代法收敛，则 设迭代矩阵L的特征值为i (i=1,n)，则有1,() (1)A D L U LDLDU ()1L 12det() | ()1nnLB . 1)1()1()()1det()det()det(1111 nniiiniiiaaUDLDL 于是所以|1-|1，即 02.迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性定理8说明解Ax=b的SOR迭代法，只有在(0, 2)范围内取松弛因子，才可能收敛.(SOR方法收敛的充分条件) 设有方程组 Ax=b，如果：(2) 0

18、2.则解方程组 Ax=b的SOR迭代法收敛. 在上述假定下，设迭代矩阵L的任一特征值为，只要证明|1即可. 定理定理9 9(1) A为对称正定矩阵， ;TA D L L 事实上，设y为对应的L的特征向量，即, 0),(,21 TnyyyyyyL ,)1()(1yyLDLDT 亦即.)()1(yLDyLDT 有内积),)(),)1(yyLDyyLDT 则,),(),(),(),(),(yLyyDyyyLyDyyDyT 因为A正定，所以D正定，记).(),(),(),(ibayLyLyyyyLT 迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性(, )0Dy y 令 ，则由复向量内积的性质

19、有(, )Ly ya ib 0(, )() , )2 ,TAy yDLL y ya .)()(biabia (,)(,)(,)(,)(,)TDy yDy yL y yDy yLy y .)()(2222222baba 当02时，有(分子减分母). 0)2)(2()()(22 aaa即L的任一特征值满足|1, 故SOR迭代法收敛.迭代法的收敛性与稳定性关于解某些特殊方程组迭代法的收敛性因为及一阶定常迭代法迭代法的收敛性与稳定性迭代法的收敛速度()lim,.kkxxxBxf 则且设迭代法收敛，即对任取 ，记0 x由定理3证明中可知，如果 且 越小时，迭代法收敛越快. 现设有方程组( )1B ( )

20、B 由基本定理有 ，且误差向量 满足0( )1B ( )( )*kkxx ( )(0)kkB (1)( )(0,1,)kkxBxfk ,()n nijxBxfBbR 迭代法的收敛性与稳定性迭代法的收敛速度故()( 0 ).kkB 现设B为对称矩阵，则有()( 0 )( 0 )2222().kkkBB 下面确定使初始误差缩小 所需的迭代次数, 即使10s .10)(skB 取对数，得到所需最少迭代次数为.)(ln10lnBsk 此式说明，满足精度所需迭代次数与 成反比，当 越小， 越大，则满足所需迭代次数越少，即迭代法收敛越快. ( )1B ln( )RB ln( )RB 迭代法的收敛性与稳定性

21、迭代法的收敛速度 称 为迭代法 的渐近收敛速度，简称迭代法收敛速度.定义定义 5ln( )RB (1)( )(0,1,)kkxBxfk 对于SOR迭代法希望选择松弛因子 使迭代过程收敛较快，在理论上即确定最佳因子opt使).()(min20optLL 对某些特殊类型的矩阵，建立了SOR方法最佳因子理论. 例如，对所谓具有“性质A”等条件的线性方程组建立了最佳松弛因子公式.)(1122Jopt 其中 为解 的Jacobi迭代法的迭代矩阵的谱半径.( )J Axb 迭代法的收敛性与稳定性迭代法的收敛速度 若Jacobi 迭代矩阵J 为非负矩阵，则下列关系有一个且仅有一个成立： (1) (J)= (G)=0； (2) 0 (G) (J)1；(3) (J)= (G)=1； (4) 1 (J) (G).说明：当Jacobi 迭代矩阵J为非负矩阵时, Jacobi方法和 GaussSeidel 方法同时收敛或同时发散, 若为同时收敛, 则后者比前者收敛快.迭代法的收敛性与稳定性迭代法的收敛速度已知方程组.9.08.07.015.005.015.005.01321 xxx判断雅可比迭代法