代數(shù)多重網(wǎng)格算法new

《代數(shù)多重網(wǎng)格算法new》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、代數(shù)多重網(wǎng)格算法¤2007年2月14日1基本思想Gauss-Seidel算法的特點(diǎn)是,最初幾步收斂的很快,但是很快就開始停滯不前.到最后幾乎不收斂.從數(shù)值試驗(yàn)的圖像可以看出,Gauss-Seidel迭代當(dāng)插值點(diǎn)少的時(shí)候,收斂速度極快,但當(dāng)插值點(diǎn)多的時(shí)候,由于上述效應(yīng)收斂速度極慢.因此,代數(shù)多重網(wǎng)格(AlgebraicMulti-Grid)算法利用這些特點(diǎn),將由具體方程離散出來(lái)的矩陣,重投到一系列由細(xì)到粗的網(wǎng)格上,在每一層網(wǎng)格上只做若干次Gauss-Seidel迭代.與傳統(tǒng)的多重網(wǎng)格算法不同,該算法不需要提供任何網(wǎng)格的信息

2、.所有的信息完全只來(lái)自方程離散后的矩陣.假設(shè)Possion方程?￠u=f(1)用某種離散方法(比如,有限元或有限差分),在某個(gè)相當(dāng)細(xì)的網(wǎng)格上,最后產(chǎn)生線性問(wèn)題Ax=b:(2)現(xiàn)在考慮如何將其投影到一個(gè)較粗的網(wǎng)格上.假設(shè)á=fáig;i=1;￠￠￠;N為細(xì)網(wǎng)格上的一組分片一次線性有限元基函數(shù).則矩陣A是一個(gè)N￡N的矩陣,且元素aij可以看作是對(duì)應(yīng)基函數(shù)的一個(gè)雙線性運(yùn)算a(ái;áj).我們?nèi)绻獙重新投影到一個(gè)對(duì)應(yīng)基函數(shù)為?=f?ig;i=1;￠￠￠;M;M<

3、(3)這里P是一個(gè)M￡N的矩陣.相應(yīng)的,如果令A(yù)~=PAPT;x~=Px;b~=Pb;(4)則A~x~=b~(5)¤該文檔為李若教授講授的《數(shù)值分析高等算法》的課堂筆記,由王何宇整理.1就可以看作是(2)投影到粗網(wǎng)格上以后的問(wèn)題.代數(shù)多重網(wǎng)格的做法,就是對(duì)第k步的線性問(wèn)題Akx=bk(6)先用Gauss-Seidel迭代進(jìn)行幾步迭代,得到一個(gè)近似解xk,然后將殘問(wèn)題Akx=bk?Akxk(7)用投影矩陣Pk重投到粗一層的網(wǎng)格上得到第k+1步的問(wèn)題TAk+1x=bk+1;Ak+1=PkAkPk;bk+1=Pkbk?Akxk

4、;(8)如此不斷迭代和重投,直到得到一個(gè)規(guī)模相當(dāng)小的線性問(wèn)題后,可以用直接法(Gauss消去法)求得精確解,然后用記錄下的一系列Pk矩陣,還原出原問(wèn)題的解.在還原的時(shí)候,仍然使用Gauss-Seidel迭代在每一層來(lái)改進(jìn)數(shù)值解.如此整個(gè)過(guò)程為一步AMG迭代.2算法步驟現(xiàn)在給出嚴(yán)格的算法步驟.對(duì)過(guò)程AMG(Ak,xk,bk),第一步如果Ak的階數(shù)小于一個(gè)給定的整數(shù),比如20,則用Gauss消去法解出并xk并返回;否則,對(duì)問(wèn)題(6)做3至5步Gauss-Seidel迭代;第二步產(chǎn)生問(wèn)題(8),令xk+1=0;第三步遞歸調(diào)用A

5、MG(Ak+1,xk+1,bk+1);第四步x=x+PTx;kkkk+1第五步做3至5步Gauss-Seidel迭代,返回.所以對(duì)問(wèn)題(2),執(zhí)行AMG(A,x,b)完成一次AMG迭代(迭代更新了x).而整個(gè)求解過(guò)程為doAMG(A,x,b)while(

6、b-Ax

7、

8、心點(diǎn)的選取,應(yīng)該滿足如下兩點(diǎn):1.不能太多:核心點(diǎn)彼此之間,不能相鄰;22.不能太少:所有被移除的點(diǎn),必須至少與一個(gè)核心點(diǎn)相鄰.根據(jù)這個(gè)原則,和稀疏矩陣存儲(chǔ)規(guī)則,我們?cè)O(shè)計(jì)算法如下:第一步產(chǎn)生一維數(shù)組c[1:N],并置所有元素初值為零;第二步選出核心點(diǎn):fori=1:N,如果c[i]==0,則xi為核心點(diǎn),同時(shí)將所有滿足aij6=0的c[j]+=1;1第三步假設(shè)xi為第k個(gè)選出的核心點(diǎn),則P的第k行元素為:0如果aij==0,如果aij6=0.c[j]注意該算法仍然只用了矩陣的信息而沒(méi)有使用網(wǎng)格的信息.3算法分析該算法實(shí)際

9、上的迭代過(guò)程完全基于Gauss-Seidel迭代.所以其收斂的要求和Gauss-Seidel一樣,為矩陣對(duì)稱正定.但是要達(dá)到加速收斂的效果,要求矩陣必須有網(wǎng)格和方程的背景,否則這樣做是沒(méi)有意義的.3