正交收缩变换

我们将利用一种特殊的正交变换来实现这些收缩方案。这些收缩方案与一个与待收缩（锁定或清除）的 Ritz 值相关的特征向量有关。给定一个单位长度的向量 y，算法7.8计算一个正交矩阵 Q，使得 Q e_1 = y（因此 y = Q^* e_1）。下面的正交收缩变换算法7.8与在 IRLM 中使用的算法4.9（参见第4.5节）相同，但为了完整性，我们再次呈现它。

算法 7.8：IRAM的正交消去变换
(1)  从维度为k的向量y开始，满足 \|y\| = 1。
(2)  Q = 0; \quad Q(:, 1) = y
(3)  \sigma = y(1)^2; \quad \tau_0 = |y(1)|
(4)  对于 j = 2, ..., k
(5)      \sigma := \sigma + y(j)^2, \tau = \sqrt{\sigma}
(6)      如果 \tau_0 \neq 0
(7)          \gamma = (y(j) / \tau) / \tau_0,
(8)          Q(1: j-1, j) = -y(1: j-1) \gamma
(9)          Q(j, j) = \tau_0 / \tau
(10)     否则
(11)         Q(j-1, j) = 1
(12)     结束如果
(13)     \tau_0 = \tau
(14) 结束循环

按照算法7.8构造的正交矩阵 Q 具有非常特殊的形式，可以写成

Q = R + y e_1^*, \quad\text{其中}\quad R e_1 = 0, R^* y = 0, \tag{7.18}

其中 R 是上三角矩阵。它也可以写成

Q = L + y g^*, \quad\text{其中}\quad L e_1 = 0, L^* y = e_1 - g, \tag{7.19}

其中 L 是下三角矩阵， 并且 g^* \equiv e_1^* + \frac{1}{\eta_1} e_1^* R 。

现在，考虑矩阵 Q^* H Q。从 Q^* = (L + y g^* )^*, Q = (R + y e_1^* ) 来自（7.19）和（7.18）将得到

\begin{aligned} Q^* H Q &= Q^* H ( R + y e_1^*) \\ &= (L^* + g y^*) H R + Q^*Hy e_1^* \\ &= L^*HR + g y^*H R + Q^*Hy e_1^*. \end{aligned}

由于 L^* 和 R 都是上三角矩阵，因此 L^*HR 是上海森堡矩阵，其第一行和第一列均为零，由于 Le_1 = Re_1 = 0。

从这一讨论中，我们看到当 y 是 H 的右特征向量 且 Hy = y \theta 时，则 H_+ \equiv Q^* H Q 具有以下形式

H_+ = \begin{bmatrix} \theta & h^* \\ 0 & H_2 \end{bmatrix}. \tag{7.20}

另一方面，当 y 是 H 的左特征向量 且 y^*H = \theta y^* 时，则 H_+ \equiv Q^* H Q 具有以下形式

H_+ = \begin{bmatrix} \theta & 0 \\ h & H_2 \end{bmatrix}, \tag{7.21}

其中 H_2 是上海森堡矩阵。

我们将使用（7.20）来锁定一个已收敛的 Ritz 值，并使用（7.21）来清除一个不想要的但已收敛的 Ritz 值。

需要注意的是，如算法7.8计算的那样， Q 将具有与机器精度 \epsilon_M 相当的逐元素相对误差，且没有元素增长。此外，扩展到复数运算非常直接（不像 Givens 或 Householder 变换）。