クリロフ部分空間

べき乗の像が張る線型部分空間

クリロフ部分空間(クリロフぶぶんくうかん、英語: Krylov subspace線型代数において、n正方行列Anベクトルbによって生成されるr次クリロフ部分空間は、bAのべき乗の像が張る線型部分空間である。

ロシアの応用数学者で海軍技術者であったアレクセイ・クリロフ英語版にちなんで名づけられた。

大規模疎行列の1個または少数の固有値の計算や、大規模な連立一次方程式の求解に用いられる現代的な反復法では、行列を消去法などで順次変型すると疎行列の構造が崩れてしまい次第に密化するので演算量や記憶を保持する量が共に増大してしまい,ついには扱いきれなくなりがちである。そこでクリロフ系の解法では,元の疎行列を変型せずに,ベクトルに対する線型の作用素としてだけ利用する。つまり与えられたベクトルに対して行列を乗じるという計算を,行列の疎性を活かして(行列が対称であれば対称性も)行うのである。 を初期ベクトルとすると、を順に掛けてを得るといった方法を取る。このようなアルゴリズムを総称して、クリロフ部分空間法と呼ぶ。これは数値線形代数において最も成功した手法の一つである。

ベクトル列は急速に線型従属に近づくため、クリロフ部分空間を用いる方法には、エルミート行列に対してはランチョス法、非エルミート行列に対してはアーノルディ法などの直交化手法が含まれることが多い。

主なクリロフ部分空間法として、アーノルディ法ランチョス法GMRES法(generalized minimum residual)、 BiCGSTAB法 (stabilized biconjugate gradient, 共役勾配法の一つ)、QMR法 (quasi minimal residual)[1][2]、 TFQMR法 (transpose-free QMR)[3]、MINRES法 (minimal residual)[4] などが知られている。

出典

編集
  1. ^ Freund, R. and Nachtigal, N. "QMR: A Quasi-Minimal Residual Method for Non-Hermitian Linear Systems." Numer. Math. 60, 315-339, 1991.
  2. ^ Freund, R. and Nachtigal, N. "An Implementation of the QMR Method Based on Coupled Two-Term Recurrences." SIAM J. Sci. Statist. Comput. 15, 313-337, 1994.
  3. ^ Roland W. Freund, A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, en:SIAM Journal on Scientific Computing 1993; 14(2):470–482.
  4. ^ Christopher C. Paige and Michael A. Saunders, Solution of sparse indefinite systems of linear equations, en:SIAM Journal on Numerical Analysis 1975; 12(4):617–629.

参考文献

編集
  • Saad, Yousef (2003). Iterative methods for sparse linear systems (2nd ed. ed.). SIAM. ISBN 0898715342. OCLC 51266114 
  • David S. Watkins (2008). The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM.
  • Liesen, J. and Strakos, Z. (2012). Krylov subspace methods: principles and analysis. OUP Oxford.
  • Gerard Meurant and Jurjen Duintjer Tebbens (2020). "Krylov methods for nonsymmetric linear systems - From theory to computations", Springer Series in Computational Mathematics, vol.57. ISBN 978-3-030-55250-3, doi:10.1007/978-3-030-55251-0.
  • Iman Farahbakhsh: "Krylov Subspace Methods with Application in Incompressible Fluid Flow Solvers", Wiley, ISBN 978-1119618683 (2020).
  • 藤野清次、阿部邦美、杉原正顯、中嶋徳正:「線形方程式の反復解法」、丸善、 ISBN 978-4621087411(2013年9月27日)。

外部リンク

編集