问题
我有一组方程,其中的变量用小写变量表示,常量用大写变量表示
A = a + b
B = c + d
C = a + b + c + d + e
我在 pandas DataFrame 中获得了有关这些方程结构的信息,其中包含两列:常量和变量
例如
df = pd.DataFrame([['A','a'],['A','b'],['B','c'],['B','d'],['C','a'],['C','b'],
['C','c'],['C','d'],['C','e']],columns=['Constants','Variables'])
然后我使用 NetworkX 将其转换为稀疏 CSC 矩阵
table = nx.bipartite.biadjacency_matrix(nx.from_pandas_dataframe(df,'Constants','Variables')
,df.Constants.unique(),df.Variables.unique(),format='csc')
转换为稠密矩阵时,表格如下所示
矩阵([[1, 1, 0, 0, 0],[0, 0, 1, 1, 0],[1, 1, 1, 1, 1]], dtype=int64)
我想要的是找到哪些变量是可解的(在这个例子中,只有e是可解的),对于每个可解的变量,它的值取决于什么常量(在这种情况下,由于e = C-B-A,它依赖于A, B 和 C)
尝试解决方案
我首先尝试使用 rref 来求解可解变量。我使用了符号库 sympy 和函数 sympy.Matrix.rref,这正是我想要的,因为任何可解变量都会有自己的行,其中几乎全是零和 1 个一,我可以逐行检查。
但是,这个解决方案并不稳定。首先,它非常慢,并且没有利用我的数据集可能非常稀疏的事实。此外, rref 对于浮点的处理不太好。因此,我决定转向由 Removing unsolvable equations from an underdetermined system 插入的另一种方法。 ,建议使用 svd
方便的是,scipy.sparse库中有一个svd函数,即scipy.sparse.linalg.svds。然而,由于我缺乏线性代数背景,我不明白在我的 table 上运行这个函数所输出的结果,或者如何使用这些结果来获得我想要的结果。
问题的更多详细信息
- 我的问题中每个变量的系数都是 1。这就是前面显示的两列 pandas DataFrame 中数据的表达方式
- 我的实际例子中的绝大多数变量都是不可解的。目标是找到少数可解决的问题
- 如果替代方法符合此问题的限制,我非常愿意尝试它。
这是我第一次发布问题,因此,如果这不完全遵循准则,我深表歉意。请留下建设性的批评,但要温和!
最佳答案
您正在求解的系统具有以下形式
[ 1 1 0 0 0 ] [a] [A]
[ 0 0 1 1 0 ] [b] = [B]
[ 1 1 1 1 1 ] [c] [C]
[d]
[e]
即五个变量的三个方程 a, b, c, d, e
。正如您的问题中提到的答案所提到的,人们可以使用 pseudoinverse 来解决这种不确定的系统。 ,Numpy 直接根据 pinv 提供功能。
自 M
具有线性独立的行,在这种情况下,伪逆具有 M.pinv(M) = I
的属性,其中I
表示单位矩阵(在本例中为 3x3)。因此,正式地,我们可以将解决方案写为:
v = pinv(M) . b
哪里v
是 5 分量解向量,并且 b
表示右侧 3 分量向量 [A, B, C]
。然而,这个解决方案并不是唯一的,因为可以添加来自所谓的内核或 null space 的向量。矩阵 M
(即,一个向量 w
,其中 M.w=0
),它仍然是一个解决方案:
M.(v + w) = M.v + M.w = b + 0 = b
因此,唯一有唯一解的变量是那些来自 M
零空间的所有可能向量的相应分量的变量。为零。换句话说,如果将零空间的基组装成一个矩阵(每列一个基向量),那么“可解变量”将对应于该矩阵的零行(列的任何线性组合的相应分量将那么也为零)。
让我们将其应用到您的特定示例中:
import numpy as np
from numpy.linalg import pinv
M = [
[1, 1, 0, 0, 0],
[0, 0, 1, 1, 0],
[1, 1, 1, 1, 1]
]
print(pinv(M))
[[ 5.00000000e-01 -2.01966890e-16 1.54302378e-16]
[ 5.00000000e-01 1.48779676e-16 -2.10806254e-16]
[-8.76351626e-17 5.00000000e-01 8.66819360e-17]
[-2.60659800e-17 5.00000000e-01 3.43000417e-17]
[-1.00000000e+00 -1.00000000e+00 1.00000000e+00]]
从这个伪逆中,我们看到变量 e
(最后一行)确实可以表示为 - A - B + C
。然而,它也“预测”a=A/2
和b=A/2
。为了消除这些非唯一解(例如 a=A
和 b=0
同样有效),让我们借用 SciPy Cookbook 中的函数来计算零空间。 :
print(nullspace(M))
[[ 5.00000000e-01 -5.00000000e-01]
[-5.00000000e-01 5.00000000e-01]
[-5.00000000e-01 -5.00000000e-01]
[ 5.00000000e-01 5.00000000e-01]
[-1.77302319e-16 2.22044605e-16]]
该函数已经返回组装成矩阵的零空间的基础(每列一个向量),我们看到,在合理的精度内,唯一的零行确实只是与变量 e
对应的最后一行。 .
编辑:
对于方程组
A = a + b, B = b + c, C = a + c
对应的矩阵M
是
[ 1 1 0 ]
[ 0 1 1 ]
[ 1 0 1 ]
在这里我们看到矩阵实际上是方阵,并且是可逆的(行列式是 2
)。因此,伪逆与“正常”逆一致:
[[ 0.5 -0.5 0.5]
[ 0.5 0.5 -0.5]
[-0.5 0.5 0.5]]
对应于解决方案a = (A - B + C)/2, ...
。自 M
是可逆的,它的内核/零空间是空的,这就是 Cookbook 函数仅返回 []
的原因。为了了解这一点,让我们使用内核的定义 - 它由所有非零向量 x
组成。这样M.x = 0
。然而,自从 M^{-1}
存在,x
给出为 x = M^{-1} . 0 = 0
这是一个矛盾。从形式上来说,这意味着找到的解决方案是唯一的(或者所有变量都是“可解的”)。
关于pandas - 使用 svd 求解欠定 scipy.sparse 矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50843004/