GUPTRI算法

计算GUPTRI形式的算法基于两种简化（阶梯形式）[121]。第一种是RZ-阶梯形式，揭示了右奇异结构和零特征值的Jordan结构。

RZ-算法使用有限次数的酉等价变换，其中在第k~(= 1, 2, \ldots)步，n_k = A^{(k)}的列零空间维数，n_k - r_k = A^{(k)}和B^{(k)}的交集列零空间维数。这里，A^{(1)} = A和B^{(1)} = B，对于k > 1，\{A^{(k)}, B^{(k)}\}对应于第k-1步等价变换后的降阶矩阵对。结构指标（RZ-指标）显示Kronecker结构如下：

\begin{aligned} n_k - r_k &= \text{ number of } L_{k-1} \text{ blocks}, \\ r_k - n_{k+1} &= \text{ number of } J_{k}(0) \text{ blocks}. \end{aligned}

在我们陈述一般情况之前，我们考虑一个6\times 8的矩阵束在RZ-阶梯形式中：

\begin{aligned} A_{rz} - \lambda B_{rz} &= \begin{bmatrix} -\lambda B_{11} & A_{12} - \lambda B_{12} & A{13} - \lambda B_{13} \\ 0 & - \lambda B_{22} & A_{23} - \lambda B_{23} \\ 0 & 0 & - \lambda B_{33} \\ \end{bmatrix} \\ &= \left[\begin{array}{cccc|cc|cc} 0 & 0 & 0 & 0 & {\bf x} & {\bf x} & x & x \\ 0 & 0 & 0 & 0 & {\bf x} & {\bf x} & x & x \\ 0 & 0 & 0 & 0 & {\bf x} & {\bf x} & x & x \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & {\bf y} & {\bf y} \\ 0 & 0 & 0 & 0 & 0 & 0 & {\bf y} & {\bf y} \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array}\right] - \lambda \left[\begin{array}{cccc|cc|cc} 0 & {\bf x} & {\bf x} & {\bf x} & x & x & x & x \\ 0 & 0 & {\bf x} & {\bf x} & x & x & x & x \\ 0 & 0 & 0 & {\bf x} & x & x & x & x \\ \hline 0 & 0 & 0 & 0 & {\bf y} & {\bf y} & y & y \\ 0 & 0 & 0 & 0 & 0 & {\bf y} & y & y \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & z \\ \end{array}\right]. \end{aligned}

每次降阶后的非零元素用唯一字母标记（第一步用x，第二步用y，以此类推），并以粗体或斜体显示。A_{rz}的超对角块具有满列秩，B_{rz}的对角块具有满行秩。满秩块的非零元素用粗体标记。我们在后续例子中也使用这种表示法。

A_{rz} - \lambda B_{rz}中的对角块（定义“楼梯”）的大小为r_i \times n_i，并显示以下信息：

\begin{aligned} n_1 = 4 &= \text{dim}~{\cal N}(A^{(1)}), \quad r_1 = 3 = n_1 - \text{dim}~{\cal N}(A^{(1)}\cap B^{(1)}), \\ n_2 = 2 &= \text{dim}~{\cal N}(A^{(2)}), \quad r_2 = 2 = n_2 - \text{dim}~{\cal N}(A^{(2)}\cap B^{(2)}), \\ n_3 = 2 &= \text{dim}~{\cal N}(A^{(3)}), \quad r_3 = 1 = n_3 - \text{dim}~{\cal N}(A^{(3)}\cap B^{(3)}), \\ n_4 = 0 &= \text{dim}~{\cal N}(A^{(4)}). \end{aligned}

现在，我们可以得出A_{rz} - \lambda B_{rz}的KCF是{\rm diag}(L_0, L_2, J_1(0), J_3(0))。

一般来说，设A和B是复数m \times n矩阵。那么可以证明存在酉矩阵U \: \in {\mathcal C}^{m \times m}和V \: \in {\mathcal C}^{n \times n}，使得矩阵束A - \lambda B被变换为所谓的RZ-阶梯形式[121,122]：

U^*(A - B)V = \begin{bmatrix} A_{rz} & A_{12} \\ 0 & A_{rest} \end{bmatrix} - \begin{bmatrix} B_{rz} & B_{12} \\ 0 & B_{rest} \end{bmatrix}, \tag{8.37}

其中A_{rz}和B_{rz}的阶梯块结构揭示了右奇异结构和零特征值的Jordan结构：

\begin{aligned} A_{rz} &= \begin{bmatrix} 0 & A_{12} & * & * & * & *\\ 0 & 0 & A_{23} & * & * & * \\ 0 & 0 & 0 & \ddots & * & * \\ \vdots & \vdots & \vdots & \ddots & A_{j-2,j-1} & * \\ 0 & 0 & 0 & \ldots & 0 & A_{j-1,j} \end{bmatrix}, \\ B_{rz} &= \begin{bmatrix} B_{11} & B_{12} & * & * & * & *\\ 0 & B_{22} & B_{23} & * & * & * \\ 0 & 0 & B_{33} & \ddots & * & * \\ \vdots & \vdots & \vdots & \ddots & B_{j-2,j-1} & * \\ 0 & 0 & 0 & \ldots & B_{j-1,j-1} & B_{j-1,j} \end{bmatrix}. \end{aligned}

(8.37)和(8.38)中的子块具有以下性质：

• B_{ii}是r_i \times n_i，A_{i-1,i}, B_{i-1,i}是r_{i-1} \times n_i，其中n_i \geq r_i \geq n_{i+1} \geq r_{i+1}。
• B_{ii} = [ 0, R_{ii}]，其中R_{ii}是r_i \times r_i且上三角。
• B_{ii}具有满行秩r_i，对于i = 1, \ldots, j-1。
• A_{i-1,i}具有满列秩n_i，对于i = 2, \ldots, j。
• A_{rest}和B_{rest}是r_{rest} \geq 0乘n_{rest} \geq 0，其中A_{rest}如果有则具有满列秩。

RZ-阶梯形式中可能出现三种情况，取决于r_{rest}和n_{rest}：

1. r_{rest} > 0且n_{rest} > 0，此时A_{rest}具有满列秩。
2. r_{rest} > 0且n_{rest} = 0。
3. r_{rest} = n_{rest} = 0。
   

在情况1和2中，块如(8.37)所示，剩余的Kronecker结构在A_{rest} - \lambda B_{rest}中。在情况3中，A_{rest} - \lambda B_{rest}不存在于(8.37)中。在所有三种情况下，A_{rz} - \lambda B_{rz}的第j个块列(8.38)可能不出现；如果出现，A_{j-1,j}也具有满列秩。为方便起见，设r_j = 0。

我们看到上面的6\times 8例子对应于情况3，并且A_{rz} - \lambda B_{rz}没有第j个块列。

第二种简化是LI（左无穷）-阶梯形式，揭示了左奇异结构和无穷特征值的Jordan结构。这种对偶阶梯形式是通过从B - \mu A的东南角开始工作，并在RZ-算法中用行压缩替换列压缩来获得的。块指标n_i和r_i是相应行零空间的维数，并定义LI-指标。此外，n_k - r_k和r_k - n_{k+1}分别是L_{k-1}^T和N_{k}块的数量。

RZ-阶梯和LI-阶梯简化为我们提供了两种类型的结构元素，必须分离以获得GUPTRI形式。例如，零特征值的右奇异结构和Jordan结构通过首先对B_{rz} - \mu A_{rz}应用RZ-阶梯简化并坚持相同的右最小指标来分离。然后我们得到\{A_r, B_r\}，并剩下一个对应于零特征值的矩阵束，比如A_2 - \lambda B_2。最后，\{A_z, B_z\}通过对A_2 - \lambda B_2进行RZ-阶梯形式变换获得。

我们回到6\times 8的例子，展示分离的R-阶梯和Z-阶梯形式：

A_{r} - \lambda B_{r} = \left[\begin{array}{cc|c|c} 0 & 0 & {\bf x} & x \\ \hline 0 & 0 & 0 &{\bf y} \end{array} \right] - \lambda \left[\begin{array}{cc|c|c} 0 & {\bf x} & x & x \\ \hline 0 & 0 & {\bf y} & {\bf z} \end{array} \right] .

和

A_{z} - \lambda B_{z} = \left[\begin{array}{cc|c|c} 0 & 0 & {\bf x} & x \\ 0 & 0 & {\bf x} & x \\ \hline 0 & 0 & 0 & {\bf y} \\ \hline 0 & 0 & 0 & 0 \end{array} \right] - \lambda \left[\begin{array}{cc|c|c} {\bf x} & {\bf x} & x & x \\ 0 & {\bf x} & x & x \\ \hline 0 & 0 & {\bf y} & y \\ \hline 0 & 0 & 0 & {\bf z} \end{array} \right] .

至于A_{rz} - \lambda B_{rz}，A_r和A_z的超对角块具有满列秩，B_r和B_z的对角块具有满行秩。下表总结了6\times 8例子的RZ-、R-和Z-阶梯形式的结构指标。我们看到RZ-阶梯指标分别是R-和Z-阶梯指标的和。

i	1	2	3	4
n_i	4	2	2	0
r_i	3	2	1	0

i	1	2	3	4
n_i	2	1	1	0
r_i	1	1	0	0

i	1	2	3	4
n_i	2	1	1	0
r_i	2	1	1	0

总之，计算(8.34)和(8.35)的GUPTRI算法包括七个简化步骤。前三个步骤对A - \lambda B的不同块应用RZ-阶梯简化，给出右奇异结构(A_r - \lambda B_r)和零Jordan结构(A_z - \lambda B_z)在A和B的左上角。类似地，接下来的三个步骤对剩余的矩阵束应用LI-阶梯简化，给出无穷Jordan结构(A_i - \lambda B_i)和左奇异结构(A_l - \lambda B_l)在A和B的右下角。然后在变换后的矩阵束中间留下一个方形的正则矩阵束，对应于A - \lambda B的有限和非零特征值。通过对这个矩阵束应用QZ算法，得到上三角块A_f - \lambda B_f。