第２５回助教の会

こんにちは，数理6研助教の冨岡です．今回は数理3研の助教の相島健助さんに「固有値問題に対する射影法について」というタイトルで行列の固有値を求めるための Lanczos 法と，Jacobi-Davidson 法という2つの方法のレビューをして頂きました．相島さん自身の研究の話もあったのですが，未発表ということで，ここでは割愛させて頂きます．

量子力学における物理量の計算，Google のページランクや，システムの安定性解析など，多くの実世界の複雑な問題では，非常に大きな行列の固有値および固有ベクトルを求めることが必要になることがあります．ここで，固有値を計算したい$n\times n$行列を$A$（ここでは簡単のために対称と仮定します）として

$$ A x = \lambda x $$

を満たすような $\lambda$ と $x$ をそれぞれ，$A$の固有値，固有ベクトルと呼びます．固有値や固有ベクトルを求めるには，行列$A$が小さい場合にはQR法などの直接法が用いられますが，行列が大きい場合には反復法が有効であることが知られています．

反復法としてもっとも代表的な方法はべき乗法です．べき乗法では適当な $x_0$ を初期ベクトルとして，

$$ x_{n+1} = A x_{n} $$

のように反復計算をします．このような反復を十分長く続けると，ベクトル$x_n$が$A$の絶対値最大の固有値に対応する固有ベクトルに収束することが知られています．この方法は非常に単純であり行列Aとの掛け算さえ計算できればよいので広く活用されていますが，収束に要する反復回数が大きくなってしまうことが問題です．

べき乗法は1本のベクトルを更新して行くのに対して，射影法は$m (>1)$次元の部分空間を更新して行く方法です．具体的には

1. 何らかの方法で部分空間の正規直交基底 $V_m$ を生成
2. 小さな行列 $V_m^TAV_m$ の固有値$\theta$，固有ベクトル$y$を求める．
3. $V_my$ がもとの行列$A$の固有ベクトルになっていれば終了，そうでなければ何らかの方法で部分空間$V_m$を更新

というような手続きを行います．ここでのポイントは，$m$が小さければ小さいほど，2で解くべき固有値問題は簡単になる代わりに，より多くの反復が必要になるというトレードオフがあるという点です．逆に言えば，$m$を増やすことで，べき乗法（$m=1$）に比べれば1回あたりの計算は大変になるものの，少ない回数の反復で固有値，固有ベクトルが得られるということです．具体的にどのように部分空間を作り，どのように更新するのかはアルゴリズムによって異なります．

射影法のひとつであるLanczos法は部分空間$V_m$として，適当な$x$を初期ベクトルとする Krylov部分空間 ${\rm span}(x, Ax, A^2x,\ldots,A^{m-1}x)$を用います．さらに，上記3で収束しなかった場合，$x:=V_my$として再度Krylov部分空間を構築します．

射影法のもう1つの手法 Jacobi-Davidson法は適当な正規化された初期ベクトルを$V_1$として，各反復ごとに1本の基底を追加しつつ$V_m$を更新します．各反復で追加する基底は修正方程式の解として得られます．修正方程式は一見複雑な形をしていますが，実はその解はRayleigh商反復という，また別の反復法の更新式と等価であることを示すことができます．また，$m$が大きくなると2で解くべき固有値問題が重くなるため，あらかじめ定めた$m$まで基底を増やすごとに，初期ベクトル$V_1=V_my$として$m=1$にリセットすることが，実用上有効であるとのことでした．

ふだん固有値や特異値を計算することは多いのですが，実際に内部でどのようなアルゴリズムが動いているのかはあまり考えずに使っていることが多いので，ユーザの立場としても様々なトレードオフを理解した上で使うことが重要であると感じました．個人的には最近注目されているランダム射影に基づく方法[1]と上記の手法の関係が気になります．

[1] N. Halko, P. G. Martinsson, and J. A. Tropp (2011) Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions. SIAM Reviews, 53(2): 217-288.

なお，今回の発表の内容は来週，道後温泉で開かれる数値解析シンポジウム(NAS2013) でより詳しく発表するということです．

Jokyonokai130531 from nwpmq516