c - 无加速结果的高斯消去法

Question

我正在开发一个 C 库(对于我自己来说，代码: https://github.com/BattlestarSC/matrixLibrary.git )来处理矩阵函数。这主要是一个学习/练习事件。

我的挑战之一是有效地求出矩阵的行列式。由于我目前的尝试失败了，我想采取不同的方法。我正在从麻省理工学院文档中阅读此方法: Determinants 这很有意义。

我遇到的问题是如何达到上述目的。由于高斯消元法适用于多变量方程组，因此我的矩阵不是由方程构建的，因此不是系统的一部分。如图所示，每个方程没有任何设定结果，并且不符合 this paper 的形式。 .

从这一点来看，我不知道如何继续使用此方法。

按照麻省理工学院论文中所述，从每组方程中获取枢轴点很有意义，但是我应该如何设置矩阵才能使所述结果有效？

Answer 1

当您执行高斯消除时，您交换行并重复从另一行中减去一行的倍数以生成上三角形式。

当您在方程组或“增广矩阵”上执行此操作时，您不会使用结果列中的任何信息。无论结果列中的数字是什么，关于交换哪些行以及用什么乘数减去哪些行的决定都将完全相同。

由于未使用“结果列”，因此可以对普通方阵执行相同的过程。由于这些操作不会改变行列式(如果每次交换时对一行取负)，因此最终会得到一个与原始矩阵具有相同 det 的上三角矩阵。

MIT 作者在开头附近的示例中调用函数 lu 来执行此操作。这对矩阵进行 L-U 分解，返回“U”部分中的高斯消除矩阵:https://en.wikipedia.org/wiki/LU_decomposition .

L-U 分解非常酷。这就像进行高斯消元法来一次性求解具有相同“矩阵部分”的所有系统，您也可以这样做，因为该过程根本不需要查看结果列。

从矩阵M开始，得到L和U，使得LU = M。这意味着，如果你想解决:

Mx = y

...其中(x 和 y 是列 vector )，您有:

LUx = y

求解Lv=y，这很容易(只需替换)，因为L是下三角的。那么你就有了:

Ux = v

...这很容易解决，因为 U 是上三角形。