クリロフ部分空間

クリロフ部分空間：大規模問題解決への効率的なアプローチ

線形代数において、クリロフ部分空間 (Krylov subspace) は、行列とベクトルから生成される特別な線形部分空間です。その効率性から、大規模な数値計算において重要な役割を果たしています。

クリロフ部分空間の定義

n次正方行列Aとn次ベクトルbを用いて、r次クリロフ部分空間Kr(A, b)は以下のように定義されます。

Kr(A, b) = span{b, Ab, A²b, ..., Ar⁻¹b}

これは、ベクトルbとその行列Aによるr-1回までの反復的な乗算で得られるベクトルによって張られる空間です。この空間は、ロシアの応用数学者アレクセイ・クリロフの名にちなんで名付けられました。

クリロフ部分空間法の必要性

現代の数値計算では、大規模な疎行列（多くの要素が0である行列）を扱うことが頻繁にあります。このような行列に対する連立一次方程式の求解や固有値計算は、直接法（例えばガウスの消去法）では計算コストとメモリ消費量が膨大になり、現実的な時間内に解を得ることが困難となる場合があります。

直接法では、行列の構造を変形して解を求めるため、疎行列の利点が失われ、行列が密行列に近づくにつれて計算量が飛躍的に増加します。

クリロフ部分空間法のメリット

クリロフ部分空間法は、この問題に対するエレガントな解決策を提供します。この手法では、元の疎行列を直接変形することなく、ベクトルに対する線形作用素として利用します。つまり、行列とベクトルの積を効率的に計算することで、疎行列の構造を維持したまま計算を進めることができます。これにより、計算コストとメモリ消費量を大幅に削減できます。

クリロフ部分空間法のアルゴリズム

クリロフ部分空間法は、初期ベクトルbから出発し、行列Aを繰り返し乗算することで、クリロフ部分空間上のベクトル列を生成します。このベクトル列は、急速に線形従属に近づくため、計算の効率化のために直交化などの手法が用いられます。

代表的な直交化手法には、エルミート行列に対するランチョス法や非エルミート行列に対するアーノルディ法などがあります。これらの手法は、クリロフ部分空間の中から、解に最も近いベクトルを効率的に求めることを目指します。

クリロフ部分空間法の種類

クリロフ部分空間法には様々な種類があり、それぞれが異なる特性を持っています。代表的な手法として以下が挙げられます。

アーノルディ法: 非エルミート行列に対する固有値問題や連立一次方程式の解法に用いられます。
ランチョス法: エルミート行列に対する固有値問題に用いられます。
GMRES法 (Generalized Minimum Residual): 非エルミート行列に対する連立一次方程式の解法で、残差ベクトルのノルムを最小化する手法です。
BiCGSTAB法 (Stabilized Biconjugate Gradient): 非エルミート行列に対する連立一次方程式の解法で、共役勾配法を改良した手法です。
QMR法 (Quasi-Minimal Residual): 非エルミート行列に対する連立一次方程式の解法で、残差ベクトルのノルムを近似的に最小化する手法です。
TFQMR法 (Transpose-Free QMR): QMR法の改良版で、転置行列を必要としない手法です。
* MINRES法 (Minimal Residual): 対称不定値行列に対する連立一次方程式の解法です。

これらの手法は、問題の特性や計算資源に応じて適切に選択されます。クリロフ部分空間法は、数値線形代数において最も成功した手法の一つであり、大規模な科学技術計算において重要な役割を果たしています。

もう一度検索