algorithm - 如何在欠定的线性方程组中找到 "partial"解？

Question

假设我有这个矩阵:

1 1 1 | 1
0 0 1 | 1

这个系统显然有无限的解决方案。

x1 = -x2
x3 = 1

x1 依赖于 x2，x2 是免费的，但我感兴趣的是 x3。是否有一种算法可以找到如下所示的解决方案:[NaN, NaN, 1] for x1, x2 and x3？

我的猜测是您可以使用高斯消去算法的变体，但我不太确定该怎么做。

Answer 1

我假设一个系统至少有一个解决方案(您可以使用标准高斯消去法来检查它)。

引理:变量的值是固定的当且仅当它是简化行阶梯形式的行中的唯一变量。

证明:如果它是行中唯一的变量，则对于齐次系统的任何解，它都必须为零。因此，它是原始系统的常数。

如果它不是行中的唯一变量，则其值不固定。事实上，行中的另一个变量是自由的，所以我们可以任意选择它的值。这个自由变量的两个不同选择给出了主变量的两个不同值。

所以最终的解决方案是这样的:

1. 使用高斯消元法得到矩阵的简化行阶梯形式。

2. 检查是否至少有一个解决方案。如果没有返回一些东西。

3. 如果变量是行中的唯一变量，则返回包含变量值的向量，否则返回 Nan。

在您的例子中，简化的阶​​梯形式是:

1 1 0 0
0 0 1 1

最后一个变量具有唯一值 1。第二个变量是自由的。第一个变量不是其所在行中的唯一变量。因此，结果是 [Nan, Nan, 3]。