QR Method

QR法

Last Update:2009年05月15日

概要

QR法とはQR分解を用いて反復的に固有値を求める方法である。

シュール分解

行列 $A \in \cal{C}^{n \times n}$ は次のようにユニタリー行列を用いて、上三角行列に変換することができる。

$\b{Q}^*\b{A}\b{Q}=\b{R}$

これをシュール分解(Schur Decomposition)という。

$\b{Q}$ はユニタリー行列なので、 $\b{A}$ の固有値は $\b{R}$ の固有値に等しい。上三角行列 $\b{R}$ の固有値はその対角成分である。よって $\b{A}$ の固有値を調べるためにはシュール分解した上三角行列 $\b{R}$ の対角成分を調べればいいことがわかる。

但し、 $n\ge5$ の場合はアベールの定理(Abel's theorem)により、は直接求められないことが知られている。

そこで反復的な計算により、にシュール分解を行うのがQR法である。

QR法

ここで、 $\b{T}_0=\b{A}$ として、 $\b{Q}_k\b{R}_k$ を $\b{T}_k$ のQR分解であるとする。

$\b{T}_{k+1}=\b{Q}_k^*\b{T}_k\b{Q}_k=\b{Q}_k^*(\b{Q}_k\b{R}_k)\b{Q}_k=\b{R}_k\b{Q}_k$ の操作を繰り返す。

つまり、 $\b{T}_k=(\b{Q}_0\b{Q}_1\ldots\b{Q}_{k-1})^*\b{A}(\b{Q}_0\b{Q}_1\ldots\b{Q}_{k-1})$

$\b{Q}_0\b{Q}_1\ldots\b{Q}_{k-1}$ はユニタリー行列であるから、 $\b{T}_k$ の固有値と $\b{A}$ の固有値は等しい

このとき、

実行列 $\b{A}$ の固有値が実数の場合

$\b{T}_k$ はシュール分解における上三角行列に収束する。

実行列 $\b{A}$ の固有値が複素数の場合

$\b{T}_k$ は次のような形に収束する
$\b{T}_k\rightarrow\(\begin{array} R_{11}&&R_{12}&&\cdots&&R_{1m}\\ 0 &&R_{22}&&\cdots&&R_{2m}\\ \vdots&& &&\ddots&&\vdots\\ 0 &&\cdots&&0 &&R_{mm}\end{array}\)$
但し、 $R_{ii}$ は実数か、互いに共役な複素数の固有値を持つ次元数が２の行列である。
これは実シュール分解(Real Schur Decomposition)と呼ばれる。

Reduction

一般的にQR分解は大きな手間を要する。そこで $\b{A}$ の固有値を変化させない、 $\b{A}$ より成分の少ない行列に変換することで計算を大幅に削減することができる。対称行列ならLanczos方を用いて固有値を変えることなく３重対角行列に相似変換できる。また、非対称行列はArnoldi法を用いることでヘッセンベルグ行列に変換できるほか、Two-Sided Lanczos Methodを用いることで３重対角行列に相似変換することができる。このような方法をReductionという。

ヘッセンベルグ行列への変換

をヘッセンベルグ行列 $\b{H}$ $h_{i,j}=0 \quad \( \quad for \quad j \quad < \quad i-1 \quad \)$ に変換してからQR法を適応すると比較的簡単にQR分解を適応することができる。

Arnoldi法を用いると次のように正規直交なベクトル列 $\b{V}$ を使っては次のようにヘッセンベルグ行列に変換できる。

$\b{H}=\b{V}^*\b{A}\b{V}$

ヘッセンベルグ行列 $\b{H}$ の固有値はRitz値と呼ばれ，と $\b{A}$ の固有値に近い

$\b{H}$ の固有値分布を求めることで、 $\b{A}$ の固有値分布を大方知ることができる．

ヘッセンベルグ行列 $\b{H}$ をQR分解する方法はギブンス回転がよく使われる。

減次(Deflation)

$h_{n,n-1}$ が十分小さくなったら, (n - 1) × (n - 1) 行列の部分の固有値を求めればよい．

そうすることで次数を減らすことができ、計算を加速することができる。

原点シフト法

次のようにあるシフト量 $\mu_k$ を導入して、求めた $\b{T}_{k+1}$ もまた $\b{T}_k$ と同じ固有値を持つ

$\b{Q}_k\b{R}_k=\b{T}_k-\mu_k\b{I}$

$\b{T}_{k+1}=\b{R}_k\b{Q}_k+\mu_k\b{I}$

$\mu_k$ を選ぶことによって収束を加速することができる。

$\mu_k$ は右下の２×２の行列の固有値のうち、一番右下の対角成分に近いものがよく使われる。これをウィルキンソンの移動法(Wilkinson's Shift)という。

参考文献

Webページ

行列の固有値問題 桂田　祐史先生による行列固有値問題に関する詳しいドキュメント: http://www.math.meiji.ac.jp/~mk/labo/text/eigen-values/eigen-values.html

数値計算の基礎: http://www7.ocn.ne.jp/~kawa1/numeric.pdf

ソフトウェアとしての数値計算: http://na-inet.jp/nasoft/

Made by Nobuyuki UMETANI 梅谷　信行

n.umetani@gmail.com