読者です 読者をやめる 読者になる 読者になる

300億円欲しい

メジャーリーグのデータ解析します

Gershgorinの定理で遊びたい

R 線形代数

行列の固有値に関する定理, Gerschgorinの定理があります. スペル分かりません.

Gerschgorin? Gershgorin? 2通り観測されます.
正しいほうが分かり次第, 修正します.

内容を整理して, 図示して動画も作りたいと思います.

Gershgorinの定理

弱い形から.

Gershgorinの定理(弱い形)


$n$次正方行列$A = [a_{ij}]$, $(i,j = 1,...,n)$の任意の固有値$\lambda$は,
\[
C_i =\{z \in \mathbb{C} \ \mid \ \left|z - a_{ii} \right| \leq r_i \}, \ r_i = \sum_{j\neq i } \left|a_{ij} \right|
\]
で定義される, 複素平面上の$n$個の円盤$C_i$(中心がAの対角成分$a_{ii}$, 半径は対角成分を除いた絶対値行和)の合併集合$\cup _{i=1} ^ n C_i$の中にある.

??????

分からないのでWikipediaを見ます.

http://en.wikipedia.org/wiki/Gershgorin_circle_theorem

よく分かりましたね.

具体例を出します.
$2\times 2$行列$A$を
\begin{align*}
A = \left(\begin{array}{cc}
0 & 1.5\\
-3.5 & 8
\end{array}\right)
\end{align*}
とします.
$A$の固有値とGershgorin discの様子を, 複素平面上で描画してみると,
f:id:gg_hatano:20130713175931p:plain
こんな感じです.

円が2つあります.
円の中心は対角成分, 円の半径は対角成分を除いた行絶対値和です.
中心が0で半径が1.5の円, 中心が8で半径が3.5の円が描けます.
固有値を計算してプロットすると, 円盤の中に入っていますね.


固有値は, どこかの円に含まれる, ということを言っています.
各円が固有値を含む...ということはまだ言っていません.
固有値がどこかの円の中にあるだけです.
固有値を持たない円があるかもしれませんが, 定理はまだ続きます.

Gershgorinの定理(強い形)

固有値は, $\cup_{i=1}^n C_i$の各連結成分の中に, それを構成する円の個数に等しい個数ずつ含まれる.


行列の対角成分と非対角成分から, 円を描きます.
各円は交わるかもしれません. 交わったら連結成分です.
連結成分が$k$個の円からできていたら, その連結成分は$k$個の固有値を含むらしいです.

固有値がどこかの円の中にあり,
円がなす連結成分は, 円の数だけ固有値を持ちます.

"各円は固有値を含みます" だったら良かったのですが, ダメな例があります.
つまり, 固有値を含まない円がある, ということです.

固有値を含まないGershgorin disc

行列$A$を,
\begin{align*}
A = \left(\begin{array}{cc}
0 & 3t\\
-7t & 8
\end{array}\right)
\end{align*}
とします.
パラメータ$t$の値を動かして, 円盤と固有値の配置を観察してみます.

円盤は,
$C_1 = \{ |z - 0| \leq 3t \}$, $C_2 = \{ |z - 8| \leq 7t \}$
です.
Gershgorinの定理から, 固有値は円盤の中にあります.



試しに$t=0.5$のときを見てみます.
\begin{align*}
A = \left(\begin{array}{cc}
0 & 1.5\\
-3.5 & 8
\end{array}\right)
\end{align*}
となります.
固有値とGershgorin discの様子を, 複素平面上で描画してみると,
f:id:gg_hatano:20130713165537p:plain
こんな感じです.

円盤は交わっていません. 各円盤に固有値が1つずつある形になっています.

困るのは, 円盤が交わっている時です.
パラメータ$t$を変化させて, 円盤と固有値の様子をアニメーションで見てみます.
$t$を0から1まで変化させてみました.

f:id:gg_hatano:20130713171140g:plain

ドヤ

2つの円からなる連結成分に, 固有値が2つ入っていますのので,
Gershgorinの定理の強い形は正しいことを言っているみたいです.

最終状態を見てみます. $t=1$のとき.
f:id:gg_hatano:20130713171750p:plain
確かに, 原点を中心とする円の方には, 固有値が乗っていません. かわいそうに.

以上です.

使用したRコード.

アニメーションの作成にはRのanimationパッケージを利用しました.
plotした画像ファイルをパラパラ漫画形式gifにしてくれます.
楽しいです.

# 2013/07/13
# Gershgorin disc theorem

#install.packages("animation")
library(animation)

main <- function(){
 for(t in seq(0,1,by=0.01)){
  A <- matrix(c(0, 3*t, -7*t, 8), 2,2)
  eigA <- eigen(A)
  u1 <- eigA$values[1]
  u2 <- eigA$values[2]
  print(u1)
  print(u2)
  plot(complex(re=Re(u1), im=Im(u1)), 
       xlim = c(-3,15), ylim = c(-8,8), xlab = "", ylab="", 
       pch=15, main = paste("t = ", t))
  par(new=T)
  plot(complex(re=Re(u2), im=Im(u2)), 
       xlim = c(-3,15), ylim = c(-8,8), xlab = "Re", ylab="Im", 
       pch=15)
  par(new=T)
  theta <- seq(-pi, pi, length=100)
  lines(3*t*cos(theta) , 3*t*sin(theta), lty=2)
  lines(7*t*cos(theta)+8,7*t*sin(theta), lty=2)
  abline(h=0)
  abline(v=0)
 }
}

saveMovie({
  main()
}, movie.name="gersh.gif", interval = 0.1)

Rのplot関数は複素数にも対応しています.
勝手に実軸と虚軸でプロットしてくれます. 素敵です.

参考文献

ステマします

線形代数汎論 (基礎数理講座)

線形代数汎論 (基礎数理講座)

6720円です. 高いです.