用numpy解决整数上的线性系统 [英] Solving linear system over integers with numpy

问题描述

我正在尝试用numpy解决一个超定线性方程组.目前，我正在做类似的事情(作为一个简单的例子):

I'm trying to solve an overdetermined linear system of equations with numpy. Currently, I'm doing something like this (as a simple example):

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

print np.linalg.lstsq(a,b)[0]

[ 1.  1.]

这有效，但使用浮点数.有什么办法只能解决整数问题吗?我已经尝试过类似的方法

This works, but uses floats. Is there any way to solve the system over integers only? I've tried something along the lines of

print map(int, np.linalg.lstsq(a,b)[0])

[0, 1]

为了将解决方案转换为整数数组，期望使用[1, 1]，但是显然我缺少了一些东西.有人能指出我正确的方向吗?

in order to convert the solution to an array of ints, expecting [1, 1], but clearly I'm missing something. Could anyone point me in the right direction?

推荐答案

您正在查看线性的系统双色子方程.快速进行Google搜索 线性Diophantine方程组费利克斯·拉泽布尼克(Felix Lazebnik).在该论文中，作者考虑了以下问题:

You are looking at a system of linear diophantine equations. A quick Google search comes up with Systems of Linear Diophantine Equations by Felix Lazebnik. In that paper, the author considers the following question:

给出一个线性方程组Ax = b，其中A = a(i，j)是m×n矩阵 具有整数项，并且b是具有整数分量的m×1列向量，系统 有一个整数解，即一个n×1个具有整数分量的解向量x?

Given a system of linear equations Ax = b, where A = a(i,j) is an m × n matrix with integer entries, and b is an m × 1 column vector with integer components, does the system have an integer solution, i.e. an n × 1 solution vector x with integer components?

这篇关于用numpy解决整数上的线性系统的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！