线性代数/主题：高斯消元法的速度

线性代数
← 主题：分析网络	主题：高斯消元法的速度	向量空间 →

我们在这本书中使用高斯消元法来解线性方程组，因为它易于理解，容易证明其正确性，并且速度快。所谓速度快是指，在我们所做的手工计算中，我们只用几步就得到了答案，只用了几分钟。然而，在实践中解决线性方程组的科学家和工程师必须使用一种足够快的算法来处理大型系统，例如 1000 个方程，10,000 个方程，甚至 100,000 个方程。这些系统是在计算机上解决的，因此机器的速度有帮助，但尽管如此，所用算法的速度仍然是一个主要考虑因素，有时是限制哪些问题可以解决的因素。

算法的速度通常通过找到解决问题所需的时间随着输入数据集中大小的增长而增长的方式来衡量。也就是说，如果我们将输入数据的规模扩大十倍，例如从 1000 个方程的系统扩大到 10,000 个方程的系统，或者从 10,000 个扩大到 100,000 个，算法将花费多少时间？所花的时间是增加了十倍，还是一百倍，还是一千倍？算法所花的时间是否与数据集的大小成正比，还是与该大小的平方成正比，还是与该大小的立方成正比等等？

这是一个在 FORTRAN 计算机语言中实现的高斯消元法代码片段。线性方程组的系数存储在 $N\!\times \!N$ 数组 A 中，常数存储在 $N\!\times \!1$ 数组 B 中。对于从 $1$ 到 $N$ 的每个 ROW，该程序已经找到了主元元素 $A(ROW,COL)$ 。现在它将进行主元变换。

-PIVINV\cdot \rho _{ROW}+\rho _{i}

(此代码片段仅用于说明，并不完整。例如，参见后面关于高斯消元法精度的主题。尽管如此，此片段对于我们的目的已经足够了，因为对完成版本（包括所有测试和子案例）的分析更复杂，但本质上得到相同的结果。)

PIVINV=1./A(ROW,COL)
DO 10 I=ROW+1, N
DO 20 J=I, N
A(I,J)=A(I,J)-PIVINV*A(ROW,J)
20 CONTINUE
B(J)=B(J)-PIVINV*B(ROW)
10 CONTINUE

最外层的循环（未显示）遍历 $N-1$ 行。对于这些行中的每一行，显示的循环对 A 中位于主元元素下方和右边的条目（以及 B 中的条目，但为了简化分析，我们将不计算这些操作——参见练习）执行算术运算。我们将假设主元是在通常的位置找到的，即 $COL=ROW$ （如上所述，对一般情况的分析更复杂，但本质上得到相同的结果）。这意味着有 $(N-ROW)^{2}$ 个条目需要进行算术运算。平均而言，ROW 将是 $N/2$ 。因此，我们估计上面的嵌套循环将运行类似 $(N/2)^{2}$ 次，也就是说，将在与方程数量的平方成正比的时间内运行。考虑到未显示的最外层循环，我们估计该算法的运行时间与方程数量的立方成正比。

运行时间与数据集大小成正比的算法速度很快，运行时间与数据集大小的平方成正比的算法速度较慢，但通常相当可用，运行时间与数据集大小的立方成正比的算法速度仍然相当合理。

这些速度估计是了解算法平均运行速度的良好方法。然而，也有一些特殊情况，在这些情况下，上面的高斯消元法代码运行得特别快，因此可能存在一些关于问题的因素，使其特别适合这种类型的解决方案。

在实践中，在计算机代数系统或标准包中找到的代码实现了高斯消元法的变体，称为三角分解。要说明这种方法需要矩阵代数的语言，我们将直到第三章才会看到它。尽管如此，上面的代码在概念上非常接近通常在应用程序中使用的代码。

求解线性方程组所需运行时间已有一些理论上的加速方法。除了高斯消元法以外，还发明了其他算法，其运行时间不是与数据集大小的立方成正比，而是与大约 $2.7$ 次方成正比（这仍然是正在积极研究的领域，因此随着时间的推移，该指数可能会略微下降）。然而，这些理论上的改进尚未得到广泛应用，部分原因是这些新方法需要相当大的数据集才能超过高斯消元法（尽管它们在超大型数据集上会胜过高斯消元法，但存在一些启动开销，使其无法在实践中已经解决的系统上更快地运行）。

练习

问题 1

计算机系统允许生成随机数（当然，这些只是伪随机数，因为它们是由某种算法生成的，但所得到的数字序列通过了许多合理的统计检验，表明其具有明显的随机性）。

用随机数填充一个 $5\!\times \!5$ 数组（例如，在 $[0..1)$ 范围内）。应用高斯消元法以查看它是否为奇异矩阵。重复该实验十次。奇异矩阵是常见还是罕见（在这个意义上）？
计时计算机求解十个 $5\!\times \!5$ 随机数数组的时间。找到平均时间。（请注意，某些系统可以很快地被发现是奇异的，例如，如果第一行等于第二行。根据第一部分，您是否期望奇异系统在您的平均值中扮演重要角色？
对 $15\!\times \!15$ 数组重复上一项。
对 $25\!\times \!25$ 数组重复上一项。
对 $35\!\times \!35$ 数组重复上一项。
绘制输入大小与平均时间的关系图。