关于特征值的子空间迭代

计算科学 线性代数 本征系统 矩阵
2021-12-14 01:13:57

我听说子空间迭代加上 Ritz 加速可以大大提高求解聚类特征值的性能,因为特征值和特征向量可以与比率线性收敛λp+1/λj,j=1,,p. 对于 Hermitian 矩阵,这甚至更快。

这真是太棒了。现在对于任何n×n复矩阵C有了足够的不亏本的特征向量,我们可以构造一个算法,以一种极其有效的方式求解所有特征值:

  1. 向对角线元素添加一个大数字以使特征值的大小变大。
  2. 添加一个零列和一个零行以使其成为n+1×n+1矩阵C.
  3. 调整Cn+1×n+1具有非常小的非零数。
  4. 将子空间迭代算法与n正交n+1维向量。根据算法的证明,它应该很快收敛,对于第一个n特征值分别对最后一个很大。
  5. 将大数减去已解决n特征值来获得原始值。有人认为可能吗?
2个回答

我的直觉说不。假设假设您的原始矩阵的特征值之一Cλk=1.0,而使用您的方法添加人工特征值λn+1=1017. 使用你的方法,你会找到一个特征值1017+1.0对于矩阵C在浮点算术中,它被四舍五入到1017. 然后你会减去1017对于您找到的所有特征值C得到那个λ1=0, 相差甚远。

这是一个极端的情况,但即使对于与λp+1,你的数值精度会很差。在浮点运算中,计算(a+b)b什么时候b远大于a会损失很多位数的准确性,给你一个不稳定的算法。

然而,这只是我的第一个猜测,我没有正式的证据给你。该算法可能存在数值稳定的变体(例如 Gram-Schmidt 与 Householder 正交化),或者我完全错了。

将(解耦的)额外维度添加到向量空间可能无法帮助区分原始中的聚类特征值n方面。您所做的任何子空间迭代都将保持第一个分区n维度和最后一个(额外的)一维子空间。虽然理论告诉您可以在较大(原始)子空间和较小子空间的基础之间快速获得“分离”,但您从完美分离开始,因此没有任何收获。

移动频谱可以(并且经常这样做)有助于分离聚集的特征值,但它必须比仅仅将任意大的实数添加到所有特征值更巧妙地完成。这里的效果是将这些特征值更紧密地聚集在一起。