Python 线性方程 - 高斯消元法

Question

目标

给定一组点，我试图找出满足所提供所有点的线性方程的系数。

例如，如果我想求线性方程 (ax + by + c = z):

3x + 2y + 2 = z

我至少需要三个三维点:

(2, 2, 12)
(3, 4, 19)
(4, 5, 24)

给定足够多的坐标点 (x, y, z)，我应该能够使用高斯消元法找到 (a, b, c)。

但是，我认为在特殊情况下我在求解矩阵时遇到了问题。您可以在此处查看我对 Python 实现的第一次尝试:https://gist.github.com/anonymous/8188272

让我们来看几个例子......

数据集 1

使用以下“手工制作”点 (x, y, z):

(2, 2, 12)
(3, 4, 19)
(4, 5, 24)

对以下矩阵执行 LU 分解:

[[  2.   2.   1.  12.]
 [  3.   4.   1.  19.]
 [  4.   5.   1.  24.]]

回解U矩阵:

[[  4.    5.    1.   24. ]
 [  0.   -0.5   0.5   0. ]
 [  0.    0.    0.5   1. ]]

返回结果(a,b,c):

[3.0, 2.0, 2.0]

正确!一切似乎都很好......

数据集 2

使用以下“手工制作”点 (x, y, z):

(3, 4, 19)
(4, 5, 24)
(5, 6, 29)

对以下矩阵执行 LU 分解:

[[  3.   4.   1.  19.]
 [  4.   5.   1.  24.]
 [  5.   6.   1.  29.]]

回解U矩阵:

[[  5.00000000e+00   6.00000000e+00   1.00000000e+00   2.90000000e+01]
 [  0.00000000e+00   4.00000000e-01   4.00000000e-01   1.60000000e+00]
 [  0.00000000e+00   0.00000000e+00   4.44089210e-16   0.00000000e+00]]

返回结果(a,b,c):

[1.0, 4.0, 0.0]

虽然从技术上讲这是一个解决方案，但不是我想要的!

数据集 3

使用以下“手工制作”点 (x, y, z):

(5, 6, 29)
(6, 7, 34)
(7, 8, 39)

对以下矩阵执行 LU 分解:

[[  5.   6.   1.  29.]
 [  6.   7.   1.  34.]
 [  7.   8.   1.  39.]]

回解U矩阵:

[[  7.00000000e+00   8.00000000e+00   1.00000000e+00   3.90000000e+01]
 [  0.00000000e+00   2.85714286e-01   2.85714286e-01   1.14285714e+00]
 [  0.00000000e+00   0.00000000e+00   0.00000000e+00   3.55271368e-15]]

执行崩溃...

想法

在数据集 2 和 3 中，最后一行和倒数第二行是“特殊的”。倒数第二行的“b”和“c”具有相同的值(在我的特殊示例中也是如此!)。不幸的是，我缺乏从中得出正面或反面的数学知识。

当最后一行全为零且其上方的行具有相等的值时，是否有我需要处理的特殊情况？

提前致谢!

Answer 1

是的，这是一种特殊情况，您需要以不同方式处理。在情况 2 和 3 中你有一个 rank deficient matrix .通常它可能意味着有无穷多个解，或者没有解。

您可以通过检查 determinant 来确定这些情况是否会发生您通过堆叠这些 3 向量制作的矩阵。

>>> import numpy as np
>>> from scipy.linalg import det
>>> data1 = np.array([(2, 2, 12), (3, 4, 19), (4, 5, 24)])
>>> data2 = np.array([(3, 4, 19), (4, 5, 24), (5, 6, 29)])
>>> data3 = np.array([(5, 6, 29), (6, 7, 34), (7, 8, 39)])
>>> det(data1)
-1.9999999999999982
>>> det(data2)
5.551115123125788e-17
>>> det(data3)
8.881784197001213e-16

示例 1 是一个满秩矩阵，它在几何上告诉您 3 个点是 linearly independent .

示例 2 和 3 生成行列式为零的矩阵，这告诉您这些点是线性相关的。