改進(jìn)的線(xiàn)性方程組迭代解法

改進(jìn)的線(xiàn)性方程組迭代解法

當(dāng)線(xiàn)性方程ax的b階數(shù)非常高時(shí)，大多數(shù)系數(shù)都是零。非常有效的解決方案是重復(fù)法。其經(jīng)典的算法有:Jacobi迭代法、Seidel迭代法和SOR方法。表示形式主要分為兩種:一般公式表示形式和矩陣迭代形式。1迭代矩陣的求解一般公式法的表達(dá)數(shù)學(xué)意義明確,計(jì)算精練。如下:其中,aij為系數(shù)矩陣A在i行j列的元素,bi為常數(shù)向量b的第i個(gè)分量,(3)式中w為SOR迭代法的加速因子。3種方法的區(qū)別與聯(lián)系在公式上表示出來(lái)其實(shí)也就是在上下標(biāo)上變動(dòng),大體形式都差不多。這很容易混淆3種方法,非常不利于記憶。雖然有了形式上歸一化的矩陣迭代形式:A=L+D+U的具體分解過(guò)程見(jiàn)文獻(xiàn)。但是同樣地,從(4)～(6)式可以明顯看出矩陣公式的表達(dá)依然太復(fù)雜(特別是SOR方法),同時(shí)由于其脫離了本身的數(shù)學(xué)背景意義,因此也非常不利于理解記憶和掌握。尤其是Seidel迭代法和SOR方法,迭代矩陣的求解過(guò)程還包含了矩陣求逆運(yùn)算((D+L)-1和(D+wL)-1),這從邏輯上來(lái)講是行不通的。因?yàn)榫仃嚽竽嫱确匠探M求解需要的計(jì)算量大得多,就算針對(duì)(D+L)和(D)+wL)都是下三角矩陣的特性,用Gauss-Jordan消元法求逆只需要處理對(duì)角線(xiàn)下方的元素,其計(jì)算量也和直接解法相當(dāng),約為n3/3次乘除法,再加上矩陣之間以及矩陣和向量之間的乘除法,得到迭代的矩陣形式共需要乘除法次數(shù):Seidel迭代法約為4n3/3+n2次;SOR方法約為:4n3/3+5n2。因此,可以說(shuō)矩陣迭代形式理論上的意義遠(yuǎn)大于實(shí)際應(yīng)用的意義,但是又沒(méi)能擺脫表達(dá)式復(fù)雜的困擾。2jacabi迭代法的特點(diǎn)下面提出的算法形式,結(jié)合了一般公式法計(jì)算上的精練和矩陣迭代形式的簡(jiǎn)潔,并且都以最簡(jiǎn)單的Jacobi迭代法的迭代矩陣為基礎(chǔ),根本不需要矩陣求逆和矩陣相乘等復(fù)雜運(yùn)算,只要經(jīng)過(guò)簡(jiǎn)單的加減和數(shù)乘運(yùn)算就可得到后面所有的迭代過(guò)程。這樣不僅便于理解記憶,還非常有利于編程實(shí)現(xiàn)。2.1迭代形式的求解對(duì)于Jacobi迭代法,其矩陣迭代形式同(4)式,里面雖要求D-1;但由于D為對(duì)角陣,所以D-1可以直接得到,不納入矩陣求逆的行列。迭代形式的求解過(guò)程也非常簡(jiǎn)單明了,不愧又稱(chēng)為簡(jiǎn)單迭代法。當(dāng)然,其求解過(guò)程還可以更直觀,具體過(guò)程如下:①檢查方程組對(duì)角線(xiàn)上系數(shù)是否全部非零:是,轉(zhuǎn)②;否,先交換方程組里方程之間順序,使得交換后的方程組對(duì)角線(xiàn)上系數(shù)全部非零,再轉(zhuǎn)②。②解出方程組對(duì)角線(xiàn)上未知變量(用其他未知變量線(xiàn)性表出),得到同解方程組:X=BJX+fJ。由(4)顯然有:其中,表示迭代矩陣BJ第i行j列的元素,表示fJ的第i個(gè)分量。2.2理解掌握的背景Jacobi迭代過(guò)程簡(jiǎn)單明了,求解過(guò)程數(shù)學(xué)背景簡(jiǎn)單明確,理解掌握起來(lái)也很容易。以Jacobi迭代矩陣形式(4)式為基礎(chǔ)來(lái)推導(dǎo)表示Seidel迭代和SOR方法的矩陣形式。2.2.1fj多量表由Seidel迭代公式(2)以及(7)可知:其中,b表示迭代矩陣BJ第i行j列的元素,f表示fJ的第i個(gè)分量。因此,可把上式即Seidel迭代過(guò)程表示如下:因此,Seidel迭代過(guò)程的求解過(guò)程計(jì)算量和Jacobi迭代過(guò)程一樣,同為n2次乘除法,比傳統(tǒng)的矩陣形式節(jié)約的計(jì)算量約為4n3/3+n2-n2=4n3/3次乘除法。2.2.2算法的基本過(guò)程嚴(yán)格說(shuō)來(lái)(8)式并非一個(gè)標(biāo)準(zhǔn)的迭代方程(形如X=BX+f),但是也正因?yàn)槿绱怂拍苋绱撕?jiǎn)潔。其運(yùn)算過(guò)程應(yīng)理解如下:第k+1次迭代時(shí):1)①BJ的第1行與X相乘所得到的標(biāo)量再加上fJ的第1個(gè)分量f之和d1,這就是第k+1次迭代得到的X(k+1)的第1個(gè)分量;②直接用d1代替X的第1個(gè)分量,再進(jìn)入步2);2)②BJ的第2行與X相乘所得到的標(biāo)量再加上fJ的第2個(gè)分量之和d2,這就是第k+1次迭代得到的X(k+1)的第2個(gè)分量;②直接用d2代替X的第2個(gè)分量,再進(jìn)入步3);i)①BJ的第i行與X相乘所得到的標(biāo)量再加上fJ的第i個(gè)分量f之和di,這就是第k+1次迭代得到的X(k+1)的第i個(gè)分量;②直接用di代替X的第i個(gè)分量,再進(jìn)入步“i+1”);n)①BJ的第n行與X相乘所得到的標(biāo)量再加上fJ第n個(gè)分量f之和dn,這就是第k+1次迭代得到的X(k+1)的第n個(gè)分量;②直接用dn代替X的第n個(gè)分量,這樣第k+1次迭代已進(jìn)行完畢,此時(shí)的X就是第kk+1次迭代得到的X(k+1);以一個(gè)簡(jiǎn)單方程組為例,算法的一次完整迭代(第k+1次迭代)過(guò)程如下:假設(shè)第k次迭代結(jié)果為:X(k)=(000)T,則:1)過(guò)程為:2)過(guò)程為:3)過(guò)程為:②得到第k+1次迭代結(jié)果為:X(k+1)=(0.31.562.684)T;在此過(guò)程中大家可能已經(jīng)發(fā)現(xiàn),在程序?qū)崿F(xiàn)該迭代過(guò)程時(shí)可以只占用X—個(gè)向量的空間,而不是普通矩陣迭代形式的至少兩倍向量空間(存儲(chǔ)X(k)與X(k+1)就能完成迭代。2.2.3程序?qū)嵱靡訫atlab語(yǔ)言為例,實(shí)現(xiàn)第k+1次迭代的程序如下:2.3矩陣法的改進(jìn)2.3.1sor迭代過(guò)程同樣地,由SOR迭代公式(3)以及(7)可知:因此,可把上式即SOR迭代過(guò)程表示如下:其中,I為與BJ階數(shù)相同的單位矩陣。因此,SOR迭代過(guò)程的求解過(guò)程計(jì)算量約為:2n2次乘除法(其中n2次為求解BJ所需計(jì)算量),比傳統(tǒng)的矩陣形式節(jié)約的計(jì)算量約為4n3/3+5n2-2n2=4n3/3+3n2。(9)式的迭代過(guò)程理解同(8)式。同樣用上例數(shù)據(jù)可以得到SOR迭代過(guò)程為(加速因子w=1.5):2.3.2基于雙向量空間的迭代其Matlab語(yǔ)言為例的程序?qū)崿F(xiàn)如下:同樣地,在程序?qū)崿F(xiàn)該迭代過(guò)程時(shí),它也可以只占用X一個(gè)向量的空間而不是普通矩陣迭代形式的至少兩倍向量空間(存儲(chǔ)X(k)與X(k+1)就能完成迭代。3求解過(guò)程的模式化新的矩陣迭代形式,結(jié)合了一般公式法計(jì)算上的精練和矩陣迭代形式的簡(jiǎn)潔,其特點(diǎn)如下:1)以最簡(jiǎn)單的Jacobi迭代法的迭代矩陣為基礎(chǔ),只要經(jīng)過(guò)簡(jiǎn)單的加減和數(shù)乘運(yùn)算就可得到Seidel和SOR的迭代過(guò)程,使得新算法形式的求解過(guò)程數(shù)學(xué)意義非常明確,表達(dá)形式也非常簡(jiǎn)潔,便于理解記憶;2)計(jì)算量小。和傳統(tǒng)的矩陣迭代形式的求解過(guò)程計(jì)算量有數(shù)量級(jí)的差別:Seidel迭代過(guò)程只需要約n2