數(shù)值分析教教案20

第5章求解線性代數(shù)方程組的迭代法5.1求解線性代數(shù)方程組的迭代法的根底知識迭代法的根本概念對于階數(shù)不太高的線性方程組，用直接法比擬有效，但對于由工程技術(shù)產(chǎn)生的高階方程組，假設(shè)其系數(shù)矩陣是無規(guī)律稀疏陣〔即矩陣的階數(shù)較大，但零元素較多〕，直接法就很難解決存儲問題，所以提出了用迭代思想求解線性方程組的方法。迭代法就是用某種極限過程去逐步逼近線性方程組精確解的方法，它需要計(jì)算機(jī)的存儲單元較少，因?yàn)樗刹槐卮鎯ο禂?shù)矩陣的零元素。迭代法的根本思想是給定方程組，構(gòu)造一個(gè)序列，使其收斂到某個(gè)極限向量，其中是方程組的精確解。在討論迭代法的過程中要用到向量范數(shù)、矩陣范數(shù)及序列極限等概念，為此，先介紹這方面的根本知識。向量范數(shù)向量范數(shù)是用來度量向量長度的。定義1：對，假設(shè)有實(shí)數(shù)與之對應(yīng)，且這種對應(yīng)法滿足下面三個(gè)性質(zhì)：1.，，而且，當(dāng)且僅當(dāng)〔非負(fù)性〕。2.，〔齊次性〕。3.，有〔三角形不等式〕，那么稱該實(shí)數(shù)為向量的范數(shù)。利用定義1中的性質(zhì)3可以證明對，有。事實(shí)上，由所以，。，定義：(5-1)其中。可以根據(jù)定義1驗(yàn)證滿足范數(shù)定義的條件，所以為的范數(shù)。由(5-1)式可知道，給定一個(gè)向量，它的范數(shù)定義可以有無窮多種，經(jīng)常采用的范數(shù)是，，時(shí)的定義。給定中的，常用的范數(shù)為：〔5-2〕〔5-3〕〔5-4〕【例5-1】計(jì)算向量的各種范數(shù)。解：=1+2+4=7；=；=4由向量范數(shù)的定義，可以討論向量的收斂問題。假設(shè)中的向量序列滿足條件：，那么稱在范數(shù)意義下收斂于中的向量。1.向量范數(shù)的連續(xù)性定理：給定中的任意向量，非負(fù)函數(shù)為向量的任意一向量范數(shù)，那么是的各分量的連續(xù)函數(shù)。2.向量范數(shù)的等價(jià)定理：給定，對于上的任意兩種范數(shù)，總存在與無關(guān)的正常數(shù)，，使關(guān)系式：，對一切成立。3.在中，假設(shè)在某一種范數(shù)意義下向量序列收斂，那么在任何范數(shù)意義下該向量序列仍收斂，即：。這里是向量的任意一種范數(shù)。4.在中，向量序列收斂于向量的充要條件為：，其中分別表示和的第個(gè)分量。矩陣范數(shù)設(shè)，定義矩陣的范數(shù)為：，那么由定義可知矩陣范數(shù)具有以下性質(zhì)：1.，，而且當(dāng)且僅當(dāng)〔非負(fù)性〕。2.，有〔齊次性〕。3.，有〔三角形不等式〕。4.，，。5.，6.，其中為單位陣。設(shè)，如果存在使得：，那么稱為矩陣的一個(gè)特征值。就是特征值對應(yīng)的特征向量。式〔5-2〕～〔5-4〕定義的三種常用向量范數(shù)對應(yīng)的矩陣范數(shù)定義為：〔列范數(shù)〕〔2-范數(shù)〕其中表示的最大特征值?！残蟹稊?shù)〕【例5-2】給定求，，。解：由，，得。又由，，得。由：得的特征多項(xiàng)式為：解，得的特征值，。從而：。對應(yīng)于向量范數(shù)的等價(jià)性，矩陣范數(shù)也有等價(jià)性結(jié)論：給定，對于上的任意兩種范數(shù)，，總存在與無關(guān)的正常數(shù)，，使關(guān)系式：成立，即上的任意兩種范數(shù)，是等價(jià)的。為上的矩陣序列，假設(shè)存在上的矩陣，使得：成立，那么稱矩陣序列是收斂的，稱為矩陣序列的收斂極限。由矩陣范數(shù)的等價(jià)性與矩陣收斂性的定義知，對矩陣序列收斂到矩陣，假設(shè)對上的一種范數(shù)成立，那么其他范數(shù)也成立。所以通常記矩陣序列是收斂于為：，而不特別強(qiáng)調(diào)是在哪種范數(shù)意義下收斂。上的矩陣序列是收斂于的充要條件為：，其中和分別表示和的第行第列的元素。譜半徑對于的上的矩陣，設(shè)的特征值為，稱=max{}為矩陣的譜半徑?！纠?-3】給定，求。解：特征多項(xiàng)式為：，那么的特征為，，從而。對于上的矩陣，有。此定理給出矩陣范數(shù)與譜半徑的關(guān)系。如果對于上的矩陣有，那么為非奇異矩陣，且有估計(jì)式：成立。給定，那么的充要條件是，其中表示的次冪。迭代法的收斂性從任意選取的初始向量出發(fā)，利用迭代格式構(gòu)造迭代序列，向量序列收斂到方程組的精確解的條件是什么呢？下同面給出了4個(gè)定理。其中前兩個(gè)定理適用于所有具有迭代格式的迭代法，后兩個(gè)定理是針對Jacobi迭代法、Gauss-Seidel迭代法和逐次超松弛迭代法提出的一些特殊的結(jié)論。1.對任意初始向量和常數(shù)項(xiàng)，由迭代格式〔〕產(chǎn)生的向量序列收斂的充要條件為。其中為所選迭代格式的迭代矩陣。2.對任意初始向量和常數(shù)項(xiàng)，由迭代格式〔〕產(chǎn)生的向量序列收斂的充要條件為：，其中為所選迭代格式的迭代矩陣。3.假設(shè)矩陣滿足：且至少有一個(gè)值，使上式中嚴(yán)格的不等號成立，那么稱矩陣具有對角優(yōu)勢。假設(shè)對所有值上式中的嚴(yán)格不等號都成立，那么稱矩陣是嚴(yán)格對角占優(yōu)矩陣。如果矩陣是嚴(yán)格對角占優(yōu)矩陣，那么矩陣非奇異。4.假設(shè)系數(shù)矩陣嚴(yán)格對角占優(yōu)，那么Jacobi迭代法和Gauss-Seidel迭代法必定收斂。逐次超松弛迭代法的必要條件是。迭代法的誤差估計(jì)上節(jié)得出的迭代法收斂的充要條件為或者，其中為迭代格式的迭代矩陣，在實(shí)際問題中，這兩種條件都很難驗(yàn)證的，對于上的矩陣，有得，所以可以用作為的一種估計(jì)得到迭代收斂的充要條件，即當(dāng)時(shí)迭代必收斂。關(guān)于這個(gè)充要條件的誤差計(jì)算，有以下定理。在方程組的迭代公式中，如果迭代矩陣滿足，那么第次迭代結(jié)果對于精確解有誤差估計(jì)式：和。5.2求解線性代數(shù)方程組的迭代方法迭代法是解線性方程組的一個(gè)重要的實(shí)用方法，特別適用于求解在實(shí)際中大量出現(xiàn)的系數(shù)矩陣為稀疏陣的大型線性方程組。本節(jié)介紹求解線性方程組的Jacobi迭代法、Gauss-Seidel迭代法和松弛迭代法。Jacobi迭代法Jacobi迭代法又稱簡單迭代法。1.Jacobi迭代原理設(shè)有線性方程組Ax＝b，即〔5-5〕的系數(shù)矩陣非奇異，不妨設(shè)。將方程組〔5-5〕變形為〔5-6〕其中。假設(shè)記那么方程組〔5-6〕可簡記為〔5-7〕選取初始向量代入迭代公式〔5-8〕產(chǎn)生向量序列，由上述計(jì)算過程所給出的迭代法稱為Jacobi迭代法，又叫簡單迭代法。式〔5-8〕為它的迭代公式，迭代矩陣為。式〔5-8〕的分量形式為〔5-9〕這是Jacobi迭代法的計(jì)算公式。如果用系數(shù)矩陣來表示，那么有其中，現(xiàn)把矩陣分解成如下形式：那么。方程組改寫成相應(yīng)的矩陣形式的迭代公式為〔5-10〕簡記為〔5-11〕式中，〔5-12〕迭代公式〔5-10〕或〔5-11〕也稱為Jacobi迭代，同時(shí)稱式〔5-12〕中的為Jacobi迭代矩陣?！纠?-4】用Jacobi迭代法求解線性方程組。解由Jacobi迭代法的計(jì)算公式〔5-9〕，有取，代入上式得如此繼續(xù)下去，迭代結(jié)果見表5-1。表5-100.00000.00000.000017.20008.30008.400029.710010.700011.5000310.570011.570012.4820410.853511.835412.8282510.951011.951012.9414610.983411.983412.9504710.994411.998112.9934810.998111.994112.9978910.999411.999412.9992迭代9次，得近似解，容易驗(yàn)證，方程組的精確解為，從表5-1中可以看出，當(dāng)?shù)螖?shù)增加時(shí)，迭代結(jié)果越來越接近精確解。2.Jacobi迭代法的MATLAB實(shí)現(xiàn)function[x,k,flag]=Jacobi(A,b,delta,max1)%求解線性方程組的迭代法,其中,%A為方程組的系數(shù)矩陣;%b為方程組的右端項(xiàng);%delta為精度要求,缺省值為1e-5;%max1為最大迭代次數(shù),缺省值100;%x為方程組的解;%k為迭代次數(shù);%flag為指標(biāo)變量flag='OK!'表示迭代收斂到指標(biāo)要求,%flag='fail!'表示迭代失敗.ifnargin<4max1=100;endifnargin<3delta=1e-5;endn=length(A);k=0;x=zeros(n,1);y=zeros(n,1);flag='OK!';while1fori=1:ny(i)=b(i);forj=1:nifj~=iy(i)=y(i)-A(i,j)*x(j);endendifabs(A(i,i))<1e-10|k==max1flag='Fail';return;endy(i)=y(i)/A(i,i);endifnorm(y-x,inf)<delta%無窮大范數(shù)break;endx=y;k=k+1;end【5-5】求解性線方程組。解：在命令窗口輸入系數(shù)矩陣和右端項(xiàng)：>>A=[41-1;1-5-1;2-1-6],b=[13-8-2]'回車得到：