Orthogonal Deflating Transformation

We shall utilize a special orthogonal transformation to implement the deflation schemes mentioned above. The deflation schemes are related to an eigenvector associated with a Ritz value that is to be deflated (either locked or purged). Given a vector $y$ of unit length, the algorithm shown in Algorithm 4.9 computes an orthogonal matrix $Q$ such that $Q e_1 = y$ (hence $e_1 = Q^* y$). This orthogonal matrix has a very special form and may be written as Q = R + y e_1^*, with R e_1 = 0 , R^* y = 0, where $R$ is upper triangular. It may also be written as Q = L + y g^* , with L e_1 = 0 , L^* y = e_1 - g, where $L$ is lower triangular and $g^* \equiv e_1^* + \frac{1}{\eta_1} e_1^* R$. Here we assume that $y^T=(\eta_1,\dots,\eta_n)$.

Now, consider the matrix $Q^* T Q$. The substitutions $Q^* = (L + y g^* )^*$, $Q = (R + y fe_1^* )$ from (4.24) and (4.23) and the facts $Q^* T y = \theta e_1$ and $1 = y^*y$ will give Q^* T Q &=& Q^* T ( R + y e_1^*)
&=& (L^* + g y^*) T R + e_1 e_1^*
&=& L^*TR + g y^*T R + e_1 e_1^*. Since both $L^*$ and $R$ are upper triangular, it follows that $L^*TR$ is upper Hessenberg with the first row and the first column each being zero due to $Le_1 = Re_1 = 0$. Also, $g y^*T R = g \theta y^*R = 0$. From this we conclude that $L^*TR$ must also be symmetric and hence tridiagonal. Therefore, we see that $T_+ \equiv Q^* T Q$ is of the form

$$T_+ = \left[ \ba{cc} \theta & 0 \\ 0 & \widehat{T} \\ \ea \right],$$

where $\widehat{T}$ is symmetric and tridiagonal.

It should be noted that, as computed by Algorithm 4.9, $Q$ will have componentwise relative errors on the order of machine precision $\epsilon_M$ with no element growth.