Jacobi 回転

Jacobi 回転法は、対称行列を対角化するための古典的な反復アルゴリズムです。小規模から中規模の行列に特に適しており、その単純さと頑健さで知られています。この方法は、一連の直交変換（回転）によって非対角要素を系統的に消去していき、最終的に元の行列の固有値を要素とする対角行列に収束させるものです。

Jacobi 法は、行列の最大の非対角要素を対象とし、それをゼロにする回転を適用します。この過程を、すべての非対角要素が十分小さくなるまで反復的に繰り返すと、対角行列が得られます。元の行列の固有値はその対角成分として得られ、固有ベクトルは過程中に適用したすべての回転行列の積から得られます。

原理

対称行列 $A$ に対して、次を満たす直交行列 $P$ を求めることが目標です。

ここで $D$ は $A$ の固有値を含む対角行列であり、$P$ の各列は対応する固有ベクトルです。

Jacobi 法は、$A$ に一連の直交変換（回転）を適用することでこれを実現します。各回転は特定の非対角要素 $A_{ij}$ を対象とし、それをゼロにします。

回転行列

Jacobi 回転行列 $R$ は、単位行列と 4 つの要素だけが異なる直交行列です。

ここで、$\cos \theta$ と $\sin \theta$ は第 $i$ 行・第 $j$ 行と第 $i$ 列・第 $j$ 列の交点に配置されます。角度 $\theta$ は、非対角要素 $A_{ij}$ がゼロになるように選ばれます。

アルゴリズム

1. 最大の非対角要素を特定する：

   • 行列 $A$ の中で（絶対値が）最大の非対角要素 $A_{ij}$ を見つけます。

2. 回転角 $\theta$ を計算する：

   • 角度 $\theta$ は次を満たすように選びます。 $$\tan(2\theta) = \frac{2A_{ij}}{A_{ii} - A_{jj}}$$
   • これから $\cos \theta$ と $\sin \theta$ を計算します。

3. 回転行列 $R$ を構築する：

   • $\cos \theta$ と $\sin \theta$ を用いて回転行列 $R$ を構築します。

4. 回転を適用する：

   • 行列 $A$ を次のように更新します。 $$A^{\prime} = R^T A R$$
   • この変換により $A_{ij}$ と $A_{ji}$ がゼロになります。

5. 変換を累積する：

   • 固有ベクトル行列 $P$ を次のように更新します。 $$P^{\prime} = P R$$
   • これにより回転が累積され、最終的な固有ベクトル行列が得られます。

6. 収束するまで繰り返す：

   • すべての非対角要素が指定した許容誤差 $\epsilon$ より小さくなるまで、この過程を繰り返します。

例

対称行列 $A$ を考えます。

ステップ 1：初期化

行列 $A$ と、回転を累積するための単位行列 $P$ から始めます。

ステップ 2：最大の非対角要素を見つける

$A$ の最大の非対角要素は $A_{13} = 2.000000$ です。

ステップ 3：回転パラメータを計算する

$(1, 3)$ 平面内の回転について、

• 角度 $\theta$ を計算します。

  $$\theta = \frac{1}{2} \arctan\left(\frac{2A_{13}}{A_{11} - A_{33}}\right).$$

  値を代入すると、

  $$\theta = \frac{1}{2} \arctan\left(\frac{2 \cdot 2.000000}{4.000000 - 5.000000}\right) = \frac{1}{2} \arctan(-4.000000).$$

  単精度演算を用いると、

  $$\theta \approx -0.674741 \, \text{radians}.$$

• $c = \cos(\theta)$ と $s = \sin(\theta)$ を計算します。

  $$c \approx 0.780869, \quad s \approx -0.624695.$$

ステップ 4：回転を適用する

回転行列 $J$ を構築します。

$A$ と $P$ を更新します。

回転後は次のようになります。

ステップ 5：他の非対角要素について繰り返す

すべての非対角要素が十分小さく（例えば許容誤差 $10^{-6}$ 未満に）なるまで、次に大きい非対角要素についてこの過程を繰り返します。

ステップ 6：最終的な対角化行列

収束後、対角化された行列 $A$ は次のようになります。

対応する固有ベクトル行列 $P$ は次のようになります。

利点

• 単純さ：アルゴリズムの実装が簡単です。
• 頑健さ：対称行列に対しては収束が保証されています。
• 精度：非常に高精度な固有値と固有ベクトルが得られます。

制限

• 収束の遅さ：大きな行列では多くの反復が必要です。
• 大きな行列に対する非効率性：非常に大きな行列やスパース行列には適していません。
• 計算コスト：各回転で行列全体を更新する必要があり、大きな系ではコストが高くなることがあります。