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

Gauss－Seidel〔高斯-賽德爾迭代法〕1.Gauss－Seidel迭代原理Jacobi迭代公式〔5-9〕用方程組表示為〔5-13〕因此，在Jacobi迭代法的計(jì)算過程中，要同時(shí)保存兩個(gè)近似解向量和。如果把迭代公式改成以下形式〔5-14〕即每算出新近似解的一個(gè)分量，再算下一個(gè)分量時(shí)，用新分量代替老分量進(jìn)行計(jì)算。這樣，在整個(gè)計(jì)算過程中，只需要個(gè)單元存貯近似解分量。選取初始向量，用迭代公式〔5-14〕產(chǎn)生近似解序列，這種方法叫Gauss－Seidel迭代法，式〔5-14〕為Gauss－Seidel迭代法的計(jì)算公式。公式〔5-14〕用矩陣表示為〔5-15〕其中移項(xiàng)可得因?yàn)?，故存在，上式可改寫成?-16〕如果用矩陣來表法，記那么于是〔5-17〕將式〔5-17〕代入式〔5-16〕這是Gauss－Seidel迭代公式的矩陣表示，式中矩陣為迭代矩陣。2.Gauss－Seidel算法〔1〕輸入,維數(shù),誤差限，最大容許迭代次數(shù)?！?〕置?！?〕計(jì)算：〔4〕假設(shè)，輸出，停機(jī)；否那么轉(zhuǎn)〔5〕?！?〕假設(shè)，置，轉(zhuǎn)〔3〕；否那么輸出失敗信息，停機(jī)。用Gauss－Seidel迭代法解例5-4。仍取，按式〔5-14〕計(jì)算得如此繼續(xù)下去，計(jì)算結(jié)果見表5-2。00.00000.00000.000017.20009.020011.6440210.430811.671912.8205310.931311.957212.9778410.991311.994712.9972510.998911.999312.9996610.999911.999913.0000計(jì)算結(jié)果說明，用Gauss－Seidel迭代法求解例5-4中的方程組比Jacobi迭代法效果好，迭代5次所得到的結(jié)果與例5-4中迭代9次所得的結(jié)果相相仿。事實(shí)上，對(duì)有些問題Gauss－Seidel迭代法確實(shí)比Jacobi迭代法收斂的快，但也有Gauss－Seidel迭代比Jacobi迭代收斂得慢，甚至還有Jacobi迭代收斂，Gauss－Seidel迭代發(fā)散的情況。3Gauss_Seidel迭代法的MATLAB實(shí)現(xiàn)function[x,k,flag]=Gau_Seid(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-4;endn=length(A);k=0;x=zeros(n,1);y=zeros(n,1);flag='OK!';while1y=x;fori=1:nz=b(i);forj=1:nifj~=iz=z-A(i,j)*x(j);endendifabs(A(i,i))<1e-10|k==max1falg='Fail!';return;endz=z/A(i,i);x(i)=z;endifnorm(y-x,inf)<deltabreak;endk=k+1;end【5-6】用Gauss_Seidel迭代法求解線性方程組。解：在命令窗口輸入系數(shù)矩陣和右端項(xiàng)：>>A=[10-2-2;-210-1;-1-23],b=[10.51]'回車得到：A=10-2-2-210-1-1-23b=1.00000.50001.0000再輸入：>>[x,k,flag]=Gau_Seid(A,b)回車得到：x=0.2311k=6flag=OK!0.14700.5084這說明經(jīng)過6次迭代得到滿足精度要求的近似解。逐次超松弛迭代法1.逐次超松弛迭代原理為了加速迭代過程的收斂，我們通過引入?yún)?shù)，在Gauss－Seidel迭代的根底上得到一種新的迭代法。記，其中由式〔5-14〕算出。于是有假設(shè)將看作修正項(xiàng)，那么Gauss－Seidel迭代的第次近似解以此項(xiàng)修正后得到新的近似解。松弛法是將乘上一個(gè)參數(shù)因子作為修正項(xiàng)而得到新的近似解，其具體公式為即〔5-19〕按式〔5-19〕計(jì)算方程組〔5-5〕的近似解序列的方法稱為松弛法，稱為松弛因子。當(dāng)時(shí)稱為低松弛，是Gauss－Seidel迭代，時(shí)稱為超松弛法，簡(jiǎn)稱SOR法〔SuccessiveOver-Relaxation〕。2.松弛迭代算法〔1〕輸入,維數(shù),誤差限,最大容許迭代次數(shù)?！?〕置。〔3〕計(jì)算：〔4〕假設(shè)，輸出，停機(jī)；否那么轉(zhuǎn)〔5〕?！?〕假設(shè)，置，轉(zhuǎn)〔3〕；否那么輸出失敗信息，停機(jī)?！?-7】取，用超松弛法求解方程組。解由迭代公式〔5-19〕，有將代入上式得如此繼續(xù)下去，計(jì)算結(jié)果如表5-3所示。01.00001.00001.000011.00001.00001.560021.00001.39201.618431.27441.46821.640441.21801.41361.593451.20231.39161.606861.19321.40341.600771.20511.40271.601681.19991.40001.599491.20001.39961.6001所以，方程組有解與精確解比擬，誤差為松弛法的迭代公式〔5-19〕的矩陣表示為〔5-20〕因?yàn)椋蚀嬖?，從而有存在，式?-20〕可改寫成〔5-21〕松弛法的迭代矩陣為松弛因子的選取對(duì)收斂速度影響極大，但目前尚無可供實(shí)用的計(jì)算最正確松弛因子的方法。實(shí)際計(jì)算時(shí)，通常是根據(jù)系數(shù)矩陣的性質(zhì)及實(shí)際計(jì)算經(jīng)驗(yàn)，通過試算來確定松弛因子的值。特別當(dāng)為對(duì)稱正定的三對(duì)角時(shí)，有其中為Jacobi迭代矩陣的譜半徑。為了提高計(jì)算效率，改善收斂性，又產(chǎn)生了對(duì)稱超松弛法，簡(jiǎn)稱SSOR法。對(duì)稱超松弛法實(shí)質(zhì)上是將同等看待，連續(xù)兩次使用SOR迭代公式得到。它的優(yōu)點(diǎn)是對(duì)某些使用SOR法不收斂的問題，可以構(gòu)造出收斂的SSOR法；松弛法對(duì)松弛因子十分敏感，SSOR法那么不敏感；充分利用內(nèi)外交換時(shí)所得到的信息，提高計(jì)算效率。3.超松弛迭代法MATLAB實(shí)現(xiàn)function[x,k,flag]=SOR(A,b,ep,w,max1)%求解線性方程組的迭代法,其中,%A為方程組的系數(shù)矩陣;%b為方程組的右端項(xiàng);%delta為精度要求,缺省值為1e-5;%max1為最大迭代次數(shù),缺省值100;%w為超松超松弛因子,缺省為1;%x為方程組的解;%k為迭代次數(shù);%flag為指標(biāo)變量flag='OK!'表示迭代收斂到指標(biāo)要求,%flag='fail!'表示迭代失敗.ifnargin<5max1=100;endifnargin<4w=1;endifnargin<3ep=1e-5;endn=length(A);k=0;x=zeros(n,1);y=zeros(n,1);flag='OK!';while1y=x;fori=1:nz=b(i);forj=1:nifj~=iz=z-A(i,j)*x(j);endendifabs(A(i,i))<1e-10|k==max1flag='fail';return;endz=z/A(i,i);x(i)=(1-w)*x(i)+w*z;endifnorm(y-x,inf)<epbreak;endk=k+1;end【5-8】用松弛迭代法求線性方程組。解：在命令窗口輸入系數(shù)矩陣和右端項(xiàng)：>>A=[2-100;-12-10;0-12-1;00-12],b=[1010]'回車得到：A=2-100-12-100-12