QR分解

QR分解とは、//m// × //n// 実行列 //A//を、 //m// 次直交行列 //Q// と //m// × //n// 上三角行列 //R// との積への分解により表すこと、またはそう表した表現をいうGolub。このような分解は常に存在するGolub。

QR分解は線型最小二乗問題を解くために使用される。また、固有値問題の数値解法の1つであるQR法の基礎となっている。

1. 定義
-----

1.1. 正方行列
---------

すべての実正方行列 //A//は直交行列//Q//と上三角行列//R//を用いて

と分解できる。もし//A//が正則ならば、//R//の対角成分が正になるような因数分解は一意に定まる。

もし//A//が複素正方行列ならば、//Q//がユニタリ行列 となるような分解//A// = //QR//が存在する。

もし//A//が//n//個の線形独立な列を持つなら、//Q//の最初の//n//列は//A//の列空間の正規直交基底をなす。より一般的に、1   ≤   //k//   ≤   //n//の任意の//k//について、//Q//の最初の//k//列は//A//の最初の//k//列の線型包をなす//。A//の任意の列//k//が//Q//の最初の//k//列にのみ依存するということは、//R//が三角行列であることから明らかである。

1.2. 矩形行列
---------

より一般的に、//m//   ≥   //n//である複素//m//×//n//行列//A//を、//m//×//m//ユニタリ行列//Q//と//m//×//n//上三角行列//R//に分解することができる。//m//×//n//上三角行列の下から行はすべてゼロであるため、//R//や、//R//と//Q//両方の分割を簡単に行うことができる。

ここで、//R//1は//n//×//n//上三角行列、//0//は×//n//零行列、//Q//1は//m//×//n//行列、//Q//2は//m//×行列で、//Q//1と//Q//2は両方直交する列を持つ。

//Q//1//R//1をGolubはAの薄いQR分解と呼び、 Trefethen & Bauは軽減QR分解と呼んでいる。もし//A//が最大階数//n//であり、//R//1の対角成分を正にするならば、//R//1と//Q//1は一意に定まる。しかし一般的に//Q//2はそうではない。//R//1は//A//* //A// のコレスキー分解の上三角部分に等しい。

1.3. QL・RQ・LQ分解
---------------

同様に、//L//を下三角行列として、QL、RQ、LQ分解を定義することができる。

2. QR分解の計算
----------

QR分解を計算する手法として、グラム・シュミット分解、ハウスホルダー変換、ギブンス回転などがある。それぞれ利点と欠点がある。

2.1. グラム・シュミットの正規直交化法の使用
------------------------

グラム・シュミットの正規直交化法を最大階数行列の列に適用することを考える。内積 とする。

射影の定義より、

したがって、

ここでを新しく計算された正規直交基底上に表すことができ、であるから、

これは行列の形に書くことができ、

ただし、

2.1.1. 例
--------

の分解を考える。

正規直交行列に対して、

が常に成り立つから、グラム・シュミット法により以下の手順でを計算できる。

したがって、

2.1.2. RQ分解との関係
---------------

RQ分解は行列//A//を上三角行列//R//と直交行列//Q//に変換する。QR分解との違いはこれらの行列の順番だけである。

QR分解はグラム・シュミットの正規直交化法を//A//の//最初の列//から//最後の列//の順に適用する。

RQ分解はグラム・シュミットの正規直交化法を//A//の//最後の行//から//最初の行//の順に適用する。

2.1.3. 利点と欠点
------------

グラム・シュミットの正規直交化法は本来、数値的に不安定である。射影の応用として直交化との幾何学的な類似性があるが、直交化自体は数値的な差異が生じやすい。しかしながら、実装が簡単という大きな利点があり、外部線形代数ライブラリが利用できない場合のプロトタイピングに便利なアルゴリズムである。

2.2. ハウスホルダー変換の使用
-----------------

ハウスホルダー変換 はベクトルを取り、平面または超平面に関する鏡映をする変換である。この演算は//m//×//n//行列 の//QR//変換の計算に使うことができる。

//Q//は一つの座標を除いたすべての座標が未知でもベクトルを鏡映するために使用できる。

スカラ//α//に対してを満たすようなの任意の実//m//次元列ベクトルを考える。もしこのアルゴリズムが浮動小数点演算を用いて実装されている場合、桁落ちを防ぐため、行列//A//の最終的な上三角部分においてすべての要素が0である後のピボット座標に対し、//α//をの//k//番目の座標の逆符号とする。複素行列の場合、

Stoerとし、以下の//Q//の導出において転置を共役転置に読み替えること。

ここで、をベクトルT、||·||をユークリッド距離、を//m//×//m//単位行列とし、

あるいは、が複素行列ならば、

とおく。

は//m//×//m//ハウスホルダー行列であり、

これにより//m//×//n//行列//A//を上三角の形に漸次変換できる。まず、xの最初の列を選んで得られるハウスホルダー行列//Q//1に//A//を乗算する。この結果、行列//Q//1//A//は左の列がゼロになる。

この操作を//A//′ に繰り返すと、ハウスホルダー行列//Q//′2が得られる。//Q//′2は//Q//1より小さいということに注意すること。//A//′の代わりに//Q//1//A//で計算したいため、//A//′を左上に拡張し、ひとつの1を埋める必要がある。つまり、一般的には

とする。回このプロセスを繰り返すと、のとき、

は上三角行列である。であるからして、

とすると、はのQR分解である。

このメソッドは先述のグラム・シュミット法よりも数値的安定性がある。

下表にサイズ//n//の正方行列を仮定したときの、ハウスホルダー変換によるQR分解の//k//番目のステップにおける計算量を示す。

これらの数を//n//   −   1ステップまで合計して、このアルゴリズムの複雑さは

と表せる。

2.2.1. 例
--------

の分解を考える。

まず、行列//A//の最初の列、ベクトルを、に変換する鏡映を見つける必要がある。

今、

とする。

ここで、

であり、であるから、

and であり、 である。

今、

を見てみると、すでにほぼ三角行列である。あとは要素をゼロにするだけでよい。

における小行列を取り、同じプロセスを

に再び適用する。

先述のメソッドと同様にして、このプロセスの次のステップが正しく動作するために、1で直和を取ることにより、ハウスホルダー変換

を得る。

今、

または、有効数字四桁で、

を得た。

行列//Q//は直交行列であり、//R//は上三角行列であるため、//A// = //QR//は求めるべきQR分解である。

2.2.2. 利点と欠点
------------

ハウスホルダー変換の使用は、//R//行列のゼロを生成するメカニズムに鏡映を利用しているため、最もシンプルな数値的に安定したQR分解アルゴリズムである。しかしながら、新しいゼロ要素を生成するすべての鏡映において//Q//、//R//行列両方の全体が変化するため、ハウスホルダー変換は帯域幅が重く、並列化できない。

2.3. ギブンス回転の使用
--------------

//QR//分解はギブンス回転を使用しても計算できる。各回転により行列の亜対角要素がゼロになり、//R//行列を構成できる。すべてのギブンス回転を結合することで直交行列//Q//を構成できる。

実際には、行列全体を構成して乗算をするようなギブンス回転は行われない。代わりに、疎な要素を計算するような無駄な計算をしない、疎なギブンス行列乗算と同等なあるギブンス回転の手順が採られる。そのギブンス回転の手順は少しの非対角成分をゼロにするだけで済み、ハウスホルダー変換よりも容易に並列化できる。

2.3.1. 例
--------

の分解を考える。

まず、左下隅の要素、をゼロにする回転行列を構成する必要がある。この行列はギブンス回転で求めることができる。まずベクトルを、//X//軸に沿って回転させる。このベクトルは角度を持つ。直交ギブンス回転行列を次のように作る。

ここでの結果は要素がゼロである。

同様にしてそれぞれ非対角要素・要素がゼロであるようなギブンス行列・を構成し、三角行列を構成する。直交行列はすべてのギブンス行列の積で表される。したがって、であり、//QR//分解はである。

2.3.2. 利点と欠点
------------

ギブンス回転によるQR分解は、アルゴリズムを完全に動かすのに必要な行の順序を決定するのが簡単ではないため、実装に最も手間がかかる。しかしながら、新しいゼロ要素がゼロになる予定の要素の行とその上の行にしか影響しないという特筆すべき利点がある。これにより、ギブンス回転アルゴリズムはハウスホルダー変換手法よりも帯域幅効率が良く、容易に並列化できる。

3. 行列式や固有値の積との関係
----------------

QR分解を正方行列の行列式の絶対値を求めるのに利用できる。ある行列がと分解できるとする。このとき

である。

//Q//はユニタリであるため、である。したがって、を//R//の対角要素とすると、

となる。

さらに、行列式は固有値の積に等しいため、をの固有値とすると、

となる。

QR分解の定義を非正方行列に導入し、固有値を特異値に置き換えることで、上記性質を非正方行列に拡張することができる。

非正方行列//A//のQR分解を

とする。ただし、は零行列、はユニタリ行列。

特異値分解と行列式の性質から、をの特異値として、

との特異値は同じであるが、複素固有値が異なる場合があることに注意すること。しかしながら、//A//が正方ならば、下記は真である。

結論として、QR分解を使うことによって行列の固有値や特異値の積を効率よく計算することができる。

4. 列のピボット
---------

ピボットQRは列のピボットの新しいステップにおいて、それぞれ初めに残りの列で最も大きいものを取るという点で、通常のグラム・シュミット法とは異なっている。したがって、置換行列//P//を次のように導入する。

列のピボットは//A//が階数落ちである、またはその疑いがある場合に便利である。また、数値的精度を向上させることもできる。通常、//R//の対角成分が非増加、つまりとなるように//P//を選ぶ。この手段により特異値分解よりも低い計算コストで//A//の階数を求めることができ、いわゆるRank Revealing QR分解の基礎となっている。

5. 線形逆問題への利用
------------

行列の逆行列を直接求めるのに比べ、QR分解を利用した逆問題の解法は、条件数が減少していることからも分かるように、数値的に安定している。

次元がで階数がであるような行列に対して、劣決定線形問題を解くためには、まずの転置行列のQR分解を求める。ただし、Qは直交行列であり、Rはという特殊な形である。ここで、は正方右三角行列、零行列は次元である。計算すると、この逆問題の解を次のように表すことができる。

ここで、はガウスの消去法で計算でき、は前方置換法を用いることで直接計算できる。後者の手法の方が数値的精度が高く、計算量も少ないという利点がある。

ノルムを最小にするような過決定問題の解を求めるためには、まずのQR分解を求める。を直交行列全体のうち最初の列を含む行列、を先述の通りに置くと、この問題の解はと表せる。劣決定の場合と同様に、の逆行列を直接計算しなくても、後方置換法を用いることで早く正確にを求めることができる。QR分解として実装されている。)

6. 一般化
------

岩澤分解はQR分解を半単純リー群に一般化している。

7. 脚注
-----

8. 参考文献
-------

8.1. 和文
-------

8.2. 英文
-------

last1=Golub .

9. 関連項目
-------

QR法
固有値分解
LU分解
特異値分解

10. 外部リンク
---------

[1] 行列のQR分解の実行
[2] QR分解の計算のサブルーチンの詳細
[3] QR分解の計算のルーチンの詳細と例
[4] LAPACKのC++、C#、Delphiなどへの移植
[5] QR分解のC++での実装