数值分析2.3迭代法的收敛性

1、一、矩阵的谱半径一、矩阵的谱半径 第第2 2章章 线性方程组的数值解法线性方程组的数值解法 迭代法的收敛性迭代法的收敛性 二、迭代法的收敛条件二、迭代法的收敛条件三、举例三、举例复习：复习：1、矩阵的特征值与特征向量的定义与计算；、矩阵的特征值与特征向量的定义与计算；设设A为方阵，为方阵，Au = u (u 0)即即是方程是方程 |E - A| = 0的根的根2、矩阵的特征值与特征向量的性质、矩阵的特征值与特征向量的性质nA.)det(213、Ak = AAA的特征值是的特征值是knkk ,.,21一、迭代法的谱半径一、迭代法的谱半径fBxxkk )()1(称迭代公式称迭代公式中的矩阵中的矩阵

2、 B 为为迭代矩阵迭代矩阵.定义定义1：定义定义2：设设A为为n阶方阵，阶方阵，i (i = 1,n)为为A的的特征值，称特征值模的最大值为矩特征值，称特征值模的最大值为矩阵阵A的谱半径，记为的谱半径，记为|max)(1iniA ,.,21n 称为矩阵称为矩阵A的谱的谱.若矩阵若矩阵A的谱为的谱为 ,.,21n 谱半径为谱半径为|max)(1iniA 则则 Ak = AAAk个个的谱为的谱为,.,21knkk ( k = 1, 2, )谱半径为谱半径为kkinikAA)(|max)(1 定理：定理：设设A为任意为任意n阶方阵，阶方阵，|.|为任意由向量为任意由向量 范数诱导出的矩阵的范数，则范

3、数诱导出的矩阵的范数，则|)(AA 证明：证明：对对A的任一特征值的任一特征值i 及相应的特征向量及相应的特征向量ui，都有，都有|iiiAuu |iiu |iuA 因为因为ui为非零向量，即为非零向量，即|ui|0，于是有，于是有|Ai 由由i 的任意性得的任意性得|)(AA 定理：定理：设设A为为n阶方阵，则对任意正数阶方阵，则对任意正数，存在，存在 一种矩阵范数一种矩阵范数|.|，使得，使得 )(|AA（证明省略）（证明省略）注：注：对对n阶方阵，一般不存在矩阵范数阶方阵，一般不存在矩阵范数|.|，使得，使得|)(AA 但若但若A为对称矩阵，则有为对称矩阵，则有2|)(AA 下面的定理对

4、建立迭代法的收敛条件十分重要下面的定理对建立迭代法的收敛条件十分重要.定理：定理：设设A为为n阶方阵，则阶方阵，则0lim kkA的充要条件为的充要条件为1)( A 证明：证明：必要性必要性: 若若0lim kkA则则0|limkkA而而|)()(0kkkAAA 于是由极限存在准则，有于是由极限存在准则，有0)(lim kkA 故故1)( A 充分性充分性: 若若, 1)( A 取取02)(1 A 则存在一种矩阵范数则存在一种矩阵范数|.|，使得，使得12)(1)(| AAA 而而kkAA| 于是于是0|lim|lim kkkkAA所以所以0lim kkA二、迭代法的收敛条件二、迭代法的收敛条

5、件定理：定理：对任意初始向量对任意初始向量 x(0)和右端项和右端项g，由迭代，由迭代 格式格式 x(k+1) = Mx(k) + g 产生的向量序列收敛的充要条件为产生的向量序列收敛的充要条件为 1)( M 证明：证明：必要性必要性 xxkk)(limgMxx gMxgMxxxkk )1()()()1( xxMk)()2(2 xxMk)()0( xxMk0)(lim)(lim)()0( xxxxMkkkk0lim kkM, 1)( M , 1)( M |I|0gMxx 0lim kkM)()()0()1()( xxMxxMxxkkk0)(lim)(lim)0()( xxMxxkkkk推论推论

6、1：证明证明:n ,.,21nnMM)(|.| )det(|21 1| )det(| M|)1( |)( | )det(|1UDLDM nnaaaLD.1|)( |22111 nnnaaaUD.)1(|)1( |2211 1|)1( | )det(| nM 20 举例：解方程组举例：解方程组 3222122321321321xxxxxxxxx讨论讨论Jacobi法与法与Gauss-Seidel法的收敛性。法的收敛性。解：解：由定理，迭代法是否收敛等价于迭代矩阵由定理，迭代法是否收敛等价于迭代矩阵的谱半径是否，故应先求迭代矩阵。而的谱半径是否，故应先求迭代矩阵。而 122111221A 1221

7、11221A 111D 022001000L 000100220UJacobi迭代法的迭代矩阵为迭代法的迭代矩阵为 0221012201ADIB0221122|3 BI, 10)( B 122011001LD可得可得 120011001)(1LD 200320220)(1ULDM0)2(20032022|3 MI, 12)( B |M|1迭代法收敛迭代法收敛松弛法收敛松弛法收敛021)( M 迭代法收敛迭代法收敛()*(1)()()*()*()(1)1kkkkkkkxxBxxBxxBxxxxB 从从而而( )(1)*( )*( )(1)( )*(1)(0)1,.11kkkkkkkxBxgBBx

8、BxxxxBBxxxxB 如如果果迭迭代代格格式式的的迭迭代代矩矩阵阵 满满足足则则迭迭代代格格式式产产生生的的序序列列收收敛敛到到方方程程组组的的精精确确解解, , 并并且且有有如如下下的的误误差差估估定定理理( (误误差差估估式式计计) )计计*( )(1)( )*(1)*(1)( )( )*:()()()kkkkkkkxBxgxBxgxxB xxB xxB xx 证证明明 由由和和有有:(1),.(2)1,.BB注注越越小小 收收敛敛越越快快接接近近 时时 收收敛敛慢慢( )(1)(1)(2)1(1)(2)(1)(0)()()()kkkkkkkxxB xxBxxBxx ( )*( )(1

9、)(1)(0)11kkkkBBxxxxxxBB ( )(1)(1)(2)( )(1)(1)(2)()kkkkkkkkxBxgxBxgxxB xx 又又因因为为，( )*(1)(0)1kkBxxxxB 由由误误差差估估计计式式估估计计迭迭代代次次数数( )*(1)(1)(0)(0)1ln()l1nkkBxxxxxkBBxB (3)(3)估估计计迭迭代代次次数数),.,2 , 1(|1niaanijjijii 51121012110A 210121012B 若若A为严格对角占优阵为严格对角占优阵，则则Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛。迭代法均收敛。归纳判断迭代法收敛

10、的方法如下：归纳判断迭代法收敛的方法如下：3. 只好根据迭代矩阵的谱半径判断只好根据迭代矩阵的谱半径判断.例例1：设有方程组：设有方程组Ax=b，其中，其中 111212121212121A讨论用三种迭代法求解的收敛性。讨论用三种迭代法求解的收敛性。Gauss-Seidel法与松弛法法与松弛法(02)均收敛。均收敛。又因为又因为Jacobi迭代法的迭代矩阵为迭代法的迭代矩阵为 000212121212121B故故|B|1=|B|=1，因，因此不能用范数判断。此不能用范数判断。下面计算迭代矩阵的谱半径。下面计算迭代矩阵的谱半径。0)1()(|221212121212121 BI1)( B 故故J

11、acobi迭代法不收敛。迭代法不收敛。例例2：设方程组：设方程组Ax=b的系数矩阵为的系数矩阵为 49103A则则Jacobi法与法与Gauss-Seidel法的迭代矩法的迭代矩阵分别是阵分别是 04/93/100B 2/1503/100M其谱半径分别为其谱半径分别为215)(,230)( MB 故这两种迭代法均不收敛。故这两种迭代法均不收敛。但若交换两个方程的次序，得原方程组的同但若交换两个方程的次序，得原方程组的同解方程组解方程组 10349,AbxA其其中中显然显然A是严格对角占优阵，因此对方程组是严格对角占优阵，因此对方程组bxA 用用Jacobi法和法和Gauss-Seidel法均收

12、敛。法均收敛。例例3：设：设A=(aij)是二阶方阵，且是二阶方阵，且a11a220.试证试证 求解方程组求解方程组Ax=b的的Jacobi法与法与Gauss-Seidel法法同时收敛或发散。同时收敛或发散。 0022211112aaaaBJ22112112)(aaaaBJ 而而Gauss-Seidel法的迭代矩阵为法的迭代矩阵为 22112112111200aaaaaaBSG其谱半径为其谱半径为22112112)(aaaaBSG 则有则有2)()(JSGBB 显然显然)()(SGJBB 与与同时小于同时小于1、等于、等于1或大于或大于1，因此有相同的敛散性。，因此有相同的敛散性。例例4：设线性方程组：设