# Точное усреднение в сети за 2N сложений обратной подстановкой: анализ и численный тест на 53 узлах

- Опубликовано: 2026-11-11 14:53 UTC
- Раздел: Цифра и вычисления › Софт и сервисы
- Теги: консенсус по среднему, распределённое усреднение, обратная подстановка, матрица Лапласа графа, метод собственных шагов, перестановка Катхилла — Макки, графовый КИХ-фильтр, ориентированные графы, численная устойчивость, Applied Network Science
- Адрес: https://realtech.media/ru/news/rt-a08b31a659c9945247503ca0_tochnoe_usrednenie_v/

**Математическая работа в Applied Network Science описывает точный метод консенсуса по среднему, не требующий умножений при вычислении. Его проверили численно на графе из 53 узлов.**

![Exact network averaging in 2N additions by back substitution: analysis and 53-node numerical test](https://realtech.media/media/2026/11/d4307f1f4254bd85.jpg)
*Aeroprints.com, Wikimedia Commons, CC BY-SA 3.0*

Исследователь Ricardo Merched опубликовал в журнале Applied Network Science математическую работу о консенсусе по среднему: как N агентов кооперативной сети находят точное арифметическое среднее разрозненных локальных данных без центрального процессора. По данным статьи, на неориентированном связном графе точное среднее можно вычислить рекурсиями прямой и обратной подстановки при полной сложности всего от 2N сложений [1]. Для неориентированных графов существующие схемы требуют O(KN²) умножений, где K — число различных собственных значений матрицы Лапласа графа [1].

Автор формулирует консенсус по среднему как задачу наименьших квадратов с линейным ограничением. Из неё получается разреженный нижнетреугольный матричный множитель: суммы его столбцов равны нулю, а разреженность совпадает с физическими связями между узлами [1].

## Обратная подстановка вместо обращения матрицы

На этапе проектирования, до запуска, симметричная перестановка обратного Катхилла — Макки приводит граф к блочно-трёхдиагональному профилю. Узлы затем выполняют трёхпроходный последовательный алгоритм из прямой и обратной подстановок, который обходит обращение плотной матрицы, нужное для проекций минимальной нормы [1].

Треугольный множитель можно задать с постоянными элементами 1 и −1 под главной диагональю, поэтому при вычислении умножения не нужны. Сеть получает точное среднее за 2N шагов обмена, всего с 2N сложениями. Треугольные подстановки обратно устойчивы, поэтому, как сообщает работа, результат не зависит от алгебраической связности графа и обусловленности его матрицы Лапласа [1].

В работе также дана альтернативная точная форма — матричный графовый фильтр с конечной импульсной характеристикой. Строго нижнетреугольная часть переупорядоченного множителя нильпотентна, поэтому ряд Неймана конечен. В графе из 53 узлов оператор обратился в нуль за 23 итерации, а вся операция заняла 47 матричных проходов со сложностью порядка N² сложений [1].

## Почему метод собственных шагов численно неустойчив

Конечновременной метод собственных шагов (eigenstep) использует переменные шаги, равные обратным величинам различных ненулевых собственных значений матрицы комбинирования; в теории это гасит моды расхождения за K итераций. Статья показывает, что ненормированные рекурсии численно неустойчивы на больших или плохо обусловленных матрицах: шаги намного превышают пороги устойчивости и умножают ошибки округления при вычислениях с конечной точностью [1].

Для старших мод автор выводит оценку усиления ошибки первого порядка: число обусловленности спектра минус единица в степени, пропорциональной размерности сети. В тесте на неориентированной сети из 53 узлов с ветвью-путём машинная ошибка округления около 2,22×10⁻¹⁶ выросла до порядка 10⁴², и сеть не достигла консенсуса [1].

Работа также обобщает метод собственных шагов на ориентированные графы с несимметричными матрицами комбинирования. Теорема 1 утверждает, что переменные собственные шаги сходятся ровно за K шагов для диагонализируемых несимметричных матриц [1].

## Источники

1. [Applied Network Science](https://doi.org/10.1007/s41109-026-00795-2)
2. [bioengineer.org](https://bioengineer.org/exact-network-consensus-method-cuts-multiplications-using-ordered-back-substitution)

---

Источник: RealTech, realtech.media — https://realtech.media/ru/news/rt-a08b31a659c9945247503ca0_tochnoe_usrednenie_v/