之前我在博客里介紹過牛頓-拉弗遜迭代法，對數(shù)據(jù)挖掘技術(shù)熟悉的同學(xué)應(yīng)該還知道有梯度下降法（其實也是一種迭代算法）。今天剛好有朋友和我討論泊松圖像融合算法，我說我過去文章里給出的是最原始、最直觀的實現(xiàn)算法。對于理解泊松融合的原理比較有幫助，但是效率可能并不理想。印象中，泊松融合是有一個以矩陣為基礎(chǔ)的快速算法的。但是過去我淺嘗輒止了，也沒深究，今天剛好再提到，小看了一下，似乎涉及高斯-塞德爾迭代法。好吧，博主君暫且把知道的這部分內(nèi)容做個介紹吧。特別說明：以下內(nèi)容主要取材自《數(shù)值方法（MATLAB版）（第四版）》馬修斯等著，電子工業(yè)出版社2010年出版發(fā)行。

一、雅各比迭代法

考慮如下方程組：

4x?y+z=74x?8y+z=?21?2x+y+5z=15
上述方程可表示成如下形式：
x=7+y?z4y=21+4x+z8z=15+2x?y5
這樣就提出了下列雅可比迭代過程：

xk+1yk+1zk+1=7+yk+zk4=21+4xk+zk8=15+2xk?yk5(3)

如果從P0=(x0,y0,z0)=(1,2,2)開始，則上式中的迭代將收斂到解(2,4,3)。

將x0=1,y0=2和z0=2代入上式中每個方程的右邊，即可得到如下新值：

x1=7+2?24=1.75y1=21+4+28=3.375z1=15+2?25=3.00

新的點P1=(1.75,3.375,3.00)比P1更接近(2,4,3)。使用迭代過程（3）生成點的序列{P0}將收斂到解(2,4,3)。

這個過程稱為雅可比迭代，可用來求解某些類型的線性方程組。從上表中可以看出，經(jīng)過19步選代，選代過程收斂到一個精度為9 位有效數(shù)字的近似值（2.00000000， 4.00000000， 3.00000000）。但有時雅可比迭代法是無效的。通過下面的例子可以看出，重新排列初始線性方程組后，應(yīng)用雅可比迭代法可能會產(chǎn)生一個發(fā)散的點的序列。

設(shè)重新排列的線性方程組如下：

?2x+y+5z=154x?8y+z=?214x?y+z=7

這些方程可以表示為如下形式：

x=?15+y?5z2y=21+4x+z8z=7?4x+y5

這可以用如下雅可比迭代過程求解：

xk+1yk+1zk+1=?15+yk+5zk2=21+4xk+zk8=7?4xk+yk

如果從P0=(x0,y0,z0)=(1,2,2)開始，則上式中的迭代將對解(2,4,3)發(fā)散。將x0=1，y0=2和z0=2帶入上式中每個方程的右邊，即可得到新值x1，y1和z1：

x1=?15+2+102=?1.5y1=21+4+28=3.375z1=7?4+2=5.00

新的點P1=(?1.5,3.375,5.00)比P0更遠(yuǎn)地偏離(2,4,3)。使用上述迭代過程生成點的序列是發(fā)散的。

二、高斯-塞德爾迭代法

有時候通過其他方面可以加快迭代的收斂速度。觀察由雅可比迭代過程（3）產(chǎn)生的三個序列{xk}，{yk}和{zk}，它們分別收斂到2，4和3。由于xk+1被認(rèn)為是比xk更好的x之近似值，所以在計算yk+1時用xk+1來替換xk是合理的。同理，可用xk+1和yk+1計算zk+1。下面的例子演示了對上述例子中給出的方程組使用上述方法的情況。

設(shè)給定上述線性方程組并利用高斯-塞德爾（Gauss-Seidel）迭代過程求解：

xk+1=7+yk?zk4yk+1=21+4xk+1+zk8zk+1=15+2xk+1?yk+15

如果從P0=(x0,y0,z0)=(1,2,2)開始，用上式中的迭代可收斂到解(2,4,3)。
將y0=2和z0=2代入上式第一個方程可得

x1=7+2?24=1.75

將x1=1.75和z0=2代入第二個方程可得

y1=21+4×1.75+28=3.75

將x1=1.75和y1=3.75代入第三個方程可得

z1=15+2×1.75?3.755=2.95

新的點P1=(1.75,3.75,2.95)比P0更接近解(2,4,3)，而且比之前例子中的值更好。用迭
代（7）生成序列{Pk收斂到(2,4,3)。

正如前面討論的，應(yīng)用雅各比迭代法計算有時可能是發(fā)散的。所以有必要建立一些判定條件來判斷雅可比迭代是否收斂。在給出這個條件之前，先來看看嚴(yán)格對角占優(yōu)矩陣的定義。
設(shè)有N×N維矩陣A，如果

其中，i是行號，j是列號，則稱該矩陣是嚴(yán)格對角占優(yōu)矩陣。顯然，嚴(yán)格對角占優(yōu)的意思就是指對角線上元素的絕對值不小于所在行其他元素的絕對值和。

a11x1+a12x2+...+a1jxj+...+a1NxNa21x1+a22x2+...+a2jxj+...+a2NxN......aj1x1+aj2x2+...+ajjxj+...+ajNxN......aN1x1+aN2x2+...+aNjxj+...+aNNxN=b1=b2=bj=bN

設(shè)第k點為Pk=(x(k)1,x(k)2,...,x(k)j,...,x(k)N,)，則下一點為Pk+1=(x(k+1)1,x(k+1)2,...,x(k+1)j,...,x(k+1)N,)。向量Pk的上標(biāo)(k)可用來標(biāo)識屬于這一點的坐標(biāo)。迭代公式根據(jù)前面的值(x(k)1,x(k)2,...,x(k)j,...,x(k)N,)，使用上述線性方程組中第j行求解x(k+1)j。

雅可比迭代：

x(k+1)j=bj?aj1x(k)1?...?ajj?1x(k)j?1?ajj+1x(k)j+1?...?ajNx(k)Najj

其中j=1,2,...,N。
雅可比迭代使用所有舊坐標(biāo)來生成所有新坐標(biāo)，而高斯-塞德爾迭代盡可能使用新坐標(biāo)得到更新的坐標(biāo)。

高斯-塞德爾迭代：

x(k+1)j=bj?aj1x(k+1)1?...?ajj?1x(k+1)j?1?ajj+1x(k)j+1?...?ajNx(k)Najj

其中j=1,2,...,N。

下面的定理給出了雅可比迭代收斂的充分條件。
（雅可比選代） 設(shè)矩陣A具有嚴(yán)格對角優(yōu)勢，則AX=B有惟一解X=P。利用前面給出的迭代式可產(chǎn)生一個向量序列{Pk}，而且對于任意初始向量P0，向量序列都將收斂到P。

當(dāng)矩陣A具有嚴(yán)格對角優(yōu)勢時，可證明高斯-塞德爾迭代法也會收斂。在大多數(shù)情況下，高斯-塞德爾迭代法比雅可比迭代法收斂得更快，因此通常會利用高斯-塞德爾迭代法。但在某些情況下，雅可比迭代會收斂，而高斯-塞德爾迭代不會收斂。

轉(zhuǎn)載地址：http://blog.csdn.net/baimafujinji/article/details/50582462（如有侵權(quán)，聯(lián)系我，我會及時撤掉）

總結(jié)

以上是生活随笔為你收集整理的Jacobi迭代法与Gauss-Seidel迭代法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。