高斯消元法 - 线性方程矩阵，算法

Question

高斯消元法 - 线性方程矩阵，算法

4

假设我们有一个简单的矩阵，3行7列。该矩阵仅包含0和1，如下所示：

1 0 1 1 1 0 0
0 0 1 1 0 0 0
0 0 1 0 1 1 0

场景：如果我们知道每行非零元素的总和，（第一行为4，在第二行为2，在第三行为3。）（蓝线）

此外，如果我们知道每一列的总和（1、0、3、2、2、1、0）（绿线）

还有，如果我们知道从左上到右下的每条对角线的总和（1、0、1、2、3、0、1、1、0）（红线），逆时针方向

最后，我们还知道从左下到右上的每条对角线的总和（0、0、2、1、3、2、1、0、0）（黄线）

我的问题是：在这些值作为输入的情况下（以及矩阵的长度为3x7），

4, 2, 3
1, 0, 3, 2, 2, 1, 0
1, 0, 1, 2, 3, 0, 1, 1, 0
0, 0, 2, 1, 3, 2, 1, 0, 0

我们如何绘制第一个矩阵？

经过很多思考，我得出结论，这是一个具有3x7未知值和一些方程的线性方程系统。

对吗？

我应该如何在C或其他语言中编写算法来解决这些方程？

我应该使用高斯消元之类的方法吗？

非常感谢任何帮助！

- Lamp

在这种特殊情况下，您可以将其视为线性方程组来解决，因为有21个未知数和超过21个方程式。但一般情况下，您不能这样做，因为会有mn个未知数，而只有m+n+2(m+n-1)个方程式。 - ElKamina

如果我们有一个10x15的数组，我们该如何解决它？ - Lamp

将其视为线性系统可以消除值只能为1或0的约束，这意味着n>3时没有唯一解。对于给定的和集合，是否存在唯一解取决于是否可以通过两个矩阵获得相同的和集合，其中一个矩阵有一个1和n*m-1个0，并且1位于不同的位置，我认为这是不可能的，但需要再思考一下。 - Pete Kirkham

4个回答

2

从第一列开始。你知道红色和黄色列表的第一个值，即上下值。从绿色列表的第一个值中减去这两个值的总和，现在你也有了中间值。

现在只需向右工作。

从红色列表中的下一个值中减去第一列的中间值，你就有了第二列的顶部值。从黄色列表中的下一个值中减去相同的中间值，你就有了第二列的底部值。从这两个值的总和中减去绿色列表中的下一个值，现在你也有了第二列的中间值。

以此类推。

如果你要编写代码，可以看到前两列是特例，这会使代码很丑陋。我建议在左侧使用两个全零的“幽灵”列，这样你就可以使用单个方法来确定每列的顶部、底部和中间值。

这也很容易推广。你只需要使用(#行)-1个幽灵列。

享受吧。

- unpythonic

你说的“ghost”列是什么意思？如果我们有一个更大的数组，比如（10x15）..我们该怎么解决它？ - Lamp

1

这种方法对于在两个维度上都大于3的数组不起作用（3是“幸运”的边角情况）。该解决方案基于这样的假设，即我们可以通过从角落中减去值来分解整个列。 - OleGG

我的实际数组长度更大。我需要一种通用的方法来进行矩阵操作...也许... - Lamp

1

对于一个由10x15个1和0组成的数组，您将尝试查找150个未知数，并且如果忽略值仅限于1或0，则会有10+15+2*(10+15-1)=73个方程式。显然，您无法基于此创建具有唯一解的线性系统。

那么这个约束条件足以给出唯一的解吗？

对于一个带有以下总和的4x4矩阵，存在两个解：

- 1 1 1 1
| 1 1 1 1
\ 0 1 1 0 1 1 0
/ 0 1 1 0 1 1 0

0   0   1   0 
1   0   0   0 
0   0   0   1 
0   1   0   0 

0   1   0   0 
0   0   0   1 
1   0   0   0 
0   0   1   0

所以我不会期望对于更大的矩阵有唯一的解 - 相同的对称性会存在于许多地方：

- 1 1 0 0 1 1
| 1 1 0 0 1 1
\ 0 1 0 0 1 0 1 0 0 1 0
/ 0 1 0 0 1 0 1 0 0 1 0

0   0   0   0   1   0 
1   0   0   0   0   0 
0   0   0   0   0   0 
0   0   0   0   0   0 
0   0   0   0   0   1 
0   1   0   0   0   0 

0   1   0   0   0   0 
0   0   0   0   0   1 
0   0   0   0   0   0 
0   0   0   0   0   0 
1   0   0   0   0   0 
0   0   0   0   1   0

- Pete Kirkham

0

这个作为另一种变化怎么样？

Count the amount of unknown squares each sum passes through   
While there are unsolved cells
   Solve all the cells which are passed through by a sum with only one unknown square
       Cells are solved by simply subtracting off all the known cells from the sum
   Update the amount of unknown squares each sum passes through

没有边界情况，但与先前的答案非常相似。这将首先解决所有角落，然后是邻近角落的位置，然后是比那更内部一步的位置，依此类推...

编辑：还要将总和为零的任何路径清零，这应该可以解决任何可解的问题（我想）

- RussS

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Esch · Accepted Answer

您可以使用奇异值分解来计算矩阵形式下的线性齐次（和非齐次）方程组的非零最小二乘解。

快速概述请参见：

http://campar.in.tum.de/twiki/pub/Chair/TeachingWs05ComputerVision/3DCV_svd_000.pdf

您应该首先将系统写成矩阵方程Ax = b的形式，其中x是未知数21个作为列向量，A是28 x 21矩阵，当乘以它时形成线性系统。您需要计算这些线性方程的矩阵A，计算A的奇异值分解，并将结果插入到等式9.17中，如所示。

有很多C库可以为您计算SVD，因此您只需要制定矩阵并执行9.17中的计算即可。最困难的部分可能是理解它们如何工作，使用库SVD函数所需的代码相对较少。

为了让您开始形成线性系统方程的过程，考虑一个简单的3 x 3案例。

假设我们的系统是以下形式的矩阵

1 0 1
0 1 0
1 0 1

我们将在线性系统中输入以下内容：

2 1 2             (sum of rows                 - row)
2 1 2             (sum of colums               - col)
1 0 3 0 1         (sum of first diagonal sets  - t2b)
1 0 3 0 1         (sum of second diagonal sets - b2t)

所以现在我们为线性系统创建一个矩阵。

 A            a1 a2 a3 b1 b2 b3 c1 c2 c3     unknowns (x)    =   result (b)
sum of row 1 [ 1  1  1  0  0  0  0  0  0 ]      [a1]                [2]       
sum of row 2 [ 0  0  0  1  1  1  0  0  0 ]      [a2]                [1]
sum of row 3 [ 0  0  0  0  0  0  1  1  1 ]      [a3]                [2]
sum of col 1 [ 1  0  0  1  0  0  1  0  0 ]      [b1]                [2]
sum of col 2 [ 0  1  0  0  1  0  0  1  0 ]      [b2]                [1]
sum of col 3 [ 0  0  1  0  0  1  0  0  1 ]      [b3]                [2]
sum of t2b 1 [ 1  0  0  0  0  0  0  0  0 ]      [c1]                [1]
sum of t2b 2 [ 0  1  0  1  0  0  0  0  0 ]      [c2]                [0]
sum or t2b 3 [ 0  0  1  0  1  0  1  0  0 ]      [c3]                [3]
sum of t2b 4 [ 0  0  0  0  0  1  0  1  0 ]                          [0]
sum of t2b 5 [ 0  0  0  0  0  0  0  0  1 ]                          [1]
sum of b2t 1 [ 0  0  0  0  0  0  1  0  0 ]                          [1]
sum of b2t 2 [ 0  0  0  1  0  0  0  1  0 ]                          [0]
sum of b2t 3 [ 1  0  0  0  1  0  0  0  1 ]                          [3]
sum of b2t 4 [ 0  1  0  0  0  1  0  0  0 ]                          [0]
sum of b2t 5 [ 0  0  1  0  0  0  0  0  0 ]                          [1]

当你扩展Ax时，你会发现你得到了线性方程组。例如，如果你把未知列乘以第一行，你得到的是：

a1 + a2 + a3 = 2

你只需要在方程中的任意一列中放置1，其他地方放置0。

现在，你只需要计算A的SVD并将结果插入到公式9.17中计算未知数。

我建议使用SVD，因为它可以高效地计算。如果你愿意，你可以将矩阵A与结果向量b（A | b）合并，并将A放置在简化行梯阵形式中以获得结果。