雅可比法

佇數值線性代數中，雅可比法（Jacobi Method）是一種解對角元素差不多攏是各行佮各列的絕對值上大的值的線性方程組的算法。求解出逐个對角元素並插入近似值。一直疊代直至收斂。這个算法是雅可比矩陣的精簡版。方法的名來是德國數學家卡爾 ・ 雅可比。

是咧講

予定一个 _ n×n _ 線性方程組

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

其中 :

$ A={ \ begin { bmatrix } a _ { 十一 } & a _ { 十二 } & \ cdots & a _ { 一 n } \ \ a _ { 二十一 } & a _ { 二十二 } & \ cdots & a _ { 二 n } \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \ a _ { n 一 } & a _ { n 二 } & \ cdots & a _ { nn } \ end { bmatrix } } , \ qquad \ mathbf { x }={ \ begin { bmatrix } x _ { 一 } \ \ x _ { 二 } \ \ \ vdots \ \ x _ { n } \ end { bmatrix } } , \ qquad \ mathbf { b }={ \ begin { bmatrix } b _ { 一 } \ \ b _ { 二 } \ \ \ vdots \ \ b _ { n } \ end { bmatrix } } . $

_ A _ 會當分解做對角的部份 _ D _ 佮賰的部份 _ R _ :

$ A=D + R \ qquad { \ text { 其中 } } \ qquad D={ \ begin { bmatrix } a _ { 十一 } & 零 & \ cdots & 零 \ \ 零 & a _ { 二十二 } & \ cdots & 零 \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \ 零 & 零 & \ cdots & a _ { nn } \ end { bmatrix } } , \ qquad R={ \ begin { bmatrix } 零 & a _ { 十二 } & \ cdots & a _ { 一 n } \ \ a _ { 二十一 } & 零 & \ cdots & a _ { 二 n } \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \ a _ { n 一 } & a _ { n 二 } & \ cdots & 零 \ end { bmatrix } } $

線性方程組會當重寫為 :

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

雅可比法是一種疊代方法。佇每一改疊代中，頂一改算出的x予人用佇正爿邊仔，用來算出倒爿的新的x。這个過程會當如下表示：

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

對逐个元素會當用以下公式：

$ x _ { i } ^ { ( k + 一 ) }={ \ frac { 一 } { a _ { ii } } } \ left ( b _ { i }-\ sum _ { j \ neq i } a _ { ij } x _ { j } ^ { ( k ) } \ right ) , \ quad i=一 , 二 , \ ldots , n . $

注意計算 _ x _ i ( _ k _ + 一 ) 需要x( _ k _ ) 中除了家己以外的逐个元素。無親像高斯-賽德爾疊代，咱袂用得 _ x _ i ( _ k _ + 一 ) 崁 _ x _ i ( _ k _ )，因為佇咧紲落來的計算中閣愛用著遮的值。這是雅可比和高斯-窒德爾方法上蓋顯示的差別，嘛是為啥物前者會當用並行算法而後者袂當的原因。上細需要的存儲空間是兩个長度為 _ n _ 彼个向量。

算法

選擇一个初初猜想值 $ x ^ { 零 } $

while 未收斂

for i  :=一 step until n do

$ \ sigma=零 $

for j  :=一 step until n do

if j  !=i then

$ \ sigma=\ sigma + a _ { ij } x _ { j } ^ { ( k 影一 ) } $

end if

end ( j-loop )

$ x _ { i } ^ { ( k ) }={ { \ left ( { b _ { i }-\ sigma } \ right ) } \ over { a _ { ii } } } $

end ( i-loop )

檢查敢是有收斂

end ( 未收斂的時陣繼續循環 )

收斂

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

$ \ rho ( D ^ { 影一 } R ) < 一 . $

保證收斂的條件是矩陣 _ A _ 為嚴格抑是無可約地對角占優矩陣。嚴格的行對角占優矩陣指對每一行，對角線頂懸的元素之絕對值大過其他的元素絕對值的佮，即

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

有時就算袂滿足現此時，雅可比法會當收斂。

舉例

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

$ A={ \ begin { bmatrix } 二 & 一 \ \ 五 & 七 \ \ \ end { bmatrix } } , \ b={ \ begin { bmatrix } 十一 \ \ 十三 \ \ \ end { bmatrix } } , \ quad x ^ { ( 零 ) }={ \ begin { bmatrix } 一 \ \ 一 \ \ \ end { bmatrix } } . $

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

$ D ^ { 影一 }={ \ begin { bmatrix } 二分之一 & 零 \ \ 零 & 七分之一 \ \ \ end { bmatrix } } , \ L={ \ begin { bmatrix } 零 & 零 \ \ 五 & 零 \ \ \ end { bmatrix } } , \ quad U={ \ begin { bmatrix } 零 & 一 \ \ 零 & 零 \ \ \ end { bmatrix } } . $

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

$ T={ \ begin { bmatrix } 二分之一 & 零 \ \ 零 & 七分之一 \ \ \ end { bmatrix } } \ left \ { { \ begin { bmatrix } 零 & 零 \ \ 鋪五 & 零 \ \ \ end { bmatrix } } + { \ begin { bmatrix } 零 & 影一 \ \ 零 & 零 \ \ \ end { bmatrix } } \ right \ }={ \ begin { bmatrix } 零 & 板空吱五 \ \ 抹空七一四 & 零 \ \ \ end { bmatrix } } . $

解出 C 為：

$ C={ \ begin { bmatrix } 二分之一 & 零 \ \ 零 & 七分之一 \ \ \ end { bmatrix } } { \ begin { bmatrix } 十一 \ \ 十三 \ \ \ end { bmatrix } }={ \ begin { bmatrix } 五鋪五 \ \ 一孵八五七 \ \ \ end { bmatrix } } . $

用計算出來 T 和 C，阮估計 $ x $ 為 $ x ^ { ( 一 ) }=Tx ^ { ( 零 ) } + C $

$ x ^ { ( 一 ) }={ \ begin { bmatrix } 零 & 板空吱五 \ \ 抹空七一四 & 零 \ \ \ end { bmatrix } } { \ begin { bmatrix } 一 \ \ 一 \ \ \ end { bmatrix } } + { \ begin { bmatrix } 五鋪五 \ \ 一孵八五七 \ \ \ end { bmatrix } }={ \ begin { bmatrix } 五曉空 \ \ 一孵一四三 \ \ \ end { bmatrix } } . $

繼續疊代得：

$ x ^ { ( 二 ) }={ \ begin { bmatrix } 零 & 板空吱五 \ \ 抹空七一四 & 零 \ \ \ end { bmatrix } } { \ begin { bmatrix } 五曉空 \ \ 一孵一四三 \ \ \ end { bmatrix } } + { \ begin { bmatrix } 五鋪五 \ \ 一孵八五七 \ \ \ end { bmatrix } }={ \ begin { bmatrix } 四堵九二九 \ \ 抹一爿七一三 \ \ \ end { bmatrix } } . $

這个過程一直重複一直到收斂（一直到 $ \ | Ax ^ { ( n ) }-b \ | $ 有夠細）。 這个例佇二十五遍疊代了後的解是

$ x={ \ begin { bmatrix } 七孵一一一 \ \ 抹三鋪二二二 \ end { bmatrix } } . $

外部連結

• 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