QR分解

QR分解（キューアールぶんかい、）とは、"m" × "n" 実行列 "A"を、 "m" 次直交行列 "Q" と "m" × "n" 上三角行列 "R" との積への分解により表すこと、またはそう表した表現をいう。このような分解は常に存在する。
QR分解は線型最小二乗問題を解くために使用される。また、固有値問題の数値解法の1つであるQR法の基礎となっている。
定義.
正方行列.
すべての実正方行列 "A"は直交行列"Q"と上三角行列(別名右三角行列)"R"を用いて
と分解できる。もし"A"が正則ならば、"R"の対角成分が正になるような因数分解は一意に定まる。
もし"A"が複素正方行列ならば、"Q"がユニタリ行列 (つまりformula_2)となるような分解"A" = "QR"が存在する。
もし"A"が"n"個の線形独立な列を持つなら、"Q"の最初の"n"列は"A"の列空間の正規直交基底をなす。より一般的に、1 ≤ "k" ≤ "n"の任意の"k"について、"Q"の最初の"k"列は"A"の最初の"k"列の線型包をなす"。A"の任意の列"k"が"Q"の最初の"k"列にのみ依存するということは、"R"が三角行列であることから明らかである。
矩形行列.
より一般的に、"m" ≥ "n"である複素"m"×"n"行列"A"を、"m"×"m"ユニタリ行列"Q"と"m"×"n"上三角行列"R"に分解することができる。"m"×"n"上三角行列の下から("m"−"n")行はすべてゼロであるため、"R"や、"R"と"Q"両方の分割を簡単に行うことができる。
ここで、"R"1は"n"×"n"上三角行列、"0"は("m" − "n")×"n"零行列、"Q"1は"m"×"n"行列、"Q"2は"m"×("m" − "n")行列で、"Q"1と"Q"2は両方直交する列を持つ。
"Q"1"R"1をはAの薄い("thin")QR分解と呼び、 Trefethen & Bauは軽減("reduced")QR分解と呼んでいる。もし"A"が最大階数"n"であり、"R"1の対角成分を正にするならば、"R"1と"Q"1は一意に定まる。しかし一般的に"Q"2はそうではない。"R"1は"A"* "A" ("A"が実行列の場合"A"T"A"に等しい)のコレスキー分解の上三角部分に等しい。
QL・RQ・LQ分解.
同様に、"L"を下("lower")三角行列として、QL、RQ、LQ分解を定義することができる。
QR分解の計算.
QR分解を計算する手法として、グラム・シュミット分解、ハウスホルダー変換、ギブンス回転などがある。それぞれ利点と欠点がある。
グラム・シュミットの正規直交化法の使用.
グラム・シュミットの正規直交化法を最大階数行列の列formula_4に適用することを考える。内積formula_5 (複素ベクトルの場合 formula_6)とする。
射影の定義より、
したがって、
ここでformula_9を新しく計算された正規直交基底上に表すことができ、formula_10であるから、
これは行列の形に書くことができ、
ただし、
例.
の分解を考える。
正規直交行列formula_16に対して、
が常に成り立つから、グラム・シュミット法により以下の手順でformula_16を計算できる。
したがって、
RQ分解との関係.
RQ分解は行列"A"を上三角行列"R"(別名右三角)と直交行列"Q"に変換する。QR分解との違いはこれらの行列の順番だけである。
QR分解はグラム・シュミットの正規直交化法を"A"の"最初の列"から"最後の列"の順に適用する。
RQ分解はグラム・シュミットの正規直交化法を"A"の"最後の行"から"最初の行"の順に適用する。
利点と欠点.
グラム・シュミットの正規直交化法は本来、数値的に不安定である。射影の応用として直交化との幾何学的な類似性があるが、直交化自体は数値的な差異が生じやすい。しかしながら、実装が簡単という大きな利点があり、外部線形代数ライブラリが利用できない場合のプロトタイピングに便利なアルゴリズムである。
ハウスホルダー変換の使用.
ハウスホルダー変換 (または"ハウスホルダー鏡映")はベクトルを取り、平面または超平面に関する鏡映をする変換である。この演算は"m"×"n"行列formula_21 ("m" ≥ "n")の"QR"変換の計算に使うことができる。
"Q"は一つの座標を除いたすべての座標が未知でもベクトルを鏡映するために使用できる。
スカラ"α"に対してformula_22を満たすようなformula_21の任意の実"m"次元列ベクトルformula_24を考える。もしこのアルゴリズムが浮動小数点演算を用いて実装されている場合、桁落ちを防ぐため、行列"A"の最終的な上三角部分においてすべての要素が0である後のピボット座標formula_25に対し、"α"をformula_24の"k"番目の座標の逆符号とする。複素行列の場合、
とし、以下の"Q"の導出において転置を共役転置に読み替えること。
ここで、formula_28をベクトル(1 0 … 0)T、||·||をユークリッド距離、formula_29を"m"×"m"単位行列とし、
あるいは、formula_21が複素行列ならば、
とおく。
formula_16は"m"×"m"ハウスホルダー行列であり、
これにより"m"×"n"行列"A"を上三角の形に漸次変換できる。まず、xの最初の列を選んで得られるハウスホルダー行列"Q"1に"A"を乗算する。この結果、行列"Q"1"A"は左の列が(最初の行を除き)ゼロになる。
この操作を"A"′ ("Q"1"A"から最初の列と最初の行を除いたもの)に繰り返すと、ハウスホルダー行列"Q"′2が得られる。"Q"′2は"Q"1より小さいということに注意すること。"A"′の代わりに"Q"1"A"で計算したいため、"A"′を左上に拡張し、ひとつの1を埋める必要がある。つまり、一般的には
とする。
formula_37回このプロセスを繰り返すと、formula_38のとき、
は上三角行列である。であるからして、
とすると、
formula_12はformula_21のQR分解である。
このメソッドは先述のグラム・シュミット法よりも数値的安定性がある。
下表にサイズ"n"の正方行列を仮定したときの、ハウスホルダー変換によるQR分解の"k"番目のステップにおける計算量を示す。
これらの数を"n" − 1ステップ(サイズ"n"の正方行列であるため)まで合計して、このアルゴリズムの(浮動小数点演算の観点からの)複雑さは
と表せる。
例.
の分解を考える。
まず、行列"A"の最初の列、ベクトルformula_45を、formula_46に変換する鏡映を見つける必要がある。 
今、
とする。
ここで、
であるから、
である。
今、
を見てみると、すでにほぼ三角行列である。あとは(3, 2)要素をゼロにするだけでよい。
(1, 1)における小行列を取り、同じプロセスを
に再び適用する。
先述のメソッドと同様にして、このプロセスの次のステップが正しく動作するために、1で直和を取ることにより、ハウスホルダー変換
を得る。
今、
または、有効数字四桁で、
を得た。
行列"Q"は直交行列であり、"R"は上三角行列であるため、"A" = "QR"は求めるべきQR分解である。
利点と欠点.
ハウスホルダー変換の使用は、"R"行列のゼロを生成するメカニズムに鏡映を利用しているため、最もシンプルな数値的に安定したQR分解アルゴリズムである。しかしながら、新しいゼロ要素を生成するすべての鏡映において"Q"、"R"行列両方の全体が変化するため、ハウスホルダー変換は帯域幅が重く、並列化できない。
ギブンス回転の使用.
"QR"分解はギブンス回転を使用しても計算できる。各回転により行列の亜対角要素がゼロになり、"R"行列を構成できる。すべてのギブンス回転を結合することで直交行列"Q"を構成できる。
実際には、行列全体を構成して乗算をするようなギブンス回転は行われない。代わりに、疎な要素を計算するような無駄な計算をしない、疎なギブンス行列乗算と同等なあるギブンス回転の手順が採られる。そのギブンス回転の手順は少しの非対角成分をゼロにするだけで済み、ハウスホルダー変換よりも容易に並列化できる。
例.
の分解を考える。
まず、左下隅の要素、formula_59をゼロにする回転行列を構成する必要がある。この行列formula_60はギブンス回転で求めることができる。まずベクトルformula_61を、"X"軸に沿って回転させる。このベクトルは角度formula_62を持つ。直交ギブンス回転行列formula_60を次のように作る。
ここでformula_65の結果はformula_66要素がゼロである。
同様にしてそれぞれ非対角要素formula_68・formula_69要素がゼロであるようなギブンス行列formula_70・formula_71を構成し、三角行列formula_72を構成する。直交行列formula_73はすべてのギブンス行列の積formula_74で表される。したがって、formula_75であり、"QR"分解はformula_12である。
利点と欠点.
ギブンス回転によるQR分解は、アルゴリズムを完全に動かすのに必要な行の順序を決定するのが簡単ではないため、実装に最も手間がかかる。しかしながら、新しいゼロ要素formula_77がゼロになる予定の要素の行(i)とその上の行(j)にしか影響しないという特筆すべき利点がある。これにより、ギブンス回転アルゴリズムはハウスホルダー変換手法よりも帯域幅効率が良く、容易に並列化できる。
行列式や固有値の積との関係.
QR分解を正方行列の行列式の絶対値を求めるのに利用できる。ある行列がformula_12と分解できるとする。このとき
である。
"Q"はユニタリであるため、formula_80である。したがって、formula_81を"R"の対角要素とすると、
となる。
さらに、行列式は固有値の積に等しいため、formula_83をformula_21の固有値とすると、
となる。
QR分解の定義を非正方行列に導入し、固有値を特異値に置き換えることで、上記性質を非正方行列formula_21に拡張することができる。
非正方行列"A"のQR分解を
とする。ただし、formula_88は零行列、formula_16はユニタリ行列。
特異値分解と行列式の性質から、formula_90をformula_21の特異値として、
formula_21とformula_72の特異値は同じであるが、複素固有値が異なる場合があることに注意すること。しかしながら、"A"が正方ならば、下記は真である。
結論として、QR分解を使うことによって行列の固有値や特異値の積を効率よく計算することができる。
列のピボット.
ピボットQRは列のピボットの新しいステップにおいて、それぞれ初めに残りの列で最も大きいものを取るという点で、通常のグラム・シュミット法とは異なっている。したがって、置換行列"P"を次のように導入する。
列のピボットは"A"が(ほぼ)階数落ちである、またはその疑いがある場合に便利である。また、数値的精度を向上させることもできる。通常、"R"の対角成分が非増加、つまりformula_97となるように"P"を選ぶ。この手段により特異値分解よりも低い計算コストで"A"の(数値的な)階数を求めることができ、いわゆるの基礎となっている。
線形逆問題への利用.
行列の逆行列を直接求めるのに比べ、QR分解を利用した逆問題の解法は、条件数が減少していることからも分かるように、数値的に安定している。
次元がformula_98で階数がformula_99であるような行列formula_21に対して、劣決定(formula_101)線形問題formula_102を解くためには、まずformula_21の転置行列のQR分解formula_104を求める。ただし、Qは直交行列(つまり、formula_105)であり、Rはformula_106という特殊な形である。ここで、formula_107はformula_108正方右三角行列、零行列はformula_109次元である。計算すると、この逆問題の解を次のように表すことができる。formula_110
ここで、formula_111はガウスの消去法で計算でき、formula_112はを用いることで直接計算できる。後者の手法の方が数値的精度が高く、計算量も少ないという利点がある。
ノルムformula_113を最小にするような過決定(formula_114)問題formula_102の解formula_116を求めるためには、まずformula_21のQR分解formula_12を求める。formula_119を直交行列formula_16全体のうち最初のformula_121列を含むformula_98行列、formula_107を先述の通りに置くと、この問題の解はformula_124と表せる。劣決定の場合と同様に、formula_107の逆行列を直接計算しなくても、を用いることで早く正確にformula_126を求めることができる。(formula_119とformula_107は数値ライブラリによっては高速な("economic")QR分解として実装されている。)
一般化.
はQR分解を半単純リー群に一般化している。