ゲルシュゴリンの定理のソースを表示

[[数学]]における'''ゲルシュゴリンの定理'''（ゲルシュゴリンのていり、{{lang-en-short|''Gershgorin circle theorem''}}）は[[正方行列]]の[[固有値]]の大まかな存在範囲を示す<ref name="Yamamoto1">{{Cite book |和書 |author=山本哲朗 |title=数値解析入門 |edition=増訂版 |date=2003-06 |publisher=[[サイエンス社]] |series=サイエンスライブラリ 現代数学への入門 14 |ISBN=4-7819-1038-6}}</ref>。'''ゲルシュゴリンの円板定理'''とも呼ばれる<ref>{{Cite book|和書|author=長谷川秀彦ほか|title=固有値計算と特異値計算|year=2019|publisher=[[丸善出版]]|series=計算力学レクチャーコース|ISBN=978-4-621-30473-0}}</ref>。この定理を初めて発表したのは[[ソビエト連邦|ソヴィエト]]の数学者{{仮リンク|セムヨン・アラノヴィッチ・ゲルシュゴリン|en|Semyon Aranovich Gershgorin|label=ゲルシュゴリン}} である{{harv|Gershgorin|1931}}。近年では{{いつ|date=2024年8月24日 (土) 20:04 (UTC)}}[[精度保証付き数値計算]]に用いられることもある<ref name="oishi">[[大石進一]] et. al. (2018), 精度保証付き数値計算の基礎, コロナ社.</ref><ref>[[大石進一]]：「精度保証付き数値計算」、コロナ社、（1999年）</ref>。

== 定理の主張と証明 ==
{{math|''n''&nbsp;&times;&nbsp;''n''}}-[[複素数|複素]]行列 {{mvar|A}} の各成分を <math>a_{ij}</math> とする。また各 {{math|''i''&nbsp;∈&nbsp;{{mset|1,&nbsp;…,&nbsp;''n''}}}} に対して
: <math>R_i = \sum_{j\neq{i}} \left|a_{ij}\right|</math>
を第 {{mvar|i}}-行の非対角成分の[[絶対値|絶対]]和とする。このとき、{{math|''a''<sub>''ii''</sub>}} を中心とする半径 {{math|''R''<sub>''i''</sub>}} の閉円板 {{math|''D''(''a''<sub>''ii''</sub>,&nbsp;''R''<sub>''i''</sub>)}} を'''{{vanchor|ゲルシュゴリン円板}}''' ({{en|''Gershgorin disc''}}) と言う。

; 定理 (Gershgorin) : {{mvar|A}} の任意の[[固有値]]は少なくとも一つのゲルシュゴリン円板 {{math|''D''(''a''<sub>''ii''</sub>,&nbsp;''R''<sub>''i''</sub>)}} の上に載っている

証明. {{mvar|A}} の固有値 {{mvar|λ}} とそれに属する固有ベクトル {{math|1='''x'''&nbsp;=&nbsp;(''x''<sub>''j''</sub>)}} を取り、固有ベクトル {{math|'''x'''}} のうち[[絶対値]]が最大となる成分の番号 {{math|1=''i''&nbsp;∈&nbsp;{{mset|1,&nbsp;…,&nbsp;''n''}} ({{mabs|''x''<sub>''i''</sub>}}&nbsp;=&nbsp;max<sub>''j''</sub>&nbsp;{{mabs|''x''<sub>''j''</sub>}})}} を選ぶと {{math|{{mabs|''x''<sub>''i''</sub>}}&nbsp;>&nbsp;0}} である（さもなくば {{math|1='''x'''&nbsp;=&nbsp;0}} である）。{{math|'''x'''}} は固有ベクトルゆえ {{math|1=''A'''''x'''&nbsp;=&nbsp;λ'''x'''}} が成り立つが、これは各行について
: <math> \sum_j a_{ij} x_j = \lambda x_i</math>
が成り立つということであり、対角成分を移行して
: <math> \sum_{j \neq i} a_{ij} x_j = \lambda x_i - a_{ii} x_i</math>
が得られる。{{mvar|i}} を上で述べたように選んだならば、選び方から {{math|1=''x''<sub>''i''</sub>&nbsp;≠&nbsp;0}} だから、両辺を {{math|''x''<sub>''i''</sub>}} で割って絶対値を取れば
: <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</math>
を得る。ここで最後の不等号が成り立つことは
: <math>\left| \frac{x_j}{x_i} \right| \leq 1 \quad \text{for }j \neq i</math>
による。

; 系: {{mvar|A}} の固有値は {{mvar|A}} の（行ではなく）列に対応して作られるゲルシュゴリン円板の上にも載っていなければならない。
証明は {{mvar|A}} の代わりに {{mvar|A}} の転置行列 {{math|''A''<sup>T</sup>}} を考えればよい。
; 例: [[対角行列]]に対しゲルシュゴリン円板はその行列のスペクトルそのものである。逆にゲルシュゴリン円板がスペクトルに一致するならば、その行列は対角行列である。

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

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

== さらに強い結果 ==
[[#ゲルシュゴリン円板|ゲルシュゴリン円板]]の一つが、ほかのどの円板と交わらないならば、その円板はちょうど一つの固有値を含む。しかし、円板が他の円板と交わるならば、その円板は一つも固有値を含まないことが起こり得る（例えば
: <math>A=\begin{pmatrix}0&1\\4&0\end{pmatrix}</math> や <math>A=\begin{pmatrix}1&-2\\1&-1\end{pmatrix} </math>
など）。一般の場合に、定理の主張を以下のように強めることができる。

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

証明. ''A'' の対角成分と同じ成分を持つ対角行列 ''D'' に対し、
: <math>B(t)=(1-t)D + tA,\quad (t\in [0,1])</math>
と置く。ここで ''B''(''t'') の固有値が連続パラメタ ''t'' に関して連続であるという事実を認めることにして、円板の合併に属する固有値の何れかが他の円板へ移るならば、適当な ''t'' に対してその固有値はどの円板にも属さない状態が起きることを示す（そうすればゲルシュゴリンの定理に矛盾する）。

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

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

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

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

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

== 例 ==
[[File:Gershgorin Disk Theorem Example.svg|right|300px]]
行列
:<math> A = \begin{bmatrix}
 10  & -1 & 0   & 1\\
 0.2 & 8  & 0.2 & 0.2\\
 1   & 1  & 2   & 1\\
 -1  & -1 & -1  & -11
\end{bmatrix}</math>
の固有値を評価するためにゲルシュゴリンの定理を適用しよう。一行ごとに見て、対角成分 ''a''<sub>''ii''</sub> を円板の中心にとり、残りの成分は等式
: <math> \sum_{j\ne i} |a_{ij}| = R_i</math>
に放り込んで円板の半径を求めると、四つの円板
: <math> D(10,2), \; D(8,0.6), \; D(2,3), \; D(-11,3)</math>
が得られる。

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

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

== 関連項目 ==
* [[ペロン-フロベニウスの定理]]: 成分が非負値の場合
* {{ill|メツラー行列|en|Metzler matrix}}
* [[二重確率行列]]
* {{ill|ミュアヘッドの不等式|en|Muirhead's inequality}}
* {{仮リンク|フルヴィッツ行列|en|Hurwitz matrix}}

==出典==
{{reflist}}
== 参考文献 ==
* Gerschgorin, S. "Über die Abgrenzung der Eigenwerte einer Matrix." Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk 6, 749&ndash;754, 1931 [http://mi.mathnet.ru/eng/izv/y1931/i6/p749]
* [[Richard S. Varga|Varga, R. S.]] ''Geršgorin and His Circles.'' Berlin: [[Springer-Verlag]], 2004. ISBN 3-540-21100-4. [http://www.math.kent.edu/~varga/pub/corrections.pdf Errata].
* [[Richard S. Varga]] 2002 ''Matrix Iterative Analysis'', Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
* {{cite book |author=[[Gene H. Golub|Golub, G. H.]]; [[Charles F. Van Loan|Van Loan, C. F.]]|title=Matrix Computations |publisher=[[:en:Johns Hopkins University Press|Johns Hopkins University Press]] |location=Baltimore |year=1996 |pages=320 |isbn=0-8018-5413-X |oclc= |doi= |accessdate=}}

== 外部リンク ==
*{{planetmath reference|id=3709|title=Gershgorin's circle theorem}}
* Eric W. Weisstein. "[http://mathworld.wolfram.com/GershgorinCircleTheorem.html Gershgorin Circle Theorem]." From MathWorld&mdash;A Wolfram Web Resource. 
* Semyon Aranovich Gershgorin biography at [http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Gershgorin.html  MacTutor]
{{linear algebra}}
{{DEFAULTSORT:けるしゆこりんのていり}}
[[Category:線型代数学]]
[[Category:行列論]]
[[Category:数学に関する記事]]
[[Category:数値解析]]
[[Category:数学のエポニム]]