QR分解

QR分解：定義と応用

QR分解は、線形代数において重要な行列分解の一種です。m×nの実行列Aを、m次直交行列Qとm×nの上三角行列Rの積として表現する手法、またはその表現自体を指します。Aが正則な場合、Rの対角成分を正とする分解は一意に定まります。複素行列の場合、Qはユニタリ行列となります。QR分解は常に存在することが保証されています。

定義:

正方行列: 任意の実正方行列Aは、直交行列Qと上三角行列Rを用いてA=QRと分解できます。Aが正則な場合、Rの対角成分が正となる分解は一意に定まります。複素正方行列の場合、Qはユニタリ行列となります。
矩形行列: m≧nである複素m×n行列Aは、m×mユニタリ行列Qとm×n上三角行列Rに分解できます。この場合、Rの下から(m-n)行はすべてゼロとなります。この性質を利用して、RやQをさらに分割し、効率的な計算を行うことができます。例えば、A = Q₁R₁という薄いQR分解(thin QR decomposition)や、軽減QR分解(reduced QR decomposition)が用いられます。

QR分解の計算アルゴリズム:

QR分解を計算する主なアルゴリズムとして、以下の3つがあります。

1. グラム・シュミットの正規直交化法: Aの列ベクトルを正規直交化することでQを求め、Rは内積を用いて計算します。実装が容易ですが、数値的に不安定なため、大規模な行列には適しません。

2. ハウスホルダー変換: 反射変換を用いて、Aを上三角行列Rに変換します。数値的に安定しており、広く利用されています。計算量はO(n³)です。

3. ギブンス回転: 回転行列を用いて、Aの非対角要素を順次ゼロ化していくことでRを求めます。並列化が容易で、帯域幅が狭い行列に適しています。

それぞれのアルゴリズムの比較:



線形逆問題への応用:

QR分解は、線形逆問題を解く上で重要な役割を果たします。

劣決定問題 (m < n): Aᵀ = QR の分解を用いて最小ノルム解を求めます。
過決定問題 (m ≥ n): A = QR の分解を用いて最小二乗解を求めます。

QR分解を用いることで、直接逆行列を求めるよりも数値的に安定した解を得ることができます。特に、条件数の大きな行列に対しては有効です。

行列式や固有値との関係:

正方行列A = QR の場合、|det(A)| = |det(R)| = |∏ᵢrᵢᵢ| が成り立ちます。行列式は固有値の積に等しいため、QR分解から固有値の積の絶対値を効率的に求めることができます。非正方行列の場合は、固有値の代わりに特異値を用いて同様の関係が成り立ちます。

列のピボット:

ピボットQR分解は、列の入れ替えを考慮することで、数値的安定性を向上させ、行列の階数を推定するのに役立ちます。

結論:

QR分解は、線形代数における基本的な行列分解の一つであり、線形最小二乗問題、固有値問題、特異値問題など、様々な数値計算において広く利用されています。グラム・シュミット法、ハウスホルダー変換、ギブンス回転といった様々なアルゴリズムが存在し、問題の特性や計算環境に応じて最適なアルゴリズムを選択する必要があります。それぞれのアルゴリズムの長所と短所を理解することで、効率的かつ正確な計算を実現することができます。

もう一度検索