Jacobi_method

在數值線性代數中，**雅可比法**（Jacobi Method）是一種解對角元素幾乎都是各行和各列的絕對值最大的值的線性方程組的算法。求解出每個對角元素並插入近似值。不斷疊代直至收斂。這個算法是雅可比矩陣的精簡版。方法的名字來源於德國數學家卡爾・雅可比。

## 描述

給定一個 _n×n_ 的線性方程組

　
: $A\mathbf {x} =\mathbf {b} $

其中:

　
: $A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.$

_A_ 可以分解成對角部分 _D_ 和剩餘部分 _R_:

　
: $A=D+R\qquad {\text{其 中}}\qquad D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}},\qquad R={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\a_{21}&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}}$

線性方程組可以重寫為:

　
: $D\mathbf {x} =\mathbf {b} -R\mathbf {x} $

雅可比法是一種疊代方法。在每一次疊代中，上一次算出的 **x** 被用在右側，用來算出左側的新的 **x**。這個過程可以如下表示：

　
: $\mathbf {x} ^{(k+1)}=D^{-1}(\mathbf {b} -R\mathbf {x} ^{(k)}).$

 
對每個元素可以用以下公式：

　
: $x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\neq i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n.$

注意計算 _x_i(_k_+1) 需要 **x**(_k_) 中除了自己之外的每個元素。 不像高斯 - 賽德爾疊代，我們不能用 _x_i(_k_+1) 覆蓋 _x_i(_k_)，因為在接下來的計算中還要用到這些值。這是雅可比和高斯 - 塞德爾方法最顯著的差別，也是為什麼前者可以用並行算法而後者不能的原因。最小需要的存儲空間是兩個長度為 _n_ 的向量。

## 算法

選擇一個初始猜想值 $x^{0}$ 

　
: while 未收斂 

　
: for i := 1 step until n do 

　
: $\sigma =0$

　
: for j := 1 step until n do 

　
: if j != i then

　
: $\sigma =\sigma +a_{ij}x_{j}^{(k-1)}$

　
: end if

　
: end (j-loop)

　
: $x_{i}^{(k)}={{\left({b_{i}-\sigma }\right)} \over {a_{ii}}}$

　
: end (i-loop)

　
: 檢查是否收斂

　
: end (未收斂時繼續循環)

## 收斂

標準的收斂情況是當疊代矩陣的譜半徑

　
: $\rho (D^{-1}R)<1.$

保證收斂的條件是矩陣 _A_ 為嚴格或不可約地對角占優矩陣。嚴格的行對角占優矩陣指對於每一行，對角線上的元素之絕對值大於其餘元素絕對值的和，即

　
: $\left|a_{ii}\right|>\sum _{j\neq i}{\left|a_{ij}\right|}.$

有時即使不滿足此條件，雅可比法仍可收斂。

## 舉例

一個形如 $Ax=b$ 的線性方程式，估計初始 $x^{(0)}$ ：

　
: $A={\begin{bmatrix}2&1\\5&7\\\end{bmatrix}},\ b={\begin{bmatrix}11\\13\\\end{bmatrix}},\quad x^{(0)}={\begin{bmatrix}1\\1\\\end{bmatrix}}.$

我們用上文描述的方程式 $x^{(k+1)}=D^{-1}(b-Rx^{(k)})$ 來估計 $x$ 。首先，將等式寫為 $D^{-1}(b-Rx^{(k)})=Tx^{(k)}+C$ 以方便計算，其中 $T=-D^{-1}R$ 和 $C=D^{-1}b$ 。注意 $R=L+U$ 中的 $L$ 和 $U$ 是 $A$ 的嚴格
遞增和遞減部分。變成如下數值：

　
: $D^{-1}={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}},\ L={\begin{bmatrix}0&0\\5&0\\\end{bmatrix}},\quad U={\begin{bmatrix}0&1\\0&0\\\end{bmatrix}}.$

令 $T=-D^{-1}(L+U)$ as

　
: $T={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}\left\{{\begin{bmatrix}0&0\\-5&0\\\end{bmatrix}}+{\begin{bmatrix}0&-1\\0&0\\\end{bmatrix}}\right\}={\begin{bmatrix}0&-0.5\\-0.714&0\\\end{bmatrix}}.$

解出 C 為：

　
: $C={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}{\begin{bmatrix}11\\13\\\end{bmatrix}}={\begin{bmatrix}5.5\\1.857\\\end{bmatrix}}.$

用計算出來的 T 和 C，我們估計 $x$ 為 $x^{(1)}=Tx^{(0)}+C$

　
: $x^{(1)}={\begin{bmatrix}0&-0.5\\-0.714&0\\\end{bmatrix}}{\begin{bmatrix}1\\1\\\end{bmatrix}}+{\begin{bmatrix}5.5\\1.857\\\end{bmatrix}}={\begin{bmatrix}5.0\\1.143\\\end{bmatrix}}.$

繼續疊代得：

　
: $x^{(2)}={\begin{bmatrix}0&-0.5\\-0.714&0\\\end{bmatrix}}{\begin{bmatrix}5.0\\1.143\\\end{bmatrix}}+{\begin{bmatrix}5.5\\1.857\\\end{bmatrix}}={\begin{bmatrix}4.929\\-1.713\\\end{bmatrix}}.$

這個過程一直重複直到收斂（直到 $\|Ax^{(n)}-b\|$ 足夠小）。這個例子在 25 次疊代之後的解是

　
: $x={\begin{bmatrix}7.111\\-3.222\end{bmatrix}}.$

## 一個用 Fortran 解的例子

## 參考文獻

## 外部連結

* Black, Noel; Moore, Shirley; and Weisstein, Eric W. Jacobi method. MathWorld.
* Jacobi Method from www.math-linux.com （頁面存檔備份，存於網際網路檔案館）
* Module for Jacobi and Gauss–Seidel Iteration
* Numerical matrix inversion （頁面存檔備份，存於網際網路檔案館）