数值分析迭代法的收敛性学习教案

1、数值数值(shz)分析迭代法的收敛性分析迭代法的收敛性第一页，共31页。一、迭代法的谱半径一、迭代法的谱半径(bnjng)fBxxkk )()1(称迭代称迭代(di di)公式公式中的矩阵中的矩阵(j zhn) B 为迭代矩阵为迭代矩阵(j zhn).定义定义1：定义定义2：设设A为为n阶方阵，阶方阵，i (i = 1,n)为为A的特的特征值，称特征值模的最大值为矩阵征值，称特征值模的最大值为矩阵A的的谱半径，记为谱半径，记为|max)(1iniA ,.,21n 称为矩阵称为矩阵A的谱的谱.第1页/共31页第二页，共31页。若矩阵若矩阵(j zhn)A的谱为的谱为 ,.,21n 谱半径谱半径(

2、bnjng)为为|max)(1iniA 则则 Ak = AAAk个个的谱为的谱为,.,21knkk ( k = 1, 2, )谱半径为谱半径为kkinikAA)(|max)(1 第2页/共31页第三页，共31页。定理：设A为任意n阶方阵，|.|为任意由向量 范数诱导(yudo)出的矩阵的范数，则|)(AA 证明(zhngmng)：对对A的任一特征值的任一特征值i 及相应及相应(xingyng)的特征向量的特征向量ui，都有，都有|iiiAuu |iiu |iuA 因为因为ui为非零向量，即为非零向量，即|ui|0，于是有，于是有|Ai 由由i 的任意性得的任意性得|)(AA 第3页/共31页第

3、四页，共31页。定理(dngl)：设A为n阶方阵，则对任意正数，存在 一种矩阵范数|.|，使得 )(|AA（证明（证明(zhngmng)省略）省略）注：对n阶方阵，一般不存在(cnzi)矩阵范数|.|，使得|)(AA 但若但若A为对称矩阵，则有为对称矩阵，则有2|)(AA 第4页/共31页第五页，共31页。下面的定理对建立迭代法的收敛条件十分下面的定理对建立迭代法的收敛条件十分(shfn)重重要要.定理定理(dngl)：设：设A为为n阶方阵，则阶方阵，则0lim kkA的充要条件为的充要条件为1)( A 证明证明(zhngmng)：必要性必要性: 若若0lim kkA则则0|limkkA而而|

4、)()(0kkkAAA 于是由极限存在准则，有于是由极限存在准则，有0)(lim kkA 故故1)( A 第5页/共31页第六页，共31页。充分性充分性: 若若, 1)( A 取取02)(1 A 则存在则存在(cnzi)一种矩阵范数一种矩阵范数|.|，使得，使得12)(1)(| AAA 而而kkAA| 于是于是(ysh)0|lim|lim kkkkAA所以所以(suy)0lim kkA第6页/共31页第七页，共31页。二、迭代法的收敛二、迭代法的收敛(shulin)条件条件定理：对任意初始向量定理：对任意初始向量 x(0)和右端项和右端项g，由迭，由迭代代 格式格式 x(k+1) = Mx(k

5、) + g 产生产生(chnshng)的向量序列收敛的充的向量序列收敛的充要条件为要条件为 1)( M 第7页/共31页第八页，共31页。证明证明(zhngmng)：必要性必要性 xxkk)(limgMxx gMxgMxxxkk )1()()()1( xxMk)()2(2 xxMk)()0( xxMk0)(lim)(lim)()0( xxxxMkkkk0lim kkM, 1)( M 第8页/共31页第九页，共31页。, 1)( M |I|0gMxx 0lim kkM第9页/共31页第十页，共31页。)()()0()1()( xxMxxMxxkkk0)(lim)(lim)0()( xxMxxkk

6、kk推论1：第10页/共31页第十一页，共31页。证明证明(zhngmng):n ,.,21nnMM)(|.| )det(|21 1| )det(| M|)1( |)( | )det(|1UDLDM nnaaaLD.1|)( |22111 nnnaaaUD.)1(|)1( |2211 第11页/共31页第十二页，共31页。1|)1( | )det(| nM 20 第12页/共31页第十三页，共31页。举例举例(j l)：解方程组：解方程组 3222122321321321xxxxxxxxx讨论讨论(toln)Jacobi法与法与Gauss-Seidel法的收法的收敛性。敛性。解：由定理，迭代法

7、是否收敛解：由定理，迭代法是否收敛(shulin)等价于迭代等价于迭代矩阵的谱半径是否，故应先求迭代矩阵。而矩阵的谱半径是否，故应先求迭代矩阵。而 122111221A第13页/共31页第十四页，共31页。 122111221A 111D 022001000L 000100220UJacobi迭代迭代(di di)法的迭代法的迭代(di di)矩阵为矩阵为 0221012201ADIB0221122|3 BI, 10)( B 第14页/共31页第十五页，共31页。 122011001LD可得可得 120011001)(1LD 200320220)(1ULDM0)2(20032022|3 MI第

8、15页/共31页第十六页，共31页。, 12)( B 第16页/共31页第十七页，共31页。|M|1迭代法收敛迭代法收敛(shulin)松弛法收敛松弛法收敛(shulin)021)( M 迭代法收敛迭代法收敛第17页/共31页第十八页，共31页。()*(1)()()*()*()(1)1kkkkkkkxxBxxBxxBxxxxB 从从而而( )(1)*( )*( )(1)( )*(1)(0)1,.11kkkkkkkxBxgBBxBxxxxBBxxxxB 如如果果迭迭代代格格式式的的迭迭代代矩矩阵阵 满满足足则则迭迭代代格格式式产产生生的的序序列列收收敛敛到到方方程程组组的的精精确确解解, , 并

9、并且且有有如如下下的的误误差差估估定定理理( (误误差差估估式式计计) )计计*( )(1)( )*(1)*(1)( )( )*:()()()kkkkkkkxBxgxBxgxxB xxB xxB xx 证证明明 由由和和有有第18页/共31页第十九页，共31页。:(1),.(2)1,.BB注注越越小小 收收敛敛越越快快接接近近 时时 收收敛敛慢慢( )(1)(1)(2)1(1)(2)(1)(0)()()()kkkkkkkxxB xxBxxBxx ( )*( )(1)(1)(0)11kkkkBBxxxxxxBB ( )(1)(1)(2)( )(1)(1)(2)()kkkkkkkkxBxgxBxg

10、xxB xx又又因因为为，第19页/共31页第二十页，共31页。( )*(1)(0)1kkBxxxxB 由由误误差差估估计计式式估估计计迭迭代代次次数数( )*(1)(1)(0)(0)1ln()l1nkkBxxxxxkBBxB (3)(3)估估计计迭迭代代次次数数第20页/共31页第二十一页，共31页。),.,2 , 1(|1niaanijjijii第21页/共31页第二十二页，共31页。 51121012110A 210121012B第22页/共31页第二十三页，共31页。第23页/共31页第二十四页，共31页。归纳判断迭代法收敛(shulin)的方法如下：3. 只好根据迭代矩阵的谱半径判断

11、只好根据迭代矩阵的谱半径判断.第24页/共31页第二十五页，共31页。例例1：设有方程组：设有方程组Ax=b，其中，其中(qzhng) 111212121212121A讨论用三种讨论用三种(sn zhn)迭代法求解的迭代法求解的收敛性。收敛性。第25页/共31页第二十六页，共31页。Gauss-Seidel法与松弛法法与松弛法(02)均收敛均收敛(shulin)。又因为又因为Jacobi迭代迭代(di di)法的迭代法的迭代(di di)矩阵为矩阵为 000212121212121B故故|B|1=|B|=1，因，因此不能用范数判断。此不能用范数判断。第26页/共31页第二十七页，共31页。下面

12、下面(xi mian)计算迭代矩阵的谱半径。计算迭代矩阵的谱半径。0)1()(|221212121212121 BI1)( B 故故Jacobi迭代法不收敛迭代法不收敛(shulin)。第27页/共31页第二十八页，共31页。例例2：设方程组：设方程组Ax=b的系数的系数(xsh)矩阵为矩阵为 49103A则则Jacobi法与法与Gauss-Seidel法的迭代矩阵法的迭代矩阵(j zhn)分别是分别是 04/93/100B 2/1503/100M其谱半径分别为其谱半径分别为第28页/共31页第二十九页，共31页。215)(,230)( MB 故这两种迭代法均不收敛故这两种迭代法均不收敛(shulin)。但若交换但若交换(jiohun)两个方程的次序，得原方程组两个方程的次序，得原方程组的同解方程组的同解方程组 10349,AbxA其中其中显然显然A是严格对角是严格对角(du jio)占优阵，因此对方程组占优阵，因此对方程组bxA 用用Jacobi法和法和Gau