|TOP Page|


QR Method

QR法




Last Update:2009年05月15日


概要

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

シュール分解

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

\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)により、Qは直接求められないことが知られている。

そこで反復的な計算により、にシュール分解を行うのが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}の固有値は等しい

このとき、

Reduction

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

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

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

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

\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は右下の2×2の行列の固有値のうち、一番右下の対角成分に近いものがよく使われる。これをウィルキンソンの移動法(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