ヤコビ法・ガウス・ザイデル法の収束

$A = D - L - U$ と分解して反復行列 $B_{J} = D^{- 1} (L + U)$ , $B_{GS} = (D - L)^{- 1} U$ を作り、そのスペクトル半径 $ρ (B)$ を固有値から求めて、 $ρ (B) < 1$ により反復法が収束するかを判定できる

前提

固有値と固有ベクトル（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）

この技能までの道筋（44 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）

説明

連立 1 次方程式 $A x = b$ を、近似解を何度も更新して解く方法がヤコビ法とガウス・ザイデル法です。この技能では、 $A = D - L - U$ と分解して反復行列 $B$ を作り、その固有値の絶対値の最大値（スペクトル半径） $ρ (B)$ を求めて、反復がどんな初期値からでも真の解に近づくか（収束するか）を、実際に反復を計算する前に判定します。大きな連立方程式を数値的に解く前に、その方法が使えるかを確かめる場面で使います。

なぜそうしてよいのか

$A$ の対角成分だけを並べた行列を $D$ 、対角より下の部分に $- 1$ を掛けたものを $L$ 、対角より上の部分に $- 1$ を掛けたものを $U$ とすると、 $A = D - L - U$ です（ここでは $A$ の対角成分 $a_{ii}$ がすべて $0$ でないとします）。 $A x = b$ は $D x = (L + U) x + b$ と書き直せるので、右辺に古い近似 $x^{(k)}$ を入れて新しい近似を作るのがヤコビ法 $x^{(k + 1)} = D^{- 1} (L + U) x^{(k)} + D^{- 1} b$ です。一方 $(D - L) x = U x + b$ と書き直し、計算済みの新しい成分をすぐ使うのがガウス・ザイデル法 $x^{(k + 1)} = (D - L)^{- 1} U x^{(k)} + (D - L)^{- 1} b$ です。 $D - L$ は対角成分が $a_{ii} \neq = 0$ の下三角行列なので正則です。どちらも $x^{(k + 1)} = B x^{(k)} + c$ の形で、 $B_{J} = D^{- 1} (L + U)$ 、 $B_{GS} = (D - L)^{- 1} U$ を反復行列といいます。

真の解 $x^{*}$ も $x^{*} = B x^{*} + c$ を満たすので、引き算すると誤差 $e^{(k)} = x^{(k)} - x^{*}$ は $e^{(k + 1)} = B e^{(k)}$ 、つまり $e^{(k)} = B^{k} e^{(0)}$ となります。 $B$ が固有ベクトル $p_{1}, \dots, p_{n}$ の基底をもつ場合、 $e^{(0)} = \sum c_{i} p_{i}$ と表せば $B^{k} e^{(0)} = \sum c_{i} λ_{i}^{k} p_{i}$ です。すべての固有値が $∣ λ_{i} ∣ < 1$ なら $λ_{i}^{k} \to 0$ で誤差は $0$ に近づき、逆に $∣ λ_{i} ∣ \geq 1$ の固有値があれば、その方向の成分をもつ初期値では誤差が消えません。

そこで固有値（複素数も含む）の絶対値の最大値を $ρ (B) = max_{i} ∣ λ_{i} ∣$ と定め、スペクトル半径と呼びます。「どんな初期値からでも収束する $⟺ ρ (B) < 1$ 」が成り立ちます（固有ベクトルの基底がとれない場合も成り立つことが知られています）。誤差はおおよそ 1 回ごとに $ρ (B)$ 倍になるので、 $ρ (B)$ が小さいほど速く収束します。

手順

対角成分 $a_{ii}$ がすべて $0$ でないことを確かめ、 $A = D - L - U$ と分解する。 $D$ は対角部分、 $L$ は狭義下三角部分の符号を反転したもの、 $U$ は狭義上三角部分の符号を反転したもの。
反復行列を作る。ヤコビ法は $B_{J} = D^{- 1} (L + U)$ （ $D^{- 1}$ は対角成分を $1/ a_{ii}$ にした行列）、ガウス・ザイデル法は $(D - L ∣ E)$ を掃き出して $(D - L)^{- 1}$ を求め、 $B_{GS} = (D - L)^{- 1} U$ を計算する。
特性方程式 $det (B - λ E) = 0$ を解いて、 $B$ の固有値を複素数も含めてすべて求める。
スペクトル半径 $ρ (B) = max_{i} ∣ λ_{i} ∣$ を求める（複素数 $p + q i$ の絶対値は $p^{2} + q^{2}$ ）。
$ρ (B) < 1$ ならどんな初期値からでも収束、 $ρ (B) \geq 1$ なら収束しない初期値があると判定する。

例題

$A = (4213)$ を係数行列とする連立 1 次方程式 $A x = b$ にガウス・ザイデル法を用いる。反復行列 $B_{GS}$ のスペクトル半径 $ρ (B_{GS})$ を求めよ。

例題の解答

手順 1：対角成分は $4, 3$ でともに $0$ でない。 $D = (4003)$ 、 $L = (0 - 2 00)$ 、 $U = (00 - 1 0)$ とすると $A = D - L - U$ 。

手順 2： $D - L = (4203)$ 。 $(D - L ∣ E) = (42031001)$ の第 1 行を $\frac{1}{4}$ 倍し、第 2 行から第 1 行の 2 倍を引き、第 2 行を $\frac{1}{3}$ 倍すると $(1001 \frac{1}{4} - \frac{1}{6} 0 \frac{1}{3})$ 。よって $(D - L)^{- 1} = (\frac{1}{4} - \frac{1}{6} 0 \frac{1}{3})$ で、 $B_{GS} = (D - L)^{- 1} U = (00 - \frac{1}{4} \frac{1}{6})$ 。

手順 3： $det (B_{GS} - λ E) = (- λ) (\frac{1}{6} - λ) = 0$ より、固有値は $λ = 0, \frac{1}{6}$ 。

手順 4： $ρ (B_{GS}) = max {0, \frac{1}{6}} = \frac{1}{6}$ 。

手順 5： $\frac{1}{6} < 1$ なので、ガウス・ザイデル法はどんな初期値からでも収束する（誤差はおよそ 1 回ごとに $\frac{1}{6}$ 倍になる）。

答え: $\frac{1}{6}$

よくある誤り

$L, U$ を $A$ の下側・上側の成分そのまま（符号を反転せず）にして $B_{J} = D^{- 1} (L + U)$ を計算してしまう誤り。 $A = D - L - U$ の約束では $L, U$ は符号を反転したものなので、例えば $A = (4213)$ なら正しくは $B_{J} = (0 - \frac{2}{3} - \frac{1}{4} 0)$ 。符号を誤ると一般には固有値も変わる。
スペクトル半径を固有値の最大値としてしまう誤り。例えば固有値が $- 2, \frac{1}{2}$ なら $ρ (B) = \frac{1}{2}$ ではなく、絶対値の最大値をとって正しくは $ρ (B) = 2$ （収束しない）。
複素数の固有値を無視したり、実部だけで判定したりする誤り。例えば固有値が $\frac{1 \pm i}{2}$ なら絶対値は $\frac{1}{4} + \frac{1}{4} = \frac{1}{2}$ で、正しくは $ρ (B) = \frac{1}{2} < 1$ と求めて収束と判定する。
反復行列 $B$ ではなく係数行列 $A$ の固有値で判定してしまう誤り。誤差は $e^{(k)} = B^{k} e^{(0)}$ で変化するので、正しくは $B_{J} = D^{- 1} (L + U)$ や $B_{GS} = (D - L)^{- 1} U$ の固有値から $ρ (B) < 1$ を調べる。また $ρ (B) = 1$ の場合は収束と判定できない。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

ヤコビ法・ガウス・ザイデル法の収束

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題