就上下文而言，我正在从头开始创建一个线性代数库，用于 C 语言的学习。现在我正在计算特征值，但我对 QR 算法的实现是不同的。以下是我对 QR 算法的理解，在第一块代码之后（我相信是）问题的核心：Givens 旋转。

请注意，给出的代码是类似 python 的伪代码，而不是 C（尽管给出的代码看起来与源代码没有太大不同）。

我无法理解这里出了什么问题以及为什么。详情如下：

我的实现一开始就出现了分歧，并且在 3 次迭代之后绝对是显而易见的。我目前对算法的理解（使用 Hessenberg）是这样的：

给定$n \times n$海森堡矩阵$\mathbf H$，我想用 QR 算法计算它的特征值。为此，我必须申请$n - 1$从左侧转置 Givens 旋转（即$\mathbf G^T_{n-1}\mathbf G^T_{n-2}...\mathbf G^T_1\mathbf H$）。给定的旋转等价于$\mathbf Q^T$. 因此，我们可以以相反的顺序相乘来完成 QR 算法（即$\mathbf {\overline H} = \mathbf H\mathbf G_1\mathbf G_2...\mathbf G_{n-1}$）。这最终会聚成一个上三角形，在其对角线上可以找到相应的特征值。

在代码中：

for i = 0 until convergence:
    for k = 0 to n-1:       // rotation to make H upper triangular
        givensLeft(H, k)
    for k = 0 to n-1:       // back to Hessenberg
        givensRight(H, k)

吉文斯轮换是我主要担心的，因为我不完全确定它们是否正常工作。我知道只有行/列$k$和$k+1$被影响到的。因此，我可以通过乘以子矩阵从左侧执行 Givens 旋转$\mathbf H_{k:k+1, \ k:n}$由转置的 Givens 矩阵$\mathbf G^T$：

$$\begin{bmatrix} c_k &-s_k \\ s_k & c_k \end{bmatrix}$$

要从右侧执行 Givens 旋转（在 QR 算法中，这会将 Hessenberg 从由左 Givens 旋转引起的上三角形重新返回其形式），我将乘以子矩阵$\mathbf H_{1:k+1, \ k:k+1}$由（未转置的）Givens 矩阵$\mathbf G$：

$$\begin{bmatrix} c_k & s_k \\ -s_k & c_k \end{bmatrix}$$

在代码中：

givensLeft(H, k):
    a = H[k][k]
    b = H[k+1][k]
    r = hypot(a, b)
    c = a/r
    s = -1*b/r

    // these could be more efficient, I know
    for i = k+1 to H.columns:
        a = H[k][i]
        b = H[k+1][i]
        H[k][i] = c*a - s*b

    for i = k+1 to H.columns:
        a = H[k][i]
        b = H[k+1][i]
        H[k][i] = s*a + c*b

givensRight(H, k):
    a = H[0][k]
    b = H[0][k+1]
    r = hypot(a, b)
    c = a/r
    s = -1*b/r

    for i = 0 to k+1:
        a = H[i][k]
        b = H[i][k+1]
        H[i][k] = c*a - s*b

    for i = 0 to k+1:
        a = H[i][k]
        b = H[i][k+1]
        H[i][k+1] = s*a + c*b

我能想到的唯一问题是 Givens 旋转问题，因为它们似乎构成了整个 QR 算法，但我不知道会出现什么问题。我在网上看了几件事，概述了带有 Hessenberg 的 QR 算法（例如this和this），这个实现是直接从前者编写的（使用算法 4.1 和 4.2）。我在这里或其他地方找不到任何有类似问题的人。

我的问题是概念性的吗？还是只是错误的编程？提前谢谢了。