交换一列时更新 QR 分解

计算科学 线性代数 线性求解器 线性规划
2021-11-30 16:56:10

我有一系列输入矩阵

A1,A2,A3,

之间的区别在于替换单个列。在我了解之前,我必须为一些固定向量,所以我还有一系列向量AiAi+1Ai+1Ai1bb

A11b,A21b,A31b,

计算。为了您的兴趣,这出现在单纯形法的实现中,但我更喜欢从数值线性代数的角度来处理。问题:

  1. 更换一列后,我在哪里可以找到更新 QR 分解的参考资料?
  2. 由于我只对 QR 分解感兴趣以解决一系列线性问题,这也可以在算法中加以利用吗?

我使用 QR 分解只是因为这是一种标准方法 - 如果您对上述设置有更好的建议,请随时提供您的建议。

1个回答

有大量关于单纯形法实施的数值方面的文献,包括更新基的因式分解的方法以及以乘积形式保持基的逆的技术。替换基矩阵的一列是“秩一更新”,因为它可以写成将矩阵添加到只有一个非零列并因此秩为一的基。

QR 分解通常不用于单纯形法的实现,因为与其他方法相比它非常慢。在实践中,基的初始 LU 因式分解通常与每次迭代的因式分解的一级更新相结合。因为太多的一级更新会导致数值问题,所以基础通常每隔一段时间就重构一次(例如,每 50 次迭代一次。)

有有效的算法可以对 QR 分解进行一级更新。一个经典的参考是:

JW Daniel、WB Gragg、L. Kaufman 和 G. Stewart,用于更新 Gram-Schmidt QR 分解的重新正交化和稳定算法。计算数学 30: