Lanczos アルゴリズム

Lanczos 法は、サイズ $N \times N$ の対称行列 $A$ を、サイズ $m \times m$（$m \ll N$）の三重対角行列 $T$ に縮約する反復アルゴリズムです。$T$ の固有値は $A$ の端の固有値を近似し、対応する固有ベクトルも再構成できます。

Lanczos 法の主なステップ

1. 初期化：

   • ノルムが 1 のランダムな初期ベクトル $v_1$ を選びます。
   • $\beta_0 = 0$、$v_0 = 0$ とおきます。

2. 反復： $j = 1, 2, \dots, m$ について、

   • $w = A v_j - \beta_{j-1} v_{j-1}$ を計算します。
   • $\alpha_j = v_j^\top w$ を計算します。
   • $w = w - \alpha_j v_j$ を計算します。
   • $\beta_j = \|w\|$ を計算します。
   • $\beta_j = 0$ ならば停止し、そうでなければ $v_{j+1} = w / \beta_j$ とおきます。

3. 三重対角行列： $m$ 回の反復の後、行列 $T$ は次のように構築されます。

   $$T = \begin{pmatrix} \alpha_1 & \beta_1 & 0 & \dots & 0 \\\ \beta_1 & \alpha_2 & \beta_2 & \dots & 0 \\\ 0 & \beta_2 & \alpha_3 & \dots & 0 \\\ \vdots & \vdots & \vdots & \ddots & \beta_{m-1} \\\ 0 & 0 & 0 & \beta_{m-1} & \alpha_m \end{pmatrix}$$

4. $T$ の対角化：

   • 標準的な密行列の手法（例えば QR アルゴリズム）を用いて $T$ を対角化します。
   • $T$ の固有値は $A$ の端の固有値を近似します。
   • $A$ の対応する固有ベクトルは、Lanczos ベクトル $v_j$ から再構成できます。

Lanczos 法の利点

1. 効率性：

   • 行列ベクトル積だけが必要なため、スパース行列に適しています。
   • メモリ使用量は $O(N^2)$ ではなく $O(N \cdot m)$ です。

2. スケーラビリティ：

   • 密行列の手法では実行不可能な非常に大きな行列に対しても、うまく機能します。

3. 端の固有値への特化：

   • Lanczos 法は、最大または最小の固有値とその固有ベクトルを求めるのに特に効果的です。

課題と注意点

1. 直交性の喪失：

   • 有限精度の演算では、Lanczos ベクトル $v_j$ の直交性が失われることがあり、偽の固有値が現れる原因となります。
   • 対策としては、再直交化や、陰的再始動 Lanczos 法（Implicitly Restarted Lanczos Method）のようなより高度な変種の使用があります。

2. $m$ の選択：

   • 反復回数 $m$ は、精度と計算コストのバランスを取るよう慎重に選ぶ必要があります。

3. 収束：

   • 端の固有値への収束は一般に速いですが、内部の固有値には多くの反復が必要になることがあります。