スライド 1

シフト付きコレスキー LR 法における
２つの固有値近似法の収束性について
東京大学大学院情報理工学系研究科
数理情報学専攻
相島健助松尾宇泰室田一雄杉原正顯
2008.11.26
目次

はじめに（研究の背景）



dqds法について
コレスキーLRの基本的収束性
本研究


2
コレスキーLR法の２つの固有値近似法の収束速度比較
まとめ
特異値とその計算方法
特異値分解 A  U V
長方形行列
U , V : 直交行列
1 A
直交変換
T
3
 1

0






0
m
 0



0


特異値
2
2
T
A A の固有値  1 ,,  m
上２重対角行列
B
正方行列と考えてよい
2
B
の特異値( 1 ,,  m ) を計算
例）dqds 法を用いる
対象とする上2重対角行列
4
仮定
 a1 b1

a

0
,
b

0
k
k


0
a2 

 m
B

 bm1
特異値


 0







0
a
1
m
m 

m
一般性を失わない！
dqds 法のアルゴリズム (Fernando-Parlett, 1994) 5
初期設定：
qk  (ak ) , ek  (bk )
(0)
2
( 0)
2
反復計算：
for n : 0,1,  do
(n)
シフト量：s  0 の設定
d1( n1) : q1( n )  s ( n )
for k : 1, , m  1
q : d  e
e : e q / q
d : d q / q
do
( n1)
( n1)
(n)
k
k
k
( n1)
(n)
(n)
( n1)
k
k
k 1
k
( n1)
( n1)
(n)
( n1)
k 1
k
k 1
k
end for
qm( n1) : dm( n1)
end for
 s(n)
 a1


B



b1
a2
 q1( n )


(n)
B 







 bm1 

am 
e1( n )
q2( n ) 




(n) 
em1 
qm( n ) 
( B( n1) )T B( n1)  B( n) (B( n) )T  s ( n) I
dqds 法の収束定理(相島，松尾，室田，杉原, 2007)
6
( B( n1) )T B( n1)  B( n ) ( B( n ) )T  s ( n ) I
 min( n ) ： B ( n ) の最小特異値
シフト量
0  s  ( min )
(n)

s
(n)
(n)
2
m ,
2
n 0
lim ek  0 ,
B(n) 
(n)
n 

lim
q



s

k
k
n 
(n)
2
n 0
(n)
0
dqds 法の２つの特異値近似法
 q1


(n)
B 



(n)
(n)
e1
q2( n ) 

7
 em1  0 で打ち切る
n 1

2
 近似値  m  qm( n )   s ( l )
l 0
(n) 
em1  デフレーションを繰り返す
qm( n ) 
 m , m1 ,..., 1 の順に計算できる
(n)
( n1)
  s
2
n1
(l )
em1
m
l 0
収束速度 lim ( n )  lim
n1
2
(l )
n  e
n 


s
m1
l0
m1
n1
   s  0 となるようにシフト設定したい．このとき  m   s ( l )
n 1
2
(l )
2
m
l 0
l 0
（対角＋シフト総和）と（シフト総和）の収束性
8
相島，松尾，室田，杉原，JSIAM年会2008
大域的収束の条件
シフト量：0  s
B
(n)
(n)
 ( min )
(n)
2
の最小固有値  min , シフト総和 t ( n )   s ( l )
n1
(n)
l 0
qm( n )  t ( n )：単調減少
t ( n ) ：単調増加

0
2
m
| qm  t   m |
lim
0
n  | t (n)   2 |
m
(n)
(n)
2
dqds 法とコレスキーLR法の関係
9
dqds法： B の特異値 ( 1 ,,  m ) を計算
A BB


A


T
の固有値は
   (k  1,, m)
2
k
k


 （既約三重対角正定値対称行列）


B に対し dqds 法を実行
 A
に対しコレスキーLR法を実行
数学的に等価
コレスキーLR法：正定値対称行列の固有値計算アルゴリズム
dqds 法とコレスキー LR 法の歴史

コレスキー LR 法( Rutishauser, 1958 )



10
正定値対称行列の固有値計算アルゴリズム
高速化のためシフトを導入 (Rutishauser, 1960)
dqds法 ( Fernando – Parlett, 1994 )
differential quotient difference with shifts 法
 上二重対角行列の特異値計算アルゴリズム
 LAPACKのルーチンDLASQ
 三重対角行列に対するコレスキー LR 法と数学的に等価
シフト付きコレスキーLR法:既約三重対角 11
上二重
初期設定：
A A
t (0)  0
( 0)
（三重対角正定値対称行列）
反復計算：
for n : 0,1,  do
シフト量： s
(n)
A( 0 )
の設定
A( n )  s ( n ) I  ( R( n ) )T R( n )





R(n)








0






対角行列に収束
：コレスキー分解

1
( n1)
A
 R (R )
(n)
(n)
t ( n1)  t ( n )  s ( n )
end for
T
A t
(n)
(n)

0
0

m
相島，松尾，室田，杉原，2007
対角とシフトの固有値への収束性
12
相島，松尾，室田，杉原，JSIAM年会2008
大域的収束の条件（ A が既約三重対角の場合）
n)
シフト量： 0  s ( n)  (min
A
(n )
の最小固有値
 ,
(n)
min
n1
シフト総和 t ( n )   s ( l )
l 0
am( n,m)  t ( n )：単調減少
t ( n ) ：単調増加
0

m
| am( n,m)  t ( n )  m |
lim
0
(n)
n 
| t  m |
目次

はじめに（研究の背景）



dqds法について
コレスキーLRの基本的収束性
本研究


13
コレスキーLR法の２つの固有値近似法の収束速度比較
まとめ
対象とする正定値対称行列について
Aui  i ui (i  1,, m)
正定値対称行列
固有値
     ( 0)
1
固有値ベクトル
m
u1 ,, um
14
シフト付きコレスキーLR法
15
上三角
初期設定：
A A
t (0)  0
( 0)
（正定値対称行列）
R(n)
反復計算：
for n : 0,1,  do
シフト量： s
(n)
A( n1)  R( n ) ( R( n ) )T
t ( n1)  t ( n )  s ( n )
end for





ある種の例外を除き
右下成分のみ収束
の設定
A( n )  s ( n ) I  ( R( n ) )T R( n )



0

：コレスキー分解
A( n )  t ( n )
＊
0
0

m
Rutishauser, 1960
すべての固有値の計算法



(n)
A 



*
( v (n) )T


(n)
v 


(n) 
a m ,m 
16
v ( n )  0 で打ち切る
近似値   a  t
(n)
m
(n)
m ,m
デフレーションを繰り返す
 ,  ,..., の順に計算できる
m
m1
1
シフト付きコレスキーLR法の収束定理
17
（Rutishauser 1960）
大域的収束の条件
シフト量:
A
0s
( n)
(n )
の最小固有値

( n)
min
 ,
(n)
min
lim (am( n,m)  t ( n ) )  m
n 
lim ai ,m ( am ,i )  0
n 
(i  1,, m  1)
(n)
n1
シフト総和 t
(n)
  s (l )
l 0
A( n )  t ( n ) I 
＊
0
0

(n)
ある種の例外を除き一般的に成立
m
(n)
(n)
lim
(
a

t
)


の略証
(Rutishauser)
m ,m
m
n 
18
1    m  0 : A
の固有値（相異なるとする）
 u1,1   u1, 2 

 

 :   : 
 :  ,  :  ,......,

 

u  u 
 m,1   m, 2 
 u1,m 


 :  :A
の固有ベクトル
 : 
（正規直交化されているとする）


u 
 m,m 
(1 )
( 2)
(n)
(


t
)(


t
)

(


t
)
2
m
m
m
(um , j ) ( j  m )

(1 )
( 2)
(n)
(


t
)(


t
)

(


t
)
j 1
j
j
j
(n)
(n)
am ,m  t  m  m1
(1)
(2)
(n)
(


t
)(


t
)

(


t
)
2
2
m
m
m
(
u
)

(
u
)

m, j
m ,m
( j  t (1) )( j  t ( 2 ) )  ( j  t ( n ) )
j 1
m1
(n)
(n)
lim
(
a

t
)


の略証
(Rutishauser)
m ,m
m
n 
19
(1 )
( 2)
(n)
(


t
)(


t
)

(


t
)
2
m
m
m
(um , j ) ( j  m )

(1 )
( 2)
(n)
(


t
)(


t
)

(


t
)
j 1
j
j
j
(n)
(n)
am ,m  t  m  m1
(1)
(2)
(n)
(


t
)(


t
)

(


t
)
2
2
m
m
m
(
u
)

(
u
)

m, j
m ,m
(1)
(2)
(n)
( j  t )( j  t )  ( j  t )
j 1
m1
     ( j  1,, m 1)
(  t )(   t )  (  t )   
  0
 
(  t )(   t )  (  t )     
固有値はすべて異なるので
(1 )
j
( 2)
m
m
(1 )
n
(n)
m
( 2)
j
m
j
m
(n)
j
m
lim
(am,m  t )  m
n
ただし um ,m  0
(n)
( n)
u m ,mは A の最小固有値の固有ベクトルの第 m 成分
目次

はじめに（研究の背景）



dqds法について
コレスキーLRの基本的収束性
本研究


20
コレスキーLR法の２つの固有値近似法の収束速度比較
まとめ
問題意識
21
一般の行列に対してコレスキーLR法を実行すると


（対角＋シフト総和）は単調減少するか？
（シフト総和＋対角）と（シフト総和）でどっちの収
束が速いか？
am( n,m)  t ( n )：単調減少？？？
t ( n ) ：単調増加
0

m
| am( n,m)  t ( n )  m |
lim
 ???
(n)
n  | t
 m |
am , m  t
(n)
(n)
 m の評価 (Rutishauser)
22
(1 )
( 2)
(n)
(


t
)(


t
)

(


t
)
2
m
m
m
(um , j ) ( j  m )

(1 )
( 2)
(n)
(


t
)(


t
)

(


t
)
j 1
j
j
j
(n)
(n)
am ,m  t  m  m1
(1)
(2)
(n)
(


t
)(


t
)

(


t
)
2
2
m
m
m
(
u
)

(
u
)

m, j
m ,m
(1)
(2)
(n)
( j  t )( j  t )  ( j  t )
j 1
m1
     ( j  1,, m 1)
(  t )(   t )  (  t )   
  0
 
(  t )(   t )  (  t )     
固有値はすべて異なるので
(1 )
j
( 2)
m
m
(1 )
m
j
j
( n)
m
(n)
lim
(am,m  t )  m
n
ただし um ,m  0
(n)
n
(n)
( 2)
j
m
m
収束は示せる
単調性は？？？
u m ,mは A の最小固有値の固有ベクトルの第 m 成分
シフト付きコレスキーLR法
23
上三角
初期設定：
A A
t (0)  0
( 0)
（正定値対称行列）
R(n)
反復計算：
for n : 0,1,  do
シフト量： s
(n)
の設定
A( n )  s ( n ) I  ( R( n ) )T R( n )
A( n1)  R( n ) ( R( n ) )T
t ( n1)  t ( n )  s ( n )
end for
：コレスキー分解



0






上三角行列を中心に考える
24
上三角
A( n )  s ( n ) I  ( R( n ) )T R( n )
A( n1)  R( n ) ( R( n ) )T
R(n)



0

t ( n1)  t ( n )  s ( n )
( R( n ) )T R( n )  A( n )  s ( n ) I  R( n1) ( R( n1) )T  s ( n ) I
R(n)







＊
0


(n)
r



( n1)
am ,m 





am( n,m)  t ( n ) の単調性の証明（本研究）


(n)
R 
 R( n1) ( R( n1) )T  s ( n ) I  0
( R( n ) )T R( n )







＊
(r ( n ) ) T


0 


( n1)
am ,m 
＊
0
 
 
(n)
r  

 
( n1)
am ,m  
am ,m  r
( n1)
a m ,m  r
( n 1 )
(n) 2
(n) 2


( n1)
r 


(n)
am ,m 
＊
0
 am( n,m)  s ( n )







0  (n)
s I

(n)
am ,m 
＊
(r ( n1) ) T
（右下の成分に関する等号）
n 1
  s  am ,m   s ( l ) （両辺にシフト総和を足す）
n
(l )
(n)
l 0
 am ,m  t
( n1)
25
( n1)
単調減少
l 0
 am ,m  t  r
(n)
(n)
(n) 2
  s (l ) )
n
( t
( n 1 )
l 0
一般の行列における収束性（本研究）
26
大域的収束の条件
シフト量:
n)
かつ um,m  0
0  s ( n)  (min
A の最小固有値 min , シフト総和 t   s
u m ,m は A の最小固有値の固有ベクトルの第 m 成分
(n )
n1
(n)
(n)
(l )
l 0
am( n,m)  t ( n )：単調減少
t ( n ) ：単調増加
0

m
(n)
| am ,m  t  m |
lim
0
(n)
n 
| t  m |
(n)
| am( n,m)  t ( n )  m |
lim
0
(n)
n 
| t  m |
A  s I  (R ) R
(n)
(n)
(n)
T
(n)
A( n1)  R( n ) ( R( n ) )T
t ( n1)  t ( n )  s ( n )
27
の略証



(n)
A 



U (n)
(n)
(v )
T


(n)
v 


(n) 
a m ,m 
A( n )  s ( n ) I の固有値： m  t ( n1) , m1  t ( n1) ,...,1  t ( n1)
v
( n 1 )
v(n)
 t

 t
( n 1 )
m
m 1
( n 1 )
| am( n,m)  t ( n )  m |
lim
0
(n)
n 
| t  m |
v ( n1)
v
(n)
 t

 t
の略証
( n 1 )
m
( n 1 )
m 1
28
A( n1)







U ( n1)
(v
( n 1 )
)
T


( n 1 )
v 


( n 1 ) 
a m ,m 
A( n1) の固有値： m  t ( n1) , m1  t ( n1) ,...,1  t ( n1)
一般化されたBauer-Fike の定理より
| min  (m  t
( n1)
( n1)
) | | am ,m  (m  t
( n1)

( n1)
min
( n1)
)|  v
( n1) 2
: U ( n1) の最小固有値
| am( n,m)  t ( n )  m |
lim
0
(n)
n 
| t  m |
v ( n1)
v
(n)
 t

 t
の略証
( n 1 )
m
( n 1 )
A( n1)
m 1
| min  (m  t
( n1)
( n1)
29







U ( n1)
(v
) | | am ,m  (m  t
( n1)

( n1)
min
( n 1 )
( n1)
)
T
)|  v


( n 1 )
v 


( n 1 ) 
a m ,m 
( n1) 2
: U ( n1) の最小固有値
v
| am ,m  t  m |
 ( n1)
( n1)
( n1)
( n1)
| m  t |
|  min  (m  t ) | (m1  t )
( n1)
( n1)
(n)
lim
| min  (m  t
n
( n1)
( n1)
2
) |  m1  m  0
目次

はじめに（研究の背景）



dqds法について
コレスキーLRの基本的収束性
本研究


30
コレスキーLR法の２つの固有値近似法の収束速度比較
まとめ
まとめ



31
シフト付きコレスキーLR法の２つの近似法：（対
角＋シフト総和）と（シフト総和）を比較した
（対角＋シフト総和）は単調減少する
最終的には（シフト総和＋対角）の方が（シフト総
和）より収束が速い
am( n,m)  t ( n )：単調減少
t ( n ) ：単調増加
0

m
(n)
| am ,m  t  m |
lim
0
(n)
n 
| t  m |
(n)

Download Report