QR法

QR法による固有値計算

QR法は、行列の固有値を計算するための数値解析的な手法です。この方法は、行列のQR分解を繰り返し適用することで、元の行列を固有値が対角要素に現れる上三角行列へと変換していくことを目指します。その過程で用いられる行列の相似変換により、元の行列と変換後の行列は同じ固有値を持ちます。

アルゴリズム

1. 初期化: 固有値を求めたい行列をA₁とします。
2. QR分解: Aₖを直交行列Qₖと上三角行列Rₖに分解します。Aₖ = QₖRₖ
3. 行列積: Aₖ₊₁ = RₖQₖを計算します。これはAₖ₊₁ = Qₖ⁻¹AₖQₖという相似変換に相当します。
4. 反復: ステップ2と3を繰り返し、Aₖが収束するまで続けます。収束した行列の対角成分が、元の行列A₁の固有値となります。

この反復過程において、各Aₖは元の行列A₁と相似であるため、固有値は常に保存されます。しかし、固有ベクトルは一般には変化します。固有ベクトルを求めるには、収束した行列から固有値を抽出した後、元の行列A₁を用いて個々の固有値に対応する固有ベクトルを改めて計算する必要があります。

対称行列の場合

行列A₁が対称行列である場合、QR法によって得られる行列Aₖは反復を繰り返すことで三重対角行列に収束していきます。三重対角行列は対角線とその両隣りの成分以外がゼロである行列で、固有値計算が簡略化されます。これは計算コスト削減に繋がる重要な性質です。

原点移動付きQR法

標準的なQR法では、収束までに多くの反復が必要となる場合があります。収束を加速させるために、原点移動付きQR法が用いられます。この方法は、各反復において、行列からある値μₖI（Iは単位行列）を引いた行列をQR分解します。具体的には、以下の手順となります。

1. 初期化: 固有値を求めたい行列をA₁とします。
2. 原点移動とQR分解: Aₖ - μₖIを直交行列Qₖと上三角行列Rₖに分解します。(Aₖ - μₖI) = QₖRₖ
3. 逆変換: Aₖ₊₁ = RₖQₖ + μₖIを計算します。これはAₖ₊₁ = Qₖ⁻¹AₖQₖという相似変換に相当します。
4. 反復: ステップ2と3を繰り返し、Aₖが収束するまで続けます。

μₖの値の選び方によって収束速度が大きく変化します。一般的な方法として、Akの右下隅の2×2小行列の固有値のうち、Akの右下隅の値に近いほうを選択するウィルキンソンの移動法がよく用いられます。この方法により、収束を効果的に促進することができます。

まとめ

QR法は、数値的に安定した固有値計算アルゴリズムであり、特に大規模行列への適用に適しています。対称行列の場合には三重対角行列への収束という利点があり、原点移動付きQR法を用いることで、収束速度の向上も期待できます。これらの特徴から、QR法は工学や科学技術計算において広く利用されている重要な手法です。

もう一度検索