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

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

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