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

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

Матричное тождество Вудбери: $$\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-категории .

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

Обсуждение

Чтобы доказать этот результат, начнем с доказательства более простого. Заменив A и C единичной матрицей I , мы получим другое тождество, немного более простое: $$\left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-1}V.$$Чтобы восстановить исходное уравнение из этого сокращенного тождества , замените $U$ к $A^{-1}U$ и $V$ к $CV$.

Эту идентичность можно рассматривать как комбинацию двух более простых идентичностей. Получаем первое тождество из $$I=(I+P)^{-1}(I+P)=(I+P)^{-1}+(I+P)^{-1}P,$$таким образом, $$(I+P)^{-1}=I-(I+P)^{-1}P,$$и аналогично $$(I+P)^{-1}=I-P(I+P)^{-1}.$$Вторая идентичность – это так называемая сквозная идентичность. $$(I+UV)^{-1}U=U(I+VU)^{-1}$$что мы получаем из $$U(I+VU)=(I+UV)U$$после умножения на $(I+VU)^{-1}$ справа и рядом $(I+UV)^{-1}$ слева.

Собрав все вместе, $$\left(I+UV\right)^{-1}=I-UV\left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-1}V.$$где первое и второе равенство вытекают из первого и второго тождества соответственно.

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

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

В скалярном случае сокращенная версия просто $${\frac {1}{1+uv}}=1-{\frac {uv}{1+uv}}.$$

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

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

$${\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}}$$

Продолжение слияния членов крайней правой части приведенного выше уравнения приводит к тождеству Хуа. $$\left({A}+{B}\right)^{-1}={A}^{-1}-\left({A}+{A}{B}^{-1}{A}\right)^{-1}.$$

Другая полезная форма того же тождества: $$\left({A}-{B}\right)^{-1}={A}^{-1}+{A}^{-1}{B}\left({A}-{B}\right)^{-1},$$

что, в отличие от приведенных выше, справедливо, даже если $B$ является сингулярным и имеет рекурсивную структуру, которая дает $$\left({A}-{B}\right)^{-1}=\sum _{k=0}^{\infty }\left({A}^{-1}{B}\right)^{k}{A}^{-1}$$если радиус спектральный $A^{-1}B$ меньше единицы. То есть, если приведенная выше сумма сходится, то она равна $(A-B)^{-1}$.

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

Вариации

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

Если A , B , U , V — матрицы размеров n × n , k × k , n × k , k × n соответственно, то $$\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. ранга

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

Вариант, когда B сингулярный и, возможно, даже неквадратный: $$(A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}BVA^{-1}.$$

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

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

В общем, тождество Вудбери недействительно, если одна или несколько инверсий заменены псевдообратными (Мура – ​​Пенроуза) . Однако, если $A$ и $C$ положительно полуопределены и $V=U^{\mathrm {H} }$ (имея в виду, что $A+UCV$ сама по себе положительно полуопределена), то следующая формула дает обобщение: $${\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}}$$

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

Выводы

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

Формулу можно доказать, проверив, что $(A+UCV)$ умноженное на предполагаемое обратное в правой части тождества Вудбери, получим тождественную матрицу: $${\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}}$$

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

показывать Алгебраическое доказательство

First consider these useful identities,$${\begin{aligned}U+UCVA^{-1}U&=UC\left(C^{-1}+VA^{-1}U\right)=\left(A+UCV\right)A^{-1}U\\\left(A+UCV\right)^{-1}UC&=A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}\end{aligned}}$$ Now, $${\begin{aligned}A^{-1}&=\left(A+UCV\right)^{-1}\left(A+UCV\right)A^{-1}\\&=\left(A+UCV\right)^{-1}\left(I+UCVA^{-1}\right)\\&=\left(A+UCV\right)^{-1}+\left(A+UCV\right)^{-1}UCVA^{-1}\\&=\left(A+UCV\right)^{-1}+A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}.\end{aligned}}$$

показывать Вывод посредством блочного исключения

Deriving the Woodbury matrix identity is easily done by solving the following block matrix inversion problem$${\begin{bmatrix}A&U\\V&-C^{-1}\end{bmatrix}}{\begin{bmatrix}X\\Y\end{bmatrix}}={\begin{bmatrix}I\\0\end{bmatrix}}.$$ Expanding, we can see that the above reduces to$${\begin{cases}AX+UY=I\\VX-C^{-1}Y=0\end{cases}}$$which is equivalent to $(A+UCV)X=I$. Eliminating the first equation, we find that $X=A^{-1}(I-UY)$, which can be substituted into the second to find $VA^{-1}(I-UY)=C^{-1}Y$. Expanding and rearranging, we have $VA^{-1}=\left(C^{-1}+VA^{-1}U\right)Y$, or $\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}=Y$. Finally, we substitute into our $AX+UY=I$, and we have $AX+U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}=I$. Thus, $(A+UCV)^{-1}=X=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}.$ We have derived the Woodbury matrix identity.

показывать Вывод из разложения LDU

We start by the matrix$${\begin{bmatrix}A&U\\V&C\end{bmatrix}}$$By eliminating the entry under the A (given that A is invertible) we get$${\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}A&U\\0&C-VA^{-1}U\end{bmatrix}}$$ Likewise, eliminating the entry above C gives$${\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}={\begin{bmatrix}A&0\\V&C-VA^{-1}U\end{bmatrix}}$$ Now combining the above two, we get$${\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}={\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}$$ Moving to the right side gives$${\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}I&0\\VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}{\begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix}}$$which is the LDU decomposition of the block matrix into an upper triangular, diagonal, and lower triangular matrices. Now inverting both sides gives$${\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix}}^{-1}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}^{-1}{\begin{bmatrix}I&0\\VA^{-1}&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}{\begin{bmatrix}A^{-1}&0\\0&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}{\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}A^{-1}+A^{-1}U\left(C-VA^{-1}U\right)^{-1}VA^{-1}&-A^{-1}U\left(C-VA^{-1}U\right)^{-1}\\-\left(C-VA^{-1}U\right)^{-1}VA^{-1}&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}\qquad \mathrm {(1)} \end{aligned}}$$ We could equally well have done it the other way (provided that C is invertible) i.e.$${\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}{\begin{bmatrix}I&0\\C^{-1}V&I\end{bmatrix}}$$ Now again inverting both sides,$${\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&0\\C^{-1}V&I\end{bmatrix}}^{-1}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}^{-1}{\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&0\\-C^{-1}V&I\end{bmatrix}}{\begin{bmatrix}\left(A-UC^{-1}V\right)^{-1}&0\\0&C^{-1}\end{bmatrix}}{\begin{bmatrix}I&-UC^{-1}\\0&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}\left(A-UC^{-1}V\right)^{-1}&-\left(A-UC^{-1}V\right)^{-1}UC^{-1}\\-C^{-1}V\left(A-UC^{-1}V\right)^{-1}&C^{-1}+C^{-1}V\left(A-UC^{-1}V\right)^{-1}UC^{-1}\end{bmatrix}}\qquad \mathrm {(2)} \end{aligned}}$$ Now comparing elements (1, 1) of the RHS of (1) and (2) above gives the Woodbury formula$$\left(A-UC^{-1}V\right)^{-1}=A^{-1}+A^{-1}U\left(C-VA^{-1}U\right)^{-1}VA^{-1}.$$

Приложения

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

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

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

См. также

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

Примечания

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

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

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