第六章求解線性方程組的迭代法

,哈爾濱工程大學(xué),數(shù)值逼近與數(shù)值代數(shù),注,:,這是母版,請(qǐng)別修改,1,引言,第,6,章 求解線性方程組的迭代法,考慮,線性方程組,也就是,AX=b,.(1.1),低階稠密的,線性方程組用直接法,(,如高斯消去法和三角分解法,),。,大型稀疏非帶狀的,線性方程組,(n,很大,且零元素很多,.,如偏微方程數(shù)值解產(chǎn)生的,線性方程組,n,10,4,),的求解問(wèn)題？,零元素多，適合用,迭代法。,我們將介紹迭代法的一般理論及雅可比迭代法、高斯,塞德?tīng)柕?、超松弛迭代法，研究它們的收斂性?例,1,求解線性方程組,記為,Ax=b,即,精確解,x,*,=(3,2,1),T,.,改寫,(1.2),為,或?qū)憺?x=B,0,x+f,即,任取初值,如,x,(0),=(0,0,0),T,代入,(1.3),得到,x,(1),=,(2.5,3,3),T,.,反復(fù)迭代,即,x,(k+1),=B,0,x,(k),+f,，,(k=0,1,2,),2,基本迭代,法,考慮,線性方程組,也就是,Ax=b,.(2.1),進(jìn)行矩陣分裂,A=M-N,(2.2),其中,M,為可選擇的非奇異矩陣,且使,Mx,=d,容易求解,.,于是,Ax=,b,x,=M,-1,Nx+M,-1,b.,可得一階定常迭代法,:,一、雅可比迭代法,可以得到計(jì)算公式,(,雅可比迭代法,),：,對(duì),k=0,1,二、高斯,塞德?tīng)柕?還可得到迭代計(jì)算公式：,對(duì),k=0,1,稱為,高斯,塞德?tīng)柕?.,例,2,求解線性方程組,(1.2),取初值,x,(0),=(0,0,0),T,高斯,塞德?tīng)柕ㄓ值葍r(jià)于：,對(duì),k=0,1,SOR,迭代法的計(jì)算公式,:,對(duì),k=0,1,三、逐次超松馳,(SOR),迭代法,說(shuō)明,:,1),=1,GS;,2),運(yùn)算量,;,3),1,超松馳,1,低松馳,;,4),控制迭代終止的條件,:,例,3,用上述迭代法解線性代數(shù)方程組,初值,x,(0),=0,，寫出計(jì)算格式。,P242.,作業(yè),:P259,2.,3,迭代法的,收斂性分析,一、一階定常迭代法的基本定理,1)Jacobi:B,J,=D,-1,(L+U),，,f,J,=D,-1,b;,2)Gauss-Seidel:B,G,=(D-L),-1,U,，,f,G,=(D-L),-1,b;,3)SOR:B,SOR,=(D-wL),-1,(1-w)D+wU,，,f,SOR,=w(D-wL),-1,b.,迭代的統(tǒng)一格式：,x,(k+1),=,Bx,(k),+f,例,5,考察用,雅可比迭代法求解線性方程組,定義,3,（,1,）,按行嚴(yán)格對(duì)角占優(yōu)：,（,2,）,按行弱對(duì)角占優(yōu)：,上式至少有一個(gè)不等號(hào)嚴(yán)格成立。,二、某些特殊,方程組的迭代收斂性,*,定義,每行每列只有一個(gè)元素是,1,其余元素是零的方陣稱為置換陣,(,或排列陣,).,作業(yè),:P259,5.,定理,6(,對(duì)角占優(yōu)定理,),若矩陣,A,按行,(,或列,),嚴(yán)格對(duì)角占優(yōu)，或按行,(,或列,),弱對(duì)角占優(yōu)且不可約；則矩陣,A,非奇異。,定理,7,若矩陣,A,按行,(,或列,),嚴(yán)格對(duì)角占優(yōu),或按行,(,或列,),弱對(duì)角占優(yōu)不可約；則,Jacobi,迭代、,Gauss-Seidel,迭代都收斂。,證明,若矩陣,A,按行嚴(yán)格對(duì)角占優(yōu)，,或按行,(,或列,),弱對(duì)角占優(yōu)不可約，,則,GS,迭代收斂。假若不然，,(B,G,)1,，即迭代矩陣,B,G,的某一特征值,使得,|,|1,，并且,類似地，若矩陣,A,按行嚴(yán)格對(duì)角占優(yōu)，,或按行,(,或列,),弱對(duì)角占優(yōu)不可約，,則,Jacobi,迭代收斂。假若不然，,(B,J,)1,，即迭代矩陣,B,J,的某一特征值,使得,|,|1,，并且,定理,9,對(duì)于線性方程組,Ax,=,b,，若,A,為對(duì)稱正定矩陣，則當(dāng),0,2,時(shí)，,SOR,迭代收斂,.,證明,只需證明,1,（其中,為,L,的任一特征值）,.,定理,10,對(duì)于線性代數(shù)方程組,Ax=b,，若,A,按行,(,或列,),嚴(yán)格對(duì)角占優(yōu)，,或按行,(,或列,),弱對(duì)角占優(yōu)不可約；,則當(dāng),0w,1,時(shí)，,SOR,迭代收斂。,作業(yè),:P260,7,8.,