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

Линейные системы

Д.К. ХОМУТОВ (homutov_-dk@mail.ru)

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

О СВОЙСТВАХ МЕТОДА ОРТОГОНАЛЬНОЙ ПРОЕКЦИИ

В ЗАДАЧЕ О КОНСЕНСУСЕ

В статье изучается асимптотическое поведение многоагентной системы

с информационными связями. Доказано, что для произвольного орграфа

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

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

дообратной матрицей для введенной вспомогательной матрицы. Также

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

щей орграфу связей, в котором влияния на фиксированного агента меня-

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

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

ных систем с различными протоколами.

Ключевые слова: многоагентная система, консенсус, собственный проек-

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

DOI: 10.31857/S000523102305001X, EDN: AFGUFJ

1. Введение

Многоагентные системы (МАС) с информационными связями (см., напри-

мер, [1-5]), как обычно, представляются взвешенным орграфом связей, а сам

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

помощью лапласовской матрицы. Протоколы - модели МАС для дискрет-

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

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

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

ром и т.п.) соответствующих матриц. В таких моделях существование остов-

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

характеристик. Асимптотическое поведение системы, как это было установ-

лено в [6-8], определяется собственным проектором лапласовской матрицы,

построенной для орграфа связей. Для дискретной модели консенсус также

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

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

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

определению регулярности [9], стохастическая матрица регулярна, если ранг

предела последовательности ее степеней равен 1. Если собственный проек-

тор имеет ранг больше 1, то не для каждого вектора начальных значений

консенсус достигается. В этом случае любой метод, приводящий к консенсу-

су, называем методом регуляризации. Слово “регуляризация” связано с тем,

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

хастической матрицей ранга 1. А ранг предела последовательности степеней

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

В первой части работы приведена графовая интерпретация одного из ме-

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

Исследованы свойства метода проекции с помощью псевдообратной матрицы.

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

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

ражается на подпространство области сходимости процедуры ДеГроота.

В [10] были рассмотрены некоторые элементы графовой интерпретации

метода ортогональной проекции. Однако это касалось только соотношения

весов множеств исходящих деревьев на множестве вершин базовых бикомпо-

нент (определение приведено в следующем разделе) в результирующей мат-

рице, и не вносило вклад в обоснования применения самого метода. В [11] для

системы с отдельными базовыми бикомпонентами (без небазовых вершин)

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

ратной по Муру-Пенроузу для вспомогательной матрицы, построенной по

лапласовской матрице. В настоящей работе мы полностью решаем постав-

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

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

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

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

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

входящих дуг (в общем, всех вершин) в исходном орграфе связей. Выведено

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

2. Необходимые понятия и вспомогательные результаты

Пусть Γ = (V, E) - орграф с множеством вершин V и множеством дуг E.

Определение 1. Непустое подмножество вершин K орграфа Γ =

= (V, E) называют базовой бикомпонентой, если все вершины, принадлежа-

щие K, взаимно достижимы, и нет дуг (i, j), где j ∈ K, i ∈ V \ K. Мно-

жество вершин всех базовых бикомпонент обозначим через K. Множество

вершин, не принадлежащих базовым бикомпонентам, обозначим через^K =

= V \ K, и назовем их небазовыми.

Для орграфа из рис. 1,а множества {1, 2}, {3, 4, 5} и {6, 7} являются базо-

выми бикомпонентами.

Рассмотрим многоагентную систему (МАС) с множеством агентов

{1, . . . , n}. Для МАС пусть A - матрица связей (влияний), A = (a_ij ), где

a_ij - вес влияния j-го агента на i-го. Также для системы построим орграф

связей с множеством вершин V = {1, . . . , n}, в котором каждому элементу

a_ij > 0 матрицы A соответствует дуга (j,i) с весом a_ij.

Рис. 1. a — Cистема с тремя базовыми бикомпонентами {1, 2}, {3, 4, 5}, {6, 7}.

б — “Cклеивание” базовых бикомпонент в одну вершину 0.

Определение 2. 1) Вес орграфа G равен произведению весов всех его_∏

дуг: ε(G) =(i,j)∈E a_ji. 2) Вес множества орграфов G = {G_i} равен сумме

∑

весов всех орграфов, входящих в данное множество, т.е. ε(G) =_i ε(G_i).

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

содержит небазовые вершины.

Ключевую роль в теории многоагентных систем с информационными свя-

зями играет лапласовская матрица орграфа связей, определяемая следую-

щим образом: L = Δ(A) - A, где Δ(A) - диагональная матрица с i-м диа-

гональным элементом, равным сумме весов входящих дуг в вершину i. Если

0_n = (0,... ,0)^T и 1_n = (1,... ,1)^T - векторы порядка n из нулей и единиц, со-

ответственно, то L1_n = 0_n, т.е. L - вырожденная матрица, и сумма ее строч-

ных элементов равна нулю. Если орграф связей неориентированный, то L -

симметричная, положительно полуопределенная.

Определение 3. Собственным проектором (см., например, [12]) квад-

ратной матрицы A называют такой проектор - идемпотентную матри-

цу A^⊢, что R(A^⊢) = N (A^ν ) и N (A^⊢) = R(A^ν ), где ν - индекс матрицы, т.е.

такое наименьшее число, для которого имеет место rank(A^ν ) = rank(Aν+1).

Отметим, что собственный проектор L^⊢ для лапласовской матрицы L яв-

ляется неотрицательной стохастической матрицей. В общем случае L^⊢ для

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

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

рицы.

Замечание 1. Для любой лапласовской матрицы L indL = 1, и

(1)

LL^⊢ = L^⊢L = 0_n×n.

Для любой прямоугольной матрицы A ∈ R^m×n существует единственная

матрица A⁺ ∈ R^n×m, для которой выполняются следующие четыре условия:

1) A⁺AA⁺ = A⁺; 2) AA⁺A = A; 3) (AA⁺)^∗ = AA⁺; 4) (A⁺A)^∗ = A⁺A. Мат-

рицу A⁺ называют псевдообратной по Муру-Пенроузу.

Определение 4. Две матрицы A = (a_ij) и B = (b_ij) - однотипные, ес-

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

a_ij = 0 тогда и только тогда, когда b_ij = 0.

В матричных обозначениях следуем книге [13]. Для A обозначим через A_ij

подматрицу, получаемую удалением i-й строки и j-го столбца A. Также для

подматрицы, образуемой строками с номерами из множества α ⊆ {1, . . . , n} и

(_α)

столбцами с номерами из множества β⊆{1, . . . , n}, примем обозначение A

.¹

Теорема 1. 1) Собственный проектор L^⊢ лапласовской матрицы L сов-

падает с нормированной матрицей максимальных исходящих лесов Q = (q_ij)

взвешенного орграфа Γ:

ε(F^j→i)

l^⊢ij = q_ij =

i, j = 1, . . . , n,

ε(F)

где ε(F) — вес множества всех остовных максимальных исходящих лесов

орграфа Γ, ε(F^j→i) — вес множества тех остовных максимальных исхо-

дящих лесов, где вершина j является корнем одного из исходящих деревьев,

а i достижима из j.

2) Если i и j принадлежат одной базовой бикомпоненте, то соответ-

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

Теорема 2 (Матричная теорема о деревьях). Алгебраическое дополнение

любого элемента i-й строки лапласовской матрицы равно суммарному весу

остовных исходящих из i-й вершины деревьев.

Заметим, что если в лапласовской матрице орграфа какой-либо столбец

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

равным весу множества всех остовных исходящих деревьев.

3. Интерпретация метода ортогональной проекции

с помощью псевдообратной матрицы

Рассмотрим базовую дифференциальную модель

(2)

x(t) = -Lx(t),

где x_i(t) - характеристика i-го агента.

Отметим, что протокол (2) изучен многими авторами (см., например,

[3-5]). Известно, что если 0 — простое собственное значение лапласовской

матрицы L, то при любом векторе начальных характеристик x(0) асимпто-

тический консенсус существует и равен пределу [6]

lim x(t) = L^⊢x(0).

t→∞

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

(_α)

ставится запятая. В некоторых работах через A

обозначают минор подматрицы.

А если 0 — кратное собственное значение лапласовской матрицы L, то для

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

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

при любом векторе начальных значений? Такая проблема регуляризации воз-

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

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

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

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

ции, определяется однозначно с точностью до множителя.

К немногочисленным работам по многоагентным системам с несвязным

орграфом связей относятся [7, 10]. В [7] исследовано несколько протоколов

латентного консенсуса. В основе этих протоколов лежит добавление дополни-

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

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

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

зей к орграфу добавляется полный граф с малыми весами. Такой протокол

имеет следующее представление:

(3)

x(t) = -(L + δD)x(t),

∑_n

где δ > 0, D = I - 1v^T , v_i > 0,

v_i = 1.

i=1

В [7] в частности доказано, что если x(t) - решение системы (3), то

lim

lim x(t) = 1v^T L^⊢x(0).

δ→+0

t→∞

Если v =1n 1, то имеем

lim

lim x(t) = EL^⊢x(0),

δ→+0

t→∞

где E — матрица с элементами n-1.

Регуляризация “в духе” PageRank приводит к усреднению строк собствен-

ного проектора.

Другой метод регуляризации — метод ортогональной проекции, был пред-

ложен в [10]. Его также можно применить как для модели ДеГроота —

x_k = Pxk-1, так и для непрерывного протокола. Согласно этому методу, про-

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

симметричной идемпотентной матрицей S, отображается на подпространство

Q_L — область сходимости процедуры ДеГроота. Образ R(S) матрицы S сов-

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

столбцов матрицы I - P и вектора из единиц. Если x₀ — вектор начальных

мнений, а x′0 - преобразованный вектор, тогда |x′0 - x₀| будет минималь-

ной, поскольку матрица S - ортогональный проектор. Некоторые коорди-

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

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

P^∞S является не только стохастической матрицей, но и матрицей единич-

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

ложительные координаты, то результирующий вектор P^∞Sx₀ также будет

положительным.

Ортогональный проектор S на подпространство Q_L = R(L) ⊕ Span(1)

представляется в виде

(4)

S = UU⁺ = U(U^TU)-1U^T,

где U — матрица полного столбцового ранга r, полученная из L отбрасы-

ванием по одному столбцу, соответствующему какой-либо вершине из каж-

дой базовой бикомпоненты орграфа, и добавлением столбца 1_n в качестве

первого.

3.1. Связь между обобщенно обратной матрицей для U

и методом ортогональной проекции

Графовая интерпретация метода ортогональной проекции частично была

дана в [10] с помощью матриц X и Z (см. п. 3. теоремы 3 в [10]). В [11] была

приведена связь между обобщенно обратной матрицей для U и методом ор-

тогональной проекции для класса орграфов без небазовых вершин. В настоя-

щем разделе мы рассмотрим более общий случай, предположим, что орграф

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

не принадлежащие множеству K. Покажем, что метод ортогональной проек-

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

Пусть E₁₀ — квадратная матрица порядка n, первый столбец которой со-

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

Вначале предположим, что rank(L) = n - 1. В этом случае нет необходи-

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

достигается, и L^⊢ = E₁₀U-1.

Если rank(L) < n - 1, то

(5)

L^⊢S = L^⊢UU⁺ = E₁₀U⁺,

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

щенно обратной матрицы для U: в первом случае U-1, а во втором — U⁺.

Таким образом имеет место следующее утверждение.

Утверждение 1.

1) Если rank(L) = n - 1, то L^⊢S = L^⊢I = E₁₀U-1.

2) Если rank(L) < n - 1, то L^⊢S = E₁₀U⁺.

Из утверждения 1 следует, что если в системе достигается консенсус, то он

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

дящих деревьев орграфа коммуникаций. В свою очередь, эти веса, согласно

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

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

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

общем случае первой строкой псевдообратной по Муру-Пенроузу матрицы U.

Известно, что (см., например, Приложение А в [14]) элементы псевдообрат-

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

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

∑

⁽i₂ ... i_r)

⁽i₁ ... i_r)

det U

2...r

1...r

(6)

u+1i

= i²<...<ir ∑ (

⁽k₁ ... k_r))2

det U

1...r

k₁<...<kr

Используя (6), далее мы охарактеризуем метод ортогональной проекции

и элементы матрицы U⁺ с помощью лесной структуры орграфа связей. Для

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

рица L имеет представление (7).

⎛

⎞

L₁

···

⎜

⎟

L₂

···

⎜

⎟

⎜

⎟

(7)

⎜

⎟,

⎜

⎟

⎝₀

··· L_v

⎠

∗

···

∗ L_R

где v — число базовых бикомпонент в соответствующем орграфе, ∗ — блоки,

которые в общем случае — ненулевые, L_R — подматрица L, строки и столб-

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

det L_R равен весу множества остовных исходящих деревьев орграфа Γ_ξ, полу-

ченного из Γ “склеиванием” всех вершин из K в одну вершину ξ (см. [15]). На

рис. 1,б приведен орграф “склеиванием” базовых вершин орграфа из рис. 1,а.

)

(_i

)

(i₁...ir

2...ir

Утверждение 2. 1) Миноры detU

и det U

равны нулю, ес-

1...r

2...r

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

ствующей вершине из^K.

)

(i₂...ir

2) Минор det U

равен нулю, если множество {i₂, . . . , i_r} содержит

2...r

все вершины одной базовой бикомпоненты.

)

(i₂...ir

3) Абсолютное значение ненулевого минора det U

равно произведе-

2...r

нию detL_R на вес множества всех исходящих лесов на K c корнями из вер-

шин {1,... ,n} \ {i₂,... ,i_r}.

Утверждение 3. Пусть {j₁,...,jms} — множество всех вершин неко-

торой базовой бикомпоненты s, содержащееся в {i₁,... ,i_r}, и пусть в нем

нет вершин других базовых бикомпонент. Тогда:



)



(

)



∑



⁽i₁ ... i_r

K_p

(8)



et U



et U



^d

⁼

^d

,

1...r

2...r

p=1

где K_p = (i₁ . . . i_r) \ j_p, p = 1, . . . , m_s;

(_j

)

(_K

)

p Kp

2) det U

= 0 и detU

= 0, p = 1, . . . , m_s, имеют один и тот же

1...r

2...r

знак.

Отметим, что (i₁ . . . i_r)\j_p означает, что из упорядоченного набора (i₁ . . . i_r)

удален элемент j_p. А запись j_p K_p указывает на то, что к упорядоченному

набору K_p слева добавлен элемент j_p.

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

рая впервые была доказана в [10] для системы без небазовых агентов.

Теорема 3. Для системы с произвольным орграфом связей сумма эле-

ментов первой строки матрицы U⁺ равна 1:

∑

u+1i = 1.

i=1

Итак, метод ортогональной проекции в МАС с любым орграфом связей и

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

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

(u⁺¹¹, . . . , u+1n)(x₁(0), . . . , x_n(0))^T .

В частности, если орграф связей содержит остовное дерево, то в этом слу-

чае матрица U будет квадратной, невырожденной, и, согласно (6), выполня-

ется



(

)



(1...n)\i



((1...n)\i

det U

 detU

det U



2...n

u+1i = u-11i =

=l⊢1i.

(det U)²

det U

Последнее равенство следует из теоремы

1, согласно которой,

((1...n)\i)

|det U

| совпадает с алгебраическим дополнением любого элемента

2...n

i-й строки лапласовской матрицы орграфа связей.

Утверждение 4. Если i₁ и j₁ принадлежат одной базовой компоненте,

l⊢1i

1i1

то

u+1j

l^⊢

1j1

Используя утверждение 3, числитель выражения (6) можно представить

как

)

∑

⁽i₂ ... i_r)

⁽i₁ ... i

Σ=

det U

2...r

1...r

i₁=1 i₂<...<ir

(

∑

⁽i₁ ... i_r))2

∑∑

det U

ϱ2si,

1...r

i₁<...<ir

s=1 i=1

где q_s = (m₁m₂ · · · m_v)/m_s, s = 1, . . . , v. Для каждой базовой бикомпоненты s

с множеством вершин N_s число ϱ_si равно произведению веса множества всех

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

рованными вершинами.

Пусть P₁ = {1, . . . , m₁} — множество вершин первой базовой бикомпонен-

ты. Согласно выражению (6),

(

)

(

)

∑

∑∑

K_i

iK_i

W₁ = u+1i

=D-1

det U

2...r

1...r

i=1

i=1 K_i

(

∑

⁽P₁ im1+1 ... ir))2

(9)

=D-1

det U

=D-1

ϱ21i,

1...r

m₁+1<...<ir

i=1

где K_t = (1 . . . m₁im1+1 . . . ir) \ t, t = 1, . . . , m1. Напомним, что в (9) для каж-

дой базовой бикомпоненты s число ϱ_si равно произведению веса множества

всех деревьев базовой бикомпоненты s на произведение весов всех деревьев

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

теля блока L_R. С помощью (9) можно определить отношение сумм весов в

разных бикомпонентах.

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

∑_n

(_N\i)

(1...n)

шин m₁ = n, то из (9) в силу

det U

= detU

= det U непосред-

i=1

2...n

1...n

ственно следует:

∑

⁽N\i⁾

det Udet U

W₁ = D-1

det U

det U =

(

)₂

= 1.

2...n

i=1

det U

4. Явное выражение для собственного проектора

произведения положительной диагональной

матрицы на лапласовскую

Как было отмечено во введении, асимптотическое поведение многих мо-

делей МАС определяется свойствами собственного проектора лапласовской

матрицы орграфа связей. При этом k-й столбец характеризует “важность”

k-го агента в итоговом консенсусе. Для сильно связного орграфа связей чем

больше значения ℓ⊢1k, тем сильнее влияния k-го агента на итоговое значение.

Рассмотрим следующую задачу: если влияния других агентов на k-го агента

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

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

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

в τ_k раз, то лапласовская матрица M орграфа с новыми весами будет рав-

на T L, где L — матрица орграфа до изменения его весов, T = diag(τ₁, . . . , τ_n).

В данном разделе докажем, что собственный проектор M^⊢ можно предста-

вить как L^⊢D, где D — некоторая диагональная матрица. Согласно теореме 1

матрицы L^⊢ и M^⊢ — однотипны.

Если rankL^⊢ = 1, то очевидно, что всегда существует положительная диа-

гональная матрица D, такая, что M^⊢ = L^⊢D. Однако, если rankL^⊢ > 1, то

существование диагональной матрицы не очевидно. Кроме того, в первом

случае если не известна M^⊢, то нахождение D не является тривиальной за-

дачей.

Теорема 4. Если M = TL, где T = diag(τ₁,...,τ_n) — положительная

диагональная матрица, а L — произвольная лапласовская матрица, то су-

ществует неотрицательная диагональная матрица D, для которой имеет

место:

(10)

M^⊢ = L^⊢

Следствие 1 (из теоремы 4). Если орграф связей сильно связный, и T =

= diag(l⊢11,... ,l⊢1n), то:

1) для собственного проектора матрицы M = T L имеет место M^⊢ =

=1n11^T;

2) матрица T L — сбалансированная.

Пример 1. Рассмотрим многоагентную систему с орграфом связей, при-

веденным на рис. 1. Также рассмотрим матрицы L0R и U, первая из которых

соответствует орграфу со “склеенными” в вершину 0 базовыми бикомпонен-

тами:

⎛

⎞

-1

⎜

⎟

⎜

⎟

⎜

-4 -1

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

-4

⎜

⎟

⎜

-3 0

⎟

⎜

⎟

U =

;

⎜

⎟

⎜

⎟

⎜

⎟

-2 -3

⎜

⎟

⎜

⎟

-1

-2 0 0

⎜

⎟

⎜

⎟

⎜

-1

⎟

⎠

^⎝ 1

-4 0

-2 -2 0

⎛

⎞

⎜

-5 5

⎟

⎜

⎟

⎜

−1 0

-2 0 0

⎟

⎜

⎟

L0R =

⎜

⎟^.

-1

⎜

⎟

⎝-40

⎠

−4 0

Выясним, из каких величин складывается элемент u⁺¹⁶ матрицы U⁺. Сум-

ма в числителе выражения (6) для u⁺¹⁶ содержит шесть ненулевых слагаемых,

Рис. 2. Два леса — а и б , состоящие из трех исходящих деревьев

с корнями 2, 4 и 6.

Рис. 3. Два леса — а и б , состоящие из трех исходящих деревьев

с корнями 2, 4 и 7.

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

слагаемых равно

)

⁽1357 . .. 12

⁽613578 . .. 12⁾

det U

23 ...

12 ... 10

Согласно п. 3 утверждения 2 абсолютное значение ненулевого минора

(13578...12)

det U

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

23...10

на K с корнями {2, 4, 6} = {1, . . . , 12}\{1, 3, 5, 7, 8, . . . , 12} на det L_R = 80.

На рис. 2,а и 2,б приведены оба леса на множестве вершин K = {1, . . . , 7},

исходящие из корней {2, 4, 6}. Вес первого леса равен 8, второго — 32, т.е.

сумма весов этих лесов равна 40. Если это число умножим на вес дерева,

(13578...12)

показанного на рис. 1,б , т.е. на 80, то получится det U

= 40 · 80 =

23...10

= 3200.

(13568...12)

Аналогичную графовую интерпретацию имеет минор det U

23...10

= -60 · 80 = -4800, абсолютное значение которого равно произведению веса

множества всех исходящих лесов на K с корнями {1 . . . 12}\{1 3 5 6 8 . . . 12} =

= {2 4 7} на det L_R = 80.

На рис. 3 приведены оба леса, исходящие из корней {2, 4, 7}: вес первого

леса равен 12, а второго равен 48, т.е. сумма весов двух лесов равна 60. Итак,

(13578...12)

det U

= -60 · 80 = -4800.

23...10

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

ненты {6, 7}, то получим:



)



)



⁽613578 . .. 12



⁽713568 . .. 12



det U

=

det U

=

12 ... 10



)



)



⁽13578 . .. 12



⁽13568 . .. 12



det U

+

det U

 = 3200 + 4800 = 8000.

23 ... 10

5. Заключение

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

с использованием матрицы U⁺, ранее приведенного только для узкого клас-

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

обобщением протокола консенсуса и представляется элементами псевдообрат-

ной матрицы U⁺. Установлено, что собственный проектор матрицы T L, где

T — положительная диагональная матрица, можно представить как (TL)^⊢ =

= L^⊢D, где D — положительная диагональная матрица. Доказано, что если

орграф сильно связный, то у диагональной матрицы D все диагональные эле-

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

простой способ регуляризации произвольного орграфа.

ПРИЛОЖЕНИЕ

Доказательство утверждения 2. 1) Матрица U имеет следующий

вид:

⎛

⎞

⎛

⎞

U₁

l₁₂

··· l1k′

01,n-k

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

U =

⎜

⎟

^⎟,

⎜

⎟

⎝

⎠

lk2

··· l_kk′

01,n-k

⎝

U_v

⎠

1n-k,1

∗

L_R

1n-k,1

∗

∗ L_R

∑_v

где k^′ = k - v + 1, k =

m_i (v — число базовых бикомпонент), а матрица

i=1

L_R - квадратная и невырожденная. Предположим, что упомянутый минор

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

(_i

)

1...ir

строка с номером из множества {k + 1, . . . , n}. Тогда подматрица U

1...r

будет иметь блочно-треугольный вид, правый нижний квадратный блок L_R′

(_i

)

1...ir

которой содержит нулевую строку. Поэтому det L_R′ = 0, и det U

= 0.

1...r

2) Пусть множество {i₂, . . . , i_r} содержит все вершины {j₁, . . . , jms } од-

ной — s-й базовой бикомпоненты. Тогда подматрица со строками {j₁, . . . , jms }

)

(i₂...ir

содержит всего m_s - 1 ненулевых столбцов. Минор det U

состоит из

2...r

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

взятых из различных строк и столбцов. Поэтому каждый такой член содер-

(_i

)

2...ir

жит нулевой множитель, и минор det U

равен нулю.

2...r

)

(i₂...ir

3) Если минор det U

отличен от нуля, то согласно пункту 2), мно-

2...r

жество {i₂, . . . , i_r} состоит из m_s - 1 строк (s = 1, . . . , v) из каждой базовой

бикомпоненты и строк, соответствующих вершинам из^K. Очевидно, что ми-

нор равен определителю блочно-диагональной матрицы, т.е.

⎛

⎞

U′1

)

⎜

⎟

⁽i₂ ... i_r

⎜

⎟

det U

= det

⎜

⎟,

2...r

⎝

U^′v

⎠

∗

L_R

где матрица U^′i получена из U_i вычеркиванием одной, например, i_k-й строки.

Согласно матричной теореме о деревьях, определитель матрицы U^′i равен ми-

нору любого элемента i_k-й строки U_i и его абсолютное значение равно сумме

весов всех исходящих деревьев из i_k-й вершины i-й базовой бикомпоненты.

Это рассуждение верно для любого блока U^′t.

(_i

)

2...ir

Таким образом, абсолютное значение ненулевого минора det U

равно

2...r

произведению det L_R на вес множества всех исходящих лесов на K с корнями

{1, . . . , n}\{i₂, . . . , i_r}.

Доказательство утверждения 3. 1) Не уменьшая общности, пред-

положим, что вершины пронумерованы так, что j_p = p, p = 1, . . . , m_s. Пусть

в множестве вершин {i₁, . . . , i_r} подмножество {i₁, . . . , i_r′ }, где r^′ = r - |K|,

является подмножеством множества базовых вершин. Рассмотрим определи-

(1...m

)

s...ir

тель det U

и представим его в блочном виде как

1...r

⎛

⎞

l₁₂

l1ms

01,r′-ms

⎜

⎟

⎜

⎟

⎜

⎟

det

⎜

⎟=

lms2

··· lmsms

01,r′-ms

⎜

⎟

⎝

···

⎠

1_r′-p,1

0r′-p,1

Q_r′-ms

∗

L_R

⎞

^⎛ Qms

= det ^⎝

∗ Q_r′-ms

⎠_.

∗

L_R

Согласно матричной теореме о деревьях 2, алгебраическое дополнение пер-

вого элемента любой k-й строки блока Qms равно сумме весов деревьев, ис-

ходящих из вершины k. Поэтому определитель матрицы Qms равен сумме

весов всех исхдящих деревь)в базовой бикомпоненты с множеством вершин

(1...m



s...ir

{1, . . . , m_s}, а

detU

 — произведению суммы весов всех исходящих

1...r

деревьев базовой бикомпоненты с вершинами {1, . . . , m_s} на |det Q_r′-ms |, ко-

торый равен сумме весов максимальных исходящих лесов на K \ {1 . . . m_s} с

вершинами: K\{i₁, . . . , i_r′ }, и на det L_R. Таким образом, выполняется равен-

ство (8).

)

(_K

)

(jp Kp

2) Покажем, что знаки миноров det U

= 0 и detU

= 0, p =

1...r

2...r

= 1, . . . , m_s, совпадают.

)

∑ms

(i₁...ir

Заметим, что det U

(-1)1+k+ldet Usk1ξ = (-1)^lζξ, где l — чис-

1...r

k=1

)

(i₁...ir

ло строк в U

до s-й базовой бикомпоненты, U^s = (1ms U_s), ζ > 0 —

1...r

вес множества всех исходящих деревьев в s-й базовой бикомпоненте, ξ —

(_j

)

p Kp

произведение определителей других блоков. Поскольку U

отличается

)

1...r

(i₁...ir

от U

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

1...r

только знаком и имеет место

)

⁽j_pK_p

⁽i₁ ... i_r)

det U

= detU

(-1)l+p-1 = (-1)2l+p-1ζξ,

1...r

где p — номер строки в s-м блоке.

)

(jp Kp

Итак, знак det U

равен (-1)p-1ξ. Легко можно установить, что

1...r

(_K

)

det U

имеет знак (-1)p+1ξ.

2...r

Доказательство теоремы 3. В силу (6) сумму элементов первой

строки U⁺ можно записать как

∑

Σ_K + ΣK

(Π.1)

u+1i

i₁∈N

где Σ_K соответствует элементам из K, член Σ K — вершинам из^K = N \ K, а

(

∑

⁽i₁ ... i_r))2

det U

1...r

i₁<...<ir

Согласно п. 1 утверждения 2, если множество {i₁, . . . , i_r} содержит не все вер-

)

(i₁...ir

шины из^K, то соответствующий член det U

в представлении D равен

1...r

нулю. Также, в силу п. 1 утверждения 2 имеет место

∑

⁽i₂ ... i_r)

⁽i₁ ... i_r)

ΣK =

det U

= 0.

2...r

1...r

i₁∈K i2<...<ir

Отметим, что в Σ_K и D входит множитель det L_R. Доказательство равен-

ства единице соотношенияΣKD^{приведенов[11].}

Доказательство утверждения 4. Справедливость данного утвер-

ждения следует из представления u⁺ . Действительно, все соответствующие1k

(_i

)

1...ir

(j₁...jr

множители det U

, det U

в выражении (6) для u+1i

и u⁺ отлича-1j

1...r

)

(_j

)

(i₂..

.ir

2...jr

ются только знаком, а det U

и detU

— весами исходящих дере-

2...r

вьев из i₁ и j₁.

Доказательство теоремы 4. Теорему докажем конструктивно, т.е.

построим такую диагональную матрицу D. Не уменьшая общности, предпо-

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

также построим вспомогательную матрицу B^L (Π.2), которая получена из L

заменой первого столбца в каждом блоке L_s, соответствующем базовой би-

компоненте s, на столбец из единиц:

⎛

⎞

BL1

···

⎜

⎟

⎜

BL2 ···

⎟

(Π.2)

B^L =^⎜

⎟,

⎜

⎟

⎝₀

⎠

··· B^Lv

∗

···

∗ L_R

диагональные блоки B^Ls, s = 1, . . . , v, для матрицы B^L определены как

⎛

⎞

ls12

1ms

⎜

⎟

⎜

ls22

ls2ms

⎟

(Π.3)

B^Ls =

⎜

⎟

⎝

⎠

... l^s

lsms2

msms

Аналогично B^L и B^Ls, определим матрицы B^M и B^Ms для M.

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

строки L на τ_i. Определим собственный проектор M^⊢ согласно п. 1 теоре-

мы 1:

ε(F^j→i)

(Π.4)

m^⊢ij =

ε(F)

Согласно теореме 2 для каждой s-й базовой бикомпоненты сумма весов

всех исходящих деревьев (на множестве всех вершин из данной базовой би-

компоненты) равна det(B_s). Поэтому ε(F) = det(B^M ).

Пусть ни в одном максимальном исходящем лесе вершина i не достижима

из j. Так как графы, соответствующие лапласовским матрицам L и M = T L,

имеют одинаковую структуру, то m^⊢ij = l^⊢ij = 0.

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

се i достижима из j, причем j является вершиной из s-й базовой бикомпо-

ненты. Обозначим через {Γ_k(V, E_k)} множество всех остовных подграфов,

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

орграфов, в которых i достижима из корневой вершины j, с добавлением к

ним всех недостающих дуг из базoвых бикомпонент. Пусть BLk и BMk — со-

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

B^L и B^M . Диагональные блоки BLk и BMk, которые соответствуют базовым

бикомпонентам, совпадают с аналогичными блоками матриц B^L и B^M со-

ответственно. Очевидно, что число ε(F^j→i) для орграфа, соответствующего

матрице M, равно сумме алгебраических дополнений элементов (j, i^′) мат-

∑

, где i^′ ∈ {1, . . . , n} — номер столбца BMk ,

i^′

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

вующей базовой бикомпоненте s.

Пусть j^′ ∈ {1, . . . , m_s} — номер строки блока с номером s, который соот-

ветствует строке j.

Важно подчеркнуть, что в отличие от i^′, номер j^′ указывает на строку

блока s. Тогда в силу B^Mq = BMkq для всех q и k получим

∑

M^k

ji^′

det B

ε(F^j→i)

m^⊢ij =

ε(F)

=^kdetBM



)

∏



∑

⁽(1 . . . m_s) \ j^′



det B^Mq

et B^M

det M^kR

^d



2...m_s

q=1,q=s

∏

det M_R det B^M

q=1



((1...m

)∑



s)\j^′

det B^s



det M^kR

2...ms

det M_Rdet B^Ms

Отметим, что L^kR и M^kR — блоки, соответствующие небазовым вершинам

в матрицах BLk и BMk соответственно. Далее полученное выражение пред-

ставляем через матрицу L:



)

∏



∑

⁽(1 . . . m_s) \ j^′



τ_i

et L^M

det L^kR

^d



2...m_s

m^⊢ij =i=1,i=j′

)

∑

⁽(1 . . . .m_s) \ p

τ_i

det B^L

det L_R

τ_p

2...m_s

i=1

p=1



((1...m

) ∑

s)\j^′

det L^Ms



det L^kR

2...ms

)

∑

⁽(1 . . . m_s) \ p

τ_j

det B^L

det L_R

τ_p

2...m_s

p=1

∏_v

Знаменатель и числитель домножим на

det(B^Li). Заметим, что данное

i=1

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

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

состоит только из базовых бикомпонент. Тогда:



∏

((1...m

)∑



s)\j^′

detL^Ms



det L^kR det B^L

det B^Lq

2...ms

q=s

m^⊢ij

)

∑

∏

⁽(1 . . . .m_s) \ p

τ_j

det B^L

det L_R

det B^L

τ_p

2...m

p=1

q=1

Заметим, что в последней дроби



∏

((1...m

) ∑



s)\j^′

det L^Ms



det L^k

det B^Lq

2...ms

q=s

l^⊢ij

∏

det L_R det B^L

q=1

Тогда

det B^Ls

(Π.5)

m^⊢ij = l^⊢

τ_jdetC_s

где матрицы C_s, s = 1, . . . , v, определены следующим образом:

⎛

⎞

ls12

ls1ms

τs1

⎜

⎟

⎜

⎟

⎜

ls22

ls2ms

⎟

⎜

τs2

⎟

(Π.6)

C_s =

⎜

⎟

⎜

⎟

⎜

⎟

⎝₁

⎠

lsms2

... l^s

msms

τ^s

Построим две диагональные матрицы F = diag(f₁, . . . , f_n) и H =

= diag(h₁,... ,h_n) следующим образом: f_t = detB^Ls и h_t = detC_s, если вер-

шина t принадлежит s-й базовой бикомпоненте. Для всех остальных диаго-

нальных элементов матриц F и H положим f_t = h_t = 1.

Тогда

(Π.7)

M^⊢ = L^⊢T-1FH-1 = L^⊢

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

В частности, она может принадлежать некоторой базовой бикомпоненте.

СПИСОК ЛИТЕРАТУРЫ

1. Olfati-Saber R., Fax J.A., Murray R.M. Consensus and cooperation in networked

multi-agent systems // Proceedings of the IEEE. 2007. V. 95. No. 1. P. 215-233.

2. Jadbabaie A., Lin J., Morse A.S. Coordination of groups of mobile autonomous

agents using nearest neighbor rules // IEEE Transactions on automatic control.

2003. V. 48. No. 6. P. 988-1001.

3. Olfati-Saber R.M., Murray R.M. Consensus Problems in Networks of Agents with

Switching Topology and Time-Delays // IEEE Trans. Automat. Control. 2004. V. 49.

No. 9. P. 1520-1533.

4. Ren W., Beard R.W., Atkins E.M. Information consensus in multivehicle cooperative

control // IEEE Control systems magazine. 2007. V. 27. No. 2. P. 71-82.

5. Mesbahi M., Egerstedt M. Graph theoretic methods in multiagent networks / Graph

Theoretic Methods in Multiagent Networks. Princeton University Press, 2010.

6. Chebotarev P., Agaev R. The Forest Consensus Theorem // IEEE Trans. Automat.

Control. 2014. V. 59. No. 9. P. 2475-2479.

7. Агаев Р.П., Чеботарев П.Ю. Модели латентного консенсуса // АиТ. 2017. № 1.

C. 106-120.

8. Agaev R.P. On the role of the eigenprojector of the Laplacian matrix for reaching

consensus in multiagent second-order systems // Autom. Remote Control. 2019.

Т. 80. No. 11. P. 2033-2042.

9. Гантмахер Ф. Теория матриц. М.: Наука, 1967.

10. Агаев Р.П., Чеботарев П.Ю. Метод проекции в задаче о консенсусе и регуляри-

зованный предел степеней стохастической матрицы // АиТ. 2011. № 12. C. 38-59.

11. Agaev R., Khomutov D. Graph Interpretation of the Method of Orthogonal

Projection for Regularization in Multiagent Systems

14th International

Conference “Management of Large-scale System Development” (MLSD). IEEE. 2021.

P. 1-4.

12. Rothblum G. Computation of the eigenprojection of a nonnegative matrix at its

spectral radius / Stochastic Systems: Modeling, Identification and Optimization, II.

Springer, Berlin, Heidelberg. 1976. P. 188-201.

13. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989.

14. Ben-Israel A., Greville T.N.E. Generalized Inverses: theory and applications (Second

Edition). Springer, 2003.

15. Fiedler M., Sedláček J.O. W-basich orientovanych grafu //

Časopis pro pěstováni

matematiky. 1958. V. 83. No. 2. P. 214-225.

Статья представлена к публикации членом редколлегии М.В. Губко.

Поступила в редакцию 16.06.2022

После доработки 25.12.2022

Принята к публикации 29.12.2022