Матричное тождество Вудбери

Теорема о матричных рангах

В математике (в частности , в линейной алгебре ) матричное тождество Вудбери , названное в честь Макса А. Вудбери, ^{[1] [2]} говорит, что обратную поправку ранга k некоторой матрицы можно вычислить, выполнив поправку ранга k к обратная исходной матрице. Альтернативные названия этой формулы — лемма обращения матрицы , формула Шермана–Моррисона–Вудбери или просто формула Вудбери . Однако эта личность появилась в нескольких газетах до доклада Вудбери. ^{[3] [4]}

Матричное тождество Вудбери есть ^[5]

$${\displaystyle \left(A+UCV\right)^{-1}=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1},}$$

где A , U , C и V — сообразные матрицы : A — это n × n , C — это k × k , U — это n × k , а V — это k × n . Это можно получить с помощью блочной инверсии матрицы .

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

Матричное тождество Вудбери позволяет дешево вычислять обратные задачи и решения линейных уравнений. Однако мало что известно о численной устойчивости формулы. Нет опубликованных результатов, касающихся границ погрешности. Неофициальные данные ^[6] позволяют предположить, что она может расходиться даже для, казалось бы, безобидных примеров (когда и исходная, и модифицированная матрицы хорошо обусловлены).

Обсуждение

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

$${\displaystyle \left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-1}V.}$$

сокращенного тождества ${\displaystyle U=A^{-1}X}$ ${\displaystyle V=CY}$

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

$${\displaystyle I=(I+P)^{-1}(I+P)=(I+P)^{-1}+(I+P)^{-1}P,}$$

$${\displaystyle (I+P)^{-1}=I-(I+P)^{-1}P,}$$

$${\displaystyle (I+P)^{-1}=I-P(I+P)^{-1}.}$$

сквозная идентичность ^[7].

$${\displaystyle (I+UV)^{-1}U=U(I+VU)^{-1}}$$

$${\displaystyle U(I+VU)=(I+UV)U}$$

${\displaystyle (I+VU)^{-1}}$ ${\displaystyle (I+UV)^{-1}}$

Собрав все вместе,

$${\displaystyle \left(I+UV\right)^{-1}=I-UV\left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-1}V.}$$

Особые случаи

Когда являются векторами, тождество сводится к формуле Шермана-Моррисона . ${\displaystyle V,U}$

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

$${\displaystyle {\frac {1}{1+uv}}=1-{\frac {uv}{1+uv}}.}$$

Обратная сумма

Если n = k и U = V = I _n — единичная матрица, то

$${\displaystyle {\begin{aligned}\left(A+B\right)^{-1}&=A^{-1}-A^{-1}\left(B^{-1}+A^{-1}\right)^{-1}A^{-1}\\[1ex]&=A^{-1}-A^{-1}\left(AB^{-1}+{I}\right)^{-1}.\end{aligned}}}$$

Продолжение слияния членов крайней правой части приведенного выше уравнения приводит к тождеству Хуа.

$${\displaystyle \left({A}+{B}\right)^{-1}={A}^{-1}-\left({A}+{A}{B}^{-1}{A}\right)^{-1}.}$$

Другая полезная форма того же тождества:

$${\displaystyle \left({A}-{B}\right)^{-1}={A}^{-1}+{A}^{-1}{B}\left({A}-{B}\right)^{-1},}$$

который, в отличие от приведенных выше, действителен, даже если он сингулярен, и имеет рекурсивную структуру, которая дает ${\displaystyle B}$

$${\displaystyle \left({A}-{B}\right)^{-1}=\sum _{k=0}^{\infty }\left({A}^{-1}{B}\right)^{k}{A}^{-1}}$$

спектральный радиус ${\displaystyle A^{-1}B}$ ${\displaystyle (A-B)^{-1}}$

Эту форму можно использовать в пертурбативных разложениях, где B — возмущение A.

Вариации

Биномиальная обратная теорема

Если A , B , U , V — матрицы размеров n × n , k × k , n × k , k × n соответственно, то

$${\displaystyle \left(A+UBV\right)^{-1}=A^{-1}-A^{-1}UB\left(B+BVA^{-1}UB\right)^{-1}BVA^{-1}}$$

при условии, что A и B + BVA ⁻¹ UB несингулярны. Невырожденность последнего требует существования B ⁻¹ , поскольку он равен B ( I + VA ⁻¹ UB ) и ранг последнего не может превосходить ранг B. ^[7]

Поскольку B обратим, два члена B , обрамляющие величину в скобках, обратную в правой части, можно заменить на ( B ⁻¹ ) ⁻¹ , что приводит к исходному тождеству Вудбери.

Вариант для случая, когда B сингулярна и, возможно, даже неквадратна: ^[7]

$${\displaystyle (A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}BVA^{-1}.}$$

Существуют также формулы для некоторых случаев, когда A сингулярно. ^[8]

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

В общем, тождество Вудбери недействительно, если одна или несколько инверсий заменены псевдообратными (Мура – ​​Пенроуза) . Однако если и положительно полуопределены , и (подразумевается, что это само по себе положительно полуопределено), то следующая формула дает обобщение: ^{[9] [10]} ${\displaystyle A}$ ${\displaystyle C}$ ${\displaystyle V=U^{\mathrm {H} }}$ ${\displaystyle A+UCV}$

$${\displaystyle {\begin{aligned}\left(XX^{\mathrm {H} }+YY^{\mathrm {H} }\right)^{+}&=\left(ZZ^{\mathrm {H} }\right)^{+}+\left(I-YZ^{+}\right)^{\mathrm {H} }X^{+\mathrm {H} }EX^{+}\left(I-YZ^{+}\right),\\Z&=\left(I-XX^{+}\right)Y,\\E&=I-X^{+}Y\left(I-Z^{+}Z\right)F^{-1}\left(X^{+}Y\right)^{\mathrm {H} },\\F&=I+\left(I-Z^{+}Z\right)Y^{\mathrm {H} }\left(XX^{\mathrm {H} }\right)^{+}Y\left(I-Z^{+}Z\right),\end{aligned}}}$$

где можно записать как потому что любая положительная полуопределенная матрица равна для некоторого . ${\displaystyle A+UCU^{\mathrm {H} }}$ ${\displaystyle XX^{\mathrm {H} }+YY^{\mathrm {H} }}$ ${\displaystyle MM^{\mathrm {H} }}$ ${\displaystyle M}$

Выводы

Прямое доказательство

Формулу можно доказать, проверив, что раз ее предполагаемое обратное значение в правой части тождества Вудбери дает идентификационную матрицу: ${\displaystyle (A+UCV)}$

$${\displaystyle {\begin{aligned}&\left(A+UCV\right)\left[A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right]\\={}&\left\{I-U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}+\left\{UCVA^{-1}-UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&\left\{I+UCVA^{-1}\right\}-\left\{U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}+UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&I+UCVA^{-1}-\left(U+UCVA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UC\left(C^{-1}+VA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UCVA^{-1}\\={}&I.\end{aligned}}}$$

Альтернативные доказательства

Приложения

Это тождество полезно в некоторых числовых вычислениях, где A ⁻¹ уже вычислено и желательно вычислить ( A  +  UCV ) ⁻¹ . При наличии обратного A достаточно найти обратное C ⁻¹  +  VA ⁻¹ U , чтобы получить результат, используя правую часть тождества. Если C имеет гораздо меньшую размерность, чем A , это более эффективно, чем непосредственное инвертирование A  +  UCV . Распространенным случаем является поиск обратного обновления A  +  UCV низкого ранга A (где U имеет только несколько столбцов, а V только несколько строк) или поиск аппроксимации обратной матрицы A  +  B , где матрица B можно аппроксимировать матрицей UCV низкого ранга , например, используя разложение по сингулярным значениям .

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

В случае, когда C является единичной матрицей I , матрица известна в числовой линейной алгебре и числовых уравнениях в частных производных как матрица емкости . ^[4] ${\displaystyle I+VA^{-1}U}$

Смотрите также

• Формула Шермана-Моррисона
• дополнение Шура
• Лемма об определителе матрицы , формула обновления ранга k до определителя
• Обратимая матрица
• Псевдообратная обратная задача Мура – ​​Пенроуза § Обновление псевдообратной

Примечания

1. Макс А. Вудбери, Инвертирование модифицированных матриц , Memorandum Rept. 42, Группа статистических исследований, Принстонский университет, Принстон, Нью-Джерси, 1950, 4 стр. MR 38136.
2. Макс А. Вудбери, Стабильность матриц вывода-входа . Чикаго, Иллинойс, 1949. 5 стр. MR 32564.
3. Гутманн, Луи (1946). «Методы расширения для вычисления обратной матрицы». Анна. Математика. Статист . 17 (3): 336–343. дои : 10.1214/aoms/1177730946 .
4. Хагер, Уильям В. (1989). «Обновление обратной матрицы». Обзор СИАМ . 31 (2): 221–239. дои : 10.1137/1031049. JSTOR  2030425. МР  0997457.
5. Хайэм, Николас (2002). Точность и устойчивость численных алгоритмов (2-е изд.). СИАМ . п. 258. ИСБН 978-0-89871-521-7. МР  1927606.
6. "Обсуждение MathOverflow" . MathOverflow .
7. Хендерсон, HV; Сирл, СР (1981). «О получении обратной суммы матриц» (PDF) . Обзор СИАМ . 23 (1): 53–60. дои : 10.1137/1023004. hdl : 1813/32749 . JSTOR  2029838.
8. Курт С. Ридель, «Тождество Шермана-Моррисона-Вудбери для матриц, повышающих ранг с применением к центрированию», SIAM Journal on Matrix Analysis and Applications , 13 (1992)659-662, doi : 10.1137/0613040 препринт MR 1152773
9. Бернштейн, Деннис С. (2018). Скалярная, векторная и матричная математика: теория, факты и формулы (пересмотренное и расширенное изд.). Принстон: Издательство Принстонского университета. п. 638. ИСБН 9780691151205.
10. Шотт, Джеймс Р. (2017). Матричный анализ для статистики (Третье изд.). Хобокен, Нью-Джерси: John Wiley & Sons, Inc., с. 219. ИСБН 9781119092483.

• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 2.7.3. Формула Вудбери», Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8

Внешние ссылки

• Некоторые матричные тождества
• Вайсштейн, Эрик В. «Формула Вудбери». Математический мир .