python - 找到最大的线性独立表达式子集的最有效方法是什么

我有一个表达式列表

from sympy import *

x = symbols('x')

e0 = x
e1 = x**2
e2 = 2*x**2

如何找到线性独立表达式的最大子集？
您可以假设要对表达式进行排序，即首选具有较低索引的表达式。

我尝试迭代以下内容:

a = numbered_symbols('a')
a0 = next(a)
a1 = next(a)
a2 = next(a)

solve(a0*e0 + a1*e1, a0, a1)
# {a0: 0, a1: 0}

solve(a0*e0 + a1*e1 + a2*e2, a0, a1, a2)
# {a1: -2*a2, a0: 0}

所以我取e0和e1。要自动执行此操作:

from operator import mul
from toolz import take

def _linear_independent(exprs):
    c = list(take(len(exprs), numbered_symbols("c")))
    expr = sum(map(mul, exprs, c))
    res = solve(expr, c)
    return all(v == 0 for v in res.values())

def max_independent_set(exprs):
    max_set = [exprs[0]]
    for e in exprs[1:]:
        if _linear_independent(max_set + [e]):
            max_set.append(e)
    return max_set

max_independent_set([e0, e1, e2]) # [x, x**2]

有没有更有效(运行时)的方法来做到这一点？
目前，我需要调用solve N-1，并且要解决的系统正在增加。也许可以将其分解为更小的任务？

奖励:我也在寻找一种方法来使用多个自变量来做到这一点。我目前的方法不起作用(它不仅解决了系数):

x, y = symbols('x y')
e0 = x
e1 = y
exprs = [e0, e1]

c = list(take(len(exprs), numbered_symbols("c")))
expr = sum(map(mul, exprs, c))
res = solve(expr, c)  # [{c0: -c1*y/x}]

我的表达式描述了 R^N -> R 中的函数。以前我会在我的数据集上评估它们并根据相关性排除它们。

最佳答案

您可以使用一些矩阵例程来计算它。函数 linear_eq_to_matrix 将方程组转换为矩阵:

>>> A, b = linear_eq_to_matrix([x, x**2, 2*x**2], [x, x**2])
>>> pprint(A)
⎡1  0⎤
⎢    ⎥
⎢0  1⎥
⎢    ⎥
⎣0  2⎦

(如果您有常数因子，它们将作为等式的右侧放入 b 中)。这是您想要的转置，因为您想要的矩阵运算适用于列。 A.T.columnspace 将返回跨越 A.T 列的列:

>>> A, b = linear_eq_to_matrix([x, x**2, 2*x**2], [x, x**2])
>>> pprint(A.T.columnspace())
⎡⎡1⎤  ⎡0⎤⎤
⎢⎢ ⎥, ⎢ ⎥⎥
⎣⎣0⎦  ⎣1⎦⎦

这告诉您第一个和第二个元素跨越空间(因为您获得了 A.T 的第一列和第二列)。如果您还想知道如何根据那些线性无关的元素重写其他元素，请使用 A.T.nullspace() 。

例如:

>>> pprint(A.T.nullspace())
⎡⎡0 ⎤⎤
⎢⎢  ⎥⎥
⎢⎢-2⎥⎥
⎢⎢  ⎥⎥
⎣⎣1 ⎦⎦

这意味着 -2*(x**2) + 1*(2*x**2) = 0 (所以最后两个元素是线性无关的。

举一个更大的例子:

>>> A, b = linear_eq_to_matrix([x, 2*x, x**2, 2*x**2, x**3, x + x**2], [x, x**2, x**3])
>>> pprint(A.T)
⎡1  2  0  0  0  1⎤
⎢                ⎥
⎢0  0  1  2  0  1⎥
⎢                ⎥
⎣0  0  0  0  1  0⎦
>>> pprint(A.T.columnspace())
⎡⎡1⎤  ⎡0⎤  ⎡0⎤⎤
⎢⎢ ⎥  ⎢ ⎥  ⎢ ⎥⎥
⎢⎢0⎥, ⎢1⎥, ⎢0⎥⎥
⎢⎢ ⎥  ⎢ ⎥  ⎢ ⎥⎥
⎣⎣0⎦  ⎣0⎦  ⎣1⎦⎦
>>> pprint(A.T.nullspace())
⎡⎡-2⎤  ⎡0 ⎤  ⎡-1⎤⎤
⎢⎢  ⎥  ⎢  ⎥  ⎢  ⎥⎥
⎢⎢1 ⎥  ⎢0 ⎥  ⎢0 ⎥⎥
⎢⎢  ⎥  ⎢  ⎥  ⎢  ⎥⎥
⎢⎢0 ⎥  ⎢-2⎥  ⎢-1⎥⎥
⎢⎢  ⎥, ⎢  ⎥, ⎢  ⎥⎥
⎢⎢0 ⎥  ⎢1 ⎥  ⎢0 ⎥⎥
⎢⎢  ⎥  ⎢  ⎥  ⎢  ⎥⎥
⎢⎢0 ⎥  ⎢0 ⎥  ⎢0 ⎥⎥
⎢⎢  ⎥  ⎢  ⎥  ⎢  ⎥⎥
⎣⎣0 ⎦  ⎣0 ⎦  ⎣1 ⎦⎦

请注意，我们有 3 个零空间的生成向量和 3 个列空间的生成向量，它们与 rank-nullity theorem (3 + 3 = 6) 匹配。对于列空间，我们得到了 A.T 的第一、第二和第五列，这意味着它们是线性无关的元素(或者，我们可以将列乘以我们从中提取矩阵的项向量 Matrix([x, x**2, x**3]).T 。

在零空间中，每列中最后的 1 表示可以删除的元素，它上面的项(实际上是它们的否定)告诉您如何根据其他项(例如 2*x = -(-2)*x 、 2*x**2 = -(2)*x**2 、 x + x**2 = -(1)*x + -(1)*x**2 )重写它。

这确实要求您从您认为是术语的表达式列表开始(在本例中为 [x, x**2, x**3] )。这很重要。从对您的问题的评论中举个例子，如果您的术语只是 [cos(x), cos(x)*sin(y)] ，则 [cos(x)] 是线性相关的，但如果您的术语是 [cos(x), sin(y)] 则甚至不是线性系统(如果它们是 [cos(x), cos(x)*sin(y)] ，则甚至不是线性系统。

关于python - 找到最大的线性独立表达式子集的最有效方法是什么，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43008815/