Представьте себе FPV-дрон, который должен мгновенно стабилизироваться после резкого маневра уклонения, чтобы нанести точный удар. Или крылатую ракету, огибающую рельеф местности на сверхмалой высоте, где любая ошибка в расчетах приведет к удару о землю. Или гражданскую ступень Falcon 9, совершающую посадку на морскую платформу.

Что объединяет эти процессы? За каждым из них стоит незримая, но железная логика теории устойчивости.

Если вы когда-нибудь занимались теорией управления (Control Theory), вы знаете этот страх: система может пойти вразнос. Чтобы этого не случилось, инженеры и математики используют один мощный инструмент — Уравнение Ляпунова. Это тот самый «серый кардинал» линейной алгебры, который отвечает на главный вопрос жизни, Вселенной и всего такого (в инженерном смысле): «упадет или не упадет?»

В чем проблема? Почему нельзя просто «посмотреть»?

Казалось бы, зачем нам сложные матрицы? Хочешь узнать, устойчива ли ракета — запусти симуляцию на 10 минут модельного времени. Если не упала — значит, устойчива.

Но симуляция — это «черный ящик». Она говорит «что» произошло, но не говорит «почему». А главное, она не дает гарантий. Если ракета не упала за 10 минут, упадет ли она за 11? А если ветер подует чуть сильнее?

Уравнение Ляпунова дает алгебраический критерий. Оно превращает вопрос о будущем (динамика, время) в вопрос о структуре (алгебра, матрицы). Решив его один раз, мы получаем математическую гарантию устойчивости для любых начальных условий.

О чем эта статья?

Я взял за основу хорошую, но, к сожалению, краткую англоязычную статью про Lyapunov equation, полностью перевел её и, самое главное, насытил дополнительным контентом:

• ? Python-код: реализация методов и визуализация.

• ? Интуиция: объяснения «на пальцах», зачем нам это нужно.

• ? Визуализация: от «шарика в чаше» до векторных полей.

• ⚙️ Алгоритмическая магия: разбор того, как уйти от чудовищной сложности к элегантной с помощью разложения Шура.

Зачем это здесь?

Это пре-релиз статьи для русской Википедии.

Я выкладываю материал на суд сообщества Хабра. Я хочу, чтобы мы вместе сделали лучший материал по этой теме в рунете.

Моя просьба к вам:

1. Читайте с пристрастием. Если видите математическую неточность или знаете, как объяснить проще — пишите в комментариях.

2. Забирайте код. Он рабочий, его можно использовать для своих лаб или проектов.

3. Поддержите пост. Если вам нравится идея качественного научпопа — ставьте лайк и стрелку вверх. Чем больше людей увидит, тем качественнее станет итоговая статья в энциклопедии.

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

---

Уравнение Ляпунова

Уравнение Ляпунова — это линейное матричное уравнение, играющее фундаментальную роль в теории автоматического управления, дифференциальных уравнениях и анализе устойчивости динамических систем.

Оно названо в честь математика Ляпунова, который в 1892 году в своей докторской диссертации «Общая задача об устойчивости движения» заложил основы современной теории устойчивости.

Уравнение связывает динамику системы (матрицу ) с её энергетическими характеристиками (матрицы и ). Существует две основные формы уравнения: для непрерывного и для дискретного времени.

Непрерывное уравнение Ляпунова

Для линейной системы, описываемой дифференциальным уравнением , непрерывное уравнение Ляпунова записывается как:

Дискретное уравнение Ляпунова

Для дискретной системы (часто называемое уравнением Стейна) оно имеет вид:

Расшифровка обозначений

*   (System Matrix): Квадратная матрица описывающая динамику системы (закон, по которому система изменяет свое состояние).

*   (Unknown Matrix): Искомая эрмитова (или симметричная) матрица . В контексте теории устойчивости она определяет функцию Ляпунова которую можно интерпретировать как «обобщенную энергию» системы.

*   (Given Matrix): Известная эрмитова матрица . Она задает скорость диссипации (рассеивания) энергии. Обычно выбирается положительно определенной ().

*   (Hermitian Transpose): Эрмитово-сопряженная матрица к (транспонирование с комплексным сопряжением). Если все элементы матрицы — вещественные числа (что чаще всего встречается в инженерных задачах), то заменяется на обычное транспонирование .

Происхождение уравнения

Форма уравнения Ляпунова — это не случайный набор символов, а прямой результат дифференцирования «энергии» системы.

Вывод для непрерывного времени

Представим, что мы хотим проверить устойчивость системы Согласно методу Ляпунова, система устойчива, если её «энергия» со временем убывает.

Пусть энергия задается квадратичной формой:

где — положительно определенная матрица.

Найдём скорость изменения этой энергии по времени ():

Подставим уравнение динамики и (сопряженное ):

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

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

или, в более привычной форме:

(Примечание: Если эрмитова, то , и порядок умножения или зависит от конвенции вектора-строки или столбца, но суть — сумма двух слагаемых — остается неизменной)

Вывод для дискретного времени

В дискретном случае время течет шагами . Условие устойчивости: энергия на следующем шаге должна быть меньше, чем на текущем.

Подставим в формулу энергии :

Теперь запишем разность энергий:

Приравниваем эту разность к отрицательной величине диссипации и получаем уравнение:

Физический и геометрический смысл

Физическая аналогия: чаша и трение

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

• Матрица определяет форму чаши. Если «положительно определена», то чаша имеет дно, и шарик теоретически может скатиться в самую нижнюю точку (положение равновесия). Чем больше собственные числа , тем круче стенки чаши.

• Матрица определяет силу трения (или скорость потери энергии).

• Уравнение Ляпунова решает обратную задачу

  "У меня есть система с динамикой и я хочу, чтобы энергия терялась со скоростью . Какой формы должна быть чаша ?"

  Если решение получается положительным (правильная чаша с дном), значит, система действительно устойчива. Если же решения нет или получается «седловидной» (с перегибом, куда шарик может улететь в бесконечность), значит, система неустойчива.

Геометрический смысл: эллипсоиды

Геометрически уравнение (где — константа) задает в пространстве состояний -мерный эллипсоид.

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

Решить уравнение Ляпунова — значит найти такую ориентацию и сплюснутость эллипсоидов (матрицу ), чтобы векторы скорости системы во всех точках пространства смотрели строго внутрь этого эллипсоида (образовывали тупой угол с вектором нормали).

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

Красные контуры представляют линии уровня функции Ляпунова , форма которых определяется решением уравнения .

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

Применение к анализу устойчивости

Этот раздел описывает «сердце» применения уравнения Ляпунова. Главная ценность приведенных ниже теорем заключается в том, что они превращают сложную задачу анализа дифференциальных уравнений (где нужно предсказывать будущее системы) в задачу линейной алгебры (где нужно просто решить уравнение).

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

Основная идея: «обратный подход»

Обычно метод функций Ляпунова работает так: мы угадываем функцию энергии и проверяем, убывает ли она. Угадать такую функцию для сложной системы — искусство.

Уравнение Ляпунова позволяет действовать наоборот:

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

2.  Мы спрашиваем математику: «какая форма "чаши" обеспечит такое убывание для нашей системы ?»

3.  Мы решаем уравнение относительно .

4.  Вердикт: если полученная матрица оказывается положительно определенной (, то есть чаша имеет дно), то система устойчива. Если же не является таковой (например, у неё есть отрицательные собственные числа), то система неустойчива.

Случай непрерывного времени

Для системы, описываемой уравнением .

Теорема

Система является глобально а��имптотически устойчивой (все траектории сходятся к нулю) тогда и только тогда, когда для любой заданной симметричной положительно определенной матрицы (например, ) решение уравнения

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

Простой пример (скалярный случай)

Пусть наша система — это просто число: .

*   Устойчивый случай ():

    Уравнение Ляпунова превращается в .

    Возьмем (положительное число).

 

Результат: .

Это «правильная» энергия . Система устойчива.

*   Неустойчивый случай ():

Результат: .

Энергия перевернута (холм вместо ямы). Положительно определенного решения не существует. Система неустойчива.

Геометрический смысл

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

*   Вектор — это скорость потока.

*   Вектор — это нормаль к эллипсоидам энергии.

*   Уравнение гарантирует, что во всех точках пространства угол между скоростью и нормалью тупой (косинус <0). Это заставляет поток течь «вниз» по уровням энергии к центру.

Случай дискретного времени

В отличие от непрерывного времени, где система «течет» как вода (плавно изменяя состояние), в дискретном времени система совершает мгновенные «прыжки» или шаги:

Уравнение динамики:

Здесь матрица — это инструкция для прыжка: «в��зьми вектор , умножь его на и перенеси в новую точку ».

Теорема

Линейная система является глобально асимптотически устойчивой (со временем затухает в ноль) тогда и только тогда, когда для любой положительно определенной матрицы решение уравнения:

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

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

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

Почему уравнение выглядит иначе?

В непрерывном мире мы требовали, чтобы скорость изменения энергии была отрицательной (). В дискретном мире понятий «скорость» или «производная» нет. Вместо этого мы сравниваем энергию «завтра» и энергию «сегодня».

1.  Энергия сегодня: .

2.  Энергия завтра (после прыжка):

3.  Изменение энергии за один шаг:

Мы требуем, чтобы было отрицательным (система теряет энергию на каждом шаге). Отсюда и получается уравнение:

Матрица "энергии завтра" минус Матрица "энергии сегодня" равна минус Диссипация.

Простой пример (скалярный случай)

Пусть система — это банковский счет, где сумма умножается на коэффициент каждый месяц: .

Уравнение Ляпунова для скаляров: .

*   Устойчивый случай (инфляция съедает деньги)

Пусть (деньги уменьшаются вдвое). Зададим скорость потерь .

Результат: Мы нашли «правильную чашу». Система устойчива.

*   Неустойчивый случай (депозит растет): Пусть (деньги удваиваются).

    Результат: . Решение отрицательное (перевернутая горка). Устойчивости нет.

Геометрический смысл: прыжки по эллипсам

Представьте себе стадион с беговыми дорожками в форме эллипсов. Самый маленький эллипс — в центре.

*   Каждый эллипс — это уровень энергии .

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

  Решить уравнение Ляпунова — значит подобрать такую форму дорожек (матрицу $P$), чтобы при любом прыжке из любой точки бегун гарантированно приземлялся на дорожку, которая находится ближе к центру, чем та, с которой он прыгнул.

Визуализация прыжков

На графике мы покажем траекторию системы. Точки — это положения системы на шагах . Пунктирная линия показывает последовательность. Фон — линии уровня функции Ляпунова. Обратите внимание: в отличие от непрерывного случая, траектория не обязана касаться линий уровня под определенным углом. Она просто должна "перепрыгнуть" через линию уровня внутрь.

Визуализация: сравнение устойчивой и неустойчивой систем

Для иллюстрации давайте создадим график, где решим уравнение Ляпунова для двух случаев.

1.  Случай А (устойчивый): Спираль, скручивающаяся внутрь. Матрица задает эллипсы, которые «обнимают» траектории.

2.  Случай Б (неустойчивый): Спираль, раскручивающаяся наружу. Если мы попытаемся решить уравнение с , мы получим матрицу , которая не будет положительно определенной (это будет седловая поверхность, будет неопределенной знака), что сигнализирует о неустойчивости.

---

Методы решения: между красотой и эффективностью

Здесь начинается самое интересное.

Глядя на уравнение , любой, кто проходил курс линейной алгебры, скажет: «Эй, так это же линейное уравнение! Давайте просто выразим ».

И формально он будет прав. Но дьявол, как всегда, кроется в деталях — а точнее, в вычислительной сложности.

Если мы попробуем решить это уравнение «в лоб», как обычную систему , нас ждет катастрофа. Для матрицы размером сложность такого решения составит .
Чтобы вы понимали масштаб трагедии: для матрицы (что в инженерии считается небольшим размером) количество операций будет порядка .

Ваш ноутбук не скажет вам спасибо.

К счастью, умные люди (Бартелс, Стюарт, Китагава) придумали, как использовать структуру уравнения, чтобы снизить сложность до приемлемых .

Давайте разберем два подхода:

«наивный» (аналитический) и «профессиональный» (численный).

---

1. Аналитический подход (или «Ловушка Кронекера»)

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

Идея проста: давайте превратим матрицу в длинный вектор-столбец , просто поставив её столбцы друг под другом. Тогда матричное уравнение превращается в классическую систему линейных уравнений:

Для формирования матрицы используется произведение Кронекера ().

---

Врезка: Что такое произведение Кронекера?

Если обычное умножение матриц — это «строка на столбец», то произведение Кронекера — это «матрица в матрице», своего рода математический фрактал.

Представьте, что у нас есть маленькая матрица размером и любая матрица . Произведение получается так: мы берем матрицу и заменяем каждый её элемент на целую матрицу , умноженную на этот элемент.

Визуально это выглядит так:

Если тоже размером , то результат раздуется до :

Именно этот оператор позволяет «распаковать» матричное уравнение в одну длинную систему линейных уравнений. Но цена за это удобство — квадратичный взрыв размеров. Матрица превращается в монстра .

---

В непрерывном времени () уравнение трансформируется в:

В дискретном времени () — в:

В чем подвох?

В размере матрицы .

Если исходная система имела размерность , то новая система имеет размерность . Матрица коэффициентов при этом становится монстром размером .

• При эта матрица содержит элементов.

• Решение системы методом Гаусса требует куба от размерности: .

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

2. Взгляд физика: интегралы и ряды

Если система устойчива, решение уравнения Ляпунова можно записать в явном виде, который имеет глубокий физический смысл.

Это сумма (или интеграл) всей «истории» энергии системы.

Непрерывное время

Если матрица гурвицева (все собственные числа имеют отрицательную вещественную часть, ), решение можно представить как интеграл:

Что это значит?
Это накопленная энергия отклика системы на начальное возмущение.
Проверить это легко. Вспомните скалярный случай (где ). Его решение:

Матричная формула — это прямое обобщение этого интеграла.

Дискретное время

Если матрица шуровская (все собственные числа лежат внутри единичного круга, ), интеграл заменяется на бесконечную сумму:

Это матричный аналог геометрической прогрессии. Для скаляра (или ) решение выглядит как:

Но как считать это на компьютере быстро?
Интегралы и ряды считать долго. Векторизация убивает память.
Здесь на сцену выходит «тяжелая артиллерия» численных методов — алгоритм Бартелса — Стюарта, основанный на разложении Шура. О нем и пойдет речь дальше.

Сравнение методов решения уравнения Ляпунова.

Сверху. График демонстрирует «проклятие размерности». Наивный метод решения через векторизацию (красная линия, ) становится вычислительно невозможным уже для небольших матриц, в то время как специализированные алгоритмы (зеленая линия, ) остаются эффективными.

Снизу. Геометрическая интерпретация аналитических решений для устойчивых систем. Решение представляет собой накопленную сумму реакций системы: площадь под кривой затухания (для непрерывного времени) или сумму убывающих импульсов (для дискретного времени).

3. Численное решение (алгоритм Бартелса — Стюарта)

В инженерной практике — будь то стабилизация ракеты, управление роботом, дроном или балансировка энергосети — размерности матриц легко достигают .
Как мы выяснили выше, «наивный» метод здесь потребует операций. Если ваш компьютер выполняет миллиард операций в секунду, ждать решения придется около 30 лет.

Нам нужно что-то побыстрее.

Бартелс и Стюарт предложили алгоритм, который стал «золотым стандартом». Именно он работает под капотом, когда вы вызываете lyap в MATLAB, scipy.linalg.solve_continuous_lyapunov в Python или функции библиотеки LAPACK.

Главная идея: «удобная система координат»

Сложность решения системы линейных уравнений напрямую зависит от формы матрицы.

• С плотной (заполненной числами) матрицей работать тяжело и дорого.

• С квазитреугольной матрицей (где почти половина элементов — нули) уравнения решаются мгновенно, методом простой подстановки.

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

Пошаговый разбор (для уравнения )

Шаг 1. Разложение Шура (Schur Decomposition)

Это фундамент метода. Мы ищем такую ортогональную матрицу , которая приведет к верхнему квазитреугольному виду .

• : Ортогональная матрица (). Она отвечает за переход в новый базис.

• : Верхняя квазитреугольная матрица. На диагонали такой матрицы стоят блоки (вещественные собственные числа) и (вещественные блоки, соответствующие комплексно-сопряженным собственным числам). Ниже — нули.

Как это считается?
Матрицы и не падают с неба. Для их нахождения используется итерационный QR-алгоритм (обычно с двойным сдвигом Фрэнсиса). Он последовательно «вычищает» поддиагональные элементы, пока матрица не примет нужную форму.

Если вы хотите разобраться, как именно работает эта магия под капотом (от вращений Гивенса до сходимости), я подробно разобрал механику QR-алгоритма в своем курсе: Численные методы: QR-алгоритм и разложение Шура. Рекомендую заглянуть, если хотите понимать, что происходит внутри scipy.linalg.schur.

Алгоритм приведения к верхнетреугольной форме.

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

Матрица имеет верхне-гессенбергову форму, если , при .

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

Шаг 1. Первый столбец

Вместо того чтобы занулять элементы, начиная со 2-го (), мы будем занулять, начиная с 3-го ().
Элемент останется (это будет поддиагональ).

Вектор для построения Хаусхолдера берется из части первого столбца:

Матрица преобразования будет иметь блочный вид:

Где — матрица Хаусхолдера размера .

Что происходит при умножении?

1. Слева (): действует только на строки . Она создает нули в позициях и ниже.

   

   (Жирным выделен измененный первый столбец).

2. Справа (): Теперь мы умножаем результат на .
   

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

   первый столбец.

   Поэтому наши нули остаются на месте!

Шаг 2. Второй столбец

Теперь мы работаем со вторым столбцом. Мы хотим занулить элементы ниже (то есть ).
Мы строим матрицу , которая оставляет нетронутыми уже первые две строки и столбца.

Умножение слева создаст нули под . Умножение справа перемешает столбцы , не затрагивая столбец 1 и 2.

Итог алгоритма

Повторяя этот процесс раза, мы получаем матрицу, у которой под главной диагональю есть еще одна линия ненулевых элементов, а всё что ниже — нули. Это и есть Верхняя форма Хессенберга.

Именно с этой формы стартует QR-алгоритм Фрэнсиса (гонка за горбом), так как один шаг QR-итерации для такой матрицы стоит , а не .

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

import numpy as np

def householder_reflection(v):
    """Возвращает матрицу отражения, обнуляющую вектор v ниже первого элемента."""
    n = len(v)
    x = np.array(v, dtype=float)
    norm = np.linalg.norm(x)
    if norm == 0:
        return np.eye(n)
    
    # Выбор знака для точности
    sign = np.sign(x[0]) if x[0] != 0 else 1
    x[0] += sign * norm
    x /= np.linalg.norm(x)
    
    return np.eye(n) - 2 * np.outer(x, x)

def to_hessenberg(A):
    """Приводит матрицу A к форме Хессенберга подобием."""
    A_h = A.copy()
    n = A_h.shape[0]
    
    for k in range(n - 2):
        # 1. Берем вектор под диагональю k-го столбца
        # Нам нужно занулить элементы начиная с A[k+2, k]
        x = A_h[k+1:, k]
        
        # 2. Строим отражение
        P_small = householder_reflection(x)
        
        # 3. Расширяем до полного размера (блочная матрица)
        # | I_k+1   0   |
        # |  0    P_small |
        H_k = np.eye(n)
        H_k[k+1:, k+1:] = P_small
        
        # 4. Применяем подобие: H A H^T
        # Умножение слева (работа со строками)
        A_h = H_k @ A_h
        # Умножение справа (работа со столбцами)
        A_h = A_h @ H_k.T
        
    return A_h

# Тест
if __name__ == "__main__":
    np.set_printoptions(precision=4, suppress=True)
    A = np.random.randn(5, 5)
    H = to_hessenberg(A)
    
    print("Исходная матрица A:\n", A)
    print("\nФорма Хессенберга H:\n", H)
    
    # Проверка собственных чисел (должны совпадать)
    print("\nСобств. числа A:", np.sort(np.linalg.eigvals(A).real))
    print("Собств. числа H:", np.sort(np.linalg.eigvals(H).real))

Примечание. О двойном сдвиге Френсиса.

Двойной сдвиг Фрэнсиса (Francis Double Shift) — это гениальный алгоритмический трюк в численно линейной алгебре, который делает QR-алгоритм применимым на практике для вещественных матриц. Если говорить просто: это способ найти комплексные собственные числа вещественной матрицы, не выходя при этом в комплексную арифметику.

В чем проблема обычного QR-алгоритма?

Чтобы найти собственные числа, QR-алгоритм использует сдвиги (shifts) для ускорения сходимости. Обычно в качестве сдвига берется элемент из нижнего правого угла матрицы (). Но у вещественных матриц часто бывают комплексные собственные числа (они всегда идут парами: и ).

• Если мы хотим найти такое число, нам нужно сделать сдвиг на комплексное число .

• Как только мы вычитаем комплексное из вещественной матрицы (), вся матрица становится комплексной.

• Последствия: Объем памяти вырастает в 2 раза, количество операций умножения — в 4 раза. Это дорого и неэффективно.

Идея Фрэнсиса: «Ходим парами»

Джон Фрэнсис (John Francis) придумал, как обойти это ограничение.
Вместо одного шага со сдвигом , давайте сделаем сразу два шага подряд: один со сдвигом , а второй — с его комплексно-сопряженным .

Математически это эквивалентно работе с полиномом от матрицы:

Раскроем скобки:

Магия:

• Сумма сопряженных чисел — это вещественное число ().

• Произведение — это тоже вещественное число ().

• Значит, матрица остается полностью вещественной, даже если сдвиги были мнимыми!

Реализация: «Погоня за горбом» (Bulge Chasing)

Фрэнсис придумал, как не перемножать матрицы целиком (это было бы долго, ). Он использовал теорему о неявном Q (Implicit Q Theorem).

1. Мы вычисляем только первый столбец воображаемой матрицы .

2. Это создает «возмущение» (горб, bulge) в верхней части матрицы Хессенберга.

3. Затем мы с помощью вращений Хаусхолдера или Гивенса «прогоняем» этот горб вниз по диагонали, пока он не исчезнет в правом нижнем углу.

В процессе этого прогона матрица преобразуется так, словно мы честно сделали два QR-шага с компле��сными сдвигами, но вся арифметика осталась вещественной.

Итог

Благодаря двойному сдвигу Фрэнсиса:

1. Алгоритм работает очень быстро (кубическая сходимость).

2. Мы остаемся в вещественных числах ( памяти вместо ).

3. На выходе получается та самая матрица Шура с блоками (вещественные с.ч.) и (комплексные пары), которая нужна нам для алгоритма Бартелса — Стюарта.

Именно этот алгоритм работает внутри функции scipy.linalg.schur и делает возможным быстрое решение уравнения Ляпунова.

Как это работает с геометрической точки зрения?
Алгоритм использует преобразования Хаусхолдера (матрицы отражения).

1. Первое отражение создает «возмущение» (ненулевой горб) в левом верхнем углу матрицы, кодирующее информацию о двойном сдвиге.

2. Серия последующих отражений «гонит» этот горб вниз по диагонали, восстанавливая треугольную структуру.

Этот процесс (Bulge Chasing) позволяет выполнить сложную математическую операцию над всей матрицей, затрагивая на каждом шаге только 3 строки и 3 столбца, что обеспечивает высочайшую скорость .

Матрица Хаусхолдера - это матрица вида , где вектор и . Это также матрица отражения относительно плоскости с нормалью :

Шаг 2. Трансформация уравнения

Берем наше уравнение:

Подставляем в него (и помним, что ):

Теперь применим «сэндвич-трюк»: умножим все уравнение слева на , а справа на . Благодаря свойству ортогональности (), внешние матрицы «аннигилируют», а внутренние группируются:

Шаг 3. Замена переменных

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

Здесь:

• — искомая матрица в повернутом базисе.

• — пересчитанная правая часть (легко вычисляется).

Шаг 4. Решение квазитреугольной системы («Матричное домино»)

Это самый красивый момент. Казалось бы, уравнение выглядит так же сложно, как исходное. Но нет!

Поскольку — квазитреугольная матрица, мы можем находить элементы по одному (или блоками по 2 элемента), начиная с углов.

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

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

Это снижает сложность с до .

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

Уравнение Сильвестра — это уравнение вида . Оно является более общим случаем уравнения Ляпунова (где не обязательно равно ).

По сути, мы сводим решение большого уравнения Ляпунова к последовательному решению множества крошечных уравнений Сильвестра (для связей между блоками) и уравнений Ляпунова (для самих блоков на диагонали).

Теперь разберем подробно, как выглядит это решение.

Итак, мы получили уравнение .

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

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

Запишем уравнение только для этого блока:

Взгляните на правую часть (). Все слагаемые в суммах содержат индексы или . Поскольку мы идем с конца (), эти значения нам уже известны! Мы просто переносим их в правую часть как константы.

Нам остается решить маленькое линейное уравнение относительно :

Здесь возможны всего три сценария:

Сценарий А: Скаляр + Скаляр ()
Если и — обычные числа (вещественные собственные числа):

Сценарий Б: Скаляр + Блок (или наоборот)

Это уравнение Сильвестра для прямоугольной матрички . Это система из 2-х линейных уравнений с 2-мя неизвестными. Решается элементарно методом Крамера или подстановкой.

Сценарий В: Блок + Блок

Самый сложный случай (когда сталкиваются два комплексно-сопряженных собственных числа). Мы ищем матрицу размером (4 неизвестных).

Уравнение вида для матриц можно развернуть через векторизацию (Кронекера) в систему :

Решить систему линейных уравнений для компьютера — это наносекунды.

Шаг 5. Возвращение домой

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

Вуаля! Задача решена, процессор холоден, ракета летит стабильно.

4. Дискретный мир: Алгоритм Китагавы

Если в непрерывном времени мы решаем дифференциальные уравнения, то в цифровых системах управления (DSP, компьютерное зрение, экономика) мы живем в мире дискретных шагов.
Уравнение здесь меняется на:

Идеологически алгоритм решения остается прежним (разложение трансформация подстановка), но алгебра меняется. Этот метод часто называют алгоритмом Китагавы.

Шаг 1. Разложение Шура (Фундамент)

Здесь всё без изменений. Мы находим ортогональную матрицу и верхнюю квазитреугольную :

Шаг 2. Трансформация уравнения

Подставим разложение в наше дискретное уравнение .
Помним, что .

Снова применяем «сэндвич-трюк»: умножаем всё уравнение слева на и справа на .

1. В первом слагаемом () внешние матрицы и аннигилируют с домноженными, оставляя «начинку».

2. Во втором слагаемом () и правой части () образуются новые переменные в повернутом базисе.

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

Шаг 3. Решение квазитреугольной системы

Теперь перед нами уравнение, где — верхняя квазитреугольная матрица. Как и в методе Бартелса — Стюарта, мы используем обратную подстановку, начиная с нижнего правого угла. Давайте посмотрим, во что вырождается это уравнение для самого последнего диагонального элемента . Из-за квазитреугольной структуры матрицы , элемент в углу зависит ��олько от самого себя:

Выносим за скобки:

Отсюда мгновенно получаем решение:

В чем фундаментальное отличие?

• В непрерывном случае: В знаменателе было . Деление на ноль происходило, если собственное число .

• В дискретном случае: В знаменателе стоит . Деление на ноль происходит, если , то есть . Это блестяще согласуется с теорией устойчивости: дискретная система теряет устойчивость, когда собственные числа выходят на единичную окружность. Алгоритм буквально «ломается» ровно в тот момент, когда система становится неустойчивой.

Шаг 4. Эффект домино

Вычислив угловой элемент , мы поднимаемся к соседним (например, ). Уравнение для них снова становится линейным с одним неизвестным, так как все "нижние" значения уже найдены. Мы распутываем матрицу с конца к началу.

Шаг 5. Восстановление

Возвращаемся в исходные координаты:

---

Шпаргалка: Сравнение методов

Чтобы уложить все в голове, давайте сведем два метода в одну таблицу.

Сравнение условий разрешимости (скалярный случай).

Графики показывают зависимость решения от собственного числа матрицы .

Слева (Непрерывный): решение уходит в бесконечность (сингулярность) при . Это соответствует нейтральной устойчивости (система не меняет состояние).

Справа (Дискретный): решение имеет две точки разрыва при и . Это границы единичного круга на комплексной плоскости. Если собственное число попадает на эту границу, дискретное уравнение Ляпунова не имеет единственного решения.

Вот переработанный раздел. Я сохранил единый стиль с предыдущими частями (используем как матрицу энергии) и добавил немного физической интуиции про «мощность» и «энергию», чтобы переход выглядел естественно.

---

Связь миров: от дискретного к непрерывному

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

Дискретная система — это, по сути, «покадровая съемка» непрерывного процесса. Если мы начнем уменьшать время между кадрами (шаг ), то дискретное уравнение должно плавно превратиться в непрерывное.

Давайте проверим это математически, используя старый добрый метод Эйлера.

1. От динамики к статике

Возьмем линейную непрерывную систему:

Чтобы загнать её в компьютер, мы дискретизируем время с шагом . Заменим производную конечной разностью:

Выразим состояние на следующем шаге:

Мы получили классическую дискретную систему , где матрица перехода за один шаг:

2. Трансформация уравнения Ляпунова

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

Важный физический нюанс:

В непрерывном уравнении матрица задает мощность диссипации (Джоули в секунду).

В дискретном уравнении правая часть — это энергия, потерянная за один шаг.

Поскольку шаг длится секунд, то энергия за шаг примерно равна .

Поэтому правая часть дискретного уравнения должна быть масштабирована на :

Подставим сюда наше выражение для :

Помним, что . Раскроем скобки, удерживая в голове, что :

Матрицы и уничтожаются. Остается:

3. Магия малых величин

Разделим всё уравнение на (считая, что ):

А теперь — финал. Устремим шаг времени к нулю (). Мы переходим от «слайд-шоу» к плавному кино.
Слагаемое , содержащее множитель , исчезает.

В пределе получаем:

Мы строго доказали, что непрерывное уравнение Ляпунова является математическим пределом дискретного. Это подтверждает целостность теории: неважно, как вы моделируете время, законы сохранения энергии (и устойчивости) остаются неизменными.

Иллюстрация: сходимость на практике

Лучше один раз увидеть, чем сто раз продифференцировать.
На графике ниже показана ошибка сходимости. Мы берем одну и ту же систему, решаем для нее непрерывное уравнение (получаем «идеальную» ), а затем решаем дискретное уравнение с уменьшающимся шагом . График в логарифмическом масштабе — это прямая линия, уходящая вниз. Это означает, что разница между матрицами стремится к нулю линейно вместе с .

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

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

P.S. Если этот материал оказался полезным, и вы хотите видеть больше подобных разборов для Википедии — дайте знать. Наука должна быть открытой и понятной.

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from mpl_toolkits.mplot3d import Axes3D
from scipy.linalg import solve_continuous_lyapunov, solve_discrete_lyapunov, schur, norm, expm
import time

class LyapunovLab:
    """
    Лаборатория для визуализации и решения уравнений Ляпунова.
    Включает методы для анализа устойчивости, геометрии и алгоритмов.
    """

    def __init__(self):
        # Настройки стилей графиков
        plt.rcParams['figure.figsize'] = (10, 6)
        plt.rcParams['axes.grid'] = True
        plt.rcParams['grid.alpha'] = 0.3
        print("LyapunovLab инициализирована. Готовы к экспериментам.")

    def run_all(self):
        """Запускает все демо-примеры последовательно."""
        self.demo_stability_bowl()
        self.demo_geometric_vectors()
        self.demo_schur_structure()
        self.demo_benchmark_complexity()
        self.demo_discrete_convergence()
        plt.show()

    def demo_stability_bowl(self):
        """
        Демонстрация 1: Физическая аналогия (Чаша).
        Показывает функцию Ляпунова как поверхность, по которой скатывается состояние.
        """
        print("\n--- Демо 1: Физическая аналогия (Чаша) ---")
        # Устойчивая матрица (спиральный сток)
        A = np.array([[-0.5,  2.0],
                      [-2.0, -1.0]])
        Q = np.eye(2)
        
        # Решаем уравнение: A.T * P + P * A = -Q
        P = solve_continuous_lyapunov(A.T, -Q)
        
        # Сетка
        x = np.linspace(-2, 2, 30)
        y = np.linspace(-2, 2, 30)
        X, Y = np.meshgrid(x, y)
        
        # V(x) = x^T P x
        Z = P[0,0]*X**2 + (P[0,1]+P[1,0])*X*Y + P[1,1]*Y**2
        
        fig = plt.figure(figsize=(10, 7))
        ax = fig.add_subplot(111, projection='3d')
        
        ax.plot_surface(X, Y, Z, cmap='viridis', alpha=0.8, edgecolor='none')
        ax.plot_wireframe(X, Y, Z, color='black', alpha=0.1, rstride=3, cstride=3)
        
        # Траектория "скатывания"
        from scipy.integrate import odeint
        t = np.linspace(0, 10, 200)
        path = odeint(lambda state, t: A @ state, [1.8, 1.8], t)
        path_z = [vec @ P @ vec for vec in path] # Высота траектории
        
        ax.plot(path[:,0], path[:,1], path_z, color='red', lw=2, label='Траектория системы')
        ax.scatter([0], [0], [0], color='red', s=50, label='Равновесие')
        
        ax.set_title("Функция Ляпунова: Энергетическая чаша\n$V(x) = x^T P x$")
        ax.set_xlabel('$x_1$'); ax.set_ylabel('$x_2$'); ax.set_zlabel('Energy')
        ax.legend()
        plt.tight_layout()

    def demo_geometric_vectors(self):
        """
        Демонстрация 2: Геометрия (Тупой угол).
        Показывает, что вектор скорости всегда смотрит внутрь эллипса энергии.
        """
        print("\n--- Демо 2: Геометрия векторов ---")
        A = np.array([[-1.0,  1.5],
                      [-1.5, -1.0]])
        Q = np.eye(2)
        P = solve_continuous_lyapunov(A.T, -Q)
        
        # Выбираем точку на эллипсе
        x0 = np.array([1.5, 1.0])
        # Нормируем точку под уровень энергии C=3
        current_energy = x0 @ P @ x0
        x0 = x0 * np.sqrt(3.0 / current_energy)
        
        # Векторы
        v_vel = A @ x0   # Скорость (Ax)
        v_norm = P @ x0  # Нормаль (Px)
        
        fig, ax = plt.subplots(figsize=(6, 6))
        
        # Рисуем эллипс
        limit = 2.5
        vals = np.linspace(-limit, limit, 100)
        X, Y = np.meshgrid(vals, vals)
        Z = P[0,0]*X**2 + (P[0,1]+P[1,0])*X*Y + P[1,1]*Y**2
        ax.contour(X, Y, Z, levels=[3.0], colors='black', linewidths=2)
        
        # Рисуем векторы
        ax.quiver(*x0, *v_norm, color='crimson', scale=10, label='Нормаль (Px)')
        ax.quiver(*x0, *v_vel, color='navy', scale=10, label='Скорость (Ax)')
        
        ax.set_title("Геометрия: Скорость против Нормали\nУгол > 90° обеспечивает устойчивость")
        ax.set_aspect('equal')
        ax.legend()
        
    def demo_benchmark_complexity(self):
        """
        Демонстрация 3: Сложность O(n^6) vs O(n^3).
        Сравнение наивного метода и метода Бартелса-Стюарта.
        """
        print("\n--- Демо 3: Бенчмарк (Битва алгоритмов) ---")
        
        # Наивный решатель (через Кронекера)
        def naive_solve(A_in, Q_in):
            n = A_in.shape[0]
            # vec(AX + XA^T) = (I x A + A x I) vec(X)
            # Обратите внимание: для XA^T это (A x I), для AX это (I x A)
            M = np.kron(np.eye(n), A_in) + np.kron(A_in, np.eye(n))
            return np.linalg.solve(M, -Q_in.reshape(-1)).reshape(n, n)

        sizes = range(2, 21, 2) # Небольшие размеры, т.к. наивный метод очень медленный
        times_naive = []
        times_smart = []
        
        print(f"{'N':<5} | {'Naive (s)':<10} | {'Smart (s)':<10}")
        for n in sizes:
            A = -np.eye(n) + 0.1*np.random.randn(n, n)
            Q = np.eye(n)
            
            t0 = time.time()
            naive_solve(A, Q)
            times_naive.append(time.time() - t0)
            
            t0 = time.time()
            solve_continuous_lyapunov(A.T, -Q)
            times_smart.append(time.time() - t0)
            
            print(f"{n:<5} | {times_naive[-1]:<10.4f} | {times_smart[-1]:<10.4f}")

        fig, ax = plt.subplots()
        ax.plot(sizes, times_naive, 'r-o', label='Naive $O(n^6)$')
        ax.plot(sizes, times_smart, 'g-s', label='Bartels-Stewart $O(n^3)$')
        ax.set_title("Взрыв сложности: Почему важен алгоритм")
        ax.set_xlabel("Размер матрицы N")
        ax.set_ylabel("Время (сек)")
        ax.legend()
        ax.set_yscale('log')

    def demo_schur_structure(self):
        """
        Демонстрация 4: Матрица Шура.
        Визуализация того, как A превращается в T.
        """
        print("\n--- Демо 4: Разложение Шура ---")
        # Создаем матрицу с комплексно-сопряженными числами
        T_true = np.array([[ -1,  2, 0, 0],
                           [ -2, -1, 0, 0], # Блок 2x2
                           [  0,  0,-3, 1],
                           [  0,  0, 0,-4]])
        # Запутываем её
        Q_orth, _ = np.linalg.qr(np.random.randn(4, 4))
        A = Q_orth @ T_true @ Q_orth.T
        
        T, U = schur(A, output='real')
        
        fig, axes = plt.subplots(1, 3, figsize=(12, 4))
        
        for ax, mat, title in zip(axes, [A, U, T], ['Исходная A', 'Ортогональная U', 'Форма Шура T']):
            im = ax.imshow(mat, cmap='Blues')
            ax.set_title(title)
            fig.colorbar(im, ax=ax, fraction=0.046, pad=0.04)
            
            # Подсветим нули на T
            if title == 'Форма Шура T':
                # Рисуем треугольник нулей
                n = mat.shape[0]
                poly = patches.Polygon([[-0.5, 1.5], [-0.5, n-0.5], [n-2.5, n-0.5]], 
                                       closed=True, color='white', alpha=0.5, hatch='///')
                ax.add_patch(poly)
                ax.text(1, 2.5, "Zeros", color='gray', fontweight='bold', rotation=45)

        plt.suptitle("Визуализация разложения Шура ($A = U T U^T$)", y=1.02)
        plt.tight_layout()

    def demo_discrete_convergence(self):
        """
        Демонстрация 5: Связь времен.
        Показывает, что при delta -> 0 решение дискретного уравнения сходится к непрерывному.
        """
        print("\n--- Демо 5: Сходимость (Дискретное -> Непрерывное) ---")
        A = np.array([[-0.5, 2.0], [-2.0, -1.0]])
        Q = np.eye(2)
        
        # Истинное непрерывное решение
        P_cont = solve_continuous_lyapunov(A.T, -Q)
        
        deltas = np.logspace(-1, -4, 15)
        errors = []
        
        for d in deltas:
            # Дискретный аналог: x_{k+1} = (I + dA)x_k
            A_disc = np.eye(2) + d * A
            # Дискретная диссипация энергии ~ d * Q
            Q_disc = d * Q
            
            # Решаем дискретное (нужно передать A.T, т.к. scipy решает AXA^H - X = -Q)
            try:
                P_disc = solve_discrete_lyapunov(A_disc.T, -Q_disc)
                errors.append(norm(P_disc - P_cont, 'fro'))
            except:
                errors.append(np.nan)

        fig, ax = plt.subplots()
        ax.loglog(deltas, errors, 'm-o', lw=2, label='Ошибка $|P_{disc} - P_{cont}|$')
        ax.set_title("Сходимость дискретного решения к непрерывному")
        ax.set_xlabel("Шаг времени $\delta$ (log)")
        ax.set_ylabel("Ошибка (log)")
        ax.grid(True, which="both", linestyle='--')
        ax.legend()

# --- Точка входа ---
if __name__ == "__main__":
    lab = LyapunovLab()
    lab.run_all()

Этот код проверен и работает. Теперь вы можете экспериментировать самостоятельно!