QR法

QR法（きゅーあーるほう、QR algorithm）は、行列Aの固有値を求める方法[1]の一つで行列のQR分解を利用するものである。QR法は数値解析的に安定なアルゴリズムである。

手順

行列Aの次数をnとする。

まず

A 1 = A {\displaystyle A_{1}=A}

とおく。以下、

A k = Q k R k {\displaystyle A_{k}=Q_{k}R_{k}}
A k + 1 = R k Q k ( = Q k − 1 A k Q k ) {\displaystyle A_{k+1}=R_{k}Q_{k}\left(=Q_{k}^{-1}A_{k}Q_{k}\right)}
( k = 1 , 2 , ⋯ , m ) {\displaystyle (k=1,2,\cdots ,m)}

と繰り返す。この繰り返し手順は相似変換であるため、行列A1の固有値と行列Akの固有値はすべて一致する （ただし、固有ベクトルは必ずしも一致しない）。したがって、固有ベクトルを求める必要があれば、行列Am+1の固有値を求めた後、 行列Aに戻って各固有値に対応する固有ベクトルをそれぞれ求めなければならない。

特別な場合

行列Aが対称行列である場合、 相似変換後に得られる行列Am+1は 三重対角行列となる。

原点移動付きQR法

上記手順では、Akが収束するまで繰り返すQR分解の回数が多くなりやすい。 このため、上記繰り返し手順を

A k − μ k I = Q k R k {\displaystyle A_{k}-\mu _{k}I=Q_{k}R_{k}}
A k + 1 = R k Q k + μ k I ( = Q k − 1 A Q k ) {\displaystyle A_{k+1}=R_{k}Q_{k}+\mu _{k}I\left(=Q_{k}^{-1}AQ_{k}\right)}
( k = 1 , 2 , ⋯ , m ) {\displaystyle (k=1,2,\cdots ,m)}

と置き換えて、QR分解の回数を減らそうとすることがある。 このような手順を原点移動付きQR法という。

μkの選択方法として、Akの右下隅の2×2小行列の固有値のうち、 Akの右下隅の値に近いほうを選択することが多い（ウィルキンソンの移動法）。

脚注

[脚注の使い方]
  1. ^ “"固有値の数値計算法 - F. QR法", 『岩波 数学辞典』”. JapanKnowledge. 2022年1月29日閲覧。

関連項目

  • 表
  • 話
  • 編
  • 歴
連立一次方程式
ベクトル
ベクトル空間
計量ベクトル空間
行列・線型写像
演算・操作
不変量
クラス
行列式
多重線型代数
数値線形代数
基本的な概念
ソフトウェア
ライブラリ
反復法・技法
人物
行列値関数
その他
カテゴリ カテゴリ