2.2 Jacobi 法 -- 温故知新

1960 年代まで主流であった Jacobi 法について簡単に説明しよう。 これは実対称行列を $2$ 次元の回転変換により変形していって、対角成分以外 の成分の絶対値を小さくしていくというものであり、行列のサイズ $N$ が $10$ 程度の小さなものであれば現在でも実用的である。

なぜ「対角成分以外の成分の絶対値を小さくしていく」のか？これについて 説明しよう。まず次の定理は簡単であるが重要である。

一般の行列の場合も次の定理が成り立つ。 おおざっぱにまとめると「行列の固有値は対角成分に近く、 そのずれは非対角成分の大きさによる」。

証明. $A x=\lambda x$ , $x=(x_1,\ldots,x_N)\ne 0$ とする。今 $x$ の絶対値最大 の成分を $x_k$ とする:

$$\max_{i=1,2,\ldots,N}\vert x_{i}\vert=\vert x_k\vert.$$

方程式 $A x=\lambda x$ の第 $k$ 成分を書くと

$$\sum_{j=1}^N a_{k j}x_j=\lambda x_k.$$

これから

$$(\lambda - a_{k k})x_k=\sum_{1\le j\le N,j\ne k}a_{k j}x_j.$$

(以下 $1\le j\le N,j\ne k$ を単に $j\ne k$ と書くことにする。) よって

$$\vert\lambda-a_{k k}\vert\le \sum_{j\ne k}\vert a_{k j}\vert\left\vert\frac{x_j}{x_k}\right\vert \le \sum_{j\ne k}\vert a_{k j}\vert,$$

したがって $\lambda\in \Delta_k\subset\dsp \bigcup_{i=1}^N \Delta_i$ .

つぎに

$$D=\diag(a_{11},\cdots,a_{NN}), \quad A_t=(1-t)D+t A$$   $$\mbox{($t\in[0,1]$)}$$

とおくと、$A_t$ に対する円板は

$$\Delta_i(t)=\{z\in\C; \vert z-a_{ii}\vert\le t\sum_{j\ne i}\vert a_{ij}\vert\}$$

である。$A_i$ の固有値は $t$ に ついて連続的に変化し、$t=0$ のとき $\Delta_i(0)=\{a_{ii}\}$ にそれぞれ重 複個数だけある。$t$ を増加させれば、いくつかの円板が拡大して合流するが、 $k$ 個の $\Delta_{i}(t)$ が合流すれば、その中に $A_t$ の $k$ 個の固有値 が存在する。ゆえに $t=1$ に達したとき、$\Delta_i$ の $k$ 個が連結成分を なせば、その中に $A_1=A$ の $k$ 個の固有値が存在する。 $\qedsymbol$ $\qedsymbol$

証明. $0\not\in \dsp\bigcup_{i=1}^N\Delta_i$ より、 0 は $A$ の固有値ではない。ゆえに $A$ は正則である。$\qedsymbol$ $\qedsymbol$

なぜか今のカリキュラムの盲点となってしまって、 紹介されることがないが、 「代数方程式の根は方程式の係数の連続関数である」 行列の固有方程式の係数は、行列の成分の連続関数であることは明らかだから、 「行列の固有値は行列の成分の連続関数である」。 Gerschgorin の定理はあざやかに連続性を見せてくれる。