固有値計算

固有値を数値的に求める問題。

特性方程式は使わない#

$\det (A-\lambda I)=0$ を解くのは最悪の方法。

• 5 次以上の多項式に解の公式が無い
• 多項式の係数から根を求めるのは極めて悪条件

代わりに相似変換の反復で対角に近づける。

主な手法#

手法	用途
べき乗法	最大固有値だけ。$A^{k}v$ を繰り返す
逆反復法	特定の固有値の近く
QR 法	全固有値。実用の標準
Lanczos / Arnoldi	大規模疎行列。一部の固有値のみ

QR 法は $A=QR$ と分解して $A^{\prime }=RQ$ とする操作を繰り返す。 $A^{\prime }$ は $A$ と相似（固有値が同じ）で、反復すると上三角に近づく。

コスト#

密行列の全固有値で $𝒪(n^3)$。

CMA-ES が 毎世代ではなく $𝒪(n^2)$ 世代に 1 回だけ分解するのは、 このコストが次元の増加とともに支配的になるため。

対称行列は特別扱い#

対称行列は固有値が実数、 固有ベクトルが直交するので、専用の高速で安定な手法がある。 NumPy でも eigh（対称用）と eig（一般）が分かれており、 対称と分かっているなら eigh を使うべき。

参考文献#

• Lloyd N. Trefethen, David Bau III. Numerical Linear Algebra. SIAM, 1997. https://doi.org/10.1137/1.9780898719574
• Gene H. Golub, Charles F. Van Loan. Matrix Computations, 4th ed. Johns Hopkins University Press, 2013. https://www.press.jhu.edu/books/title/10678/matrix-computations