1.5 Пример работы алгоритма Григорьева

Рассмотрим работу алгоритма на матрице ТСЛУ (1.1).

1. Инициализируем пустое множество J.

2. Включаем в него столбец, в котором лежит минимум первой строки, то есть первый.

; а

3. Включаем второй столбец, потому что минимум второй строки, 0, встречается среди столбцов, не лежащих в J, ровно один раз.

, а

4. Включаем третий столбец в J, так как в нем лежит строгий по не принадлежащим J столбцам минимум третьей строки.

, а

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

• 

• 

• 

6. Добавляем вычисленную константу ко всем столбцам J (они выделены жирным шрифтом).

7. Снова делаем множество J пустым, последовательно добавляя в него столбцы. Начинаем с первого, так как в нем и лежит минимум первой строки.

; а

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

; а

9. Множество J максимально: в остальных столбцах лежат по 2 минимума 3 и 4 строк, а значит, вне J строгих минимумов строк нет. Вычисляем константу.

• 

• 

10. Добавляем единицу ко столбцам из J:

.

11. Получаем решение путём вычитания первой строки исходной матрицы первую строку исходной:

Так как в разделе 3.1 было приведено другое решение, сделаем вывод, что строка, полученная добавлением одной и той же константы ко всем столбцам решения системы, так же будет решением этой системы [5].

1.6 Тропические рекуррентные последовательности

Рекуррентная последовательность – это последовательность, каждый следующий член которой выражается через предыдущие. – рекуррентная последовательность [20], удовлетворяющая вектору a, если для любого выполняется, что

(1.6)

где , – i-ая координата вектора.

Например, для чисел Фибоначчи , а значит, после его подстановки в формулу (1.6) получаем равенство .

Исходя из этого определим тропическую рекуррентную последовательность. Вектор , так как в тропической математике нулевым элементом является + . Удовлетворяющая ему последовательность [20] для выполнено тропическое линейное уравнение

(1.7)

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

Особенностью тропических рекуррентных последовательностей является то, что их члены определены неоднозначно (в отличие от классических, где однозначность имеется). Происходит это по следующей причине: допустим, для члена, определяемого, согласно (1.7), соотношением , справедливо, что . Тогда чтобы уравнение выполнялось, минимум также должен достигаться на первом мономе – в таком случае значение определяется однозначно. Но если , то есть минимум уже достигается на двух мономах, то может быть любым числом, большим или равным . Тогда множество решений задаётся лучом, однозначность теряется.

А теперь заметим, что рекуррентные последовательности можно записывать с помощью матриц. Объясняется это следующим образом: формула 1.7 – это тропическое линейное уравнение, задающее один член последовательности. Значит, для задания k членов необходимо решить k членов, то есть систему из k уравнений. Запишем их для n=2:

Систему линейных уравнений с 2 до k можно представить трёхдиагональной матрицей:

Аналогично, например, для матрица будет пятидиагональной.

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

Вывод

Приведённые в данном разделе определения – это необходимый минимум для дальнейших размышлений. Некоторые тонкости работы исследуемого алгоритма, алгоритма Д. Ю. Григорьева для решения систем тропических линейных уравнений, будут рассмотрены в сравнении с алгоритмом Гаусса, но основные идеи разобраны достаточно подробно. Также показана связь рассматриваемых в работе трёхдиагональных матриц с рекуррентными последовательностями.