Доброго времени суток, 
Помогите мне пожалуйста с алгоритмном решения системы линейных уравнений


Эта задача аналитически решения не имеет.
У меня есть идея только побирать значения A.

Буду благодарен за хороший совет по этому поводу.

м метод, симплекс метод, метод джордана - гауса? геометрический метод?
я угадал?

К сожалению - нет
Все они расчитаны на слушчай, когда мы ищем X, а тут обратная задача - найти матрицу А, которая размером в n*n.

а11 а12 а13       х1 = у1
а21 а22 а23   *  х2 = у2
а31 а32 а33       х2 = у3

Хм.. прошу прощение.. я перепутал с простым методом Гауса для решения СЛАУ и ему подобными
Не думал о подходе к задаче со стороны моделирования.. но возможно это лучший вариант.

Как раз аналитически-то ее решить просто, проблема в том, что таких решений слишком много. Ну, например:

1) Если среди элементов вектора X нет нулевых, то все элементы матрицы A, кроме элементов на главной диагонали, можно сделать нулевыми, а диагональные элементы выбрать так, чтобы для каждого i выполнялось условие  A_{ii}*X_i=Y_i. Если среди X_i есть равные нулю, то более-менее очевидно, что предыдущий случай можно расширить, подбирая также элементы A_{i,i+1}.
2) Любой вектор в R^n можно превратить в любой другой вектор композицией поворота и домножения на скаляр. Соответственно, матрицу A можно легко соорудить из матрицы поворота. 

Ну и т.д. Соответственно, в такой постановке задача решается, но, подозреваю, это неинтересно. На матрицу A должны быть наложены какие-то дополнительные условия. Это так?

Да, есть ограничение, что ее определитель должен быть максимальным из возможных.



Спасибо за совет. В Х нулевых элементов нет. Их вообще нигде нет, ни в А, ни в Х, ни в Y. Там могут быть разве что относительно малые значения например 0.1.

Но это дает интересную почву для размышлений.

Ножно и в самом деле задать диагональные элементы А
A_{ii}=Y_i / X_i  - (N - 1) * 0.1

остальные элементы можно задать A_{ij} = 0.1

А для выполнения условия максимального определителя, цыклически недиагональные элементы увеличивать, а диагональные уменьшать.
Вот только как бы его узнать это максимальное значение определителя, к которому стремится? 

Тогда это интереснее.   Но только максимальным вообще или максимальным по абсолютному значению? 

Наверное, второе (иначе задача развалится на несколько принципиально разных случаев) и, скорее всего, это сопровождается условием, что элементы векторов X и Y положительны? Кстати, давайте уж сразу все условие (вместе с источником задачи, если таковой есть), а то выяснять часть условий "на ходу" как-то неправильно.


Нет, не годится. Если нас интересует максимум по модулю, то можно легко проверить (хотя бы для N=2--3), что в этом случае определитель будет уменьшаться, а не расти.

Похоже, что в этом случае надо использовать как раз второй вариант из тех, что я предлагал. Некое обоснование (это не строгое доказательство, но, по-видимому, его можно довести до кондиции) таково: 

Матрица A может быть представлена в виде произведения матрицы поворота и матрицы растяжения (диагональной с одинаковыми элементами, равными отношению длин векторов Y и X, обозначим это как L(Y)/L(X)). Определитель первой равен 1, определитель второй - (L(Y)/L(X))^N, определитель матрицы A равен их произведению, т.е. определителю матрицы растяжения. 

Любое другое преобразование также можно представить в виде аналогичной композиции, но вторая матрица будет не матрицей растяжения, а некоторой произвольной диагональной матрицей (с различными диагональными элементами). При этом, однако, в итоге нам нужно будет получить вектор той же самой длины, поэтому задача сводится к подбору набора из N чисел с фиксированной суммой так, чтобы их произведение было максимальным.  Ответ хорошо известен - числа должны быть равными. Следовательно, именно поворот и растяжение будут давать максимальное значение определителя.

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

боюсь, что можно подобрать матрицу со сколь угодно большим определителем
пример - 3d
будет считать, что оба вектора в плоскости XY
тогда среди подходящих матриц будут такие, которые поворачивают вектора в плоскости XY и умножают Z на какое-то число k, при чём k может быть любым

определитель таких матриц будет равен этому числу k, так что можно будет его выбирать любым
так что никакого максимума определитель не достигнет

этот случай вполне естественно обобщается на вектора не только в горизонтальной плоскости и не только в 3d

По условию среди элементов векторов X и Y нет нулевых. Соответственно, этот контрпример не годится.

ну рассмотрим наклонённую плоскость, например Z=X
тогда нам подходят все матрицы, которые поворачивают вектора в этой плоскости и масштабируют вдоль нормали этой плоскости, а дальше - как уже описано

да и вообще условие всех ненулевых координат векторов не так уж и много даёт по сравнению с условием, что хоть одна координата у каждого вектора ненулевая

всегда можно подобрать матрицу поворота системы координат, которая сделает из вектора с хотя бы одной ненулевой координатой вектор, у которого все координаты ненулевые, потом домножить A с одной стороны на эту матрицу, с другой на обратную к ней, определитель не изменится...

Но у такой матрицы определитель сделать сколь угодно большим не удастся. Для этого необходимо (но даже не достаточно), чтобы хотя бы один иэ элементов матрицы можно было свободно менять, а для этого необходимо, чтобы плоскость была перпендикулярна какой-то из осей координат.


Да, вот это, пожалуй, верно. Тогда получается, что задача действительно не решается, поскольку можно сначала повернуть вектор так, чтобы обнулить все его элементы, кроме одного, потом смасштабировать это как угодно (и со сколь угодно большим определителем), а потом повернуть так, как надо.

Вообщем это задача на межотраслевой балланс:
Вектор X - производство по каждой отросли
Вектор У - издержки по каждой отросли
Матрица А - матрица коефициентов взаимосвязей между отраслями - тоесть пропорция того, сколько одной отрасли необходимо продукции другой отросли на изготовление своей продукции

Можно предположить что могут быть случаи, когда X, Y - отрицательны, но если они будут нулевыми то смысла от такого балланса просто нету

Сидел думал по поводу вариантов решения.. в самом деле задача задана некоректно - матрица, которая удовлетворяет всем условиям диагональная.

Я сново перечилал литературу по этому баллансу... 
Извините меня, но я пропустил очень важный ньюанс..

Систему можно привести к другому виду:
Сумма столбцов строки i матрицы А = Y_i
Сумма строк столбца j = X_j

а11 + а12 + а13 = у1
а21 + а22 + а23 = у2
а31 + а32 + а33 = у3
----------------------------
x1        x2      x3

Тут уже 2n уровнений, что не может не радовать

Еще раз прошу прощение, что сразу этого не заметил.

Подскажите пожалуйста, каким методом можно решить такую систему?

Радикально это ничего не изменит - количество неизвестных все равно больше количества уравнений и система недоопределена.

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

Если брать последнюю постановку задачи (найти матрицу NxN с заданными суммами по строкам и столбцам), то это является частным случаем задачи на нахождение максимального потока: сделаем двудольный граф, в первой доле его - N вершин - строки, во второй - N вершин - столбцы, а между ними рёбра из каждой строки i в каждый столбец j, с бесконечной пропускной способностью; далее введём исток s и от него рёбра к каждой строке i с пропускными способностями yi; далее введём сток t и к нему рёбра от каждого столбца j с пропускной способностью xj. В итоге в этой сети наод найти максимальный поток, и если его величина равна сумме всех иксов (равно как и всех игреков), то решение существует, и искомые Aij равны потоку из строки i в столбец j. Иначе решения не существует.

Следует заметить, в этом потоковом решении среди всех возможных ответов A найдётся произвольный; я не совсем понял, остаётся ли в силе условие, что эта матрица должна иметь максимальный определитель. Если да, то пожалуй поток тут не очень применить, надо думать дальше  Хотя это странное условие - "иметь максимальный определитель" - сбивает с толку; ничего подобного я в своей практике не помню.

maxdiver, а можно поподробнее о потоке? 
Я не очень силён в теории графов.. уже почти все забыл, но постараюсь вспомнить.

Запутался про исток и сток.
Объясните, пожалуйста.

Это сообщение отредактировал(а) RYB - 9.5.2010, 19:18