ゲルシュゴリンの定理

数学におけるゲルシュゴリンの定理（ゲルシュゴリンのていり、テンプレート:Lang-en-short）は正方行列の固有値の大まかな存在範囲を示す。ゲルシュゴリンの円板定理とも呼ばれる。この定理を初めて発表したのはソヴィエトの数学者テンプレート:仮リンク であるテンプレート:Harv。近年ではテンプレート:いつ精度保証付き数値計算に用いられることもある。

定理の主張と証明

テンプレート:Math-複素行列 テンプレート:Mvar の各成分を $a_{ij}$ とする。また各 テンプレート:Math に対して

$R_i=\sum _{j\ne i}\left|a_{ij}\right|$

を第 テンプレート:Mvar-行の非対角成分の絶対和とする。このとき、テンプレート:Math を中心とする半径 テンプレート:Math の閉円板 テンプレート:Math をテンプレート:Vanchor (テンプレート:En) と言う。

定理 (Gershgorin)

テンプレート:Mvar の任意の固有値は少なくとも一つのゲルシュゴリン円板 テンプレート:Math の上に載っている

証明. テンプレート:Mvar の固有値 テンプレート:Mvar とそれに属する固有ベクトル テンプレート:Math を取り、固有ベクトル テンプレート:Math のうち絶対値が最大となる成分の番号 テンプレート:Math を選ぶと テンプレート:Math である（さもなくば テンプレート:Math である）。テンプレート:Math は固有ベクトルゆえ テンプレート:Math が成り立つが、これは各行について

$\sum _j{a}_{ij}{x}_j=\lambda x_i$

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

$\sum _{j\ne i}{a}_{ij}{x}_j=\lambda x_i-a_{ii}{x}_i$

が得られる。テンプレート:Mvar を上で述べたように選んだならば、選び方から テンプレート:Math だから、両辺を テンプレート:Math で割って絶対値を取れば

$|\lambda -a_{ii}|=\left|\frac{\sum _{j\ne i}{a}_{ij}{x}_j}{x_i}\right|\le \sum _{j\ne i}\left|\frac{a_{ij}{x}_j}{x_i}\right|\le \sum _{j\ne i}|a_{ij}|=R_i$

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

$\left|\frac{x_j}{x_i}\right|\le 1\text{for }j\ne i$

による。

系

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

証明は テンプレート:Mvar の代わりに テンプレート:Mvar の転置行列 テンプレート:Math を考えればよい。

例

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

議論

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

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

さらに強い結果

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

$A=\left(\begin{array}{cc}0& 1\\ 4& 0\end{array}\right)$ や $A=\left(\begin{array}{cc}1& -2\\ 1& -1\end{array}\right)$

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

定理

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

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

$B(t)=(1-t)D+tA,(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=\left[\begin{array}{cccc}10& -1& 0& 1\\ 0.2& 8& 0.2& 0.2\\ 1& 1& 2& 1\\ -1& -1& -1& -11\end{array}\right]$

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

$\sum _{j\ne 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 である。

関連項目

• ペロン-フロベニウスの定理: 成分が非負値の場合
• テンプレート:Ill
• 二重確率行列
• テンプレート:Ill
• テンプレート:仮リンク

参考文献

• 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.
• テンプレート:Cite book

外部リンク

• テンプレート:Planetmath reference
• Eric W. Weisstein. "Gershgorin Circle Theorem." From MathWorld—A Wolfram Web Resource.
• Semyon Aranovich Gershgorin biography at MacTutor