algorithm - Gauss-Jordan 消除与 LU 分解

Question

在“黑皮书”Numerical Recipes 第 3 版中，给出了求解线性方程组的 Gauss-Jordan 算法。紧随其后的部分是计算 LU 分解，然后使用它来求解线性方程组(请参阅第 53 页的 LUdcmp::solve)。不幸的是，这本书没有解释为什么人们更喜欢一种方法而不是另一种方法。这两种方法是否等效，或者是否有理由在特定情况下更喜欢一种方法？

Answer 1

使用 LU 分解的优点是可以重复使用它来计算多个解决方案。

例如，如果你想解方程

Ax = b

对于一个常量A和许多不同的b那么你只需要计算一次A的LU分解就可以重复使用对于每个 b。但是，如果使用 Gauss-Jordan 消元法，您将不得不为每个 b

重新做所有的工作

之所以更快，是因为 Gauss-Jordan 消去法的尺度为 O(n^3)，而 LU 分解方法的替换步骤仅尺度为 O(n^2)。因此，对于 LU 情况，您只需为每个 b 执行一次昂贵的 O(n^3) 步骤。

可以找到关于这一点的一组合理注释 here