没有加速结果的高斯消元 [英] Gaussian elimination without result for acceleration

问题描述

美好的一天，

我正在开发一个 C 库(对于我自己，代码:https://github.com/BattlestarSC/matrixLibrary.git) 来处理矩阵函数.这主要是一种学习/实践活动.我的挑战之一是有效地获取矩阵的行列式.由于我目前的尝试失败了，我想采取不同的方法.我正在阅读麻省理工学院文档中的这种方法:http://web.mit.edu/18.06/www/Spring17/Determinants.pdf 很有意义.我遇到的问题是如何达到上述目的.由于高斯消元法适用于多变量方程组，我的矩阵不是由方程构建的，因此不是系统的一部分.如在，每个方程都没有固定的结果，也不适合本文中的形式:https://math.oregonstate.edu/home/programs/undergrad/CalculusQuestStudyGuides/vcalc/gauss/gauss.html

I'm working on a C library (for myself, code: https://github.com/BattlestarSC/matrixLibrary.git) to handle matrix functions. This is mostly a learning/practice activity. One of my challenges is to take the determinant of a matrix efficiently. As my current attempts have failed, I wanted to take a different approach. I was reading though this method from MIT docs: http://web.mit.edu/18.06/www/Spring17/Determinants.pdf and it made a lot of sense. The issue I'm having is how to get to said point. As the Gaussian elimination method is good for multi-variable systems of equations, my matricies are not built from equations, and therefor are not part of a system. As in, each equation has no set result and does not fit into the form from this paper here:https://math.oregonstate.edu/home/programs/undergrad/CalculusQuestStudyGuides/vcalc/gauss/gauss.html

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

From this point, I'm at a loss as far as how to proceed with this method.

从麻省理工学院论文中描述的每组方程中获取轴心点很有意义，但我应该如何设置我的矩阵以使所述结果有效?

It makes a lot of sense to take the pivot point from each set of equations as described in the MIT paper, but how should I set up my matricies to make said result valid?

推荐答案

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

When you perform a Gaussian elimination, you swap rows and repeatedly subtract a multiple of one row from another to produce an upper triangular form.

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

When you do this on a system of equations or an "augmented matrix", you do not use any information from the result column. The decisions about which rows to swap and which to subtract with what multiplier would be exactly the same no matter what numbers are in the result column.

因为没有使用结果列"，您可以对普通方阵执行相同的过程.由于这些操作不会改变行列式(如果每次交换时都否定一行)，您最终会得到一个与原始矩阵具有相同 det 的上三角矩阵.

Because the "result column" is not used, you can perform the same procedure on a normal square matrix. Since the operations don't change the determinant (if you negate one row whenever you swap), you end up with an upper triangular matrix with the same det as the original.

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

The MIT author calls a function lu to do this in the example near the start. This does L-U decomposition on the matrix, which returns the Gaussian-eliminated matrix in the 'U' part: https://en.wikipedia.org/wiki/LU_decomposition.

L-U 分解很酷.这就像用高斯消元一次解决所有具有相同矩阵部分"的系统一样，你也可以这样做，因为这个过程根本不需要看到结果列.

L-U decomposition is pretty cool. It's like doing Gaussian elimination to solve all systems with the same "matrix part" all at once, which again you can do because the process doesn't need to see the result column at all.

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

Starting with a matrix M, you get L and U such that LU = M. That means, if you want to solve:

Mx = y

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

... where (x an y are column vectors), you have:

LUx = y

解决Lv=y，这很容易(只是替换)，因为L 是下三角.那么你有:

Solve Lv=y, which is easy (just substitution) because L is lower-triangular. Then you have:

Ux = v

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

... which is easy to solve because U is upper-triangular.

这篇关于没有加速结果的高斯消元的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！