Идемпотентные аналоги теорем отделимости и образующие идемпотентных полумодулей

• Автор: Сергеев, Сергей Николаевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 71 с. : ил.

1 Циклические проекторы и теоремы отделимости

1.1 Отделимость точки от полумодуля

1.2 Циклические проекторы: общий случай

1.3 Циклические проекторы И отделимость вКща^ х

2 Минимальные элементы и аналог теоремы Минковского

2.1 Образующие, базисы и крайние элементы

2.2 Базисы конечнопорожденных полумодулей

3 Определенные и клеточные замыкания матриц

3.1 Определенные замыкания матриц над Мщах,х

3.2 Клеточное разложение Ж” яу у

Список литературы

Список публикаций автора по теме диссертации

Актуальность темы
При решении'ряда задач в теории оптимизации (проблемы оптимизации на графах, теория оптимального управления), в физике (теория обобщенных решений уравнения Гамильтона-Якоби, низкотемпературная асимптотика в статистической физике) и в других областях явно или неявно используется линейность по отношению к операции “сложения” ©, которая является идем-потентной (а® о, = а). Этот общий принцип, сформулированный академиком В.П. Масловым [12, 13, 63], определяет развитие новой области математики, которая получила название идемпотентпная математика. Многие интересные результаты в этой области содержатся в сборнике статей [56], см. также обзоры [6, 55]. В практически важных задачах, для решения которых используется идемпотентная математика, роль идемпотентного сложения часто играет операция взятия минимума или максимума двух элементов, а основной алгебраической структурой является некоторое идемпотентное полуполе. Например, полуполе К.таХ)Х, определяемое как множество неотрицательных чисел R+, снабженное операцией идемпотентного сложения ф = max и обычного умножения О — х, или изоморфное ему полуполе ЖтаХ) определяемое как множество чисел М U {—оо} с операциями ® = max и 0 — +.
Основные приложения идемпотентной математики связаны с задачами оптимизации. Одно из первых таких приложений было описано в работах Б.А. Карре [27, 28], см. также [45, 71]. В этих работах замечено, что метод исключения Гаусса без выбора ведущего элемента можно рассматривать как прототип для оптимизационных алгоритмов на графах и применять для решения систем линейных уравнений над широким классом полуколец. Главный объект в этих работах — это ряд I ® А ф А2 ©..., где А — это некоторая квадратная матрица с элементами из идемпотентного полукольца, являющийся очевидным аналогом операции (I — А)-1 и называемый алгебраическим замыканием А. Эти идеи получили свое дальнейшее развитие в работах Г.Л. Литвинова, В.П. Маслова и др. [57, 58, 60], см. также [61],[62] и [73], посвященных универсальным алгоритмам идемпотентной математики и идемпотентному интервальному анализу.

Другие задачи линейной алгебры над идемпотентными полуполями, в частности, решение систем вида Ах — Ъ и нахождение собственных значений и собственных векторов Ах = Аж, возникают в связи с составлением расписаний, синхронизацией производства и сетями Петри [23, 33, 49].Такие приложения возникают и в физике. В качестве примера, рассмотрим модель Френкеля-Конторовой. В простейшем варианте это одномерная цепочка атомов, находящихся в периодическом потенциале. При статическом описании этой модели основная задача заключается в нахождении основных состояний и значений параметров, которые характеризуют эти состояния [21, 22]. Алгоритм для нахождения основных состояний был предложен У. Чоу и Р.Б. Гриффитсом [30].которые использовали для этого собственные векторы и собственные значения некоторого интегрального оператора над идемпотентным полуполем. Метод Чоу и Гриффитса был использован в ряде физических задач [66, 67, 76]. Близкие по своему математическому описанию задачи возникают и в математической экономике, а именно, в задачах динамической оптимизации с бесконечным горизонтом, где требуется найти траектории, приносящие максимальный доход [14, 53, 77].
В связи с этими практическими приложениями, возникает интерес к теории идемпотентных полуколец и полуполей, и к теории полумодулей (т.е. “пространств”) над этими полукольцами. Значительная часть этих результатов собрана в монографии Дж. Голана [44].Отметим, что линейная алгебра над идемпотентными полукольцами (и над полукольцами вообще) отличается тем, что в ней есть много способов определить, что такое линейная независимость, ранг и определитель, и в связи с этим возникает много новых нетривиальных задач, см. [23, 26, 33, 46, 48, 80].
Идемпотентный анализ был развит в работах В.П. Маслова и его сотрудников [4], [5], [11]-[14], [53], [63]-[65], см. также [36] и [37].Основной объект идем-потентного анализа В.П. Маслова — это полумодуль полунепрерывных функций на некотором топологическом пространстве, принимающих значение в некотором идемпотентном полукольце. В цитированных работах была развита теория идемпотентных мер, интегралов, обобщенных функций и идем-потентно линейных операторов). Эти результаты были использованы для построения обобщенных решений уравнения Гамильтона-Якоби-Беллмана, а также в упоминавшихся выше задачах динамической оптимизации с бесконечным горизонтом. В работах Г.Л. Литвинова, В.П. Маслова и Г.В. Шпиза [7, 8, 9] развит алгебраический подход к идемпотентному анализу. Этот подход отличается тем, что в нем основные топологические понятия и результаты моделируются на чисто алгебраическом уровне, с привлечением результатов теории решеток и решеточно упорядоченных групп [1, 18].
Большую роль в развитии идемпотентной математики играет эвристиче-

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

_ lai, если у = сг(г);
1 0, если у ф сг(г).
Таким образом, любая обратимая матрица существенно не отличается от перестановочной и роль обратимых матриц в идемпотентной матричной алгебре невелика. Более существенную роль играет алгебраическое замыкание матрицы А:
А* = I® А® А2 ® (3.3)
Степени матриц над полуполем Rmax = (Ж U {—оо},® = тах, © - +)
(которое изоморфно КтПу у) и их алгебраические замыкания играют важную роль в оптимизации на графах. Действительно, поставим матрице A G Ж”" в соответствие граф с п узлами и припишем каждому ребру (г, у) этого графа вес Aij. Тогда элемент (Arn)jj матрицы Ат является максимальным весом всех путей длины т, соединяющих i и у. Элемент (Ат)ц является максимальным весом всех циклических путей, то есть циклов длины т, которые проходят через г. Другими словами, это максимальный вес циклических перестановок т, таких что г & К(т) и | К(т) |= ш. Нетрудно заметить, что (A*)i3- при г т£ j является максимальным весом всех путей соединяющих г и у. Путь, соединяющий г и j с весом равным (А*)^ называется оптимальным.
Следующее предложение, связывающее вопрос существования алгебраического замыкания матрицы, т.е. сходимости ряда (3.3), с максимальным циклическим средним было впервые получено в работе Б.А. Карре [27].
Предложение 3.1.3 Алгебраическое замыкание матрицы А существует тогда и только тогда, когда А (А) < 1. В этом случае А* — 1®А©...® An_1.
Напомним, что в идемпотентных полукольцах алгебраические замыкания обладают следующими свойствами:
(.А*)1 = А* V* > О, (А*)* = А*. (3.4)
В частности, отсюда (при г = 2) следует, что неравенство А^-АД. < А*к выполняется при всех г,у и к.
Дадим следующее важное определение [23].
Определение 3.1.4 Пусть максимальное циклическое среднее А(А) квадратной матрицы А равно 1. Циклическая перестановка с максимальным циклическим средним называется критической. Подграф графа, соответствующего А, состоящий из всех вершин и ребер, принадлежащих критическим циклам, называется критическим графом матрицы А и обозначается через Gc(A).