ゲルシュゴリンの定理

数学におけるゲルシュゴリンの定理（ゲルシュゴリンのていり、英: Gershgorin circle theorem）は正方行列の固有値の大まかな存在範囲を示す^[1]。ゲルシュゴリンの円板定理とも呼ばれる^[2]。この定理を初めて発表したのはソヴィエトの数学者ゲルシュゴリン（英語版）である(Gershgorin 1931)。近年では^[いつ?]精度保証付き数値計算に用いられることもある^[3]^[4]。

定理の主張と証明

$n \times n$ -複素行列 $A$ の各成分を $a_{ij}$ とする。また各 $i \in {1, \dots, n}$ に対して

R_{i}=\sum _{j\neq {i}}\left|a_{ij}\right|

を第 $i$ -行の非対角成分の絶対和とする。このとき、 $a ii$ を中心とする半径 $R i$ の閉円板 $D (a ii, R i)$ をゲルシュゴリン円板 (Gershgorin disc) と言う。

定理 (Gershgorin): $A$ の任意の固有値は少なくとも一つのゲルシュゴリン円板 $D (a ii, R i)$ の上に載っている

証明. $A$ の固有値 $λ$ とそれに属する固有ベクトル $x = (x j)$ を取り、固有ベクトル $x$ のうち絶対値が最大となる成分の番号 $i \in {1, \dots, n} (| x i | = max j | x j |)$ を選ぶと $| x i | > 0$ である（さもなくば $x = 0$ である）。 $x$ は固有ベクトルゆえ $A x = λ x$ が成り立つが、これは各行について

\sum _{j}a_{ij}x_{j}=\lambda x_{i}

が成り立つということであり、対角成分を移行して

\sum _{j\neq i}a_{ij}x_{j}=\lambda x_{i}-a_{ii}x_{i}

が得られる。 $i$ を上で述べたように選んだならば、選び方から $x i \neq 0$ だから、両辺を $x i$ で割って絶対値を取れば

|\lambda -a_{ii}|=\left|{\frac {\sum _{j\neq i}a_{ij}x_{j}}{x_{i}}}\right|\leq \sum _{j\neq i}\left|{\frac {a_{ij}x_{j}}{x_{i}}}\right|\leq \sum _{j\neq i}|a_{ij}|=R_{i}

を得る。ここで最後の不等号が成り立つことは

\left|{\frac {x_{j}}{x_{i}}}\right|\leq 1\quad {\text{for }}j\neq i

による。

系: $A$ の固有値は $A$ の（行ではなく）列に対応して作られるゲルシュゴリン円板の上にも載っていなければならない。

証明は $A$ の代わりに $A$ の転置行列 $A T$ を考えればよい。

例: 対角行列に対しゲルシュゴリン円板はその行列のスペクトルそのものである。逆にゲルシュゴリン円板がスペクトルに一致するならば、その行列は対角行列である。

議論

この定理を解釈する一つの方法は、「複素正方行列の非対角成分のノルムが十分小さいならば、その行列の固有値は対角成分から「あまり遠くならない」」と考えることである。従って、非対角成分のノルムを減らすことで行列の固有値を近似するという方法論を考えることができる。もちろん、非対角成分を最小化する過程において対角成分は変わってしまうかもしれない。

良くある誤解は、各円盤の中に固有値が含まれるというものである。他と交わりの無い円盤についてはその円盤に固有値が含まれるが、他と交わりを持つ円盤は、固有値を含まない可能性がある．より精密には下の記述を参照。

さらに強い結果

ゲルシュゴリン円板の一つが、ほかのどの円板と交わらないならば、その円板はちょうど一つの固有値を含む。しかし、円板が他の円板と交わるならば、その円板は一つも固有値を含まないことが起こり得る（例えば

A={\begin{pmatrix}0&1\\4&0\end{pmatrix}}

や

A={\begin{pmatrix}1&-2\\1&-1\end{pmatrix}}

など）。一般の場合に、定理の主張を以下のように強めることができる。

定理: k 枚のゲルシュゴリン円板の合併が残りの n − k 枚の円板と交わらないならば、前者の円板の合併はちょうど k 個の A の固有値を含み、後者の円板には n − k 個の固有値を含む。

証明. A の対角成分と同じ成分を持つ対角行列 D に対し、

B(t)=(1-t)D+tA,\quad (t\in [0,1])

と置く。ここで B(t) の固有値が連続パラメタ t に関して連続であるという事実を認めることにして、円板の合併に属する固有値の何れかが他の円板へ移るならば、適当な t に対してその固有値はどの円板にも属さない状態が起きることを示す（そうすればゲルシュゴリンの定理に矛盾する）。

定理の主張は D = B(0) に対しては成り立つ。B(t) の対角成分は A のそれと同じであるから、ゲルシュゴリン円板の中心も共通だが、半径は A のときの t-倍される。従って B(t) に対して対応する k 枚の円板の合併は t の値に依らず残りの n − k 枚の円板と交わらない。各円板は閉だから、A の場合の両者の間の距離を d > 0 とすると、B(t) の場合のそれは t に関して単調減少だから、常に d よりも大きい。B(t) の固有値は t に関して連続だから、B(t) の k 枚の円板の合併に属する任意の固有値 λ(t) に対して、それと残りの n − k 枚の円板との距離もまた t に関して連続になる。明らかに d(0) ≥ d かつ、λ(1) は n − k 枚の円板の上にあると仮定したから d(1) = 0 である。故に 0 < d(t₀) < d となる 0 < t₀ < 1 が存在するが、これは λ(t₀) がゲルシュゴリン円板の外側にあることを意味し、これは不可能である。ゆえに λ(1) は k 枚の円板の合併に属し、定理は証明された。

応用

ゲルシュゴリンの定理は条件数の大きな行列 A に対する Ax = b (b はベクトル) の形の方程式を x について解くときに有用である。

この種の問題において、最終結果における誤差は初期データの誤差と A の条件数との積と同じオーダーになるのがふつうである。例えば b がコンマ以下6桁既知で A の条件数が 1000 ならば x はコンマ以下3桁の精度でしか保証できない。条件数が非常に大きければ、丸めによる非常に小さな誤差でさえ、その影響で拡大されてしまい、結果は意味のないものになってしまう。

A の条件数は減らした方がよいのだが、それは前処理で実行できる。つまり、P ≈ A⁻¹ となる行列 P を構成して方程式 PAx = Pb を x について解くのである。ここで A の本当の逆行列が使えればよいのだが、逆行列を求める問題は一般には非常に難しい。

さて、PA ≈ I で I は単位行列だから、PA の固有値はすべて 1 に近いはずである。ゲルシュゴリンの定理により、PA の任意の固有値はどの領域にあるのかわかっているから、P をどのように選べばよいかを大まかに評価することができる。

例

行列

A={\begin{bmatrix}10&-1&0&1\\0.2&8&0.2&0.2\\1&1&2&1\\-1&-1&-1&-11\end{bmatrix}}

の固有値を評価するためにゲルシュゴリンの定理を適用しよう。一行ごとに見て、対角成分 a_ii を円板の中心にとり、残りの成分は等式

\sum _{j\neq i}|a_{ij}|=R_{i}

に放り込んで円板の半径を求めると、四つの円板

D(10,2),\;D(8,0.6),\;D(2,3),\;D(-11,3)

が得られる。

後ろ二つの円板をより精緻にするために、列に関して同じように計算すれば $D(2,1.2)$ と $D(-11,2.2)$ が得られることに注意。

実際の固有値は 9.8218, 8.1478, 1.8995, -10.86 である。

出典

^ 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。
^ 長谷川秀彦ほか『固有値計算と特異値計算』丸善出版〈計算力学レクチャーコース〉、2019年。ISBN 978-4-621-30473-0。
^ 大石進一 et. al. (2018), 精度保証付き数値計算の基礎, コロナ社.
^ 大石進一：「精度保証付き数値計算」、コロナ社、（1999年）

参考文献

Gerschgorin, S. "Über die Abgrenzung der Eigenwerte einer Matrix." Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk 6, 749–754, 1931 [1]
Varga, R. S. Geršgorin and His Circles. Berlin: Springer-Verlag, 2004. ISBN 3-540-21100-4. Errata.
Richard S. Varga 2002 Matrix Iterative Analysis, Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
Golub, G. H.; Van Loan, C. F. (1996). Matrix Computations. Baltimore: Johns Hopkins University Press. pp. 320. ISBN 0-8018-5413-X

外部リンク

Gershgorin's circle theorem - PlanetMath.org（英語）
Eric W. Weisstein. "Gershgorin Circle Theorem." From MathWorld—A Wolfram Web Resource.
Semyon Aranovich Gershgorin biography at MacTutor

[Yamamoto1-1] 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。

[2] 長谷川秀彦ほか『固有値計算と特異値計算』丸善出版〈計算力学レクチャーコース〉、2019年。ISBN 978-4-621-30473-0。

[oishi-3] 大石進一 et. al. (2018), 精度保証付き数値計算の基礎, コロナ社.

[4] 大石進一：「精度保証付き数値計算」、コロナ社、（1999年）

[1]

[2]

[3]

[4]

定理の主張と証明

議論

さらに強い結果

応用

例

関連項目

出典

参考文献

外部リンク