正交收缩变换

我们将利用一种特殊的正交变换来实现上述的收缩方案。这些收缩方案与一个与需要收缩（锁定或清洗）的Ritz值相关联的特征向量有关。给定一个单位长度的向量y，如算法4.9所示，计算出一个正交矩阵Q，使得Q e_1 = y（因此e_1 = Q^* y）。这个正交矩阵具有非常特殊的形式，可以写成

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

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

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

其中L是下三角矩阵， g^* \equiv e_1^* + \frac{1}{\eta_1} e_1^* R。 这里我们假设 y^T=(\eta_1,\dots,\eta_n)。

现在，考虑矩阵Q^* T Q。代入 Q^* = (L + y g^* )^*， Q = (R + y fe_1^* ) 来自4.24和4.23 以及事实 Q^* T y = \theta e_1 和 1 = y^*y，将得到

\begin{aligned} Q^* T Q &= Q^* T ( R + y e_1^*) \\ &= (L^* + g y^*) TR + \theta e_1 e_1^* \\ &= L^*TR + g y^*T R + \theta e_1 e_1^*. \end{aligned}

由于L^*和R都是上三角矩阵，因此L^*TR是上Hessenberg矩阵，其第一行和第一列均为零，因为Le_1 = Re_1 = 0。同时，g y^*T R = g \theta y^*R = 0。由此我们得出L^*TR也必须是对称的，因此是三对角的。因此，我们看到 T_+ \equiv Q^* T Q 具有以下形式

T_+ = \begin{bmatrix} \theta & 0 \\0 & \widehat{T} \end{bmatrix},

其中\widehat{T}是对称且三对角的。

需要注意的是，如算法4.9计算的那样，Q将在元素相对误差上达到机器精度\epsilon_M，且没有元素增长。

算法 4.9 IRLM的正交收缩变换
(1)  以 k 维的向量 y 开始，其中 \Vert y \Vert = 1
(2)  Q = 0, \; Q(:,1) = y
(3)  \sigma=y(1)^2, \tau_0 = \vert y(1)\vert
(4)  for j = 2,...,k
(5)      \sigma=\sigma+y(j)^2, \; \tau = \sqrt\sigma
(6)      if \tau_0 \ne 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)     else
(11)         Q(j-1,j) = 1
(12)     end if
(13)     \tau_0 = \tau
(14) end for