Есть ли способ генерировать случайные решения для неквадратных линейных уравнений, предпочтительно в python?

Question

Прежде всего, я знаю, что эти темы существуют! Так что терпите меня, они не полностью ответили на мой вопрос.

В качестве примера предположим, что мы находимся в четырехмерном векторном пространстве, т.е. R^4. Мы смотрим на два линейных уравнения:

3*x1 - 2* x2 + 7*x3 - 2*x4 = 6
1*x1 + 3* x2 - 2*x3 + 5*x4 = -2 

Фактические вопросы таковы: есть ли способ создать число N точек, которые решают оба этих уравнений, используя линейные решатели из NumPy и т. Д.?

Основная проблема со всеми библиотеками python, которые я пробовал до сих пор: им нужно n уравнения для n -мерного пространства

Решение задачи очень просто для одного уравнения, поскольку вы можете просто использовать n-1 случайно сгенерированные значения и адаптировать последнее так, чтобы вектор решал уравнение.

Моим ожидаемым результатом будет список N "случайно" сгенерированных точек, которые решают k линейных уравнений в n -мерном пространстве, где k<n.

Answer 1

Поскольку у вас есть недоопределенная система уравнений (слишком мало ограничений для ваших решений или меньше уравнений, чем переменных), вы можете просто выбрать произвольные значения для x3 и x4 и решить систему в x1, x2 (здесь 2 переменные / 2 уравнения).

Вам просто нужно убедиться, что полученная система не является несовместимой (т.е. она не допускает решения) и что нет повторяющихся решений.

Например, вы можете исправить x3 = 0 и, выбрав случайные значения x4, получить решения для ваших уравнений в x1, x2

Вот пример, генерирующий 10 «случайных» решений

n = 10
x3 = 0
X = []
for x4 in np.random.choice(1000, n):
  b = np.array([[6-7*x3+2*x4],[-2+2*x3-5*x4]])
  x = np.linalg.solve(a, b)
  X.append(np.append(x,[x3,x4]))

# check solution nr. 3
[x1, x2, x3, x4] = X[3]
3*x1 - 2* x2 + 7*x3 - 2*x4
# output:  6.0
1*x1 + 3* x2 - 2*x3 + 5*x4
# output: -2.0

Answer 2

Спасибо за ответы, которые помогли мне и указали в правильном направлении.

Теперь у меня есть простое пошаговое решение моей проблемы для произвольного k<n.

1. Найти одно решение для всех приведенных уравнений. Это можно сделать с помощью

 solution_vec = numpy.linalg.lstsq(A,b)

это дает решение, как видно из ukemis answer . В моем примере выше матрица A равна коэффициентам уравнений с левой стороны, b представляет вектор с правой стороны.

2. Определите пустое пространство вашей матрицы A.

Это все векторы v, так что скалярное произведение v*A_i = 0 для каждой (!) Строки A_i из A. Следующая функция, найденная в этой теме , может использоваться для получения представителей пустого пространства A:

def nullSpaceOfMatrix(A, eps=1e-15):
    u, s, vh = scipy.linalg.svd(A)
    null_mask = (s <= eps)
    null_space = scipy.compress(null_mask, vh, axis=0)
    return scipy.transpose(null_space)  

3. Создайте столько (N) "случайных" линейных комбинаций (то есть со случайными коэффициентами) из solution_vec и результирующих векторов пустого пространства матрицы, сколько хотите! Это работает, потому что скалярное произведение аддитивно, а векторы с нулевым пространством имеют скалярное произведение 0 на векторы уравнений. Эти линейные комбинации всегда должны содержать solution_vec, как в:

linear_combination = solution_vec + a*null_spacevec_1 + b*nullspacevec_2...

, где a и b могут быть выбраны случайным образом.

Answer 3

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

Недоопределенная линейная система не имеет ни решения, ни бесконечного множества решений.

...

Существуют алгоритмы, позволяющие решить, имеет ли недоопределенная система решения, и если они есть, выразить все решения в виде линейных функций от k переменных (то же самое, что и выше). Самым простым является исключение Гаусса.

Как вы говорите, для многих функций, доступных в библиотеках (например, np.linalg.solve), требуется квадратная матрица (т.е. n уравнений для n неизвестных), и вам нужна реализация исключения Гаусса для не квадрат линейные системы .

Это не «случайно», но np.linalg.lstsq (наименьший квадрат) будет решать неквадратные матрицы:

Вернуть решение наименьших квадратов в линейное матричное уравнение.

Решает уравнение a x = b, вычисляя вектор x, который минимизирует евклидову 2-норму || б - х || ^ 2. Уравнение может быть недооценено, хорошо или переопределено (т. Е. Число линейно независимых строк a может быть меньше, равно или больше его числа линейно независимых столбцов). Если a является квадратом и имеет полный ранг, то x (но для ошибки округления) является «точным» решением уравнения.

Для получения дополнительной информации см .: решение Ax = b для неквадратной матрицы A с использованием python