數(shù)值分析2.3迭代法的收斂性

一、矩陣的譜半徑

第2章線性方程組的數(shù)值解法

§迭代法的收斂性

二、迭代法的收斂條件三、舉例復(fù)習(xí)：1、矩陣的特征值與特征向量的定義與計(jì)算；設(shè)A為方陣，Au=λu(u≠0)即λ是方程|λE-A|=0的根2、矩陣的特征值與特征向量的性質(zhì)3、Ak=AA…A的特征值是一、迭代法的譜半徑稱迭代公式中的矩陣B為迭代矩陣.定義1：定義2：設(shè)A為n階方陣，λi(i=1,…,n)為A的特征值，稱特征值模的最大值為矩陣A的譜半徑，記為稱為矩陣A的譜.性質(zhì)：若矩陣A的譜為譜半徑為則Ak=AA…Ak個(gè)的譜為(k=1,2,…)譜半徑為定理：設(shè)A為任意n階方陣，||.||為任意由向量范數(shù)誘導(dǎo)出的矩陣的范數(shù)，則證明：對(duì)A的任一特征值λi及相應(yīng)的特征向量ui，都有因?yàn)閡i為非零向量，即||ui||≠0，于是有由λi的任意性得定理：設(shè)A為n階方陣，則對(duì)任意正數(shù)ε，存在一種矩陣范數(shù)||.||，使得（證明省略）注：對(duì)n階方陣，一般不存在矩陣范數(shù)||.||，使得但若A為對(duì)稱矩陣，則有下面的定理對(duì)建立迭代法的收斂條件十分重要.定理：設(shè)A為n階方陣，則的充要條件為證明：必要性:若則而于是由極限存在準(zhǔn)則，有故充分性:若取則存在一種矩陣范數(shù)||.||，使得而于是所以二、迭代法的收斂條件定理：對(duì)任意初始向量x(0)和右端項(xiàng)g，由迭代格式x(k+1)=Mx(k)+g

產(chǎn)生的向量序列收斂的充要條件為證明：必要性設(shè)存在n維向量x*，使得則x*滿足由迭代公式有于是有因?yàn)閤(0)為任意向量，因此上式成立必須即充分性:若則λ=1不是M的特征值，所以|I－Ｍ|≠0于是對(duì)任意n維向量g，方程組(I－M)x=g有唯一解，記為x*，即并且又因?yàn)楣蕦?duì)任意初始向量x(0)，都有即由迭代公式產(chǎn)生的向量序列{x(k)}收斂。推論1：若迭代矩陣滿足||M||<1，則迭代公式產(chǎn)生的向量序列{x(k)}收斂。推論2：松弛法收斂的必要條件是0<ω<2證明:設(shè)松弛法的迭代矩陣M有特征值因?yàn)橛啥ɡ?，松弛法收斂必有又因?yàn)槎谑怯兴宰ⅲ憾ɡ肀砻?，迭代法收斂與否只決定于迭代矩陣的譜半徑，與初始向量及方程組的右端項(xiàng)無(wú)關(guān)。對(duì)同一方程組，由于不同的迭代法迭代矩陣不同，因此可能出現(xiàn)有的方法收斂，有的方法發(fā)散的情形。舉例：解方程組討論Jacobi法與Gauss-Seidel法的收斂性。解：由定理，迭代法是否收斂等價(jià)于迭代矩陣的譜半徑是否＜１，故應(yīng)先求迭代矩陣。而故A分解后的各矩陣分別為Jacobi迭代法的迭代矩陣為其特征方程為因此有故Jacobi法收斂如果用Gauss-Seidel迭代，由可得于是迭代矩陣為其特征方程為故所以Gauss-Seidel迭代法發(fā)散。???請(qǐng)思考:(1)若記不住Jacobi迭代法和Gauss-Seidel迭代法的矩陣表示，怎么寫(xiě)出迭代矩陣？(2)試歸納判斷迭代法收斂的方法？答:(1)從分量表示開(kāi)始

(2)先用兩個(gè)推論，再用充要條件，即||M||<1迭代法收斂松弛法收斂0<ω<2迭代法收斂下面對(duì)一些特殊的系數(shù)矩陣給出幾個(gè)常用的判斷收斂的條件。定義：若n階方陣A=(aij)滿足且至少有一個(gè)i

值，使上式中不等號(hào)嚴(yán)格成立，則稱A為弱對(duì)角占優(yōu)陣。若對(duì)所有i，不等號(hào)均嚴(yán)格成立，則稱A為嚴(yán)格對(duì)角占優(yōu)陣。例如：矩陣是嚴(yán)格對(duì)角占優(yōu)陣矩陣不是嚴(yán)格對(duì)角占優(yōu)陣設(shè)有線性方程組Ax=b，下列結(jié)論成立：若A為嚴(yán)格對(duì)角占優(yōu)陣，則Jacobi迭代法和Gauss-Seidel迭代法均收斂。2.若A為嚴(yán)格對(duì)角占優(yōu)陣，0<ω≤1，則松弛法收斂。3.若A為對(duì)稱正定陣，0<ω<2，則松弛法收斂.

即：若A是對(duì)稱正定陣，則松弛法收斂的充要條件為0<ω<2。歸納判斷迭代法收斂的方法如下：1.首先根據(jù)方程組的系數(shù)矩陣A的特點(diǎn)判斷；2.可根據(jù)迭代矩陣的范數(shù)判斷；3.只好根據(jù)迭代矩陣的譜半徑判斷.三、舉例例1：設(shè)有方程組Ax=b，其中討論用三種迭代法求解的收斂性。解：首先Ａ不是對(duì)角占優(yōu)陣，但Ａ是對(duì)稱陣，且其各階順序主子式均大于０，故Ａ為對(duì)稱正定陣，由判別條件３可得Gauss-Seidel法與松弛法(0<ω<2)均收斂。又因?yàn)镴acobi迭代法的迭代矩陣為故||B||1=||B||∞=1，因此不能用范數(shù)判斷。下面計(jì)算迭代矩陣的譜半徑。解特征方程可得譜半徑故Jacobi迭代法不收斂。值得注意的是：改變方程組中方程的順序，即將系數(shù)矩陣作行交換，會(huì)改變迭代法的收斂性。例2：設(shè)方程組Ax=b的系數(shù)矩陣為則Jacobi法與Gauss-Seidel法的迭代矩陣分別是其譜半徑分別為故這兩種迭代法均不收斂。但若交換兩個(gè)方程的次序，得原方程組的同解方程組顯然Aˊ是嚴(yán)格對(duì)角占優(yōu)陣，因此對(duì)方程組用Jacobi法和Gauss-Seidel法均收斂。例3：設(shè)A=(aij)是二階方陣，且a11a22≠0.試證求解方程組Ax=b的Jacobi法與Gauss-Seidel法同時(shí)收斂或發(fā)散。證明：Jacobi迭代矩陣為其譜半徑為而Gauss-Seidel法的迭代矩陣為其譜半徑為則有顯然同時(shí)