准确性

Trefethen 和 Schreiber 写了一篇出色的论文，即高斯消除的平均情况稳定性，其中讨论了您问题的准确性方面。以下是它的一些结论：

1. “对于有或没有列旋转的 QR 分解，残差矩阵的平均最大元素是$O(n^{1/2})$，而对于高斯消元法，它是$O(n)$. 这种比较表明，高斯消元法有些不稳定，但这种不稳定性只能在以低精度解决的非常大的矩阵问题中检测到。对于大多数实际问题，平均而言，高斯消元法是高度稳定的。"（强调我的）

2. “在高斯消元的前几步之后，剩余的矩阵元素大致呈正态分布，无论它们是否以这种方式开始。”

这篇论文还有很多我在这里无法捕捉到的内容，包括你提到的最坏情况矩阵的讨论，所以我强烈建议你阅读它。

表现

对于方形实矩阵，具有部分旋转的 LU 大约需要$2/3 n^3$flops，而基于 Householder 的 QR 大约需要$4/3 n^3$翻牌。因此，对于相当大的方阵，QR 因式分解的成本仅为 LU 因式分解的两倍左右。

为了$m \times n$矩阵，其中$m \ge n$, 具有部分旋转的 LU 需要$mn^2 - n^3/3$翻牌，与 QR 的$2mn^2 - 2n^3/3$（这仍然是 LU 分解的两倍）。然而，产生非常高的瘦矩阵的应用程序非常普遍（$m \gg n$) 和 Demmel 等人。有一篇不错的论文，Communication-avoiding parallel and sequence QR factorization，它（在第 4 节中）讨论了一个聪明的算法，它只需要$\log p$什么时候发送的消息$p$处理器被使用，与$n \log p$传统方法的消息。费用是这样的$O(n^3 \log p)$额外的翻牌被执行，但对于非常小的$n$这通常优于发送更多消息的延迟成本（至少在只需要执行单个 QR 分解时）。

我很惊讶没有人提到线性最小二乘问题，这在科学计算中经常出现。如果要使用高斯消元法，则必须形成并求解正规方程，如下所示：

在哪里$A$是对应于自变量观察的数据点矩阵，$x$是要找到的参数向量，并且$b$是对应于因变量观察的数据点向量。

正如 Jack Poulson 经常指出的，条件数$A^{T}A$是条件数的平方$A$，所以正规方程可能是灾难性的病态。在这种情况下，尽管基于 QR 和 SVD 的方法速度较慢，但​​它们会产生更准确的结果。

你如何衡量绩效？速度？准确性？稳定？Matlab 中的快速测试给出以下结果：

>> N = 100;
>> A = randn(N); b = randn(N,1);
>> tic, for k=1:10000, [L,U,p] = lu(A,'vector'); x = U\(L\b(p)); end; norm(A*x-b), toc
ans =
   1.4303e-13
Elapsed time is 2.232487 seconds.
>> tic, for k=1:10000, [Q,R] = qr(A); x = R\(Q'*b); end; norm(A*x-b), toc             
ans =
   5.0311e-14
Elapsed time is 7.563242 seconds.

因此，使用 LU 分解求解单个系统的速度大约是使用 QR 分解求解的速度的三倍，但代价是精度为小数位数（本例！）。

您引用的文章为高斯消除法辩护说，尽管它在数值上不稳定，但它往往在随机矩阵上表现良好，并且由于大多数矩阵可以想到的就像随机矩阵，我们应该没问题。同样的说法也适用于许多数值不稳定的方法。

考虑所有矩阵的空间。这些方法几乎在任何地方都能正常工作。那就是 99.999...% 的人可以创建的所有矩阵在不稳定的方法上都不会出现问题。GE 和其他公司将难以处理的矩阵只有很小一部分。

研究人员关心的问题往往只是那一小部分。

我们不会随机构建矩阵。我们构造具有非常特殊属性的矩阵，这些矩阵对应于非常特殊的非随机系统。这些矩阵通常是病态的。

在几何上，您可以考虑所有矩阵的线性空间。有一个零体积/测量奇异矩阵的子空间穿过这个空间。我们构建的许多问题都聚集在这个子空间周围。它们不是随机分布的。

例如，考虑热方程或分散。这些系统倾向于从系统中删除信息（所有初始状态都趋向于单个最终状态），因此描述这些方程的矩阵非常奇异。这个过程在随机情况下是非常不可能的，但在物理系统中无处不在。