反復法（パワー法、QR法など）

数値線形代数における反復法（パワー法、QR法など）

数値線形代数では、固有値や固有ベクトルを求めることが重要な課題の一つです。大規模な行列に対しては、直接的な計算（固有値分解）には膨大な計算コストがかかるため、反復法が有効に利用されます。反復法は近似を繰り返すことで、固有値・固有ベクトルや分解を求めていく手法の総称です。代表的なものに パワー法 と QR法 があります。

---

1. パワー法（Power Method）

目的: 最大固有値とその固有ベクトルの近似を求める。

• 基本的なアイデア
  任意のベクトルを反復的に行列で掛けていくと、最大固有値に対応する固有ベクトルの方向に収束していく。
  行列 $A$ と初期ベクトル $x_0$ を用いて次を繰り返す：

  $$x_{k+1} = \frac{A x_k}{\|A x_k\|}$$

  このとき、収束したベクトルは最大固有値に対応する固有ベクトルの近似となる。

• 特徴

  • 計算がシンプルで、大規模行列に適している。

  • 最大固有値しか求まらないため、他の固有値を求めるには工夫（シフト法や逆反復法）が必要。

• 応用例
  GoogleのPageRankアルゴリズムは、ウェブリンク構造を表す行列に対してパワー法を応用している。

---

2. QR法（QR Algorithm）

目的: 行列のすべての固有値（必要に応じて固有ベクトルも）を求める。

• 基本的なアイデア
  行列 $A$ にQR分解を繰り返し適用し、対角化された形に近づける。

  1. 行列 $A$ をQR分解する：

     $$A = Q R$$

  2. 行列を更新する：

     $$A’ = R Q$$

  3. これを繰り返すことで、$A_k$ が上三角行列に収束し、その対角成分が固有値の近似になる。

• 特徴

  • 行列全体の固有値を計算できる。

  • 数値的に安定で、実用的に最もよく使われる固有値計算アルゴリズムの一つ。

  • シフト戦略（Wilkinsonシフトなど）を組み合わせることで、収束が大幅に改善する。

---

3. 反復法の位置づけ

• パワー法は「最大固有値の効率的な近似」に特化。

• QR法は「すべての固有値を安定的に計算」する一般解法。

• いずれも大規模行列計算に欠かせない基本技術であり、科学技術計算、シミュレーション、機械学習（例：PCAでの共分散行列の固有分解）などで広く使われる。