解線性方程組的迭代法.ppt
《解線性方程組的迭代法.ppt》由會員分享，可在線閱讀，更多相關(guān)《解線性方程組的迭代法.ppt（79頁珍藏版）》請在裝配圖網(wǎng)上搜索。
第6章解線性方程組的迭代方法,6.1迭代法的基本概念6.2雅可比迭代法與高斯-賽德爾迭代法6.3超松弛迭代法6.4*共軛迭代法,其中A為非奇異矩陣,當(dāng)A為低階稠密矩陣時,第5章討論的選主元消去法是有效的.但對于大型稀疏矩陣方程組(A的階數(shù)n很大?104，但零元素較多),利用迭代法求解是合適的.,本章將介紹迭代法的一些基本理論及雅可比迭代法，高斯-賽德爾迭代法，超松弛迭代法，而超松弛迭代法應(yīng)用很廣泛。,下面舉簡例，以便了解迭代法的思想.,對線性方程組,Ax=b，(1.1),6.1迭代法的基本概念,6.1.1引言,例1求解方程組,記為Ax=b，其中,此方程組的精確解是x*=(3,2,1)T.現(xiàn)將(1.2)改寫為,或?qū)憺閤=B0 x+f，其中,我們?nèi)稳〕跏贾?，例如取x(0)=(0,0,0)T.將這些值代入(1.3)式右邊(若(1.3)式為等式即求得方程組的解，但一般不滿足)，得到新的值x(1)=(x1(1),x2(1),x3(1))T=(3.5,3,3)T，再將x(1)分量代入(1.3)式右邊得到x(2)，反復(fù)利用這個計算程序，得到一向量序列和一般的計算公式(迭代公式),簡寫為x(k+1)=B0 x(k)+f，,其中k表示迭代次數(shù)(k=0,1,2,?).,迭代到第10次有,從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐步逼近方程組的精確解是x*=(3,2,1)T.即有,對于任何一個方程組x=Bx+f(由Ax=b變形得到的等價方程組)，由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近方程組的解x*呢？回答是不一定.請同學(xué)們考慮用迭代法解下述方程組,但x(k)并不是所有的都收斂到解x*！,對于給定方程組x=Bx+f，設(shè)有唯一解x*，則,x*=Bx*+f.(1.5),又設(shè)x(0)為任取的初始向量,按下述公式構(gòu)造向量序列,x(k+1)=Bx(k)+f,k=0,1,2,?.(1.6),其中k表示迭代次數(shù).,定義1(1)對于給定的方程組x=Bx+f,用公式(1.6)逐步代入求近似解的方法稱為迭代法(或稱為一階定常迭代法，這里B與k無關(guān)).B稱為迭代矩陣.,(2)如果limx(k)(k→?)存在(記為x*),稱此迭代法收斂,顯然x*就是方程組的解,否則稱此迭代法發(fā)散.,由上述討論，需要研究{x(k)}的收斂性.引進誤差向量,由(1.6)減去(1.5)式，得?(k+1)=B?(k)(k=0,1,2,?)，遞推得,要考察{x(k)}的收斂性，就要研究B在什么條件下有l(wèi)imε(k)=0(k→∞)，亦即要研究B滿足什么條件時有Bk→0(零矩陣)(k→∞).,6.1.2向量序列與矩陣序列的極限,定義2設(shè)向量序列{x(k)}?Rn,x(k)=(x1(k),…,xn(k))T,如果存在x=(x1,x2,…,xn)T?Rn，使,則稱向量序列{x(k)}收斂于x，記作,顯然，,其中????為任一向量范數(shù).,定義3設(shè)矩陣序列Ak={aij(k)}?Rnn及A={aij}?Rnn,如果n2個數(shù)列極限存在，且有,則稱矩陣序列{Ak}收斂于A，記作,例2設(shè)有矩陣序列,且設(shè)|?|<1，考察其極限.,解顯然，當(dāng)|?|(2)用反證法，假定B有一個特征值?,滿足|?|?1,則存在x?0,使Bx=?x,由此可得||Bkx||=|?|k||x||,當(dāng)k→?時{Bkx}不收斂于零向量.由定理2可知(1)不成立，從而知|?|<1，即(2)成立.,(1)limBk=0;(2)?(B)<1;(3)至少存在一種從屬的矩陣范數(shù)||||?，使||B||?(3)根據(jù)第5章定理18，對任意?>0，存在一種從屬范數(shù)||||?，使||B||???(B)+?，由(2)有?(B)0，可使||B||?(1)由(3)給出的矩陣范數(shù)||B||?N時有,證明由第5章定理18，對一切k有,另一方面對任意?>0，記,顯然有?(B?)N時，,由?的任意性即得定理結(jié)論.,6.1.3迭代法及其收斂性,其中，A=(aij)∈Rnn為非奇異矩陣，下面研究如何建立解Ax=b的迭代法.,設(shè)有線性方程組,Ax=b，,其中，M為可選擇的非奇異矩陣，且使Mx=d容易求解，一般選擇A的某種近似，稱M為分裂矩陣.,將A分裂為,A=M-N.(1.9),于是，求解Ax=b轉(zhuǎn)化為求解Mx=Nx+b，即求解,從而可構(gòu)造一階定常迭代法：,其中B=M-1N=M-1(M-A)=I-M-1A，f=M-1b.稱B=I-M-1A為迭代法的迭代矩陣，選取M矩陣，就得到解Ax=b的各種迭代法.,下面給出迭代法(1.11)式收斂的充分必要條件.,也就是求解線性方程組,x=Bx+f.(1.10),定理5(一階定常迭代法的基本定理)給定線性方程組(1.10)及一階定常迭代法(1.11)式，對任意選取初始向量x(0)，迭代法(1.11)式收斂的充分必要條件是矩陣B的譜半徑?(B)<1.,由定理2知limBk=0，再由定理3，即得?(B)<1.,證明(<=)設(shè)?(B)<1，易知Ax=f(其中A=I-B)有唯一解，記為x*，則x*=Bx*+f.,誤差向量?(k)=x(k)-x*=Bk?(0),?(0)=x(0)-x*.,由設(shè)?(B))設(shè)對任意x(0)有l(wèi)imx(k)=x*,其中x(k+1)=Bx(k)+f.顯然,極限x*是線性方程組(1.10)的解,且對任意x(0)有,?(k)=x(k)-x*=Bk?(0)→0(k→?).,例3考察線性方程組(1.2)給出的迭代法(1.4)式的收斂性.,解先求迭代矩陣B0的特征值.由特征方程,可得,解得,即?(B0)1，這說明用迭代法解此方程組不收斂.,迭代法的基本定理在理論上是重要的，由于?(B)?||B||，下面利用矩陣B的范數(shù)建立判別迭代法收斂的充分條件.,定理6(迭代法收斂的充分條件)設(shè)有線性方程組x=Bx+f，A=(aij)∈Rnn，及一階定常迭代法x(k+1)=Bx(k)+f.如果有B的某種算子范數(shù)||B||=q<1，則,(1)迭代法收斂，即對任取x(0)有l(wèi)imx(k)=x*，且x*=Bx*+f.,證明由基本定理知，結(jié)論(1)是顯然的.,(2)顯然有關(guān)系式x*-x(k+1)=B(x*-x(k))及x(k+1)-x(k)=B(x(k)-x(k-1)).,于是有,反復(fù)利用②即得(2).,(4)反復(fù)利用①，則得到(4).,(3)考察,即有,注意，定理6只給出迭代法(1.11)式收斂的充分性，即使條件||B||<1對任何常用范數(shù)均不成立，迭代序列仍可能收斂.,例5迭代法x(k+1)=Bx(k)+f，其中,顯然||B||?=1.1,||B||1=1.2,||B||2=1.043,||B||F=(1.54)1/2,,但由于?(B)=0.9<1，故由此迭代法產(chǎn)生的迭代序列{x(k)}是收斂的.,下面考察迭代法(1.11)式的收斂速度.假定迭代法(1.11)式是收斂的,即?(B)<1,由?(k)=Bk?(0),?(0)=x(0)-x*,得,于是,根據(jù)矩陣從屬范數(shù)定義，有,所以||Bk||是迭代k次后誤差向量?(k)的范數(shù)與初始誤差向量?(0)的范數(shù)之比的最大值.這樣，迭代k次后，平均每次迭代誤差向量范數(shù)的壓縮率可看成是||Bk||1/k，若要求迭代k次后有,其中σ<<1，可取σ=10-s.因為?(B)<1,故||Bk||1/k<1,由||Bk||1/k<σ1/k兩邊取對數(shù)得,即,它表明迭代次數(shù)k與-ln||Bk||1/k成反比.,即,定義4迭代法(1.11)式的平均收斂速度定義為,平均收斂速度Rk(B)依賴于迭代次數(shù)及所取范數(shù)，給計算分析帶來不便，由定理4可知lim||Bk||1/k=?(B)，所以limRk(B)=-ln?(B).,定義5迭代法(1.11)式的漸近收斂速度定義為,R(B)與迭代次數(shù)及矩陣B取何種范數(shù)無關(guān)，它反映了迭代次數(shù)趨于無窮時迭代法的漸近性質(zhì)，當(dāng)?(B)越小-ln?(B)越大，迭代法收斂越快，可用,作為迭代法(1.11)式所需的迭代次數(shù)估計.,例如在例1中迭代法(1.4)式的迭代矩陣B0的譜半徑?(B0)=0.3592.若要求,則由(1.13)式知,于是有,即取k=12即可達到要求.,6.2雅可比迭代法與高斯-塞德爾迭代法,6.2.1雅可比迭代法,將線性方程組(1.1)中的系數(shù)矩陣A分成三部分,,,即A=D-L-U,設(shè)aii?0(i=1,2,?,n)，選取M為A的對角元素部分,即選取M=D(對角陣)，A=D-N，由(1.11)式得到解方程組Ax=b的雅可比(Jacobi)迭代法.又稱簡單迭代法.,其中B=I-D-1A=D-1(L+U)≡J,f=D-1b.稱J為解Ax=b的雅可比迭代法的迭代矩陣.,于是雅可比迭代法可寫為矩陣形式,其Jacobi迭代矩陣為,下面給出雅可比迭代法(2.2)的分量計算公式,記,由雅可比迭代法(2.2)有,每一個分量寫出來為,即當(dāng)aii?0時，有,等價方程組,其中aii?0(i=1,2,?,n),即由方程組Ax=b得到的,建立的雅可比迭代格式為,于是，解Ax=b的雅可比迭代法的計算公式為,由(2.3)式可知，雅可比迭代法計算公式簡單，每迭代一次只需計算一次矩陣和向量的乘法且計算過程中原始矩陣A始終不變.,6.2.2高斯-塞德爾迭代法,在Jacobi迭代中，計算xi(k+1)(2?i?n)時，使用xj(k+1)代替xj(k)(1?j?i-1)，即有,建立迭代格式,或縮寫為,稱為高斯-塞德爾(Gauss-Seidel)迭代法.,其Gauss-Seidel迭代矩陣為,G=(D-L)-1U,于是高斯-塞德爾迭代法可寫為矩陣形式,這就是說，選取分裂矩陣M為A的下三角部分,即選取M=D-L(下三角陣)，A=M-N，由(2.3)式得到解Ax=b的高斯-塞德爾(Gauss-Seidel)迭代法.,其中B=I-(D-L)-1A=(D-L)-1U≡G,f=(D-L)-1b.稱矩陣G=(D-L)-1U為解Ax=b的高斯-塞德爾迭代法的迭代矩陣.,由高斯-塞德爾迭代法(2.4)有,每一個分量寫出來為,即當(dāng)aii?0時，有(與前面一樣的式子),或,于是，解Ax=b的高斯-塞德爾迭代法的計算公式為,或,雅可比迭代法不使用變量的最新信息計算xi(k+1)，而由高斯-塞德爾迭代公式(2.6)可知，計算x(k+1)的第i個分量xi(k+1)時，利用了已經(jīng)計算出的最新分量xj(k+1)(j=1,2,?,i-1).可看作雅可比迭代法的一種改進.由(2.6)可知，高斯—塞德爾迭代公式每迭代一次只需計算一次矩陣與向量的乘法.,算法(高斯-塞德爾迭代法)設(shè)Ax=b,其中A∈Rnn為非奇異矩陣，且aii?0(i=1,2,…,n)，本算法用高斯-塞德爾迭代法解Ax=b，數(shù)組x(n)開始存放x(0)，后存放x(k)，N0為最大迭代次數(shù).,迭代一次，這個算法需要運算次數(shù)至多與矩陣A的非零元素的個數(shù)一樣多.,2.對于k=1,2,…,N0，,對于i=1,2,…,n,1.xi←0.0(i=1,2,…,n),,例6用高斯-塞德爾迭代法解線性方程組(1.2).,解用高斯-塞德爾迭代公式：取x(0)=(0,0,0)T.,迭代到第7次有,由此例可知，用高斯-塞德爾迭代法，雅可比迭代法解線性方程組(1.2)(且取x(0)=0)均收斂，而高斯-塞德爾迭代法比雅可比迭代法收斂較快(即取相同的x(0)，達到同樣精度所需迭代次數(shù)較少)，但這結(jié)論只當(dāng)A滿足一定條件時才是對的.,例1用雅可比迭代法解方程組,解：Jacobi迭代格式為,取x(0)=(0,0,0)T計算結(jié)果如下：,解：Gauss-Seidel迭代格式為,例2用Gauss-Seidel迭代法解上題.,取x(0)=(0,0,0)T計算結(jié)果如下：,6.2.3雅可比迭代與高斯-塞德爾迭代收斂性,由定理5可立即得到以下結(jié)論.,定理7設(shè)Ax=b，其中A=D-L-U為非奇異矩陣,且對角矩陣D也奇異，則,(1)解線性方程組的雅可比迭代法收斂的充要條件是?(J)<1，其中J=D-1(L+U).,(2)解線性方程組的高斯-塞德爾迭代法收斂的充要條件是?(G)<1，其中G=(D-L)-1U.,由定理6還可得到雅可比迭代法收斂的充分條件是||J||<1.高斯-塞德爾迭代法收斂的充分條件是||G||<1.,在科學(xué)及工程計算中，要求解線性方程組Ax=b,其矩陣A常常具有某些特性.例如，A具有對角占優(yōu)性質(zhì)或A為不可約矩陣，或A是對稱正定矩陣等，下面討論解這些方程組的收斂性.,定義6(對角占優(yōu)陣)設(shè)A=(aij)nn.,(1)如果A的元素滿足,稱A為嚴(yán)格(按行)對角占優(yōu)陣.,(2)如果A的元素滿足,且上式至少有一個不等式成立，稱A為弱(按行)對角占優(yōu)陣.,定義7(可約與不可約矩陣)設(shè)A=(aij)nn(n≥2)，如果存在置換陣P使,其中A11為r階方陣，A22為n-r階方陣(1≤r下載提示(請認真閱讀)
- 1.請仔細閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認領(lǐng)！既往收益都歸您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
14.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 線性方程組 迭代法
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://ioszen.com/p-3588893.html