Три задачи с одним решением

Есть три задачи. Задача первая – решить матричное уравнение A x = b, где A – матрица, x – неизвестный вектор, а b – заданная правая часть, опять вектор. Коэффициенты – действительные числа.

Во второй задаче коэффициенты (и у матрицы и у векторов) – целые числа.

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

Накал пиздеца постепенно крепчает. Целые числа мы не всегда можем делить друг на друга. Впрочем, взяв пару чисел (a, b), мы можем вычесть из большего по модулю числа меньшее по модулю, и такая процедура редукции нам отлично заменит деление.

А целые положительные числа мы можем вычитать, только меньшее из большего.

Однако, алгоритм Гаусса решения линейных систем уравнений работает во всех трех случаях (на то он и Гаусс).

Умные дядьки про третью задачу пишут страшное, примерно такое: http://documents.kenyon.edu/math/CWendler.pdf Это страшные люди, разобраться в их алгебре практически невозможно.

Попытаюсь на пальцах.

Итак, хотим мы решить системку линейных уравнений в действительных числах. Берем какую-то 4×4 матричку коэффициентов A, приписали справа единичную матрицу со знаком минус.

7.00 8.00 2.00 5.00 |-1.00 0.00 0.00 0.00
3.00 3.00 9.00 8.00 | 0.00 -1.00 0.00 0.00
2.00 9.00 8.00 9.00 | 0.00 0.00 -1.00 0.00
1.00 7.00 3.00 3.00 | 0.00 0.00 0.00 -1.00

Получили 4 вектора длины 8, я разделяю их на две части знаком |, но это чисто визуализация, алгоритм работает с длинными векторами без всякого деления на половинки.

Упорядочим вектора в лексикографическом порядке и применим полную редукцию (алгоритм Гаусса – Бухбергера, назовем так этот процесс). Редукция вектора x по вектору y определяется просто – находим первый ненулевой коэффициент y_i и заменяем x на x – (x_y / y_i) * y. Убили x_i, молодцы, получили лексикографически меньший вектор. Будем редуцировать вектор из набора по всем остальным векторам, пока хоть что-то меняется. Для красоты я еще отнормирую вектора, чтобы первый ненулевой коэффициент был 1. Это мелочь.

Отредуцировали, получили вот такую красивую картинку:

1.00 0.00 0.00 0.00 |-0.13 -0.15 0.24 -0.09
0.00 1.00 0.00 0.00 | 0.00 0.04 0.03 -0.20
0.00 0.00 1.00 0.00 | 0.09 -0.32 0.39 -0.48
0.00 0.00 0.00 1.00 |-0.06 0.28 -0.55 0.65

Слева стоит единичная матрица, справа – какая-то. Замечу, что мы могли взять неквадратную матрицу коэффициентов, могли взять вырожденную матрицу. В алгоритме ничего не поменялось бы.

Решим теперь уравнение A x = b. К вектору b припишем справа нули, и полученный вектор длины 8 редуцируем относительно полученного базиса.

560.00 1763.00 1887.00 1882.00 | 0.00 0.00 0.00 0.00

Вуаля!

0.00 0.00 0.00 0.00 | 1.00 -96.01 -94.00 -91.01

Слева у нас нули, справа – искомый вектор x, решение. Если бы редукция не удалась (b не лежало бы в образе A), то у нас слева были бы ненулевые числа. Такой прикольный алгоритм Гаусса для произвольных систем. Линейка, ВУЗ, первый курс.

Повторим процесс для целочисленных векторов, матрица такая же, как и для предыдущего варианта.

7 8 2 5 | -1 0 0 0
3 3 9 8 | 0 -1 0 0
2 9 8 9 | 0 0 -1 0
1 7 3 3 | 0 0 0 -1

Применяем редукцию Гаусса-Бухбергера… Стоп, а как редуцировать один целочисленный вектор относительно другого? Ответ. As simple as x – y или x + y. Находим как и раньше первый ненулевой элемент y_i и смотрим, можем ли мы операцией + или минус уменьшить абсолютное значение x_i (читай, уменьшить вектор относительно лексикографического порядка). Редуцируем систему векторов, пока можем, получаем:

1 0 -2 -23 | 1 -6 12 -14
0 -1 1 19 | -1 5 -10 12
0 0 -3 -92 | 5 -25 49 -58
0 0 0 209 | -12 59 -114 135

Как и раньше, для решения уравнения A x = b берем b, приписываем к нему справа четверку нулей, редуцируем полученный вектор:

560 1763 1887 1882 | 0 0 0 0

относительно системы. Получаем… Шайтан, решение:

0 0 0 0 | -1 96 94 91

Напомню, если слева у нас получились не нули (которые дальше не хотят редуцироваться ни одним из векторов системы), то пиздец – решения нету. Иначе читаем решение в правой части. Например, наша система не имеет решения для любых векторов b = (0, 0, 0, число не кратное 209). Теория чисел, хороший ВУЗ, третий курс.

Двигаемся дальше. Все то же уравнение A x = b, но в целых положительных числах. Что надо делать, мы уже знаем – нарисовать вот такую красоту надо:

7 8 2 5 | -1 0 0 0
3 3 9 8 | 0 -1 0 0
2 9 8 9 | 0 0 -1 0
1 7 3 3 | 0 0 0 -1

Редуцируем систему… Функция редукции x относительно y очень простая – определим для вектора v положительную часть v+, как поэлементную операцию {max(v_i, 0)}. Скажем, что x можно редуцировать относительно y, если x+ поэлементно не меньше y+, а сама редукция равна в этом случае x – y. Редукция опять уменьшает вектор в лексикографическом смысле. Кроме этого она заебатая тем, что редукция от вектора с неотрицательными элементами снова неотрицательная. К сожалению, так просто все не работает. Редукции запрещают друг друга. Т.е. у нас есть выбор редуцировать вектор x с помощью вектора y или c помощью вектора z, каждый выбор в общем запрещает другую редукцию. Поэтому Бухбергер предложил очень простую вещь. Он сначала полностью редуцирует систему векторов друг относительно друга, а потом добавляет N^2 попарных разностей u – v. И действует так, пока базис не становится стабильным. Чудеса заключаются в том, что хоть число базисных векторов и растет (вообще говоря неконтролируемо), наш процесс останавливается. Добавление попарных разностей u – v гарантирует, что в процессе градиентного спуска мы не залезем в локальную яму.

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

http://www.everfall.com/paste/id.php?1ydzx51iwu6v

Хороший математический ВУЗ, кандидатский минимум по алгебре, “алгоритм Бухбергера построения базиса Гребнера в идеале полиномов”.  Это он и есть. Я только аккуратно закамуфлировал в алгоритме полиномы, так что их почти не видно.

Решаем систему, редуцируем вектор

560 1763 1887 1882 | 0 0 0 0

получаем (по свойству редукции опять вектор с неотрицательными компонентами):

0 0 21 17 | 0 94 93 92

В прошлой части мы получили решение с одной отрицательной компонентой. А вот тут обломились. Нету положительных решений. А вот для правой части b = (903 2155 1985 2127) находится решение x = (48 96 94 91). Если решений несколько, найдется лучшее с точки зрения лексикографического порядка.

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

Вот такая забавная математика. В ней нет сложных идей. Есть муторные доказательства, но идеи (алгоритмы) все чистые, простецкие. Плохой алгоритм – плохая математика.

сорцы:

http://www.everfall.com/paste/id.php?rpf69siiusru

  • Pingback: Tweets that mention highly professional scums » Blog Archive » Три задачи с одним решением -- Topsy.com()

  • Ruslan Abdikeev

    С одной стороны мне жаль, что здесь не комментариев нихера потому что какой-то угрюмый человек прикрутил какую-то хрень болотную.
    С другой стороны – мне по-настоящему жаль, что everfall paste полностью протух — там боты резвятся со страшной силой, и угробили обе ссылки :(