雅可比法

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

描述

給定一個n×n的線性方程組

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

其中:

${\displaystyle 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:

${\displaystyle 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}}}$

線性方程組可以重寫為:

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

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

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

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

${\displaystyle 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的向量。

算法

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

while 未收斂

for i := 1 step until n do

${\displaystyle \sigma =0}$

for j := 1 step until n do

if j != i then

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

end if

end (j-loop)

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

end (i-loop)

檢查是否收斂

end (未收斂時繼續循環)

收斂

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

${\displaystyle \rho (D^{-1}R)<1.}$^[1]

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

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

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

舉例

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

${\displaystyle 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}}.}$

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

${\displaystyle 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}}.}$

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

${\displaystyle 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為：

${\displaystyle 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，我們估計${\displaystyle x}$為${\displaystyle x^{(1)}=Tx^{(0)}+C}$

${\displaystyle 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}}.}$

繼續迭代得：

${\displaystyle 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}}.}$

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

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

一個用Fortran解的例子

subroutine solve(A,b,x,x0,n)
implicit real*8(a-z)
integer::n,imax=200
integer::i,j,k
real*8::tol=1d-15
real*8::A(n,n),b(n),x(n),x0(n),x1(n),x2(n)

write(102,501)
501 format('Jacobi iteration',/)

x1=x0

do k=1,imax
    do i=1,n
        s=0
        do j=1,n
            if (j==i) cycle           
            s=s+A(i,j)*x1(j)      
        enddo   
        x2(i)=(b(i)-s)/A(i,i)  
    enddo
    ! the following step check if convergence is reached
    dx2=0
    do i=1,n
        dx2=dx2+(x1(i)-x2(i))**2
    enddo
    dx2=dsqrt(dx2)
    if (dx2<tol) exit
    x1=x2
    write(102,502)k,x1 ! record the iteration process
    502 format(1x,i3,<n>(1x,1pd25.15))
enddo
x=x2
end subroutine solve

program  main
implicit real*8(a-z)
integer,parameter::n=3
real*8 ::A(n,n),b(n),x(n),x0(n)

open(unit=101,file='result.txt')
open(unit=102,file='it_result.txt')

x0=(/0d0,0d0,0d0/) ! initial guess
b=(/9d0,7d0,6d0/)
A=reshape((/10,-1,0,-1,10,-4,0,-2,10/),(/3,3/))

call solve(A,b,x,x0,n) ! solve Ax=b
  
write(101,501)'x(1)','x(2)','x(3)',x
501 format('jacobi result',//,<n>(1x,a25),/,<n>(1x,1pd25.15))

end program main

參考文獻

1. [1] （頁面存檔備份，存於網際網路檔案館）,解線性方程組的迭代法

外部連結

• 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 （頁面存檔備份，存於網際網路檔案館）