Scipy - 找到矩阵列空间的基数 [英] Scipy - find bases of column space of matrix

问题描述

我正在尝试编写一个简单的Simplex算法，其第一步是找到一个基本可行的解决方案:

I'm trying to code up a simple Simplex algorithm, the first step of which is to find a basic feasible solution:

1. 选择A的线性独立列的集合B
2. 将与不在B中的列相对应的x的所有分量设置为零.
3. 求解m个所得方程，以确定x的分量.这些是基本变量.

我知道解决方案将涉及使用 scipy.linalg.svd (或 scipy.linalg.lu )和一些 numpy.argwhere / numpy.where 魔术，但我不确定具体如何.

I know the solution will involve using scipy.linalg.svd (or scipy.linalg.lu) and some numpy.argwhere / numpy.where magic, but I'm not sure exactly how.

有人有纯粹的Numpy/Scipy实现来寻找基础吗(步骤1)，或者甚至更好的是上述所有条件?

Does anyone have a pure-Numpy/Scipy implementation of finding a basis (step 1) or, even better, all of the above?

示例:

>>> A
array([[1, 1, 1, 1, 0, 0, 0],
       [1, 0, 0, 0, 1, 0, 0],
       [0, 0, 1, 0, 0, 1, 0],
       [0, 3, 1, 0, 0, 0, 1]])

>>> u, s, v = scipy.linalg.svd(A)
>>> non_zero, = numpy.where(s > 1e-7)
>>> rank = len(non_zero)
>>> rank
4
>>> for basis in some_unknown_function(A):
...     print(basis)
{3, 4, 5, 6}
{1, 4, 5, 6}

以此类推.

推荐答案

A

A QR decomposition provides an orthogonal basis for the column space of A:

q,r = np.linalg.qr(A)

如果 A 的等级为 n ，则 q 的前 n 列构成以下内容的基础 A 的列空间.

If the rank of A is n, then the first n columns of q form a basis for the column space of A.

这篇关于Scipy - 找到矩阵列空间的基数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！