对于nxn实对称阵A，任意非零n维矢量\(\vec{x}\neq 0\)，定义Rayleigh商为
\(r_A( \vec{x} ) = \frac{ \vec{x}^\top A \vec{x} }{ \vec{x}^\top \vec{x} }.\)
显然，Rayleigh商对于\(\vec{x}\)的模并不依赖。
假设A的本征值是\(\lambda_i, i=1,...,n\),从小到大排列：\(\lambda_1 \leq \lambda_2 ... \leq \lambda_n\)。
本征矢是\(\vec{v}_i, i=1,...,n\)，有\(A\vec{v}_i = \lambda_i \vec{v}_i\)。
将非零矢量\(\vec{x}\)用\(\vec{v}_i\)表达，有\(\vec{x} = \sum_i c_i \vec{v}_i\)，则Rayleigh商为
\(r_A ( \vec{x} ) = \frac{ \sum_i c_i^2 \lambda_i^2 }{ \sum_i c_i^2 } \in [ \lambda_1， \lambda_n ]\)。
计算Rayleigh商对\(\vec{x}\)的梯度
\(\nabla r_A(\vec{x}) = \frac{2}{\vec{x}^\top \vec{x}}( A \vec{x} - r_A(\vec{x})\vec{x} ).\)
取\(\nabla r_A(\vec{x}) = 0 \Leftrightarrow A \vec{x} = r_A(\vec{x})\vec{x}\)。
所以，A的Rayleigh商\(r_A(\vec{x}\)在其本征矢\(\vec{v}处取得极值，极值即A的本征值\)\lambda_i$。
若有\(k\)个（\(k\leq n\)）正交归一的n维矢量\(\{ \vec{q}_1, \vec{q}_1, \cdots \vec{q}_k \}\)，构成子空间，记nxk的矩阵\(Q_k \equiv
\begin{bmatrix}
\vec{q}_1, \vec{q}_1, \cdots, \vec{q}_{k}
\end{bmatrix}\)，
这个子空间中任意非零矢量为\(\vec{x} = \sum^k_{i=1} y_i \vec{q}_i = Q_k \vec{y}\)，\(\vec{y}\)是一个k维非零矢量，则A在这个子空间中的Rayleigh商为
\(r_A(Q_k \vec{y}) = \frac{ (Q_k \vec{y})^\top A (Q_k \vec{y}) }{ (Q_k \vec{y})^\top (Q_k \vec{y}) } = \frac{ \vec{y}^\top (Q^\top_k A Q_k) \vec{y} }{ \vec{y}^\top \vec{y} } = r_{Q^\top_k A Q_k}(\vec{y})\)。
转化为\(Q^\top_k A Q_k\)的Rayleigh商。
根据上面的分析，要想构造很小的子空间，使得该子空间内存在最大/最小本征值对应的本征矢\(\vec{v}_1, \vec{v}_n\)的近似矢量，则需要构造\(Q_k\)，使得\(r_{Q^\top_k A Q_k}\)的最小值尽量小，最大值尽量大。
我们可以从选定的\(\vec{q}_1\)开始，逐渐增加\(\vec{q}_2, \vec{q}_3, ...\)，逐渐逼近目标。
一个有用的性质是：\(\nabla r_A(\vec{q}_1) = \frac{2}{\vec{q}^\top_1 \vec{q}_1}( A \vec{q}_1 - r_A(\vec{q}_1)\vec{q}_1 )\)，这个梯度是\(A\vec{q}_1, \vec{q}_1\)的线性叠加。
于是，美妙的想法产生了：何不如此构造子空间呢：\(\kappa(A, \vec{q}_1, k) = \{ \vec{q}_1, A\vec{q}_1, A^2\vec{q}_1, \cdots, A^{k-1}\vec{q}_1 \}\)，这个子空间叫做Krylov子空间。
这样构造的话，对于\(Q_k\)，A的Rayleigh商在\(Q_k\)构造的子空间中任意一处的梯度矢量都在\(Q_{k+1}\)的子空间中。
所以，每次扩大子空间时：$Q_1, Q_2, \cdots, \(，Rayleigh商的最大值都会尽可能地增大，Rayleigh商的最小值都会尽可能地减小。
在这个意义上，Lanczos方法可以看做是Rayleigh商\)r_A$的一个梯度下降/上升过程。
如上所述的策略很美妙，但还有一个小小的问题：我们如何判断子空间已经足够大了呢？换一句话说，我们如何判断子空间中的极端本征值已经足够大，或足够小？
在\(k\)逐渐增大时，我们需要在\(\kappa(A, \vec{q}_1, k)\)中不断地对角化，得到各个子空间中的极端本征值，看它们是否收敛。如果随着\(k\)的增大，极端本征值的变化极其微小，我们则经验地认为已经收敛。
要在\(\kappa(A, \vec{q}_1, k)\)中对角化A，就需要正交归一化\(\vec{q}_1, A\vec{q}_1, \cdots\)。
Lanczos方法即如下步骤，构造\(\vec{q}_1, \vec{q}_2, \cdots\)，既保证每次增加矢量，得到的子空间都是Krylov子空间，又保证\(\vec{q}_1, \cdots, \vec{q}_2, \cdots\)是正交归一矢量。
给定单位矢量\(\vec{q}_1\)，定义\(\vec{r}_2 = A \vec{q}_1 - ( \vec{q}_1^\top A \vec{q}_1 ) \vec{q}_1, \vec{q}_2 = \vec{r}_2 / | \vec{r}_2 |\)。即从\(A\vec{q}_1\)中剔除\(\vec{q}_1\)的分量，然后归一化。
对于\(k\geq 2\)：\(\vec{r}_{k+1} = A \vec{q}_k - (\vec{q}^\top_k A \vec{q}_k) \vec{q}_k - (\vec{q}^\top_{k-1} A \vec{q}_k) \vec{q}_{k-1}, \vec{q}_{k+1} = \vec{r}_{k+1} / | \vec{r}_{k+1} |\)。即从\(A\vec{q}_k\)中剔除\(\vec{q}_{k-1}, \vec{q}_k\)的分量，然后归一化。
显然，如上构造的子空间\(\{\vec{q}_1, \vec{q}_2\} = \{\vec{q}_1, A\vec{q}_1 \}, \{\vec{q}_1, \vec{q}_2, \vec{q}_3 \} = \{ \vec{q}_1, A\vec{q}_1, A^2\vec{q}_1 \}\)。并且\(\vec{q}_1, \vec{q}_2, \vec{q}_3\)正交。
以此为起点，开始归纳法证明：如果\(i=1,2,\cdots,k\)，都有\(\{\vec{q}_1, \cdots, \vec{q}_i\} = \{ \vec{q}_1, A\vec{q}_1, \cdots, A^{i-1}\vec{q}_1 \}\)并且\(\vec{q}_1, \cdots, \vec{q}_i\)两两垂直,那么，如上构造\(\vec{q}_{k+1}\)以后，也会有\(\{\vec{q}_1, \cdots, \vec{q}_i\} = \{ \vec{q}_1, A\vec{q}_1, \cdots, A^{i-1}\vec{q}_{k+1} \}\)并且\(\vec{q}_1, \cdots, \vec{q}_{k+1}\)两两垂直。
由于\(A\vec{q}_1, A\vec{q}_2, \cdots, A\vec{q}_{k-2}\)都是子空间\(\{ \vec{q}_1, \vec{q}_2, \cdots, \vec{q}_{k-1} \}\)中的矢量，所以都垂直于\(\vec{q}_k\)，即
\(\vec{q}_k^\top A \vec{q}_{k-2} = \vec{q}^\top_k A \vec{q}_{k-3} = \cdots \vec{q}^\top_k A \vec{q}_1 = 0\)。
构造\(\vec{r}_{k+1} = A \vec{q}_k - (\vec{q}^\top_k A \vec{q}_k) \vec{q}_k - (\vec{q}^\top_{k-1} A \vec{q}_k) \vec{q}_{k-1}, \vec{q}_{k+1} = \vec{r}_{k+1} / | \vec{r}_{k+1} |\)，
则显然有\(\{\vec{q}_1, \cdots, \vec{q}_k, \vec{q}_{k+1}\} = \{ \vec{q}_1, A\vec{q}_1, \cdots, A^{k}\vec{q}_1 \}\)，剩下的任务是证明\(\vec{q}_{k+1}\)与\(\vec{q}_1, \cdots, \vec{q}_k\)垂直。
由于\(\vec{q}_{k+1}\)是\(A\vec{q}_k\)剔除\(\vec{q}_k, \vec{q}_{k-1}\)的成分构造的，自然与\(\vec{q}_k, \vec{q}_{k-1}\)正交。
因为\(\vec{q}_k\)与子空间\(\{ \vec{q}_1, \cdots \vec{q}_{k-1} \}\)正交，所以\(\vec{q}_k\)与\(A\vec{q}_1, A\vec{q}_2, \cdots, A\vec{q}_{k-2}\)都正交，即
\(\vec{q}^\top_k A \vec{q}_1 = \vec{q}^\top_k A \vec{q}_2 = \cdots = \vec{q}^\top_k A \vec{q}_{k-2} = 0\)。
利用A的对称性，上式即
\(\vec{q}^\top_1 A \vec{q}_k = \vec{q}^\top_2 A \vec{q}_k = \cdots = \vec{q}^\top_{k-2} A \vec{q}_{k} = 0\)。
因此，\(\vec{q}_{k+1}\)与\(\{ \vec{q}_1, \cdots, \vec{q}_k \}\)正交。
至此，命题得证。Lanczos方案确实可以得到正交归一化的Krylov子空间。
原文：https://www.cnblogs.com/luyi07/p/14519804.html