Тождество матрицы Вудбери

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

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

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

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

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

• 1 Обсуждение
  • 1.1 Особые случаи
    • 1.1.1 Обращение суммы
  • 1.2 Варианты
    • 1.2.1 Биномиальная обратная теорема
• 2 Выводы
  • 2.1 Прямое доказательство
  • 2.2 Альтернативные доказательства
• 3 Приложения
• 4 См. Также
• 5 Примечания
• 6 Внешние ссылки

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

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

Чтобы восстановить исходное уравнение из этого сокращенного тождества, установите $U\; =\; A\; -\; 1\; X\; \{\backslash \; displaystyle\; U\; =\; A\; ^\; \{-\; 1\}\; X\}$и $V\; =\; CY\; \{\backslash \; displaystyle\; V\; =\; CY\}$.

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

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

таким образом,

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

и аналогично

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

Второй идентификатор - это так называемый сквозной идентификатор

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

, которое мы получаем из

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

после умножения на $(I\; +\; VU)\; -\; 1\; \{\backslash \; displaystyle\; (I\; +\; VU)\; ^\; \{-\; 1\}\}$справа и на $(I\; +\; UV)\; -\; 1\; \{\backslash \; displaystyle\; (I\; +\; UV)\; ^\; \{-\; 1\}\}$слева.

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

Когда $V,\; U\; \{\backslash \; displaystyle\; V,\; U\}$- векторы, идентичность сводится к формуле Шермана – Моррисона.

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

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

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

Если p = q и U = V = I p - единичная матрица, тогда

$(A\; +\; B)\; -\; 1\; =\; A\; -\; 1\; -\; A\; -\; 1\; (B\; -\; 1\; +\; A\; -\; 1)\; -\; 1\; A\; -\; 1\; =\; А\; -\; 1\; -\; А\; -\; 1\; (АВ\; -\; 1\; +\; I)\; -\; 1.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; left\; (\{A\}\; +\; \{B\}\; \backslash \; right)\; ^\; \{-\; 1\}\; =\; A\; ^\; \{-\; 1\}\; -A\; ^\; \{-\; 1\}\; (B\; ^\; \{-\; 1\}\; +\; A\; ^\; \{-\; 1\})\; ^\; \{-\; 1\}\; A\; ^\; \{-\; 1\}\; \backslash \backslash \; =\; \{A\}\; ^\; \{-\; 1\}\; -\; \{A\}\; ^\; \{-\; 1\}\; \backslash \; left\; (\{A\}\; \{B\}\; ^\; \{\; -1\}\; +\; \{I\}\; \backslash \; right)\; ^\; \{-\; 1\}.\; \backslash \; End\; \{align\}\}\}$

Продолжение объединения членов крайней правой части приведенного выше уравнения приводит к Hua's тождество

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

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

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

который имеет рекурсивную структуру, которая дает

$(A\; -\; B)\; -\; 1\; =\; \sum \; k\; =\; 0\; \infty \; (A\; -\; 1\; B)\; k\; A\; -\; 1.\; \{\backslash \; displaystyle\; \backslash \; left\; (\{A\}\; -\; \{B\}\; \backslash \; right)\; ^\; \{-\; 1\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \backslash \; left\; (\{A\}\; ^\; \{-\; 1\}\; \{B\}\; \backslash \; справа)\; ^\; \{k\}\; \{A\}\; ^\; \{-\; 1\}.\}$

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

Варианты

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

Если A, U, B, V - матрицы размеров p × p, p × q, q × q, q × p соответственно, то

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

при условии, что A и B + BVAUB неособые. Неособенность последнего требует, чтобы B существовал, поскольку он равен B (I + VAUB), и ранг последнего не может превышать ранг B.

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

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

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

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

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

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

$(A + UCV) [A - 1 - A - 1 U (C - 1 + VA - 1 U) - 1 VA - 1] = {I - U (C - 1 + VA - 1 U) - 1 VA - 1} + {UCVA - 1 - UCVA - 1 U (C - 1 + VA - 1 U) - 1 VA - 1} = {I + UCVA - 1} - {U (C - 1 + VA - 1 U) - 1 VA - 1 + UCVA - 1 U (C - 1 + VA - 1 U) - 1 VA - 1} = I + UCVA - 1 - (U + UCVA - 1 U) (C - 1 + VA - 1 U) - 1 VA - 1 = I + UCVA - 1 - UC (C - 1 + VA - 1 U) (C - 1 + VA - 1 U) - 1 VA - 1 = I + UCVA - 1 - UCVA - 1 = I. {\ Displaystyle {\ begin {align} \ left (A + UCV \ right) \ left [A ^ {- 1} -A ^ {- 1} U \ left (C ^ {- 1} + VA ^ {- 1} U \ right) ^ {- 1} VA ^ {- 1} \ right] \\ = {} \ left \ {IU \ 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 {align}}}$

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

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

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

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

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

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

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