Автоматика и телемеханика, № 5, 2019

Обзоры

(Институт проблем передачи информации им. А.А. Харкевича РАН, Москва,

Институт радиотехники и электроники им. В.А. Котельникова РАН, Москва),

Н.А. КУЗНЕЦОВ, академик РАН (kuznetsov@cplire.ru)

(Институт радиотехники и электроники им. В.А. Котельникова РАН, Москва,

Московский физико-технический институт (ГУ)),

П.Ю. ЧЕБОТАРЕВ, д-р физ.-мат. наук (pavel4e@gmail.com)

(Институт проблем управления им. В.А. Трапезникова РАН, Москва,

Институт радиотехники и электроники им. В.А. Котельникова РАН, Москва,

Московский физико-технический институт (ГУ))

КОНСЕНСУС В АСИНХРОННЫХ МУЛЬТИАГЕНТНЫХ СИСТЕМАХ

II. МЕТОД СОВМЕСТНОГО СПЕКТРАЛЬНОГО РАДИУСА¹

Описываются математические методы анализа устойчивости, стабили-

зируемости и консенсуса линейных мультиагентных систем с дискретным

временем. В основе этих методов лежит идея привлечения понятия сов-

местного/обобщенного спектрального радиуса наборов матриц для ана-

лиза скорости сходимости матричных произведений с сомножителями из

множеств матриц со специальными свойствами. Работа продолжает об-

зор авторов “Консенсус в асинхронных мультиагентных системах”, первая

часть которого опубликована в [1].

Ключевые слова: асинхронные мультиагентные системы, консенсус,

устойчивость, стабилизируемость, марковские системы, матричные про-

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

DOI: 10.1134/S0005231019050015

1. Введение

Математические методы анализа мультиагентных систем в настоящее вре-

мя вряд ли можно считать сложившимися ввиду большого разнообразия си-

стем, объединенных термином “мультиагентные”, а также из-за сложности

анализа их функционирования. Уже первые попытки анализа такого рода

систем показали (см., например, [2], а также библиографию в [3-5]), что даже

в линейном случае классические методы анализа оказываются недостаточно

эффективными. В данной части обзора ограничиваемся описанием подходов,

развитых в последние годы для анализа устойчивости и стабилизируемости

¹ Работа поддержана грантом Российского научного фонда 16-11-00063, предоставлен-

ным ИРЭ им. В.А. Котельникова РАН. Работа третьего автора также частично поддержана

программой президиума РАН №30 “Теория и технологии многоуровневого децентрализо-

ванного группового управления в условиях конфликта и кооперации”.

лишь одного класса мультиагентных систем — так называемых линейных

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

ленные дискретные моменты времени.

C тех пор как проблематика асинхронности мультиагентных систем при-

влекла внимание исследователей, возникло множество разнообразных подхо-

дов к их исследованию, даже кратко описать которые в настоящей работе

не представляется возможным. В частности, начиная с 60-х гг. прошлого

века среди специалистов по теории автоматического управления достаточ-

но популярной стала трактовка асинхронных систем с дискретным временем

как систем в непрерывном времени с пилообразными запаздываниями (см.,

например, [6, 7] и библиографию в этих работах). В первой части настоя-

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

решении задач консенсуса. Отметим, что при анализе дискретных систем,

возникающих в компьютерных сетях, сетях передачи данных и т.п., в послед-

нее время в публикациях промежуточный этап (к которому можно отнести

выписывание тех или иных уравнений динамики, в частности уравнений с

запаздыванием) между прикладной постановкой и конечной математической

моделью все чаще опускается.

Частично по этой причине оставляем без внимания множество других спо-

собов перехода к асинхронным системам и ограничиваемся анализом той за-

дачи, к которой в конечном счете сводятся многие вопросы теории устойчи-

вости, стабилизируемости и консенсуса линейных мультиагентных систем, —

задачи о сходимости произведений матриц, описывающих поведение агентов

в последовательные промежутки времени. В последние годы данная пробле-

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

понятия совместного спектрального радиуса набора матриц (см., например,

библиографию в [8]).

В качестве достаточно показательного примера эффектов, возникающих

при асинхронном взаимодействии различных объектов, в разделе 2 рассмат-

ривается модель треугольного (валютного) арбитража в экономике, при ана-

лизе которой применение идеологии мультиагентности приводит к достаточ-

но неожиданным с экономической точки зрения выводам. Изложение этого

раздела следует работе [9].

В разделе 3 описывается наиболее простой тип мультиагентных систем,

выделенный в 70-80-х гг. прошлого века как способ описания функциониро-

вания многопроцессорных систем и систем управления с асинхронно взаи-

модействующими компонентами, см., например, [4, 5]. Рассматриваются мно-

гокомпонентные (мультиагентные) системы, компоненты которых (агенты)

подвергаются коррекции в дискретные моменты времени. Предполагается,

что в общем случае моменты коррекции различных компонент не совпадают

друг с другом. Такие системы называются рассинхронизованными. Типич-

ным примером являются многопроцессорные системы и вычислительные си-

стемы с асинхронной организацией вычислений. Возникающие при описании

динамики таких систем разностные уравнения описывают также поведение

различного рода цифровых сетей. Аналогичными уравнениями описывается

функционирование многоконтурных систем управления динамическими объ-

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

ся объектами. Подобные математические модели находят применение также

при исследовании информационного взаимодействия в живых организмах и

для описания нейроподобных сетей [10].

При исследовании проблемы консенсуса в мультиагентных системах важ-

ным является вопрос о том, каким образом моменты коррекции компонент

могут влиять на устойчивость системы. Анализируются три принципиаль-

но различающиеся как по методам исследования, так и по получающимся

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

ты системы подвергаются коррекции периодически с несовпадающими, вооб-

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

коррекции каждой компоненты представляют взаимно независимые потоки

случайных событий. Третья ситуация относится к случаю, когда никакой ин-

формацией о закономерностях, описывающих моменты коррекции компонент,

не располагаем. Полученные результаты показывают, что способ рассинхро-

низации может качественно влиять на динамику системы. В ряде случаев

рассинхронизованные системы обладают свойствами, которыми не обладают

синхронизованные системы.

Одной из отличительных черт рассинхронизованных систем является то,

что каждая компонента (агент) такой системы в каждый момент времени

либо не меняет свое состояние, либо же меняет его по заранее заданному ли-

нейному закону. В разделе 4 рассматривается более общая ситуация, когда

компоненты системы (агенты) в каждый момент времени могут недетермини-

рованно изменять свое состояние в соответствии с некоторым конечным или

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

ные системы были рассмотрены в [11]. Основной результат данного раздела,

теорема 6, утверждает, что вопрос об устойчивости подобного рода мульти-

агентных систем с недетерминированно функционирующими агентами, опи-

сываемыми линейными “положительными” законами, может быть конструк-

тивно разрешен. Аналогичный результат устанавливается в теореме 8 для

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

параллельных и последовательных соединений “элементарных” агентов.

2. Валютный арбитраж

В экономике под арбитражем понимается “инвестиционная стратегия,

не требующая дополнительных вложений и гарантирующая выигрыш при

непредвиденных обстоятельствах” [12]. При этом вся система арбитража яв-

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

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

та, по которой они продаются. Отличие арбитражных операций от спекуля-

тивных в том, что в них отсутствуют или низки капитал и риски. Прибыль

при арбитраже достигается за счет разницы фактических курсов, а не за

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

ниях курсов. Детальное описание теории арбитража можно найти, например,

в [13, 14]. Один из сценариев валютного арбитража c реальными ценами спро-

са и предложения описан в примере 5.3 из [15].

В экономической и финансовой литературе постулируется, что исполь-

зование прибыльных арбитражных возможностей приводит к уничтоже-

нию ценовых несоответствий между “идентичными” товарами и акти-

вами. Этот постулат фактически утверждает, что арбитражные операции

являются самостабилизирующимися, из него вытекает также “закон одной

цены”, объясняющий механизм образования валютных обменных курсов за

счет равенства покупательных способностей [16]. Основой современной тео-

рии финансов является условие безарбитражности (отсутствия возможности

прибыльного арбитража), содержащееся в теоремах Модильяни—Миллера о

структуре корпоративного капитала, в моделях ценообразования опционов

Блэка—Шоулза и арбитражного ценообразования активов [17].

В случае трех валют одной арбитражной операции достаточно, чтобы ис-

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

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

периодическими или экспоненциально растущими [18], не приводящими в

результате к получению безарбитражных ансамблей или наборов обменных

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

битража. Этот факт опровергает гипотезу о самостабилизируемости ар-

битражных операций.

В настоящем разделе показывается, что в случае d ≥ 5, где d — это число

не только валют, но и участников арбитражных операций, ситуация в опре-

деленном смысле еще хуже — здесь возможен сверхэкспоненциальный рост

обменных курсов!

2.1. Постановка задачи

Рассмотрим валютный рынок, в который вовлечены d различных валют,

характеризующихся курсами обмена r_ij валюты i на валюту j = i. Естествен-

но, величина r_ji обмена валюты j на валюту i обратна величине r_ij, т.е. r_ji =

= 1/r_ij (для упрощения теоретического анализа маржа при обмене не учи-

тывается).

Обменные курсы изменяются с течением времени в зависимости от состо-

яния рынка и соотношения обменных курсов. Например, если в какой-то мо-

мент времени “продавец” валюты i замечает, что обмен валюты i на валюту j

через промежуточную валюту k приносит больший выигрыш, т.е.

r_ik r_kj > r_ij, i = j, k = i,j,

то он может установить новый обменный курс валюты i на валюту j:

rij,нов = r_ik r_kj.

В общем случае будем считать, что изменение обменных курсов совершается

в соответствии с законом

rij,нов = max {r_ik r_kj, r_ij} ,

rji,нов = 1/rij,нов,

причем одновременно коррекции может подвергаться только одна упорядо-

ченная пара валют (i, j).

Введя вспомогательные величины

a_ij = log r_ij,

можно перейти от описанной выше “мультипликативной” постановки задачи

об арбитраже к “аддитивной”, которая в этом случае формулируется следую-

щим образом: имеется кососимметрическая d × d матрица A = (a_ij ) и для

тройки попарно различных индексов (i, j, k), i = j, k = i, j, производится пе-

ресчет элементов a_ij и a_ji (арбитраж матрицы A) по следующему правилу:

(1)

aij,нов = max {a_ik + a_kj, a_ij} ,

aji,нов = -aij,нов.

Тройку индексов ω = (i, j, k), i = j, k = i, j, будем называть правилом арбит-

ража.

Формулы (1) показывают, что при пересчете пары (a_ij , a_ji) независимо от

сценария арбитража элемент a_ij либо не меняет значения (тогда с матрицей A

ничего не происходит), либо же элемент a_ij может изменить значение только

следующим образом:

aij,нов = a_ik + a_kj

и при этом симметричный элемент a_ji меняет значение в соответствии со

вторым уравнением в (1), что равносильно

aji,нов = a_jk + a_ki,

причем ровно один из этих двух элементов увеличивается. Отсюда следует,

что как при max-постановке задачи, так и при ее линейной переформулировке

достаточно ограничиться анализом динамики пар (a_ij , a_ji) взаимно симмет-

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

сценарии внутрипарных пересчетов при max-постановке задачи.

2.2. Асинхронные матричные произведения

Введем в пространстве кососимметрических d × d матриц базис {e_ij },

1 ≤ i < j ≤ d, перенумеровав построчно наддиагональные элементы таких

матриц и взяв в качестве e_ij кососимметрическую матрицу, элементы с ин-

дексами (i, j) и (j, i) которой равны 1 и -1 соответственно, а остальные —

нулю. Тогда каждая матрица A = (a_ij ) в этом базисе будет представляться

некоторым вектором-столбцом

x = {a₁₂,... ,a1d,a23 ...,a2d,... ,ad-1,d}^T

в пространстве Rd(d-1)/2, где верхний индекс T означает транспонирование

вектора. При этом вычисление очередного вектора x_нов по старому x будет

определяться выражением

(2)

x_нов = B_ω

где матрица B_ω задается правилом арбитража ω = (i, j, k):

⎧

(

)

⎪

I-e_ij eTij +eTki -e^T

при k < i < j,

⎪

⎨

(

)

B_ω =

I-e_ij eTij -eTik -e^T

при i < k < j,

⎪

(

)

^⎩I - e_ij eTij - eTik + e^T

при i < j < k.

Способ построения матриц B_ω близок к способу построения так называе-

мых помесей матриц при исследовании рассинхронизованных систем [5]. От-

личие заключается в том, что при вычислении помесей матриц в [5] пересчет

каждого вектора в (2) осуществляется единственным способом. В данном же

случае пересчет каждого вектора x может производиться различными спо-

собами, поскольку множество правил пересчета (i, j, ·), у которых одинаковы

первые два индекса i и j, может содержать более одного элемента.

Для анализа сходимости полученных матричных произведений приведем

следующие примеры.

Пример 1. Рассмотрим набор правил арбитража ω₁ = (1,4,2), ω₂ =

= (1, 2, 3), ω₃ = (3, 4, 1), ω₄ = (1, 4, 2), ω₅ = (1, 3, 4), ω₆ = (2, 4, 3), ω₇ = (2, 3, 1),

ω₈ = (3,4,2), ω₉ = (2,4,1), ω₁₀ = (1,3,4), ω₁₁ = (3,4,2), ω₁₂ = (1,4,3), ω₁₃ =

= (2, 3, 4), ω₁₄ = (1, 3, 2), ω₁₅ = (1, 2, 4), ω₁₆ = (1, 4, 3) и продолжим его по

периодичности. Последовательность произведений соответствующих мат-

риц B_ω

(3)

H_n = BωnHn-1,

H₀

= I, n = 1,2,...,

оказывается периодической с периодом 32, не сходящейся к какому-либо пре-

делу.

Пример 2. Рассмотрим набор правил арбитража ω₁ = (1,4,3), ω₂ =

= (3, 4, 1), ω₃ = (3, 4, 2), ω₄ = (1, 4, 2), ω₅ = (1, 2, 4), ω₆ = (2, 3, 1), ω₇ = (1, 3, 2),

ω₈ = (2,4,3), ω₉ = (1,3,4), ω₁₀ = (2,4,1), ω₁₁ = (1,2,3), ω₁₂ = (2,3,4) и про-

должим его по периодичности. В этом случае последовательность произве-

дений (3) соответствующих матриц B_ω оказывается расходящейся, причем

нормы матриц H_n растут с подлинейной скоростью, т.е. не быстрее, чем cn,

где c — некоторая константа, а n — количество сомножителей B_ω в произве-

дении.

Пример 3. В случае d = 5 рассмотрим последовательность правил ар-

битража ω₁ = (4, 5, 3), ω₂ = (1, 2, 4), ω₃ = (4, 5, 1), ω₄ = (3, 4, 2), ω₅ = (2, 4, 5),

ω₆ = (2,3,1), ω₇ = (1,4,3) и продолжим ее по периодичности. Непосредствен-

ная проверка показывает, что спектральный радиус ρ(H₇) матрицы

H₇ = B₍₁₄₃₎B₍₂₃₁₎B₍₂₄₅₎B₍₃₄₂₎B₍₄₅₁₎B₍₁₂₄₎B₍₄₅₃₎

строго больше 1:

√

ρ(H₇) =

≃ 1,618.

Тогда последовательность норм ∥H_n∥ последовательных арбитражных опе-

раций будет расходиться с экспоненциальной скоростью:

(

)n/7

(

√

√ )n/7

(4)

≤ ∥H_n∥ ≤ C

где c, C — некоторые положительные константы.

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

участников, является частным случаем правил арбитража для пяти участни-

ков. Поэтому в случае d = 5 могут наблюдаться как последовательности мат-

риц (векторов), нормы произведений которых растут линейно, так и после-

довательности матриц (векторов), изменяющиеся периодически. При d > 5

происходит “наследование неустойчивости”, имеющейся в случаях d = 4, 5: в

этом случае наблюдаются все описанные типы поведения матричных произ-

ведений, а также поведения соответствующих последовательностей векторов

состояния — периодичность, рост с линейной скоростью, рост с экспоненци-

альной скоростью.

При возвращении от “искусственных” величин a_ij к истинным обменным

курсам r_ij = eaij получаем достаточно необычный вывод: в случае d = 4 об-

менные курсы могут меняться периодически или расти экспоненциально, в

случае же d ≥ 5 обменные курсы могут меняться периодически, расти экспо-

ненциально, а также расти со сверхэкспоненциальной скоростью — по повтор-

но-показательному закону. Например, в случае d = 5 из формулы (4) следует,

что

ecqn ≤ ∥r_n∥ ≤

Cqⁿ,

(

√

)1/7

где q =

≃ 1,071, а r_n = {r₁₂, . . . , r1d, r₂₃, . . . , r2d, . . . , rd-1,d}^T — это

вектор обменных курсов в момент времени n.

2.3. Заключительное замечание

Итак, в “мире пяти валют” гипотеза о самостабилизируемости арбит-

ражных операций не верна: помимо наследования периодичности или экспо-

ненциального роста, имеющих место в случае четырех валют, арбитражные

последовательности могут иметь новую форму поведения — сверхэкспонен-

циальный (повторно-показательный) рост. Все эти типы неустойчивости “на-

следуются” и в случаях большего числа валют. Характер поведения арбит-

ражных последовательностей зависит от числа валют: периодичность или

экспоненциальное поведение может возникнуть при переходе от трех к четы-

рем валютам, а повторно-показательная неустойчивость — при превышении

четырех валют.

3. Рассинхронизованные мультиагентные системы

Описанная в разделе 2 модель валютного арбитража представляет один

из примеров функционирования мультиагентных (многокомпонентных) си-

стем, в которых агенты (компоненты) изменяют свои состояния в дискрет-

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

случае моменты коррекции различных компонент не совпадают друг с дру-

гом. Такие системы называются рассинхронизованными. Помимо описанно-

го в разделе 2 экономического примера, типичными примерами являются

также многопроцессорные системы и вычислительные системы с асинхрон-

ной организацией вычислений. Аналогично описывается функционирование

многоконтурных систем управления динамическими объектами, т.е. систем

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

Системы управления с элементами дискретного типа являются одним из

классических объектов анализа теории управления (см., например, [3]). Наи-

более трудным этот анализ оказывается в случае, когда отдельные элементы

или подсистемы какой-либо системы подвергаются коррекции несинхронно

друг с другом. Интерес к таким системам возник еще в 50-х гг. XX в. и зна-

чительно возрос в 70-90-х гг. в связи с развитием многопроцессорных вычис-

лительных комплексов [4, 19]. Оказалось, что классические математические

методы плохо приспособлены для анализа рассинхронизованных систем. Это

потребовало развития новых методов и новых подходов [4, 5, 20].

3.1. Основные определения

Перейдем к описанию одной из простейших моделей асинхронного взаимо-

действия мультиагентных линейных систем. Рассмотрим систему W , состоя-

щую из компонент (элементов, частей, агентов) W₁, . . . , W_N . Пусть состояние

компоненты W_i описывается вектором x_i ∈ Rni , n_i ≥ 1, и изменяется в неко-

торые дискретные моменты в соответствии с правилом

(5)

xi,нов = ai1x1,стар + ai2x2,стар + ··· + a_iNxN,стар + f_i,

где aij — матрицы соответствующих размерностей, а fi — вектор внеш-

них воздействий на компоненту W_i. Обозначим через . . . < Ti0 < Ti1 < · · ·

··· < T_in < ... моменты изменения состояния компоненты W_i, см. рис 1,а.

Тогда изменение переменного состояния x_i(t) компоненты W_i может быть

описано уравнением

x_i(Tin+1) = ai1x₁(T_in) + ai2x₂(T_in) + ··· + a_iNx_N(T_in) + f_i(T_in

(6)

где предполагается постоянство функции x_i(t) на каждом интервале T_in <

< t ≤ Tin+1. Из физических соображений естественно считать, что T_in → ∞

при n → ∞. Моменты времени T_in называются моментами коррекции компо-

ненты W_i.

Если все компоненты подвергаются коррекции одновременно, например,

под воздействием единого синхронизирующего сигнала — см. рис. 1,б, т.е.

T1n = T2n = ··· = T_Nn,

-∞ < n < ∞,

то систему W назовем синхронизованной, а в противном случае — рассинхро-

низованной.

f₁

W₁

x₁

f₂

x₂

W₂

x₂

W₂

x =

x_N

f_N

W_N

Общая система

Cинхронизованная система

Рис. 1. Пример мультиагентных систем.

W₁

x₁

x₂

W₂

x₂

W₂

x_{2, нов}

x =

x_N

W_N

Рассинхронизация по фазе

Рассинхронизация по частоте

Рис. 2. Фазочастотно рассинхронизованные мультиагентные системы.

Например, система рассинхронизована, если ее моменты коррекции опре-

деляются соотношениями

(7)

T_in = τ_in + ϕ_i

i = 1,...,N, -∞ < n < ∞,

где не все τ_i или ϕ_i совпадают между собой. Такие системы называют рас-

синхронизованными по фазе (в равенствах (7) не все величины ϕ_i совпадают

между собой) и частоте (в равенствах (7) не все величины τ_i совпадают

между собой) [21-24], см. рис. 2.

В некоторых случаях естественно предполагать, что компоненты систе-

мы W подвергаются коррекции в случайные моменты времени, тогда для

анализа динамики системы W целесообразно привлечь вероятностные ме-

тоды. Наконец, возможна ситуация, когда информация о закономерностях

коррекции компонент системы W отсутствует. Эти ситуации (если интере-

суются вопросом об устойчивости системы W ) естественно ведут к понятию

абсолютной устойчивости (ср. [25]) системы W в том или ином классе рас-

синхронизаций.

В ряде ситуаций более удобна не непрерывная (6), а дискретная модель

функционирования рассинхронизованной системы (ср. [20]). В общем слу-

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

стемы W ; пусть ω ⊆ {1, . . . , N} — множество их номеров. Обозначим че-

рез A_ω блочную матрицу, получающуюся из блочной матрицы A = (a_ij ) заме-

ной строк с номерами i ∈ ω соответствующими строками единичной блочной

матрицы I.

Пример 4. В случае, когда множество ω состоит из одного элемента, на-

пример ω = {i}, матрица A_ω имеет вид

⎛

⎞

···

⎜

···

⎟

⎜

⎟

⎜

···

⎟

A_ω =

⎜

⎟.

⎜

ai1

ai2

··· a_ii

··· a_iN

⎟

⎝

⎠

···

В случае, когда множество ω состоит из нескольких элементов, например

ω = {2,i}, матрица A_ω имеет вид

⎛

⎞

···

⎜

a₂₁

a₂₂

··· a2i

··· a2N

⎟

⎜

⎟

⎜

···

⎟

A_ω =

⎜

⎟.

⎜

ai1

ai2

··· a_ii

··· a_iN

⎟

⎝

⎠

···

Обозначим через X пространство состояний системы W , т.е. множество

векторов x = {x₁, . . . , x_N }, где x_i ∈ Rni . Через X_ω обозначим линейное под-

пространство пространства X, состоящее из тех векторов x = {x₁, . . . , x_N },

для которых x_i = 0 при i ∈ ω. Тогда изменение состояния системы W в общем

случае описывается векторным равенством

x_нов = A_ωx_стар + f_ω,

где f_ω = {f₁, . . . , f_N } ∈ X_ω.

Пусть . . . < T₀ < T₁ < · · · < T_n < . . . — все моменты коррекции всех ком-

понент системы W . Обозначим через x(n) вектор состояния системы в мо-

мент T_n, а через ω(n) — множество номеров подвергающихся в этот момент

коррекции компонент. Тогда получаем следующее уравнение динамики муль-

тиагентной системы W :

x(n + 1) = Aω(n)x(n) + f(n),

f (n) ∈ Xω(n).

Синхронизованной системе W отвечает ситуация, когда ω(n) ≡ {1, . . . , N};

динамика такой системы описывается уравнением

x(n + 1) = Ax(n) + f(n).

Предположим теперь, что внешние воздействия на систему W отсутствуют.

В этом случае x = 0 оказывается положением равновесия системы W , и есте-

ственно возникает вопрос о его устойчивости. Это — центральный вопрос мно-

гочисленных публикаций, результаты которых отражены в монографии [5].

3.2. Рассинхронизация по фазе и частоте

Пусть в равенствах (7) все величины τ_i совпадают между собой. В этом

случае

(8)

T_in = τ + ϕ_i

i = 1,...,N, -∞ < n < ∞,

и система W называется рассинхронизованной по фазе [21-24, 26]. Отличи-

тельной чертой рассинхронизованной по фазе системы W является тот факт,

что описывающее ее динамику однородное уравнение

(9)

x(n + 1) = Aω(n)

x(n)

оказывается периодическим по переменной n с периодом N. Следовательно,

как хорошо известно (см., например, [3]), вопрос о его устойчивости решается

по расположению собственных значений матрицы

(10)

C =Aω(N)Aω(N-1)···Aω(1).

В том случае, когда величины фазовых рассогласований ϕ_i в (8) удовлетво-

ряют условию

0≤ϕ₁ <ϕ₂ <...<ϕ_N <τ,

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

совпадают с корнями уравнения

⎛

⎞

a₁₁ - λ a₁₂

···

a1N

⎜

λa₂₁

a₂₂ - λ

···

a2N

⎟

det⎝

⎠ = 0.

···

λaN1

λaN2

··· a_NN -λ

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

близка к процедуре метода Гаусса - Зейделя решения уравнения x = Ax.

Матрица (10) в общем случае отлична от матрицы A. Важно подчерк-

нуть, что каждая из них может быть устойчивой или неустойчивой (в смысле

устойчивости соответствующих систем W ) независимо от другой. Подчерк-

нем также, что величины фазовых рассогласований ϕ_i не влияют на вид мат-

рицы C — существен лишь их взаимный порядок.

Итак, один из фактов, который необходимо учитывать при анализе рас-

синхронизованных систем, заключается в том, что сколь угодно малая рас-

синхронизация изначально синхронизованной системы может привести к ка-

чественному изменению ее динамики — сделать устойчивую систему неустой-

чивой и наоборот.

Если система (9) рассинхронизована по фазе и частоте, т.е. не все вели-

чины τ_i в (7) совпадают между собой, то анализ ее устойчивости становится

чрезвычайно трудной задачей. Какие-либо эффективные критерии устойчи-

вости таких систем для общего случая авторам не известны. Первые резуль-

таты, касающиеся устойчивости двухкомпонентных систем W , были получе-

ны А.Ф. Клепцыным [27]. Один из возможных путей анализа устойчивости

многокомпонентных систем, рассинхронизованных по частоте и фазе, заклю-

чается в следующем. Разобьем числовую ось на интервалы равной длины,

например [nH, (n + 1)H), где H > 0, -∞ < n < ∞. Обозначим через D_n мат-

рицу перехода от состояния системы W в момент nH к состоянию системы

в момент (n + 1)H. В рассматриваемом случае различных матриц D_n может

быть лишь конечное число: F₁, . . . , F_L. Обозначим через f_lk число матриц F_l

среди матриц D_n (n = 1, . . . , k). Тогда при каждом l = 1, . . . , L существует и

конечна средняя частота

f_lk

p_l = lim

k→∞ k

встречи матриц F_l в последовательности {D_n}. Вид матриц F_l и значения

частот p_l в случае несоизмеримых τ₁, . . . , τ_N могут быть вычислены эффек-

тивно [24] с использованием геометрических построений, основанных на ре-

зультатах эргодической теории (см., например, [28]).

Теорема 1. Пусть

∥F₁∥p1 ∥F₂∥p2 · · · ∥F_L∥pL < 1

и периоды τ₁,... ,τ_N рассинхронизованной по фазе и частоте системы W

несоизмеримы. Тогда система W асимптотически устойчива.

3.3. Стохастические мультиагентные системы

В ряде ситуаций более адекватна модель со случайными моментами взаи-

модействия агентов. Рассмотрим мультиагентную систему W с многомерны-

ми в общем случае состояниями агентов (компонент). Будем предполагать,

что при каждом i = 1, . . . , N последовательность {T_in} моментов изменения

состояния соответствующего агента является простейшим потоком событий

с интенсивностью λ_i, причем эти потоки при разных i независимы.

Обозначим через D(t) случайную матрицу перехода от состояния системы

в нулевой момент времени к состоянию в момент времени t. Она определя-

ется равенством D(t) = A{ik } · · · A{i₁}, где i1, . . . , ik — номера агентов, изме-

няющих свое состояние на интервале (0, 1]. Согласно эргодической теореме

Фюрстенберга - Кестена [29] существует неслучайное число μ, для которого

с вероятностью 1 выполнено равенство

ln ∥D(t)∥

μ = lim

t→∞

Число μ называют показателем Ляпунова системы W . Систему будем назы-

вать L-устойчивой, если выполнено неравенство μ < 0.

Укажем три метода оценки показателя Ляпунова и проверки L-устойчиво-

сти. Первый из них состоит в непосредственном компьютерном моделирова-

нии рассинхронизованной системы (точнее, ее аналога с дискретным време-

нем). Второй метод, значительно менее трудоемкий, основан на следующей

алгебраической конструкции. Введем в рассмотрение матрицу

∑_N

λ_iA⊗2{i}

i=1

∑_N

λ_i

i=1

где A⊗2{i} обозначает кронекеров квадрат [30] матрицы A_{i}. Тогда, как пока-

зано, например, в [5], имеет место следующая оценка:

∑

μ≤

(ln ρ(Q))

λ_i.

i=1

Следовательно, достаточным условием L-устойчивости системы W является

неравенство ρ(Q) < 1. Когда это условие выполнено, удается оценить ско-

рость сходимости ∥D(t)∥ к нулю по вероятности.

Теорема 2. Пусть ρ(Q) ≤ σ < 1. Тогда существует такое число q, что

при всех t, ε > 0 выполняется неравенство

(

)

∑

P{∥D(t)∥ > ε} < qε-2 exp

- λ_i(1 - σ)t

i=1

Вычислительные эксперименты показывают, что оценка, которую дает

теорема 2, не очень точна. Однако она гораздо точнее тривиальной оцен-

∑_N

ки μ ≤

λ_i ln ∥A_{i}∥, не учитывающей геометрию системы. С помощью

i=1

численных экспериментов были обнаружены также эффекты приобретения

и потери устойчивости при переходе от синхронизованной (или рассинхрони-

зованной по фазе) мультиагентной системы к стохастически рассинхронизо-

ванной.

Третий метод проверки L-устойчивости и оценки показателя Ляпунова

относится к ситуации, когда удается более точно изучить геометрические ха-

рактеристики динамики системы. Он изложен в монографии [5].

3.4. Абсолютная устойчивость мультиагентных систем

Пусть при анализе устойчивости мультиагентной системы число агентов,

изменяющих свое состояние в каждый момент времени, заранее неизвестно,

как неизвестна и закономерность чередования моментов изменения состоя-

ния (коррекции) различных агентов. Тогда естественно (ср. [25]) приходим

к понятию абсолютной устойчивости мультиагентных систем. Отметим, что

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

абсолютной устойчивости нетривиальна уже в линейном случае.

Формальное определение дадим в терминах уравнения (9). Обозначим че-

рез P(A) множество всех матриц A_ω, где ω ⊆ {1, . . . , N}. Пусть F — непустое

подмножество множества P(A). Уравнение (9) (или мультиагентную систе-

му W ) назовем абсолютно устойчивым в классе взаимодействий F, если все

его решения, отвечающие различным последовательностям матриц Aω(n) ∈ F

и различным начальным условиям, ограничены при n ≥ 0.

Скажем, что последовательность матриц Aω(n) ∈ F регулярна, если каж-

дое число i = 1, . . . , N принадлежит бесконечному количеству множеств ω(n)

(n ≥ 0).

Уравнение (9) (или мультиагентную систему W ) назовем абсолютно

r-асимптотически устойчивым в классе взаимодействий F, если все его ре-

шения, отвечающие различным регулярным последовательностям матриц

Aω(n) ∈ F и различным начальным условиям, стремятся к нулю n → ∞.

Ясно, что ставить вопрос об абсолютной r-асимптотической устойчивости

уравнения (9) имеет смысл лишь тогда, когда существует хотя бы одна ре-

гулярная последовательность матриц Aω(n) ∈ F. В связи с этим множество

F ⊆ P(A), содержащее хотя бы один набор матриц Aω1,...,Aωk ∈ F, для ко-

торых

ω₁ ∪ ··· ∪ ω_k = {1,... ,N},

назовем порождающим.

Регулярные последовательности матриц Aω(n) ∈ F существуют только в

том случае, когда множество F порождающее. Примером порождающего

множества является множество P^-k(A) (при некотором k = 1, . . . , N), состоя-

щее из всех матриц A_ω, у которых множество ω содержит не более k различ-

ных элементов.

В случае, когда матрица A системы W со скалярными состояниями ком-

понент неотрицательна или симметрична, достаточные условия абсолютной

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

фию в [5]). Приведем здесь более общее утверждение о необходимых и до-

статочных условиях абсолютной устойчивости таких систем.

Теорема 3. Пусть матрица A = (a_ij) мультиагентной системы W

скалярная и симметрическая. Система W абсолютно r-асимптотически

устойчива в классе взаимодействий P^-k(A) тогда и только тогда, когда все

собственные значения матрицы A меньше 1, а собственные значения каж-

дой ее главной диагональной подматрицы порядка k больше -1.

Из этой теоремы вытекает, в частности, что никакая рассинхронизация

асимптотически устойчивой синхронизованной системы с симметрической

матрицей не приводит к потере устойчивости.

Обозначим через ρ(A) спектральный радиус матрицы A.

Теорема 4. Пусть A = (a_ij) — матрица с неотрицательными элемен-

тами. Мультиагентная система W абсолютно r-асимптотически устой-

чива в порождающем классе взаимодействий F ⊆ P(A) тогда и только то-

гда, когда ρ(A) < 1.

Из теоремы 4 вытекает достаточное условие абсолютной устойчивости рас-

синхронизованных систем с произвольными блочными матрицами A = (a_ij ).

В этом случае каждую матрицу a_ij можно понимать как линейное отобра-

жение из некоторого пространства X_j в X_i. Пусть в пространствах X_i, i =

= 1, . . . , N, зафиксированы нормы ∥ · ∥_i. Положим

∥a_ij x∥_i

∥a_ij ∥ = sup

x∈X_i,x=0

∥x∥_j

Теорема 5. Если ρ(S) < 1, где скалярная матрица S имеет вид S =

= (∥a_ij ∥), то мультиагентная система W с матрицей A абсолютно

r-асимптотически устойчива в любом порождающем классе рассинхрони-

заций.

Важно отметить, что для любого решения x(n) абсолютно устойчивой

мультиагентной системы W при каждом n = 1, . . . выполняется оценка

∥x(n)∥ ≤ c∥x(0)∥, в которой константа c не зависит от последовательности

матриц Aω(n) в уравнении (9). Если мультиагентная система W абсолютно

r-асимптотически устойчива, то для каждого решения уравнения (9) выпол-

няется более сильная оценка

∥x(n)∥ ≤ cq-κ({ω(·)},n)∥x(0)∥,

q < 1,

где константы c и q не зависят от последовательности матриц Aω(n). Здесь

κ({ω(·)}, n) — наибольшее число непересекающихся подынтервалов интер-

вала [0, n], на каждом из которых изменяет состояние каждый из агентов

системы W с последовательностью матриц Aω(n).

4. Системы с недетерминированно функционирующими агентами

В разделе 3 была рассмотрена ситуация, когда каждый из “агентов” в

мультиагентной системе может в каждый момент времени либо однозначно

реагировать на внешние воздействия по линейному закону (5), меняя свое

состояние в соответствии с правилом

(11)

xi,нов = ai1x1,стар + ai2x2,стар + ··· + a_iNxN,стар + f_i,

либо в соответствующий момент времени не менять свое состояние:

(12)

xi,нов = xi,стар.

Рассмотрим более общую ситуацию: предположим, что для каждого из

“агентов” в мультиагентной системе имеется не два варианта реакции на

внешние воздействия — (11) или (12), — а несколько. Более точно, будем

предполагать что агент с номером i, i = 1, . . . , N, может менять свое состоя-

ние в соответствии с законом

xi,нов = ai1x1,стар + ai2x2,стар + ··· + a_iNxN,стар + f_i,

где строка a_i = (ai1, . . . , a_iN ) определена не однозначно, а может выбираться

из некоторого множества строк A_i.

Обозначим в этом случае через A множество всех матриц

⎛

⎞

a₁₁

a₁₂

··· a1N

⎜

a₂₁

a₂₂

··· a2N

⎟

⎝

⎠,

···

aN1

aN2

··· a_NN

у которых каждая из строк a_i

= (ai1, . . . , a_iN ) принадлежит множеству

строк A_i, i = 1, . . . , N. В этом случае динамика полученной мультиагентной

системы W будет описываться уравнениями вида

x(n + 1) = A(n)x(n) + f(n),

A(n) ∈ A,

а соответствующую мультиагентную систему назовем мультиагентной си-

стемой с недетерминированно функционирующими агентами.

Чтобы рассмотреть вопрос о функционировании мультиагентных систем с

недетерминированными агентами, понадобятся некоторые предварительные

сведения и понятия. Дальнейшее изложение в настоящем разделе опирается

на [31].

Одной из характеристик, описывающих экспоненциальную скорость роста

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

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

Через M(N, M) будем обозначать множество вещественных (N × M)-матриц.

Это множество матриц естественным образом отождествляется с простран-

ством R^N×M , и поэтому в зависимости от контекста его можно трактовать как

топологическое, метрическое или нормированное пространство. Совместным

спектральным радиусом множества вещественных матриц A ⊂ M(N,N) на-

зывают [32] величину

(13)

ρ(A) = lim sup

∥A_n · · · A₁∥1/n = inf sup ∥A_n · · · A₁∥1/n,

n→∞A

n≥1_A

i∈A

где ∥ · ∥ — произвольная матричная норма в M(N, N), порождаемая соот-

ветствующей векторной нормой в R^N . Обобщенным спектральным радиусом

ограниченного множества матриц A ⊂ M(N, N) называют [33, 34] величину

(14)

ρ(A) = lim sup

ρ(A_n · · · A₁)1/n = sup sup ρ(A_n · · · A₁)1/n,

n→∞A

i∈A

n≥1 A_i∈A

где ρ(·) — спектральный радиус матрицы, т.е. максимум модулей ее собствен-

ных значений. Если матрицы из набора A равномерно ограничены по норме,

то по теореме Бергера - Ванга [35] ρ(A) = ρ(A). А в том случае, когда на-

бор матриц A компактен (замкнут и ограничен), супремумы по A_i ∈ A в (13)

и (14) могут быть заменены на максимумы.

Если в (14) супремум заменить на инфимум (или минимум — в слу-

чае компактного набора матриц), то получим так называемый совместный

спектральный подрадиус или нижний спектральный радиус (joint spectral

subradius или lower spectral radius) [36]:

(15)

ρ(A) = lim

inf

∥A_n · · · A₁∥1/n = inf

inf

∥A_n · · · A₁∥1/n,

n→∞

A_i∈A

n≥1

A_i∈A

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

матриц) может быть выражен равенством

(16)

ρ(A) = lim

inf

ρ(A_n · · · A₁)1/n = inf

inf

ρ(A_n · · · A₁)1/n,

n→∞

A_i∈A

n≥1

A_i∈A

как было показано в [36, теорема B1] для конечных множеств A и в [37,

лемма 1.12] и [38, теорема 1] для произвольных множеств A.

Вычисление как совместного, так и нижнего спектрального радиуса явля-

ется сложной задачей, и лишь в исключительных случаях удается описать

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

явном “формульном” виде, см., например, библиографию в [8, 39]. Традици-

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

матриц связывается с выполнением гипотезы о конечности, предполагаю-

щей, что в формулах (14) и (16) предел достигается при некотором конечном

значении n. Для обобщенного/совместного спектрального радиуса эта гипо-

теза была выдвинута Лагариасом и Вангом [40] и впоследствии опровергну-

та Бушем и Мерессом [41]. Позднее появились альтернативные контрприме-

ры [42-44]. Однако все эти контрпримеры были чистыми “теоремами несу-

ществования”, и ни один из них не давал явного описания множеств матриц,

для которых гипотеза о конечности не верна. Первый явный контрпример к

гипотезе о конечности был построен в [45], общие методы построения тако-

го рода контрпримеров предъявлены в [46, 47]. Нижний радиус в определен-

ном смысле является более сложным объектом для анализа, чем обобщенный

спектральный радиус, поскольку он в общем случае зависит от A не непре-

рывным образом [48, 49]. Тем не менее для него опровергнуть гипотезу о ко-

нечности оказалось даже проще [41, 50], чем для обобщенного спектрального

радиуса.

Несмотря на то, что в общем случае гипотеза о конечности не верна, по-

пытки описания классов матриц, для которых она все же имеет место, про-

должаются. При этом следует иметь в виду, что справедливость для какого-

либо класса матриц гипотезы о конечности дает лишь теоретическую воз-

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

поскольку на практике при уже сравнительно небольших значениях n вы-

числение спектральных радиусов ρ(A_n · · · A₁) для всех возможных наборов

матриц A₁, . . . , A_n ∈ A может потребовать слишком больших вычислитель-

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

представляют случаи, когда гипотеза о конечности выполняется для малых

значений n.

Гипотеза о конечности очевидно выполняется для множеств коммутируе-

мых матриц, а также для множеств, состоящих из верхне- или нижнетре-

угольных матриц или из матриц, являющихся с точностью до скалярного

множителя изометриями в некоторой норме (т.е. таких, что ∥Ax∥ ≡ λ_A∥x∥

при некотором λ_A). Менее очевидным примером выполнения гипотезы о ко-

нечности является класс “симметричных” ограниченных наборов матриц, в

которых вместе с каждой матрицей соответствующему набору принадлежит

и (комплексно) сопряженная ей матрица [51, предложение 18]. В частности,

в этот класс включаются множества самосопряженных матриц. Одним из

наиболее интересных классов матриц, для которых справедлива гипотеза о

конечности как для обобщенного спектрального радиуса, так и для нижнего

радиуса, является так называемый класс неотрицательных матриц с незави-

симым изменением строк [11]. Отметим, что во всех вышеупомянутых случа-

ях обобщенный спектральный радиус совпадает со спектральным радиусом

одной из матриц из A или со спектральным радиусом произведения пары

таких матриц.

Достаточно трудными являются утверждения о том, что свойством конеч-

ности обладает любое семейство (2 × 2)-матриц A, состоящее из двух мат-

риц с элементами {0, 1} [52], а также аналогичное утверждение для произ-

вольных семейств (2 × 2)-матриц A, состоящих из двух матриц с элементами

{-1, 0, 1} [53]. Наконец, свойством конечности обладает любое ограниченное

семейство матриц A, в котором все матрицы за исключением, быть может,

одной имеют ранг 1 [54-58].

Существует также ряд работ с менее конструктивными достаточными

условиями, обеспечивающими достижимость обобщенного/совместного спек-

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

графию [8].

4.1. Множества матриц с независимыми строками

Как отмечалось выше, одним из наиболее интересных классов матриц, для

которых справедлива гипотеза о конечности как для обобщенного спектраль-

ного радиуса, так и для нижнего радиуса, является так называемый класс

неотрицательных матриц с независимым изменением строк [11]. В настоящем

разделе напомним соответствующие определения, а также представим новое

доказательство соответствующих результатов о конечности, необходимое для

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

Следуя [11], множество матриц A ⊂ M(N, M) назовем множеством с неза-

висимыми строками или IRU-множеством (от independent row uncertainty

set), если оно состоит из всех матриц

⎛

⎞

a₁₁

a₁₂

··· a1M

⎜

a₂₁

a₂₂

··· a2M

⎟

⎝

⎠,

···

aN1

aN2

··· a_NM

каждая из строк a_i = (ai1, . . . , a_iM ) которых принадлежит некоторому мно-

жеству M-строк A_i, i = 1, . . . , N.

Пример 5. Пусть множества строк A₁ и A₂ следующие:

A₁ = {(a,b), (c,d)}, A₂ = {(α,β), (γ,δ), (μ,ν)}.

Тогда IRU-множество A состоит из следующих матриц:

(

)

(

)

(

)

a b

A₁₁ =

, A₁₂ =

, A₁₃ =

α β

γ δ

μ ν

(

)

(

)

(

)

c d

A₂₁ =

, A₂₂ =

,A₂₃ =

α β

γ δ

μ ν

Отметим, что любое множество матриц, состоящее из одного элемен-

та, является IRU-множеством. Другим примером классов матриц, для ко-

торых числовые характеристики (13) и (15) также могут быть явно вы-

числены, являются линейно упорядоченные множества положительных мат-

риц A = {A₁, . . . , A_n}, в которых матрицы A_i удовлетворяют соотношениям

0 < A₁ < ··· < A_n, где неравенства понимаются поэлементно. Совокупность

всех линейно упорядоченных множеств (N × M)-матриц будет обозначаться

через L(N, M).

IRU-множество матриц называется положительным, если положительны

все его матрицы, т.е. положительны все строки, образующие множества A_i.

Если множество A компактно, что равносильно компактности каждого мно-

жества строк A_i, то корректно определены величины

ρ_min(A) = minρ(A), ρmax(A) = max ρ(A).

A∈A

Будем использовать также обозначения

ρn(A) = sup

ρ(A_n · · · A₁)1/n,

ρn(A) = inf

ρ(A_n · · · A₁)1/n.

A_i∈A

Как показывает следующая теорема, гипотеза о конечности справедлива

для компактных IRU-множеств положительных матриц.

Теорема 6. Пусть A — компактное IRU-множество положительных

матриц, а^Ã — компактное множество матриц, удовлетворяющее вклю-

чениям A ⊆^Ã ⊆ co(A), где co(A) обозначает выпуклую оболочку множе-

ства A. Тогда

(i)

ρn

A) = ρ_min(A) при всех n ≥ 1, и поэтому ρ

A) = ρ_min

A) = ρ_min(A);

(ii)

ρn

A) = ρ_max(A) при всех n ≥ 1, и поэтому ρ

A) = ρ_max

A) = ρ_max(A).

Для случаев

A=A

A = co(A) данная теорема в несколько иной фор-

мулировке доказана в [59]. Как показывает следующий пример, равенства

ρ_max

A) = ρ_max(A) и ρ_min

A) = ρ_min(A) для произвольных множеств матриц

не верны.

Пример 6. Рассмотрим семейства матриц A = {A₁,A₂} и B = {B₁,B₂},

где

(

)

(

)

(

)

(

)

A₁ =

A₂ =

B₁ =

B₂ =

Тогда ρ_max(A) < ρ_max(co(A)) и ρ_min(B) > ρ_min(co(B)), поскольку

(

)

ρ_max(A) = maxρ(A) = 0, ρmax(co(A)) = max

ρ(A) ≥ ρ

(A₁ + A₂)

= 1,

A∈A

A∈co(A)

(

)

ρ_min(B) = minρ(B) = 2, ρmin(co(B)) = min

ρ(B) ≤ ρ

(B₁ + B₂)

= 1.

B∈B

B∈co(B)

4.2. Альтернатива песочных часов

Для векторов x, y ∈ R^N будем писать x ≥ y (соответственно, x > y), если

координаты вектора x не меньше соответствующих координат вектора y (со-

ответственно, строго больше соответствующей координаты вектора y). Ана-

логичные обозначения будут применяться и для матриц.

В пространстве R¹, т.е. для вещественных чисел, любые два элемента x

и y сравнимы между собой, т.е. выполняется одно из неравенств x ≤ y или

y ≤ x; в этом случае говорят, что пространство R¹ линейно упорядочено.

В пространствах же R^N при N > 1 ситуация принципиально отлична — здесь

имеется бесконечное множество пар несравнимых элементов и невыполнение

неравенства x ≥ y не влечет, вообще говоря, выполнение обратного неравен-

ства x ≤ y. Существование несравнимых элементов приводит к тому, что если

при некотором x система линейных неравенств

Ax ≥ v, A ∈ A ⊂ M(N, M)

не имеет решения, то это не означает, вообще говоря, что для какой-то мат-

риц

A∈Aбудетвыполнятьсяобратноенеравенств

Ax ≤ v. Примеры соот-

ветствующих множеств матриц A легко могут быть построены. Тем не менее,

как показывает следующая лемма, для множеств матриц с независимыми

строками все оказывается не столь безнадежным и для линейных неравенств

имеет место некий аналог линейной упорядоченности решений. А именно,

справедлива следующая лемма, играющая ключевую роль в доказательстве

теоремы 6.

Лемма 1. Пусть A⊂M(N,M) — IRU-множество матриц и пусть для

некоторой матриц

A∈Aивекторовu,vвыполняетсяравенств

Au = v.

Тогда справедливы утверждения:

H1: либо Au ≥ v при всех A ∈ A, либо же найдется такая матриц

A ∈ A,

чт

Au ≤ v

Au = v;

H2: либо Au ≤ v при всех A ∈ A, либо же найдется такая матриц

A ∈ A,

чт

Au ≥ v

Au = v.

Утверждения H1 и H2 допускают простую геометрическую интерпрета-

цию. Представим множества B_l(v) = {x : x ≤ v} и B_u(v) = {x : x ≥ v} как

нижний и верхний баллоны некоторых стилизованных песочных часов с пе-

ремычкой в точке v, а элементы Au — песчинками. Тогда согласно утвержде-

ниям H1 и H2 либо все “песчинки” Au заполняют один из баллонов (нижний

или верхний), либо же в другом баллоне (верхнем или нижнем соответствен-

но) остается хоть одна “песчинка”. Такая интерпретация дает основание на-

звать лемму 1 альтернативой песочных часов. Именно эта альтернатива иг-

рает ключевую роль как в доказательстве теоремы 6, так и в ее обобщении

на новый класс матриц. Впервые альтернатива песочных часов была пред-

ложена и использована в [60] для анализа минимаксных соотношений между

спектральными радиусами произведений матриц.

При доказательстве теоремы 6 используются лишь те свойства IRU-мно-

жеств матриц, которые сформулированы в утверждениях H1 и H2 альтерна-

тивы песочных часов (лемма 1). Поэтому представляется естественным вы-

делить класс матриц, для которых выполняются утверждения H1 и H2, и

изучить его свойства.

Скажем, что множество A ⊂ M(N, M) положительных матриц является

H-множеством (hourglass set, H-set), если каждый раз при выполнении ра-

венств

Au = v для некоторой матриц

A ∈ A и векторов u,v > 0 выполня-

ются также утверждения H1 и H2 леммы 1.

Тривиальным примером H-множеств являются линейно упорядоченные

множества положительных матриц A = {A₁, . . . , A_n}, в которых матрицы

A_i удовлетворяют соотношениям 0 < A₁ < ··· < A_n. Здесь при каждом u > 0

векторы A₁u, . . . , A_nu строго положительны и линейно упорядочены, откуда

и следует справедливость утверждений H1 и H2 для A. Менее тривиальным и

более интересным примером H-множеств, как следует из леммы 1, является

класс множеств положительных матриц с независимыми строками.

Опишем некоторые свойства классов H-множеств матриц. Введем опера-

ции сложения и умножения по Минковскому множеств матриц:

A + B = {A + B : A ∈ A, B ∈ B}, AB = {AB : A ∈ A, B ∈ B},

а также операцию умножения множества матриц на число:

tA = At = {tA : t ∈ R, A ∈ A}.

Естественно, операция сложения допустима тогда и только тогда, когда мат-

рицы из множеств A и B имеют одинаковый размер, а операция умножения

допустима тогда и только тогда, когда размерности матриц из множеств A

и B согласованы: размер строк матриц из A совпадает с размером столбцов

матриц из B. Проблем с согласованием размерностей не возникнет, когда рас-

сматриваются множества, состоящие из квадратных матриц одной и той же

размерности.

В дальнейшем, если понадобится совершать разного рода предельные пе-

реходы как с матрицами из рассматриваемых множеств, так и с самими мно-

жествами матриц, естественно ограничиться рассмотрением лишь компакт-

ных (замкнутых и ограниченных) множеств матриц. Множество всех ком-

пактных положительных множеств матриц с независимыми строками разме-

ра N ×M будем обозначать через U(N, M). Компактность каждого множества

матриц из U(N, M) равносильна компактности каждого из порождающих его

множеств строк. Множество всех конечных² положительных линейно упоря-

доченных множеств матриц размера N ×M будем обозначать через L(N, M).

Наконец, через H(N, M) обозначим множество всех компактных положитель-

ных H-множеств матриц размера N × M.

Теорема 7. Справедливы утверждения:

(i) A + B ∈ H(N, M), если A, B ∈ H(N, M);

(ii) AB ∈ H(N, Q), если A ∈ H(N, M) и B ∈ H(M, Q);

(iii) tA = At ∈ H(N, M), если t > 0 и A ∈ H(N, M).

² Можно было бы рассматривать и бесконечные множества, но в данном разделе нет

возможности останавливаться на тонкостях определения линейной упорядоченности для

бесконечных множеств.

Согласно теореме 7 множество всех подмножеств квадратных матриц

H(N, N) обладает групповыми операциями сложения и умножения, но не яв-

ляется группой ни по сложению, ни по умножению. Однако после добавления

элементов {0} и {I} к H(N, N) получившееся множество H(N, N) ∪ {0} ∪ {I}

становится полукольцом [61].

Замечание 1. В общем случае A(B1 +B₂) = AB₁+AB₂ и (A₁+A₂)B =

= A₁B + A₂B, т.е. операции Минковского неассоциативны. В частности, A +

+ A = 2A.

Замечание 2. Из теоремы 7 следует, что любая конечная сумма лю-

бых конечных произведений матриц из H(N, N) снова является матрицей

из H(N, N). Более того, при любых целых n, d ≥ 1 элементами множества

H(N, N) являются все “полиномиальные” множества матриц

∑

(17)

P (A₁, . . . , A_n) =

pi1,...,i_k Ai₁ ··· Ai_k ,

k=1 i₁,...,i_k∈{1,...,n}

где A₁, . . . , A_n ∈ H(N, N), a числовые коэффициенты pi1,...,i_k положительны.

Более того, элементами множества H(N, N) являются все множества матриц,

получающиеся как суперпозиции конечного числа полиномиальных отобра-

жений (17).

С помощью полиномов (17) и их суперпозиций можно получать не толь-

ко элементы множества H(N, N), но и элементы произвольных множеств

H(N, M), беря при этом аргументы A₁, . . . , A_n также из множеств матриц

H(N_i, M_i) произвольных размерностей. При этом надо только следить за тем,

чтобы произведения матриц Ai1 · · · Aik были допустимы, а выражение (17)

определяло множество матриц размерности N × M.

Выше были предъявлены два вида нетривиальных “элементарных” H-мно-

жеств матриц — это множества матриц с независимым изменением строк и

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

обозначим через H_∗(N, M) множество всех множеств матриц размера N × M,

получающееся как рекурсивное расширение с помощью полиномов (17) мно-

жества положительных матриц с независимым изменением строк и мно-

жества линейно упорядоченных положительных матриц. Другими словами,

H_∗(N,M) — это множество всех множеств матриц, представимых в виде зна-

чений суперпозиций матричных полиномов (17), где аргументы полиномов

“низшего уровня” берутся из матричных множеств U(N_i, M_i) ∪ L(N_i, M_i).

Согласно замечанию 1 операции Минковского неассоциативны. Поэтому

рекурсивное расширение множества положительных матриц с независимым

изменением строк и множества линейно упорядоченных положительных мат-

риц образует более широкое множество матриц, чем расширение множества

положительных матриц с независимым изменением строк и множества ли-

нейно упорядоченных положительных матриц с помощью полиномов (17).

Выше были описаны два вида нетривиальных “элементарных” H-множеств

матриц — это множества матриц с независимым изменением строк и линейно

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

через H_∗(N, M) совокупность всех множеств (N × M)-матриц, получающих-

ся как допустимые конечные суммы конечных произведений множеств поло-

жительных матриц с независимым изменением строк или множеств линей-

но упорядоченных положительных матриц. Другими словами, H_∗(N, M) —

это множество всех множеств матриц, представимых в виде значений мат-

ричных полиномов (17) с аргументами, берущимися из матричных множеств

U(N_i, M_i) ∪ L(N_i, M_i).

Вопрос 1. Имеет ли место равенство H_∗(N,M) = H(N,M)?

Ответ на этот вопрос скорее всего отрицателен, но контрпримеры авторам

неизвестны.

При рассмотрении различного рода задач, связанных с множествами мат-

риц, желательно уметь совершать предельные переходы. На самом деле, для

дальнейших целей хотелось бы уметь распространять некоторые факты, свя-

занные с H-множествами (положительных) матриц, на такого же рода мно-

жества матриц, но с неотрицательными элементами. Для достижения этой

цели, не вникая во все многообразие различных видов топологий на простран-

ствах подмножеств, ограничимся описанием лишь одной из них — топологии,

задаваемой метрикой Хаусдорфа.

Зададим на множестве M(N, M) некоторую матричную норму ∥ · ∥ и обо-

значим через K(N, M) множество всех компактных подмножеств множества

M(N, M). Тогда для любых двух множеств матриц A, B ∈ K(N, M) опреде-

лена метрика (Хаусдорфа)

{

}

H(A, B) = max sup

inf

∥A - B∥, sup

inf ∥A - B∥

A∈A

B∈B

A∈A

превращающая K(N, M) в полное метрическое пространство. Значит, множе-

ство матриц H(N, M)⊂K(N, M) также является метрическим пространством

в метрике Хаусдорфа.

Как известно, см., например, [62, раздел 1.3], отображения

(A, B) → A + B, (A, B) → AB, A → A × A × · · · × A, A → co(A),

где A и B — компактные множества, непрерывны и в метрике Хаусдорфа,

и такими же свойствами непрерывности обладает и любое полиномиальное

отображение (17).

Обозначим через H(N, M) замыкание множества H(N, M) в метрике Хаус-

дорфа. Ясно, что {0}, {I} ∈ H(N, M), а поскольку операции сложения и

умножения множества матриц по Минковскому непрерывны в метрике Хаус-

дорфа, то по теореме 8 множество H(N, N) является полукольцом. Однако

ответ на вопрос о том, когда для некоторого множества матриц A справедли-

во включение A ∈ H(N, M), требует дополнительного анализа. Ограничим-

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

дан в явном виде. Отметим, что значения любого полиномиального отобра-

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

неотрицательных матриц либо из IRU-множеств неотрицательных матриц

принадлежат замыканию в метрике Хаусдорфа множества положительных

H-множеств матриц.

Следующая теорема является обобщением теоремы 6 на случай H-мно-

жеств матриц.

Теорема 8. Пусть A ∈ H(N,N)

A — компактное множество мат-

риц, удовлетворяющее включениям A

A ⊆ co(A). Тогда

(i)

ρn

A) = ρ_min(A) при всех n ≥ 1, и поэтому ρ

A) = ρ_min

A) = ρ_min(A);

(ii)

ρn

A) = ρ_max(A) при всех n ≥ 1, и поэтому ρ

A) = ρ_max

A) = ρ_max(A).

Используя эту теорему, легко построить пример, показывающий, что не

каждое множество положительных матриц является H-множеством. Не яв-

ляются H-множествами также одноточечные множества матриц {0} и {I}, со-

стоящие из нулевой и единичной матрицы, поскольку соответствующие мат-

рицы неположительны.

Пример 7. Рассмотрим множество матриц A, состоящее из двух поло-

жительных матриц

(

)

(

)

a a

A₁ =

A₂ =

a > 0.

a²

Тогда max{ρ(A₁), ρ(A₂)} = 2a, в то время как ρ(A₁A₂) = (1 + a²)². Следова-

тельно, при a = 1

ρ(A) ≥ ∥A₁A₂∥1/2 ≥ ρ(A₁A₂)1/2 > max{ρ(A₁), ρ(A₂)},

чего в силу теоремы 8 не могло бы быть, если бы A было H-множеством.

При применении теоремы 8 одним из первых естественно возникает вопрос

о проверке для некоторого множества матриц A справедливости включения

A ∈ H(N,N). Один из таких случаев описан в следующем следствии.

Следствие 1. Пусть A — множество матриц, являющееся значени-

ем некоторого полиномиального отображения (17), аргументами которо-

го являются конечные линейно упорядоченные множества неотрицатель-

ных матриц либо компактные IRU-множества неотрицательных матриц.

Тогда для любого компактного множества матриц

A, удовлетворяющего

включениям A

A ⊆ co(A), выполняются утверждения теоремы 8.

Из теоремы 8 вытекает, что для произвольного множества A ∈ H(N, M)

имеют место равенства

(18)

ρ(A) = ρ(co(A)),

ρ(A) = ρ(co(A)).

На самом деле, как известно [37, 39], первое из этих равенств справедли-

во для произвольных (не обязательно неотрицательных) ограниченных мно-

жеств (N × N)-матриц; оно является следствием того очевидного факта, что

для любой нормы

sup ∥A_n ··· A₁∥ = sup

∥A_n · · · A₁∥.

A_i∈A

A_i∈co(A)

Второе же равенство в (18) для общих множеств матриц перестает быть вер-

ным, как видно из примера множества A = {I, -I}, для которого ρ(A) = 1,

но ρ(co(A)) = 0. В связи с этим отметим одно общее утверждение.

Теорема 9. Для любого ограниченного множества A ⊂ M(N,N),

состоящего из неотрицательных матриц, справедливо второе из ра-

венств (18).

4.3. Заключительные замечания

Термин “набор матриц с независимыми строками (или столбцами)” поза-

имствован из относительно недавней работы [11], хотя такого рода наборы

матриц фактически уже давно использовались в теории параллельных вы-

числений и теории асинхронных систем. В частном случае, когда каждая из

строк матриц из A совпадает со строкой некоторой заранее заданной матри-

цы A или единичной матрицы I, такого рода матрицы также называют [21]

помесями матриц A и I, см. раздел 3. Простейшим примером, в котором воз-

никают помеси матриц, является так называемая линейная мультиагентная

асинхронная система, в которой в каждый момент времени обновление одной

или нескольких компонент вектора состояния может происходить независи-

мо друг от друга, т.е. каждая координата вектора xn+1 принимает значение

соответствующей координаты вектора Ax_n или x_n. В [63] эти же множества

матриц названы product families.

Так как спектральный радиус не меняется при переходе к транспонирован-

ной матрице, то все утверждения теоремы 8 сохраняют силу для множеств

матриц, берущихся из класса H^T-матриц, получающегося транспонировани-

ем всех H-матриц. В частности, при транспонировании множества матриц

с независимыми строками переходят в множества матриц с независимыми

столбцами [11]. Отметим, что для множеств H^T-матриц альтернатива песоч-

ных часов, вообще говоря, не выполняется. В связи с этим естественно воз-

никает вопрос о расширении того класса матриц, для которых справедливы

приведенные в настоящем разделе теоремы.

СПИСОК ЛИТЕРАТУРЫ

1. Козякин В.С., Кузнецов Н.А., Чеботарев П.Ю. Консенсус в асинхронных муль-

тиагентных системах. I // АиТ. 2019. № 4. C. 3-40.

2. Фань Чун-Вуй. О следящих системах, содержащих два импульсных элемента с

неравными периодами повторения // АиТ. 1958. Т. 19. № 10. С. 917-930.

3. Цыпкин Я.З. Теория линейных импульсных систем. М.: Физматгиз, 1963.

4. Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation. Numerical

Methods. Englewood Cliffs. N.J.: Prentice Hall, 1989.

5. Асарин Е.А., Козякин В.С., Красносельский М.А., Кузнецов Н.А. Анализ устой-

чивости рассинхронизованных дискретных систем. М.: Наука, 1992. DOI: 10.

13140/RG.2.1.3381.6169.

6. Сейфуллаев Р.Э., Фрадков А.Л. Анализ дискретно-непрерывных нелинейных

многосвязных систем на основе линейных матричных неравенств // АиТ. 2015.

№ 6. С. 57-74.

Seifullaev R.E., Fradkov A.L. Linear Matrix Inequality-Based Analysis of the

Discrete-Continuous Nonlinear Multivariable Systems // Autom. Remote Control.

2015. V. 76. No. 6. P. 989-1004.

Hetel L., Fiter C., Omran H. et al. Recent developments on the stability of systems

with aperiodic sampling: an overview // Automatica J. IFAC.

2017. V. 76.

P. 309-335. DOI: 10.1016/j.automatica.2016.10.023.

Kozyakin V. An annotated bibliography on convergence of matrix products and

the theory of joint/generalized spectral radius: Preprint. Moscow: Institut. Inform.

Transmis. Probl. 2013. December. DOI: 10.13140/RG.2.1.4257.5040/1.

Cross R., Kozyakin V.S. Double exponential instability of triangular arbitrage

systems // Discrete Contin. Dyn. Syst. Ser. B.

2013. V. 18. No. 2. P. 349-376.

DOI: 10.3934/dcdsb.2013.18.349.

10.

Bhaya A., Kaszkurewicz E., Kozyakin V.S. Existence and Stability of a Unique

Equilibrium in Continuous-Valued Discrete-Time Asynchronous Hopfield Neural

Networks // Proc. 1995 IEEE Int. Sympos. Circuits Syst. ISCAS’95. V. 2.

1995.

P. 1140-1143. DOI: 10.1109/ISCAS.1995.520345.

11.

Blondel V.D., Nesterov Y. Polynomial-time computation of the joint spectral radius

for some sets of nonnegative matrices // SIAM J. Matrix Anal. Appl. 2009. V. 31.

No. 3. P. 865-876. DOI: 10.1137/080723764.

12.

Dybvig P.H., Ross S.A. Arbitrage // The New Palgrave Dictionary of Economics /

Ed. by S.N. Durlauf, L.E. Blume. Basingstoke: Palgrave Macmillan, 2008.

13.

Marshall B.R., Treepongkaruna S., Young M. Exploitable Arbitrage Opportunities

Exist in the Foreign Exchange Market. Discussion Paper, 10 September, Massey

Univer., Palmerston North, New Zealand, 2007.

14.

Akram Q.F., Rime D., Sarno L. Arbitrage in the Foreign Exchange Market: Turning

on the Microscope // J. Int. Econom. 2008. December. V. 76. No. 2. P. 237-253.

DOI: 10.1016/j.jinteco.2008.07.004.

15.

Eun C.S., Resnick B.G. International Financial Management. Irwin Series in

Finance, Insurance, and Real Estate. 6th edition. McGraw-Hill/Irwin, 2011.

16.

Cassel G. The Present Situation of the Foreign Exchanges. I // Econom. J.

1916.

V. 26. No. 1. P. 62-65.

17.

Ross S.A. A Simple Approach to the Valuation of Risky Streams // J. Business.

1978. V. 51. P. 453-475.

18.

Cross R., Kozyakin V., O’Callaghan B. et al. Periodic Sequences of Arbitrage: A

Tale of Four Currencies // Metroeconomica. 2012. May. V. 63. No. 2. P. 250-294.

DOI: 10.1111/j.1467-999X.2011.04140.x.

19.

Козякин В.С. Абсолютная устойчивость дискретных рассинхронизованных си-

стем // Докл. АН СССР. 1990. Т. 312. № 5. С. 1066-1070.

20.

Baudet G.M. Asynchronous iterative methods for multiprocessors // J. Assoc.

Comput. Mach. 1978. V. 25. No. 2. P. 226-244.

21.

Клепцын А.Ф., Козякин В.С., Красносельский М.А., Кузнецов Н.А. О влиянии

малой рассинхронизации на устойчивость сложных систем. I // АиТ. 1983. № 7.

С. 44-51.

Kleptsyn A.F., Kozyakin V.S., Krasnoselskii M.A., Kuznetsov N.A. Effect of Small

Synchronization Errors on Stability of Complex Systems. I // Autom. Remote

Control. 1983. V. 44. No. 7. P. 861-867.

22.

Клепцын А.Ф., Козякин В.С., Красносельский М.А., Кузнецов Н.А. О влиянии

малой рассинхронизации на устойчивость сложных систем. II // АиТ. 1984. № 3.

С. 42-47.

Kleptsyn A.F., Kozyakin V.S., Krasnoselskii M.A., Kuznetsov N.A. Effect of Small

Synchronization Errors on Stability of Complex Systems. II // Autom. Remote

Control. 1984. V. 45. No. 3. P. 309-314.

23.

Клепцын А.Ф., Козякин В.С., Красносельский М.А., Кузнецов Н.А. О влиянии

малой рассинхронизации на устойчивость сложных систем. III // АиТ.

1984.

№ 8. С. 63-67.

Kleptsyn A.F., Kozyakin V.S., Krasnoselskii M.A., Kuznetsov N.A. Effect of Small

Synchronization Errors on Stability of Complex Systems. III // Autom. Remote

Control. 1984. V. 45. No. 8. P. 1014-1018.

24.

Клепцын А.Ф., Козякин В.С., Красносельский М.А., Кузнецов Н.А. Устойчи-

вость рассинхронизованных систем // Докл. АН СССР.

1984. Т. 274. № 5.

С. 1053-1056.

25.

Айзерман М.А., Гантмахер Ф.Р. Абсолютная устойчивость регулируемых си-

стем. М.: Изд-во АН СССР, 1963.

26.

Asarin Ye. A., Kozyakin V.S., Krasnosel’ski˘ı M.A. et al. On some new types of

mathematical models of complex systems // Modelling and adaptive control (Sopron,

1986). Berlin: Springer, 1988. V. 105 of Lecture Notes in Control and Inform. Sci.

P. 10-26. DOI: 10.1007/BFb0043174.

27.

Асарин Е.А., Козякин В.С., Красносельский М.А., Кузнецов Н.А. Математиче-

ские модели устойчивости рассинхронизованных систем // Интеллект. процессы

и их моделирование. Информационные сети. М.: Изд-во РАН, 1994. С. 3-17.

28.

Walters P. An introduction to ergodic theory. N.Y.: Springer-Verlag, 1982.

29.

Furstenberg H., Kesten H. Products of random matrices // Ann. Math. Statist. 1960.

V. 31. P. 457-469. DOI: 10.1214/aoms/1177705909.

30.

Lancaster P. Theory of matrices. N.Y.-London: Academic Press, 1969.

31.

Kozyakin V. Hourglass alternative and the finiteness conjecture for the spectral

characteristics of sets of non-negative matrices // Linear Algebra Appl. 2016. V. 489.

P. 167-185. DOI: 10.1016/j.laa.2015.10.017.

32.

Rota G.-C., Strang G. A note on the joint spectral radius // Nederl. Akad. Wetensch.

Proc. Ser. A 63 = Indag. Math. 1960. V. 22. P. 379-381.

33.

Daubechies I., Lagarias J.C. Sets of matrices all infinite products of which converge //

Linear Algebra Appl. 1992. V. 161. P. 227-263. DOI: 10.1016/0024-3795(92)90012-Y.

34.

Daubechies I., Lagarias J.C. Corrigendum/addendum to: “ Sets of matrices all

infinite products of which converge” [Linear Algebra Appl. 161 (1992), 227-263;

MR1142737 (93f:15006)] // Linear Algebra Appl. 2001. V. 327. No. 1-3. P. 69-83.

DOI: 10.1016/S0024-3795(00)00314-1.

35.

Berger M.A., Wang Y. Bounded semigroups of matrices // Linear Algebra Appl.

1992. V. 166. P. 21-27. DOI: 10.1016/0024-3795(92)90267-E.

36.

Gurvits L. Stability of discrete linear inclusion // Linear Algebra Appl. 1995. V. 231.

P. 47-85. DOI: 10.1016/0024-3795(95)90006-3.

37.

Theys J. Joint Spectral Radius: Theory and Approximations: Ph. D. thesis / Faculté

des sciences appliquées, Département d’ingénierie mathématique, Center for Systems

Engineering and Applied Mechanics. Université Catholique de Louvain. 2005. May.

189 p.

38.

Czornik A. On the generalized spectral subradius // Linear Algebra Appl.

2005.

V. 407. P. 242-248. DOI: 10.1016/j.laa.2005.05.006.

39.

Jungers R. The joint spectral radius. Berlin: Springer-Verlag, 2009. V. 385 of Lecture

Notes in Control and Information Sciences. DOI: 10.1007/978-3-540-95980-9.

40.

Lagarias J.C., Wang Y. The finiteness conjecture for the generalized spectral

radius of a set of matrices // Linear Algebra Appl.

1995. V. 214. P. 17-42.

DOI: 10.1016/0024-3795(93)00052-2.

41.

Bousch T., Mairesse J. Asymptotic height optimization for topical IFS, Tetris heaps,

and the finiteness conjecture // J. Amer. Math. Soc. 2002. V. 15. No. 1. P. 77-111.

DOI: 10.1090/S0894-0347-01-00378-2.

42.

Blondel V.D., Theys J., Vladimirov A.A. An elementary counterexample to the

finiteness conjecture // SIAM J. Matrix Anal. Appl. 2003. V. 24. No. 4. P. 963-970.

DOI: 10.1137/S0895479801397846.

43.

Kozyakin V. A Dynamical Systems Construction of a Counterexample to the

Finiteness Conjecture // Proc. 44 IEEE Conf. Decision Control 2005 and 2005 Eur.

Control Conf. CDC-ECC’05. 2005. P. 2338-2343. DOI: 10.1109/CDC.2005.1582511.

44.

Kozyakin V.S. Structure of Extremal Trajectories of Discrete Linear Systems and the

Finiteness Conjecture // Autom. Remote Control. 2007. V. 68. No. 1. P. 174-209.

DOI: 10.1134/S0005117906040171.

45.

Hare K.G., Morris I.D., Sidorov N., Theys J. An explicit counterexample to

the Lagarias-Wang finiteness conjecture // Adv. Math.

2011. V. 226. No. 6.

P. 4667-4701. DOI: 10.1016/j.aim.2010.12.012.

46.

Morris I., Sidorov N. On a Devil’s staircase associated to the joint spectral radii of

a family of pairs of matrices // J. Eur. Math. Soc. (JEMS).

2013. V. 15. No. 5.

P. 1747-1782. DOI: 10.4171/JEMS/402.

47.

Jenkinson O., Pollicott M. Joint spectral radius, Sturmian measures, and the

finiteness conjecture

// Ergodic Theory Dynam. Syst.

2017.

1-39.

DOI: 10.1017/etds.2017.18.

48.

Jungers R.M. On asymptotic properties of matrix semigroups with an invariant

cone // Linear Algebra Appl. 2012. V. 437. No. 5. P. 1205-1214. DOI: 10.1016/j.laa.

2012.04.006.

49.

Bochi J., Morris I.D. Continuity properties of the lower spectral radius // Proc.

Lond. Math. Soc. (3). 2015. V. 110. No. 2. P. 477-509. DOI: 10.1112/plms/pdu058.

50.

Czornik A., Jurgas P. Falseness of the finiteness property of the spectral

subradius // Int. J. Appl. Math. Comput. Sci.

2007. V. 17. No. 2. P. 173-178.

DOI: 10.2478/v10006-007-0016-1.

51.

Plischke E., Wirth F. Duality results for the joint spectral radius and transient

behavior // Linear Algebra Appl.

2008.

V. 428. No. 10. P.

2368-2384.

DOI: 10.1016/j.laa.2007.12.009.

52.

Jungers R.M., Blondel V.D. On the finiteness property for rational matrices //

Linear Algebra Appl.

2008.

V. 428. No. 10.

2283-2295.

DOI:

10.1016/j.laa.2007.07.007.

53.

Cicone A., Guglielmi N., Serra-Capizzano S., Zennaro M. Finiteness property of

pairs of 2 × 2 sign-matrices via real extremal polytope norms // Linear Algebra

Appl. 2010. V. 432. No. 2-3. P. 796-816. DOI: 10.1016/j.laa.2009.09.022.

54.

Dai X., Huang Y., Liu J., Xiao M. The finite-step realizability of the joint spectral

radius of a pair of d × d matrices one of which being rank-one // Linear Algebra

Appl. 2012. V. 437. No. 7. P. 1548-1561. DOI: 10.1016/j.laa.2012.04.053.

55.

Liu J., Xiao M. Computation of Joint Spectral Radius for Network Model Associated

with Rank-One Matrix Set // Neural Inform. Proc. Proc. 19 Int. Conf., ICONIP 2012,

Doha, Qatar, November 12-15, 2012. P. III. Springer Berlin Heidelberg, 2012. V. 7665

of Lecture Notes Comput. Sci. P. 356-363. DOI: 10.1007/978-3-642-34487-9_44.

56.

Liu J., Xiao M. Rank-one characterization of joint spectral radius of finite matrix

family // Linear Algebra Appl. 2013. V. 438. No. 8. P. 3258-3277. DOI: 10.1016/j.laa.

2012.12.032.

57.

Morris I.D. Rank one matrices do not contribute to the failure of the finiteness

property. ArXiv.org e-Print archive. 2011. September. arXiv: 1109.4648.

58. Wang S., Wen J. The Finiteness Conjecture for the Joint Spectral Radius of a Pair of

Matrices // Proc. 9 Int. Conf. Comput. Intelligence Security (CIS), 2013, Emeishan,

China, December 14-15. 2013. P. 798-802.

59. Nesterov Y., Protasov V.Y. Optimizing the spectral radius // SIAM J. Matrix Anal.

Appl. 2013. V. 34. No. 3. P. 999-1013. DOI: 10.1137/110850967.

60. Asarin E., Cervelle J., Degorre A. et al. Entropy Games and Matrix Multiplication

Games //

Symp. Theor. Aspects Comp. Sci., (STACS

2016)

/ Ed. by

N. Ollinger, H. Vollmer. V. 47 of LIPIcs. Leibniz Int. Proc. Inform. Dagstuhl,

Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. 2016. P. 11:1-11:14.

DOI: 10.4230/LIPIcs.STACS.2016.11.

61. Golan J.S. Semirings and their applications. Dordrecht: Kluwer Academ. Publish.,

1999. DOI: 10.1007/978-94-015-9333-5.

62. Borisovich Y.G., Gel’man B.D., Myshkis A.D., Obukhovskii V.V. Multivalued

mappings

// J. Soviet Math.

1984.

24. No.

719-791.

DOI: 10.1007/BF01305758.

63. Protasov V. Yu. Spectral simplex method // Math. Program. 2016. V. 156. No. 1-2.

Ser. A. P. 485-511. DOI: 10.1007/s10107-015-0905-2.

Статья представлена к публикации членом редколлегии А.Л. Фрадковым.

Поступила в редакцию 17.09.2018

После доработки 22.10.2018

Принята к публикации 08.11.2018