2014年度・後期・数理解析・計算機数学３・第１４回 1
● 講義資料
▼ 講義予定
• 行列の固有値を求める
以下では, Aは,すべて n×n正方行列で正則であり,対角化可能と仮定する. また,{λi}ni=1 で
（重複をこめて）固有値をあらわし,{ui}ni=1は,それぞれの固有値に対する固有ベクトルでkuik= 1 であるものとする. さらに,
|λ1| ≥ |λ2| ≥ · · · ≥ |λn| と仮定する.
▼ 巾乗法
• Aの絶対値最大の固有値が単純であるとき,その絶対値最大の固有値を求める方法である.
• x0 として,u1 の成分を含むベクトルを取ったとき, yk+1=Axk, xk+1= 1
kyk+1kyk+1
によって{xk}を定める. このとき,
k→∞lim xk=u1
が成り立つ.
▼ 逆反復法
• Aの絶対値最小の固有値が単純であるとき,その絶対値最小の固有値を求める方法である.
• A−1 の固有値は{1/λi}ni=1 であり,その固有ベクトルはAの固有ベクトルと等しいことを 使う.
• x0 として,un の成分を含むベクトルを取ったとき, Ayk+1=xk, xk+1= 1
kyk+1kyk+1
によって{xk}を定める. このとき,
k→∞lim xk =un が成り立つ.
• 注意：逆反復法では Ay =xの形の連立一次方程式を何度も解くこととなるので, A のLU 分解を先に計算しておき,それを用いて連立一次方程式を解けば良い.
Jan. 21, 2015, Version: 1.0 [email protected]
2014年度・後期・数理解析・計算機数学３・第１４回 2
▼ 固有ベクトルがわかっているときに固有値を求める
• Aの固有ベクトルuが既知であるときに,uに対応する固有値λは λ=(Au, u)
kuk2 によって求めることができる.
▼ 実対称三重対角行列のすべての固有値を求める
• ここでは,A の代わりにT と書き,実対称三重対角と仮定する. すなわち,
T =T({ai},{bi}, n) =
a1 b1
b1 a2 b2
. .. ... . ..
bn−2 an−1 bn−2
bn−1 an
と書く. さらに,bi6= 0を仮定する.
• Gerschgorinの定理より,T のすべての固有値は区間
[mink ak−(|bk−1|+|bk|),max
k ak+ (|bk−1|+|bk|)]
に含まれることがわかる.
• 定理：三重対角行列T−λE に関して,
fk(λ) = detT({ai−λ},{bi}, k) とおくと,
fk(λ) = (ak−λ)fk−1(λ)−b2k−1fk−2(λ) が成り立つ. （証明は,最後の列に関して展開をすればよい.）
• 定義：次の条件を満たす関数列{fk}nk=0 をStrum 列と呼ぶ.
1. f0(x)は0 でない定数関数である.
2. fk(x)とfk−1(x)は等しい根をもたない.
3. fk(t) = 0ならばfk+1(t)fk−1(t)<0 となる.
4. fn(t) = 0 ならば,fn′(t)fn−1(t)<0となる
• 定理：f0(t) = 1,f1(t) =a1−t,fk(t) = (ak−t)fk−1(t)−b2k−1fk−2(t)によって定義される 関数列{fk(t)}nk=0 は Strum列をなす. すなわち,副対角成分に 0を持たない実対称三重対 角行列の行列式はStrum列をなす.
Jan. 21, 2015, Version: 1.0 [email protected]
2014年度・後期・数理解析・計算機数学３・第１４回 3
▼ 実対称行列を実対称三重対角行列に相似変形する
• 06=v∈Rn に対してn×n行列H(v)を
H(v) =E− 2
|v|2vvT
と定義すると,H(v)は,直交行列かつ対称行列となる. この行列による変換をHouseholder 変換と呼ぶ.
特にx,y∈Rn に対してH(x−y)は,
H(x) =y, H(y) =x, H(x−y) =y−x をみたす.
• Householder変換を n−1 回繰り返すことにより,実対称行列を実対称三重対角行列に相似
変形できる. 実際,
A=
a11 · · · a1n
...
a1n · · · ann
, A1=
a11 b12 0 · · · 0 b12 a22 a23 · · · a2n
0 a23 a33 · · · a3n
...
0 a2n a3n · · · ann
,
a1= (a11, a12, a13, . . . , a1n), b1= (a11, b12,0, . . . ,0)
とおき,|a1|=|b1|をみたすようにb12 を定めて, H1=H1(a1−b1) とおけば,
A1=H1TAH1
が成り立つ. 以下,これを繰り返せばよい.
• 実対称行列の固有値は,n−1回のHouseholder変換を行い,実対称三重対角行列に相似変形 した後, Strumの二分法で固有値を求めれば良い.
Jan. 21, 2015, Version: 1.0 [email protected]
