Найти, какие переменные свободны в недоопределенной линейной системе

Question

У меня недоопределенная система линейных уравнений.Это может быть решено, например, SimPy, где решение является функцией некоторых свободных переменных.Что я ищу, так это те свободные переменные.Этот набор переменных не уникален, но достаточно одного варианта.Например,

[1  0  1] [x1] = [1]
[0  1  0] [x2] = [1]
          [x3]

Здесь x2 определяется вторым уравнением, и либо x1, либо x3 можно использовать в качестве свободной переменной.Так, например, набор {x1} является правильным решением моей проблемы

Один из способов найти это - использовать SymPy и анализировать решения, чтобы найти, какие переменные там используются.Это довольно громоздко.Есть ли лучший способ сделать это?Желательно без каких-либо символических вычислений (возвращающих индекс свободных переменных).

Здесь тот же вопрос задается, но не получен ответ, поскольку выяснилось, что спрашивающий хотел задать что-то еще: Как определитькоторый является свободной переменной в результате sympy.linsolve

Он просто хотел единственное решение для системы.Я хочу знать свободные переменные, и мне даже не нужно знать решение.

Answer 1

Не уверен, что это точно, но я думаю, что свободной переменной является любая переменная, имеющая ненулевой коэффициент для непорового элемента в эшелоне формы , и переменная, которую она описывает.

Answer 2

Это похоже на Как найти основу для пространства столбцов прямоугольной матрицы? за исключением того, что вы запрашиваете свободные переменные, которые соответствуют столбцам, которые остаются после того, как мы выбрали основу дляпространство столбца.Таким образом, разница в размерах сводит одну проблему к другой.Вот пример с немного более сложной матрицей:

import numpy as np
from scipy.linalg import lu
M = np.array([[1, 1, 0, 1], [0, 0, 1, 0], [0, 0, 7, 0]])
U = lu(M)[2]
basis_columns = {np.flatnonzero(U[i, :])[0] for i in range(U.shape[0])}
free_variables = set(range(U.shape[1])) - basis_columns

Ответ: {1, 3}.

Предостережение: все это чувствительно к ошибкам с плавающей запятой, поэтому SymPy все еще можно использовать, если у вас есть точные рациональные числа во входных данных и вы хотите сохранить их как таковые.