Golub-Kahan-Lanczos双对角化过程

如第§6.2节所述， SVD变换方法的第一阶段是计算酉矩阵U和V，使得 U^*AV呈双对角形式。实际上，V的第一列v_1 可以选择为任意单位向量，之后U和V的其他列通常是唯一确定的。 我们将其表示为

U^{*} A V = B = \begin{bmatrix}\alpha_1 & \beta_1 & & & \\& \alpha_2 & \beta_2 & & \\& & \ddots & \ddots & \\& & & \alpha_{n-1} & \beta_{n-1} \\& & & & &\alpha_{n} \end{bmatrix}. \tag{6.4}

即使A是复数，所有\alpha和\beta也都是实数。

常数\alpha_k和\beta_k由以下公式给出：

\alpha_k = u^{\ast}_k A v_k \quad\mathrm{和}\quad\beta_k = u^{\ast}_k A v_{k+1}.

从双对角形式 (6.4)中，我们可以推导出U和V的列u_k和v_k的双重递归。乘以U，我们有

A\begin{bmatrix}v_1 & v_2 & \ldots & v_n \end{bmatrix} = U\begin{bmatrix}\alpha_1 & \beta_1 & & & \\& \alpha_2 & \beta_2 & & \\& & \ddots & \ddots & \\& & & \alpha_{n-1} & \beta_{n-1} \\& & & & &\alpha_n \end{bmatrix}.

将两边第k列对应相等，我们得到

Av_k = \beta_{k-1}u_{k-1} + \alpha_k u_k

或者

\alpha_k u_k = Av_k - \beta_{k-1}u_{k-1}, \quad\quad \beta_0 = 0. \tag{6.5}

另一方面，从关系式

A^{\ast} \begin{bmatrix} u_1 & u_2 & \ldots & u_n\end{bmatrix} = V\begin{bmatrix} \alpha_1 & & & \\& \alpha_2 & \beta_1 & \\& & \ddots & \ddots & \\& & & \beta_{n-1} & \alpha_n \end{bmatrix},

我们得到

A^{\ast} u_k = {\alpha}_k v_k + {\beta}_k v_{k+1}

或者

{\beta}_k v_{k+1} = A^{\ast} u_k - {\alpha}_k v_k.\tag{6.6}

由于U和V的列是归一化的，我们必须有

\alpha_k = \Vert Av_k - \beta_{k-1}u_{k-1}\Vert _2

以及

\beta_k = \Vert A^* u_k - \alpha_k v_k\Vert _2.

我们将递归总结在以下算法中。

算法 6.1: Golub-Kahan-Lanczos 双对角化过程
(1) 选择 v_{1} 为单位 2-范数向量，并设置 \beta_{0}=0
(2) for k=1,2,\ldots，
(3)     u_{k}=A v_{k}-\beta_{k-1} u_{k-1}
(4)     \alpha_{k}=\left\|u_{k}\right\|_{2}
(5)     u_{k}=u_{k}/\alpha_{k}
(6)     v_{k+1}=A^{*} u_{k}-\alpha_{k} v_{k}
(7)     \beta_{k}=\left\|v_{k+1}\right\|_{2}
(8)     v_{k+1}=v_{k+1}/\beta_{k}
(9) end for

收集算法前k步计算的量，我们得到以下重要关系：

A V_k = U_k B_k, \tag{6.7}

A^{\ast} U_{k} = V_k B^*_k + \beta_{k}v_{k+1}e^*_k, \tag{6.8}

以及

U^{\ast}_k U_k = I, \quad V^{\ast}_k V_k = I, \quad \mathrm{and} \quad V^{\ast}_k v_{k+1} = 0, \tag{6.9}

其中B_k是B的 k 阶前主子矩阵，如 (6.4)所定义。