Golub-Kahan-Lanczos Bidiagonalization Procedure 实现不产生双对角矩阵

计算科学 Python 数字 svd
2021-12-19 05:24:23

我正在尝试使用此网站作为参考来实施上述程序。在页面末尾,算法描述如下: 在此处输入图像描述

我想我已经将给定的算法映射到正确的代码。但是,当我使用过程中获得的 U 和 V 来计算UTAV我没有得到双对角矩阵。沿对角线的值确实是在过程中计算的值,但其余值不是零。这是我的代码:

def golub_kahan(a):
  n = a.shape[1]
  v = np.ones(n, dtype="float32") / np.sqrt(n)
  u = np.zeros(a.shape[0], dtype="float32")
  beta = 0
  U, V = np.zeros_like(a, dtype="float32"), np.zeros((n,n), dtype="float32")

  for i in range(n):
    V[:, i] = v
    u = a @ v - beta * u
    alpha = np.linalg.norm(u)
    u /= alpha
    U[:, i] = u
    v = a.T @ u - alpha * v
    beta = np.linalg.norm(v)
    v /= beta

  return U, V

我不确定我的错误在哪里,我是否以某种方式误解了算法?

1个回答

该算法存在与对称 Lanczos 三对角化算法类似的数值稳定性问题,请参见此处

在精确算术中,之后k步骤如下:UkTUk=I,VkTVk=I, 和UkTAVk=Bk, 在哪里Bk是具有对角元素的双对角矩阵αi和超对角元素βi. 然而,在浮点运算中,即使是适度的k, 矩阵 UkVk可能会远离正交。而且,UkAVk可能不仅在双对角线上有相对较大的条目,而且在远离对角线的位置也可能有相对较大的条目。然而,最大的奇异值Bk通常是最大奇异值的一个很好的近似值A,即使对于相对较小的k.

一个更稳定的双对角化算法是 Householder 双对角化算法,它在Golub 和 Van Loan 的矩阵计算第 4 版5.4.8 段中进行了描述。此方法使用 Householder 反射对矩阵进行双对角化A,相对昂贵但也非常稳定。

可以通过重新正交化改进 Lanczos 双对角化算法并保持正交性 另 见:关于双对角化及其实现的一些评论请注意,Lanczos 双对角化只需要与AAT,而 Householder 双对角化算法需要显式访问A, 这是一个缺点