克雷洛夫子空間

線性代數中，由n階方陣A與n維向量b生成的r階克雷洛夫子空間是b在A的前r次冪下（始於 $A^{0}=I$ ）的列空間張成的線性子空間，即^[1]^[2]

{\mathcal {K}}_{r}(A,b)=\operatorname {span} \,\{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}.

背景[編輯]

這一概念得名於蘇聯應用數學家、海軍工程師Alexei Krylov，他在1931年發表了一篇關於這一概念的論文。^[3]

性質[編輯]

${\mathcal {K}}_{r}(A,b),A\,{\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r+1}(A,b)$ .
令 $r_{0}=\operatorname {dim} \operatorname {span} \,\{b,Ab,A^{2}b,\ldots \}$ ，則 $\{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}$ 是線性無關的，除非 $\forall r>r_{0},\ {\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r_{0}}(A,b)$ ， $\operatorname {dim} {\mathcal {K}}_{r_{0}}(A,b)=r_{0}$ 。因此 $r_{0}$ 是克雷洛夫子空間 ${\mathcal {K}}_{r}(A,b)$ 的最大維度。
最大維度滿足 $r_{0}\leq 1+\operatorname {rank} A,\ r_{0}\leq n$ .
考慮 $\dim \operatorname {span} \,\{I,A,A^{2},\ldots \}=\deg \,p(A)$ ，其中 $p(A)$ 是A的極小多項式。我們有 $r_{0}\leq \deg \,p(A)$ 。此外 $\forall A,\ \exists b$ ，對它來說此約束是緊密的，即 $r_{0}=\deg \,p(A)$ 。
${\mathcal {K}}_{r}(A,b)$ 是由b產生的扭化 $k[x]$ -模 $(k^{n})^{A}$ 的循環子模，其中 $k^{n}$ 是k上的線性空間。
$k^{n}$ 可分解為克雷洛夫子空間的直和。^{[需要解釋]}

使用[編輯]

克雷洛夫子空間用於尋找高維線性代數問題的近似解。^[2]控制論的很多線性動態系統檢測，特別是與可控制性和可觀測性相關的測試，都要檢查克雷洛夫子空間的秩。測試等同於尋找與系統/輸出映射相關的格拉姆行列式的張成空間，因此不可控與不可觀測子空間只是克雷洛夫子空間的正交補。^[4] 阿諾德迭代法等現代迭代法可用於尋找大型稀疏矩陣的特徵值，或求解大型線性方程組。這些方法儘量避免矩陣間的運算，而將向量與矩陣相乘。從向量b開始，可以計算 $Ab$ ，然後將向量與A相乘，求得 $A^{2}b$ 等等。所有這樣的算法都稱作克雷洛夫子空間方法，是目前數值線性代數中最成功的方法之一。這些方法可用於能計算矩陣-向量乘法而無A的顯式表示的情形，從而產生了無矩陣法。

問題[編輯]

由於冪迭代的特性，向量很快就會變得近乎線性相關，因此依賴於克雷洛夫子空間的方法經常要正交化，例如厄米矩陣的蘭佐斯算法或更一般矩陣的阿諾德迭代法。

現有方法[編輯]

最著名的克雷洛夫法有共軛梯度法、誘導降維法、廣義最小殘量方法、穩定雙共軛梯度法、准最小殘差法、無轉置准最小殘差法、最小殘差法等等。

另見[編輯]

迭代法

參考文獻[編輯]

^ Nocedal, Jorge; Wright, Stephen J. Numerical optimization. Springer series in operation research and financial engineering 2nd. New York, NY: Springer. 2006: 108. ISBN 978-0-387-30303-1.
^ ^2.0 ^2.1 Simoncini, Valeria, Krylov Subspaces, Nicholas J. Higham; et al (編), The Princeton Companion to Applied Mathematics, Princeton University Press: 113–114, 2015
^ Krylov, A. N. О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем [On the Numerical Solution of Equation by Which are Determined in Technical Problems the Frequencies of Small Vibrations of Material Systems]. Izvestiia Akademii Nauk SSSR. 1931, 7 (4): 491–539 （俄語）.
^ Hespanha, Joao, Linear Systems Theory, Princeton University Press, 2017

閱讀更多[編輯]

Nevanlinna, Olavi. Convergence of iterations for linear equations. Lectures in Mathematics ETH Zürich. Basel: Birkhäuser Verlag. 1993: viii+177 pp. ISBN 3-7643-2865-7. MR 1217705.
Saad, Yousef. Iterative methods for sparse linear systems 2nd. SIAM. 2003. ISBN 0-89871-534-2. OCLC 51266114.
Gerard Meurant and Jurjen Duintjer Tebbens: 」Krylov methods for nonsymmetric linear systems - From theory to computations」, Springer Series in Computational Mathematics, vol.57, (Oct. 2020). ISBN 978-3-030-55250-3, url=https://doi.org/10.1007/978-3-030-55251-0.
Iman Farahbakhsh: "Krylov Subspace Methods with Application in Incompressible Fluid Flow Solvers", Wiley, ISBN 978-1119618683 (Sep., 2020).

[1] Nocedal, Jorge; Wright, Stephen J. Numerical optimization. Springer series in operation research and financial engineering 2nd. New York, NY: Springer. 2006: 108. ISBN 978-0-387-30303-1.

[PrincetonCompanion-2] 2.0 ^2.1 Simoncini, Valeria, Krylov Subspaces, Nicholas J. Higham; et al (編), The Princeton Companion to Applied Mathematics, Princeton University Press: 113–114, 2015

[3] Krylov, A. N. О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем [On the Numerical Solution of Equation by Which are Determined in Technical Problems the Frequencies of Small Vibrations of Material Systems]. Izvestiia Akademii Nauk SSSR. 1931, 7 (4): 491–539 （俄語）.

[Linear_Systems_Theory-4] Hespanha, Joao, Linear Systems Theory, Princeton University Press, 2017

[1]

[2]

[3]

[4]