ヤコビ反復法が収束するための必要十分条件（2次元の場合）

ヤコビ法（ヤコビの反復法）を使って線形方程式

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

の求解する時の収束条件について、世間一般では「係数行列Aが対角優位であること」ぐらいしか書いていない。しかしこれは十分条件であって、つまり、対角優位でなくても収束することがある。実際、

$\displaystyle A = \begin{pmatrix} 4 & 2 \\ 3 & 2 \end{pmatrix}$

という係数行列は、2行目で対角成分2<非対角成分3なので対角優位ではないが、実際には収束する。

では必要十分条件はなんだろうか？一般の場合は難しそうなのでとりあえず2次元で考えてみたところ導出できたのでメモがてら。

結論だけ先に書くと、2次元でヤコビ反復法が収束するための必要十分条件は、対角成分の積の絶対値が非対角成分の積の絶対値より大きいことだった。つまり

$\displaystyle A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$

に対して、 $\left| ad \right| > \left| bc \right|$ であれば、ヤコビ反復法は収束するということである。

以下証明（というか考え方）。

ヤコビ法の基本
バナッハの不動点定理は必要でない
本当の必要十分条件
具体例

ヤコビ法の基本

まず基本的なところから。ヤコビ法は、A=L+D+U（LとUは下/上三角行列、Dは対角行列）に分解して

$\displaystyle \mathbf{x^{\left(k+1\right)}} = D^{-1} \left[ \mathbf{b} - \left(L+U \right) \mathbf{x^{\left(k\right)}} \right]$

と反復する方法のことである。これを繰り返して、 $\mathbf{x^{\left(k+1\right)}}=\mathbf{x^{\left(k\right)}}$ になった時、この $\mathbf{x}$ は方程式の解と一致する。

言い換えれば、更新量 $\mathbf{{\Delta x}_{k, k+1}} = \mathbf{x^{\left(k+1\right)}}-\mathbf{x^{\left(k\right)}} = \mathbf{0}$ になった時＝不動点に到達することが、ヤコビ反復法が収束する必要十分条件であり、その点が解となる。

ここで

$\displaystyle \begin{align*} \mathbf{x^{\left(k+1\right)}} &= D^{-1} \left[ \mathbf{b} - \left(L+U \right) \mathbf{x^{\left(k\right)}} \right] \\ \mathbf{x^{\left(k\right)}} &= D^{-1} \left[ \mathbf{b} - \left(L+U \right) \mathbf{x^{\left(k-1\right)}} \right] \\ \therefore \mathbf{{\Delta x}_{k, k+1}} & = \mathbf{x^{\left(k+1\right)}}-\mathbf{x^{\left(k\right)}} \\ &= -D^{-1} \left(L+U \right) \left( \mathbf{x^{\left(k\right)}} - \mathbf{x^{\left(k-1\right)}} \right) \\ &= -D^{-1} \left(L+U \right) \mathbf{{\Delta x}_{k-1, k}} \\ \end{align*}$

であるので、この更新行列＝自己線形写像 $M=-D^{-1} \left(L+U \right)$ の性質によって、収束するかどうかが決まる。
この $M$ は、例えば2次元の場合

$\displaystyle M = -\begin{pmatrix} 1/a & 0 \\ 0 & 1/d \end{pmatrix} \begin{pmatrix} 0 & b \\ c & 0 \end{pmatrix}= -\begin{pmatrix} 0 & b/a \\ c/d & 0 \end{pmatrix}$

となる。

これを用いると、k回目の反復における更新量は

$\displaystyle \mathbf{{\Delta x}_{k, k+1}} = M^k \mathbf{{\Delta x}_{0, 1}} \\$

と書ける。

バナッハの不動点定理は必要でない

さて、ここで、慣れている人なら「自己写像の不動点判定だからバナッハの不動点定理（Mがつねに縮小写像であれば不動点が存在する）を使えば良いな」と思い当たる人がいるかもしれない。
しかしこれは正しくない。なぜなら、バナッハの不動点定理は、不動点が存在するための十分条件であって必要条件ではないからである。少し脇道に逸れるが先にそれを解説しておく。

バナッハの不動点定理を適用した時、その判定条件は

$\displaystyle \begin{gather*} \forall \mathbf{\Delta x} \neq \mathbf{0} & \sup \frac{\left| M\mathbf{\Delta x} \right|}{\left|\mathbf{\Delta x}\right|} < 1 \\ \iff \\ \forall k & \left| \mathbf{{\Delta x}_{k, k+1}} \right| < \left| \mathbf{{\Delta x}_{k-1, k}} \right| \end{gather*}$

となる。言い換えれば「次の更新量の大きさは、必ず前の更新量より小さい」ことを要請することになる。

ここで2次元の場合を考えると

$\displaystyle \begin{align*} \left| M\mathbf{\Delta x} \right| - \left|\mathbf{\Delta x}\right| &= \left| -\begin{pmatrix} 0 & b/a \\ c/d & 0 \end{pmatrix} \begin{pmatrix} \Delta x_0 \\ \Delta x_1 \end{pmatrix} \right| - \left| \begin{pmatrix} \Delta x_0 \\ \Delta x_1 \end{pmatrix} \right| \\ &= \sqrt{ \left( c/d \Delta x_0 \right)^2 + \left( b/a \Delta x_1 \right)^2 } - \sqrt{{\Delta x_0}^2 + {\Delta x_1}^2} < 1 \end{align*}$

$\displaystyle \begin{gather*} \therefore \left( c/d \Delta x_0 \right)^2 + \left( b/a \Delta x_1 \right)^2 < {\Delta x_0}^2 + {\Delta x_1}^2 \\ \left( c^2/d^2 - 1 \right) {\Delta x_0}^2 + \left( b^2/a^2 - 1 \right) {\Delta x_1}^2 < 0 \end{gather*}$

となる。これを任意の ${\Delta x_0}, {\Delta x_1}$ に対して成立させるためには、それぞれの係数が負でなければならないので

$\displaystyle \begin{align*} b^2/a^2 - 1 < 0 & \therefore \left| b \right| < \left| a \right| \\ c^2/d^2 - 1 < 0 & \therefore \left| c \right| < \left| d \right| \end{align*}$

となって、対角成分a,dに対して非対角成分c,dの大きさが小さいことになる。
すなわち（少なくとも2次元の場合において）「バナッハの不動点定理を満たすこと」は「対角優位であること」と同値となる。

しかし冒頭に挙げた反例のように、対角優位でなくてもヤコビ法が収束することがある。
ということで、バナッハの不動点定理は（ヤコビ法の）収束における必要条件ではないことが分かる。

本当の必要十分条件

さて話を戻して、では収束の必要十分条件はなにか？を考える。

冒頭の収束の定義に立ち返って見れば、必要十分条件は「何度か反復していれば不動点に到達する」ことだった。すなわち

$\displaystyle \lim_{k \to \infty} \mathbf{\Delta x_{k, k+1}} = \lim_{n \to \infty} M^n \mathbf{\Delta x_{0, 1}} = \mathbf{0}$

であるが、これを達成するためには「何度か反復していれば、必ず今より更新量が小さくなる」ことが必要十分*1で、正確には

$\displaystyle \forall k \exists n \quad \left| \mathbf{\Delta x_{k-1, k}} \right| < \left| M^n \mathbf{\Delta x_{k-1+n, k+n}} \right|$

が、収束のための必要十分条件であることが分かる。
こう考えてみると、バナッハの不動点定理を使った場合の惜しいところは、更新量が小さくなるのが「必ず直後が」になっているところだと分かる（実際には直後でなくても、その先のどこかで小さくなれば良いということ）。

では、この $M^n$ を考えたい。先に述べた通り

$\displaystyle M = -\begin{pmatrix} 0 & b/a \\ c/d & 0 \end{pmatrix}$

であるが、一般的に

$\displaystyle {\begin{pmatrix} 0 & p \\ q & 0 \end{pmatrix}}^2 = \begin{pmatrix} p q & 0 \\ 0 & p q \end{pmatrix}$

なので、

$\displaystyle M^{2n} = \begin{pmatrix} \left(bc/ad\right)^n & 0 \\ 0 & \left(bc/ad\right)^n \end{pmatrix}$

という対角行列になることが分かる。対角行列なので、この $\left| bc/ab \right|<1$ であれば（少なくとも2回反復した時に）更新量の大きさが小さくなり、それ以外の時には小さくならないことが分かる。

ということで、変形すると判定式は $\left| ad \right|>\left| bc \right|$ であり、この時ヤコビ法における更新量が小さくなる＝ヤコビ法は収束することになって、冒頭に述べた結論が示された。

また、この対角成分の積と非対角成分の積の比 $\left| bc/ab \right|$ は実際の縮小率を表しているので、この比が小さければ小さいほど、更新量は1回の反復で小さくなる＝収束速度が速いということになる。
具体的には、2回の反復で更新量は $\left| bc/ab \right|$ 倍に小さくなって、対角成分(ab)が大きければ大きいほど（つまり対角優位なほど）収束性が良いという、（既知の）法則を得られる。

具体例

最後に、具体例を少し載せる。冒頭の例である

$\displaystyle A = \begin{pmatrix} 4 & 2 \\ 3 & 2 \end{pmatrix}$

は対角優位ではないが、 $\left| ad \right| - \left| bc \right| = 4 \times 2 - 2 \times 3 = 8-6 = 2 > 0$ なので、冒頭でも述べた通り収束する。

一方、0,1成分を3に変化させた

$\displaystyle A = \begin{pmatrix} 4 & 3 \\ 3 & 2 \end{pmatrix}$

は、 $\left| ad \right| - \left| bc \right| = 4 \times 2 - 3 \times 3 = 8-9 = -1 \le 0$ なので、収束しない（発散する）。

なお、行列式が零、つまり $\det A = ad - bc = 0$ である場合、例えば

$\displaystyle A = \begin{pmatrix} 4 & 2 \\ 6 & 3 \end{pmatrix}$

に逆行列は存在しないことが高校数学レベルで既知だが、ヤコビ法にかけた場合も当然発散する。

しかし、注意すべき点として、今回の判定式は絶対値で判定するため、行列式が零でなくても係数行列に負がある場合、例えば

$\displaystyle A = \begin{pmatrix} 4 & -2 \\ 6 & 3 \end{pmatrix}$

は、行列式が $\det A = 4 \times 3 - (-2) \times 6 = 24 \neq 0$ だが、判定式では $\left| ad \right| - \left| bc \right| = 4 \times 3 - 2 \times 6 = 12-12 = 0 \le 0$ となって、収束しない（振動する）。

また、判定式をわずかに上回って正のような場合、例えば

$\displaystyle A = \begin{pmatrix} 4 & 2 \\ 6 & 3.1 \end{pmatrix}$

では、収束がかなり遅い（この例では、解(10.5, -20)に近づいてはいるので、収束はしそう）。

このことから、確かに（2次元の）ヤコビ反復法においては、対角成分と非対角成分の比が収束の速度と相関して、非対角成分が小さいほど、つまり対角優位なほど柔らかい行列と言えそうなことが分かる。

このあとは、引き続き、3次元以上について調べてみようと思う。

*1:厳密に考えると、発散はしなくてもなんか振動がありそうな気もしないでもないけど、感覚的には多分なさそう＆あんまりそこまで変なのは考えないことにしておきます。だれかこの辺り証明しておいてほしい

aokomoriuta's blog

青子守歌のブログ

ヤコビ反復法が収束するための必要十分条件（2次元の場合）

ヤコビ法の基本

バナッハの不動点定理は必要でない

本当の必要十分条件

具体例