Матричная идентичность Вудбери

Теорема о рангах матриц

В математике , в частности, в линейной алгебре , тождество матрицы Вудбери , названное в честь Макса А. Вудбери ^{[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}$ ${\displaystyle A^{-1}U}$ ${\displaystyle V}$ ${\displaystyle CV}$

Это тождество само по себе можно рассматривать как комбинацию двух более простых тождеств. Первое тождество мы получаем из таким образом, и аналогично Второе тождество — это так называемое тождество проталкивания ^[7] , которое мы получаем из после умножения на справа и на слева. $${\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}.}$$ $${\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+vu}}.}$$

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

Если 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. Макс А. Вудбери, Обращение модифицированных матриц , Меморандум Отчет 42, Статистическая исследовательская группа, Принстонский университет, Принстон, Нью-Джерси, 1950, 4 стр. MR 38136
2. Макс А. Вудбери, Устойчивость матриц «выход-вход» . Чикаго, Иллинойс, 1949. 5 стр. MR 32564
3. Гуттманн, Луис (1946). «Методы увеличения для вычисления обратной матрицы». Ann. Math. Statist . 17 (3): 336–343. doi : 10.1214/aoms/1177730946 .
4. Hager, William W. (1989). «Обновление обратной матрицы». SIAM Review . 31 (2): 221–239. doi :10.1137/1031049. JSTOR  2030425. MR  0997457.
5. Хайэм, Николас (2002). Точность и устойчивость численных алгоритмов (2-е изд.). SIAM . стр. 258. ISBN 978-0-89871-521-7. МР  1927606.
6. "Обсуждение MathOverflow". MathOverflow .
7. Хендерсон, HV; Сирл, SR (1981). «О выводе обратной суммы матриц» (PDF) . Обзор SIAM . 23 (1): 53–60. doi :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). Скалярная, векторная и матричная математика: теория, факты и формулы (пересмотренное и расширенное издание). Принстон: Princeton University Press. стр. 638. ISBN 9780691151205.
10. Шотт, Джеймс Р. (2017). Матричный анализ для статистики (третье изд.). Хобокен, Нью-Джерси: John Wiley & Sons, Inc. стр. 219. ISBN 9781119092483.

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Раздел 2.7.3. Формула Вудбери», Numerical Recipes: The Art of Scientific Computing (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8

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

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