GMRES算法原理

• 第一步，格拉姆-施密特(Gram-Schmidt)过程计算高维投影

具体请参考线性代数整理(二) ，这里不再赘述

• 第二步，Krylov子空间及Arnoldi算法

设v是非零n维向量，A是n阶方阵，向量组

生成的向量空间称为k维Krylov子空间(包含在

(n维欧几里得空间)中)，记作

，即

，生成Krylov子空间的向量组称为Krylov向量组。这里假定Krylov向量组是线性无关的。

给定Krylov向量组(k维)，求一组与之等价的规范正交向量组。使用格拉姆-施密特过程求解便可。Arnoldi在研究非对称矩阵的特征值问题时，利用Krylov向量组的特殊结构，给出了格拉姆-施密特算法的一种变体算法，现在称为Arnoldi算法。关于特征值的具体内容请参考线性代数整理(三)

假设k=4，此时Krylov向量组为:

，首先将v单位化，

，然后用v1替换原向量组的v，得

该向量组与原向量组等价。Av1在v1上的投影记为

，则从Av1中减去它在v1上的投影向量，得

，单位化后得

，用v2替换向量组

中的Av1,得

可以证明向量组

与

等价，即它们可以相互线性相关表示。即

中的每个向量可由

中若干向量的线性组合表示。

证明：由

以及

，可得

，或者写作

即Av1可由

中的前两个向量的线性组合表示。在

式两端左乘A，得

结合

可知，

可由

中前三个向量的线性组合表示(因为Av1可以分解到

中)。在

式两端左乘A，得

结合

可知，

可由

中的前四个向量的线性组合表示。

以上证明

可由

线性表示。

反过来，由

可得

，或者写作

即v2可由

中的第一、二向量的线性组合表示，在

式的两端左乘A，得

即Av2可由

中的第二、三向量的线性组合表示，在

式两端左乘A，得

即

可由

中的第三、四向量的线性组合表示，这就证明了

可由向量组

线性表示。