基本算法

Arnoldi方法是一种投影到Krylov子空间上的正交投影方法。 它从Arnoldi过程开始，如算法7.3所述。 该过程基本上可以看作是构建Krylov子空间\mathcal{K}^m(A,v)正交基的改进Gram-Schmidt过程。

算法 7.3：Arnoldi 过程
(1)  对起始向量 v，计算 v_1 = \frac{v}{\|v\|_2}
(2)  对于 j = 1, 2, ..., m 执行循环
(3)      w := A v_j
(4)      对于 i = 1, 2, ..., j 执行循环
(5)          h_{ij} = w^* v_i
(6)          w := w - h_{ij} v_i
(7)      结束循环
(8)      h_{j+1, j} = \|w\|_2
(9)      如果 h_{j+1, j} = 0，则停止
(10)     v_{j+1} = \frac{w}{h_{j+1, j}}
(11) 结束循环

上述过程 会在第(8)行计算的向量w消失时停止。 向量v_1, v_2, \ldots , v_m通过构造形成一个正交系统，被称为Arnoldi向量。 一个简单的归纳论证表明，这个系统是Krylov子空间\mathcal{K}^m(A,v)的一个基。

接下来我们考虑算法生成的量之间的一个基本关系。 以下等式很容易推导出：

A v_j = \sum_{i=1}^{j+1} h_{ij} v_i , \quad j=1,2,\ldots ,m \ . \tag{7.6}

如果我们用V_m表示列向量为v_1,\ldots, v_m的n \times m矩阵，用H_m表示由算法定义的非零元素h_{ij}的m \times m海森堡矩阵，那么以下关系成立：

A V_m = V_m H_m + h_{m+1,m} v_{m+1} e_m^{\ast} , \tag{7.7}

V_m^{\ast} A V_m = H_m \ . \tag{7.8}

关系 (7.8) 通过将 (7.7) 的两边乘以V_m^{\ast}并利用\{v_1, \ldots,v_m\}的正交性从 (7.7) 得出。

如前所述，当第(8)行计算的w的范数在某一步j消失时，算法会中断。 事实证明，这当且仅当起始向量v是j个特征向量的组合时发生（即，v_1的最小多项式是j次）。 此外，子空间\mathcal{K}_j是然后不变的，近似特征值和特征向量是精确的[387]。

投影过程在\mathcal{K}_m上提供的近似特征值\lambda_i^{(m)}是海森堡矩阵H_m的特征值。这些被称为Ritz值。 与Ritz值\lambda_i^{(m)}相关的Ritz近似特征向量定义为u_i^{(m)}= V_m y_i^{(m)}，其中y_i^{(m)}是与特征值\lambda_i^{(m)}相关的特征向量。通常，Ritz特征值的少数几个将构成A的相应特征值\lambda_i的良好近似，并且近似的质量通常会随着m的增加而提高。

原始算法包括增加m直到找到A的所有期望特征值。对于大矩阵，这在计算和存储方面都变得昂贵。 在存储方面，我们需要保留m个长度为n的向量加上一个m \times m海森堡矩阵，总共大约nm + m^2/2。对于算术成本，我们需要将v_j乘以A，成本为2 \times N_z，其中N_z是A中的非零元素数量，然后对j个向量进行正交化，成本为4(j+1)n，这随着步数j增加。因此，m维Arnoldi过程的成本在存储上为\approx nm + m^2/2，在算术操作上为\approx N_z + 2nm^2。

在算法进行过程中获得Ritz对的残差范数是相当廉价的。 设y_i^{(m)}是与特征值\lambda_i^{(m)}相关的H_m的特征向量，设u_i^{(m)}是Ritz近似特征向量u_i^{(m)}= V_m y_i^{(m)}。我们有以下关系：

(A - \lambda_i^{(m)}I ) u_i^{(m)}= h_{m+1,m}(e_m^{\ast} y_i^{(m)})v_{m+1},

因此，

\Vert ( A - \lambda_i^{(m)}I ) u_i^{(m)}\Vert _2 = h_{m+1,m} \vert e_m^{\ast} y_i^{(m)}\vert \ .

因此，残差范数等于特征向量y_i^{(m)}的最后一个分量的绝对值乘以h_{m+1,m}。残差范数并不总是指示\lambda_i^{(m)}中的实际误差，但可以非常有帮助地推导停止过程。