查找一组未知数多于方程的方程的整数解编辑1

math java apache-commons-math

2022-09-03 02:43:29

我正在尝试构建一个系统，我需要找到一组线性方程的解，其中（比方程）更多的变量。

问题归结为以下内容：

想象一组方程式：

A = A1*X1 + A2*X2 + ... + AnXn
B = B1*X1 + B2*X2 + ... + BnXn

如何找到此系统的一个或多个（正）整数解？

注意：我一直在研究apache-commons-math库，但我找不到任何关于如何解决/找到具有自由变量的系统解决方案的方向。

答案 1

使用 Lenstra–Lenstra–Lovász 格基约简算法来查找系统的 Hermite 范式。

答案 2

遵循此示例：假设等式为：

7 = x + 3y + 4z + 9w
12 = 4x + 2y + 3z + 7w

有2个方程和4个未知数。您可以将 2 个未知数设置为参数，因此系统将具有与未知数一样多的方程：

7 - (4z + 9w) = x + 3y
12 - (3z + 7w) = 4x + 2y

我们将使用 x 和 y 作为未知数。可以求解它，并将 w 和 z 作为线性解中的参数：

x = (22 - 3w - z)/10
y = (16 - 29w - 13z)/10

现在，您需要使分子可以被分母10整除。如果有解决方案，则可以测试从 1 到 10 的所有参数。

通常，您执行此操作：

选择参数，以便存在与方程一样多的未知数。尝试保留为行列式生成最小绝对值的未知数（在示例中，它是 10，但选择 y 和 z 会更好，因为它|det|=3）
求解线性系统并根据参数生成答案
测试从 1 到 det 的绝对值的参数值（如果有解，此时会找到它），直到所有未知数都有一个整数解（这就是为什么你之前选择最小的行列式绝对值）并检查它是否为正（这在示例中没有说明）。

很抱歉，如果在最后一步是蛮力，但至少有可能最小化测试的范围。也许，可能有更好的方法来解决最终的丢番图方程组，但我不知道任何方法。

编辑1

有一种方法可以避免暴力强迫最后一部分。同样，在示例中，您必须使：

22 = 3w + z (congruent, mod 10)
16 = 29w + 13z (congruent, mod 10)

应用模量：

2 = 3w + z (congruent, mod 10)
6 = 9w + 3z (congruent, mod 10)

您可以将同余系统设为三角形（高斯消去），将同余乘以模数 10 中的逆，并求和为其他同余。模数 10 中 9 的逆比是 -1，因此我们将最后一个同余相乘：

2 = 3w + z (congruent, mod 10)
-6 = -9w + -3z (congruent, mod 10)

等效于：

2 = 3w + z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)

然后，乘以 -3 并加到第一个：

2 - 3*4 = 3w + z -3w - 21z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)

等效于：

-10 = -20z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)

然后，从上到下求解（此示例对于任何 z 值似乎都是正确的）。如果参数多于同余参数，则可以有一定程度的自由度，但它们是等效的，您可以将多余的参数设置为任何值，最好是最小值为 1。

如果还有不清楚的地方，请告诉我！