我有一系列输入矩阵
和之间的区别在于替换单个列。在我了解之前,我必须为一些固定向量,所以我还有一系列向量
计算。为了您的兴趣,这出现在单纯形法的实现中,但我更喜欢从数值线性代数的角度来处理。问题:
- 更换一列后,我在哪里可以找到更新 QR 分解的参考资料?
- 由于我只对 QR 分解感兴趣以解决一系列线性问题,这也可以在算法中加以利用吗?
我使用 QR 分解只是因为这是一种标准方法 - 如果您对上述设置有更好的建议,请随时提供您的建议。
我有一系列输入矩阵
和之间的区别在于替换单个列。在我了解之前,我必须为一些固定向量,所以我还有一系列向量
计算。为了您的兴趣,这出现在单纯形法的实现中,但我更喜欢从数值线性代数的角度来处理。问题:
我使用 QR 分解只是因为这是一种标准方法 - 如果您对上述设置有更好的建议,请随时提供您的建议。
有大量关于单纯形法实施的数值方面的文献,包括更新基的因式分解的方法以及以乘积形式保持基的逆的技术。替换基矩阵的一列是“秩一更新”,因为它可以写成将矩阵添加到只有一个非零列并因此秩为一的基。
QR 分解通常不用于单纯形法的实现,因为与其他方法相比它非常慢。在实践中,基的初始 LU 因式分解通常与每次迭代的因式分解的一级更新相结合。因为太多的一级更新会导致数值问题,所以基础通常每隔一段时间就重构一次(例如,每 50 次迭代一次。)
有有效的算法可以对 QR 分解进行一级更新。一个经典的参考是:
JW Daniel、WB Gragg、L. Kaufman 和 G. Stewart,用于更新 Gram-Schmidt QR 分解的重新正交化和稳定算法。计算数学 30: