固有値問題の数値解法

数値線形代数における固有値問題の数値解法

数値線形代数において、行列の固有値と固有ベクトルを求める問題は極めて重要です。特に、大規模な行列を扱う際には、計算速度と精度の両方を高めるための効率的な数値解法が不可欠となります。

数値解法の必要性

5次以上の一般の行列（実数または複素数）では、有限回の四則演算と冪根の計算だけで固有値を厳密に求める方法は存在しません。これは、代数方程式の解法に関するガロア理論から導かれる結果です。そのため、固有値問題の数値解法においては、反復法と呼ばれる手法を用いることが必須となります。

例えば、n次代数方程式

$x^n + a_1x^{n-1} + \cdots + a_n = 0$

の解を求めることを考えます。この方程式の係数から構成される同伴行列の固有値が、元のn次代数方程式の解と一致します。しかし、一般のn次代数方程式を有限回の代数演算で解くことは不可能であるため、固有値を厳密に求める代数的な解法は存在しません。ただし、対角行列や上三角行列など、特殊な構造を持つ行列については、固有値を容易に求めることができます。

固有ベクトルの計算

固有値問題の数値解法には、固有値のみを求めるものと、固有値と固有ベクトルの両方を求めるものがあります。後者においては、以下の様な手法が用いられます。

逆べき乗法: 特定の固有値に対応する固有ベクトルを効率的に求める方法です。比較的少数の固有ベクトルを求める場合に有効です。
ヤコビ法: 実対称行列や複素エルミート行列に対して、全ての固有値と固有ベクトルを同時に求めることができる反復法です。実対称行列の場合がよく知られていますが、複素エルミート行列やより一般的な複素行列、実非対称行列に対しても拡張された手法が存在します。

代表的な手法

固有値問題の数値解法には様々なアプローチがありますが、多くは行列の構造を簡略化してから解くという戦略に基づいています。

実対称行列または複素エルミート行列: これらの行列は、直交変換またはユニタリ変換を用いて三重対角行列に変換することができます。三重対角行列の固有値問題を解くことは、元の行列の固有値問題を解くことと同等であり、三重対角行列に対する効率的なアルゴリズムが数多く開発されています。
一般の行列: 一般の行列（実数または複素数）は、ヘッセンベルグ行列と呼ばれる特殊な構造の行列に変換することができます。この変換は、Givens回転やHouseholder変換といった直交変換またはユニタリ変換を用いて行われます。ヘッセンベルグ行列に対する固有値問題を解くことで、元の行列の固有値問題を解くことができます。

これらの変換を行うための代表的な手法として、Givens回転とHouseholder変換が挙げられます。歴史的には、密行列に対してはJacobi回転を用いたJacobi対角化法が広く使われていましたが、計算量やメモリアクセスパターンなどの問題から、Givens回転やHouseholder変換を用いた手法に取って代わられました。ただし、小規模な行列や高い直交精度が要求される場合などには、現在でもJacobi法が用いられることがあります。

疎行列に対しては、クリロフ部分空間法が有効です。クリロフ部分空間法は、行列ベクトル積を繰り返し計算することで固有値問題を近似的に解く手法であり、疎行列に対しては計算コストを抑えることができます。

参考文献

一松信：「数値解析」、朝倉書店
森正武：「数値解析法」、朝倉書店
大石進一：「精度保証付き数値計算」、コロナ社
櫻井鉄也, 松尾宇泰, 片桐孝洋編：数値線形代数の数理とHPC, 共立出版
大石進一 編著：『精度保証付き数値計算の基礎』、コロナ社
日本計算工学会(編):「固有値計算と特異値計算」、丸善

もう一度検索