Алгоритм Бартельса – Стюарта

В числовой линейной алгебре алгоритм Бартельса – Стюарта используется для численного решения матричного уравнения Сильвестра. $AX-XB=C$ . Разработан Р. Х. Бартельсом и Г. В. Стюартом в 1971 году. ^{[ 1 ]} это был первый численно стабильный метод, который можно было систематически применять для решения таких уравнений. Алгоритм работает с использованием реальных разложений Шура $A$ и $B$ трансформировать $AX-XB=C$ в треугольную систему, которую затем можно решить с помощью прямой или обратной замены. В 1979 году Г. Голуб , К. Ван Лоан и С. Нэш представили улучшенную версию алгоритма, ^{[ 2 ]} известный как алгоритм Хессенберга-Шура. Это остается стандартным подходом к решению уравнений Сильвестра, когда $X$ имеет малый и средний размер.

Алгоритм

Позволять $X,C\in \mathbb {R} ^{m\times n}$ и предположим, что собственные значения $A$ отличны от собственных значений $B$ . Тогда матричное уравнение $AX-XB=C$ имеет единственное решение. Алгоритм Бартельса – Стюарта вычисляет $X$ применив следующие шаги: ^{[ 2 ]}

1. Вычислите реальные разложения Шура .

R=U^{T}AU,

S=V^{T}B^{T}V.

Матрицы $R$ и $S$ представляют собой блочные верхнетреугольные матрицы с диагональными блоками размера $1\times 1$ или $2\times 2$ .

2. Установить $F=U^{T}CV.$

3. Решите упрощенную систему $RY-YS^{T}=F$ , где $Y=U^{T}XV$ . Это можно сделать с помощью прямой замены блоков. В частности, если $s_{k-1,k}=0$ , затем

(R-s_{kk}I)y_{k}=f_{k}+\sum _{j=k+1}^{n}s_{kj}y_{j},

где $y_{k}$ это $k$ й столбец $Y$ . Когда $s_{k-1,k}\neq 0$ , столбцы $[y_{k-1}\mid y_{k}]$ должны быть объединены и решены одновременно.

4. Установите $X=UYV^{T}.$

Стоимость вычислений

Используя алгоритм QR , реальные разложения Шура на шаге 1 требуют примерно $10(m^{3}+n^{3})$ проваливается, так что общие вычислительные затраты равны $10(m^{3}+n^{3})+2.5(mn^{2}+nm^{2})$ . ^{[ 2 ]}

Упрощения и частные случаи

В частном случае, когда $B=-A^{T}$ и $C$ симметрично, решение $X$ также будет симметричным. Эту симметрию можно использовать так, что $Y$ более эффективно находится на этапе 3 алгоритма. ^{[ 1 ]}

Алгоритм Хессенберга – Шура

Алгоритм Хессенберга – Шура ^{[ 2 ]} заменяет разложение $R=U^{T}AU$ на шаге 1 с разложением $H=Q^{T}AQ$ , где $H$ — матрица верхнего Хессенберга . Это приводит к системе вида $HY-YS^{T}=F$ это можно решить с помощью прямой замены. Преимущество этого подхода в том, что $H=Q^{T}AQ$ можно найти с помощью отражений Домохозяев по цене $(5/3)m^{3}$ проваливается по сравнению с $10m^{3}$ флопов, необходимых для вычисления реального разложения Шура $A$ .

Программное обеспечение и реализация

Подпрограммы, необходимые для варианта Хессенберга-Шура алгоритма Бартельса-Стюарта, реализованы в библиотеке SLICOT. Они используются в наборе инструментов системы управления MATLAB.

Альтернативные подходы

Для больших систем ${\mathcal {O}}(m^{3}+n^{3})$ стоимость алгоритма Бартельса – Стюарта может быть непомерно высокой. Когда $A$ и $B$ являются разреженными или структурированными, так что линейные решения и умножения матриц-векторов с их участием являются эффективными, итерационные алгоритмы потенциально могут работать лучше. К ним относятся методы, основанные на проекциях, которые используют подпространства Крылова итерации , методы, основанные на неявной итерации чередующегося направления (ADI), и гибридизации, которые включают как проекцию, так и ADI. ^{[ 3 ]} Итерационные методы также можно использовать для непосредственного построения аппроксимаций низкого ранга к $X$ при решении $AX-XB=C$ .

Ссылки

^ Jump up to: ^а ^б Бартельс, Р.Х.; Стюарт, GW (1972). «Решение матричного уравнения AX+XB=C[F4]» . Коммуникации АКМ . 15 (9): 820–826. дои : 10.1145/361573.361582 . ISSN 0001-0782 .
^ Jump up to: ^а ^б ^с ^д Голуб, Г.; Нэш, С.; Ссуда, К. Ван (1979). «Метод Хессенберга – Шура для задачи AX + XB = C». Транзакции IEEE при автоматическом управлении . 24 (6): 909–913. дои : 10.1109/TAC.1979.1102170 . hdl : 1813/7472 . ISSN 0018-9286 .
^ Симончини, В. (2016). «Вычислительные методы решения линейных матричных уравнений». Обзор СИАМ . 58 (3): 377–441. дои : 10.1137/130912839 . hdl : 11585/586011 . ISSN 0036-1445 . S2CID 17271167 .

[:0-1] Jump up to: ^а ^б Бартельс, Р.Х.; Стюарт, GW (1972). «Решение матричного уравнения AX+XB=C[F4]» . Коммуникации АКМ . 15 (9): 820–826. дои : 10.1145/361573.361582 . ISSN 0001-0782 .

[:1-2] Jump up to: ^а ^б ^с ^д Голуб, Г.; Нэш, С.; Ссуда, К. Ван (1979). «Метод Хессенберга – Шура для задачи AX + XB = C». Транзакции IEEE при автоматическом управлении . 24 (6): 909–913. дои : 10.1109/TAC.1979.1102170 . hdl : 1813/7472 . ISSN 0018-9286 .

[3] Симончини, В. (2016). «Вычислительные методы решения линейных матричных уравнений». Обзор СИАМ . 58 (3): 377–441. дои : 10.1137/130912839 . hdl : 11585/586011 . ISSN 0036-1445 . S2CID 17271167 .

[ 1 ]

[ 2 ]

[ 3 ]

v т и Численная линейная алгебра
Ключевые понятия	Плавающая точка Численная стабильность
Проблемы	Система линейных уравнений Матричное разложение Умножение матриц ( алгоритмы ) Расщепление матрицы Редкие проблемы
Аппаратное обеспечение	Кэш процессора TLB Алгоритм, не обращающий внимания на кэш SIMD Многопроцессорность
Программное обеспечение	АТЛАС МАТЛАБ Базовые подпрограммы линейной алгебры (BLAS) ЛАПАК Специализированные библиотеки Программное обеспечение общего назначения