高斯消除，无结果可加速 [英] Gaussian elimination without result for acceleration

问题描述

美好的一天，

我正在使用C库(对于我自己，代码: https://github.com /BattlestarSC/matrixLibrary.git )来处理矩阵函数.这主要是一项学习/练习活动.我的挑战之一是有效地采用矩阵的行列式.由于我目前的尝试失败了，所以我想采用另一种方法.我正在从MIT文档中阅读此方法: 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.

从MIT论文中描述的每组方程中获取枢轴点很有意义，但是我应该如何设置矩阵以使所述结果有效?

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.

由于未使用结果列"，因此可以在普通方矩阵上执行相同的过程.由于这些操作不会改变行列式(如果在每次交换时都否定一行)，那么最终将得到一个上三角矩阵，该三角矩阵的单位与原始单位相同.

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屋！