В математика (конкретно линейная алгебра), Тождество матрицы Вудбери, названный в честь Макса А. Вудбери[1][2], говорит, что инверсия ранга-k исправление некоторых матрица можно вычислить, выполнив рангk исправление инверсии исходной матрицы. Альтернативные названия этой формулы - лемма об обращении матриц, Формула Шермана – Моррисона – Вудбери или просто Формула Вудбери. Однако личность появилась в нескольких газетах до отчета Вудбери.[3]
куда А, U, C и V все обозначают матрицы правильных (соответствующий) размеры. Конкретно, А является п-к-п, U является п-к-k, C является k-к-k и V является k-к-п. Это можно получить, используя поблочное обращение матрицы.
Хотя тождество в основном используется для матриц, в целом оно выполняется. звенеть или в Ab-категория.
Чтобы доказать этот результат, мы начнем с доказательства более простого. Замена А и C с единичной матрицей я, мы получаем другое тождество, которое немного проще:
Чтобы восстановить исходное уравнение из этого уменьшенная личность, набор и .
Сама идентичность может рассматриваться как комбинация двух более простых идентичностей. Первое тождество получаем из
,
таким образом,
,
и аналогично
Вторая идентичность - это так называемая сквозная идентификация[5]
В скалярном случае это (сокращенная версия) просто
Обратная сумма
Если п = q и U = V = яп - единичная матрица, то
Продолжение объединения членов крайней правой части приведенного выше уравнения приводит к Личность Хуа
Еще одна полезная форма той же личности -
который имеет рекурсивную структуру, которая дает
Эта форма может использоваться в пертурбативных разложениях, где B возмущение А.
Вариации
Биномиальная обратная теорема
Если А, U, B, V матрицы размеров п×п, п×q, q×q, q×псоответственно, то
при условии А и B + BVA−1UB неособые. Неособенность последнего требует, чтобы B−1 существуют, поскольку он равен B(я + VA−1UB) и ранг последнего не может превышать ранг B.[5]
С B обратима, два B члены, стоящие по бокам числа в скобках, обратное в правой части, можно заменить на (B−1)−1, что приводит к оригинальной идентичности Вудбери.
Вариант когда B является сингулярным и, возможно, даже неквадратным:[5]
Формулы также существуют для некоторых случаев, когда А единственное число.[6]
Производные
Прямое доказательство
Формулу можно проверить, проверив, что умноженное на его предполагаемую инверсию в правой части тождества Вудбери, дает единичную матрицу:
что эквивалентно . Исключая первое уравнение, находим, что , который можно подставить во вторую, чтобы найти . Расширяя и переставляя, мы имеем , или же . Наконец, подставляем в наш , и у нас есть . Таким образом,
Мы вывели матричное тождество Вудбери.
Вывод из разложения LDU
Начнем с матрицы
Удалив запись под А (при условии А обратима) получаем
Аналогичным образом, удалив запись выше C дает
Теперь, комбинируя два вышеупомянутых, мы получаем
Переход в правую сторону дает
который является LDU-разложением блочной матрицы на верхнетреугольную, диагональную и нижнюю треугольную матрицы.
Теперь инвертирование обеих сторон дает
Мы могли бы сделать это и другим способом (при условии, что C обратима), т.е.
Теперь снова переворачивая обе стороны,
Теперь сравнение элементов (1, 1) правой части (1) и (2) выше дает формулу Вудбери
Приложения
Это тождество полезно в некоторых численных вычислениях, где А−1 уже вычислен, и желательно вычислить (А + UCV)−1. С инверсией А в наличии, необходимо найти только обратное C−1 + VA−1U чтобы получить результат, используя правую часть тождества. Если C имеет гораздо меньший размер, чем А, это более эффективно, чем инвертирование А + UCV напрямую. Распространенный случай - поиск обратного обновления низкого ранга А + UCV из А (куда U всего несколько столбцов и V всего несколько строк), или найти приближение обратной матрицы А + B где матрица B можно аппроксимировать матрицей низкого ранга UCV, например, используя разложение по сингулярным числам.
Это применяется, например, в Фильтр Калмана и рекурсивный метод наименьших квадратов методы, чтобы заменить параметрическое решение, требуя обращения матрицы размера вектора состояния, с решением на основе условных уравнений. В случае фильтра Калмана эта матрица имеет размерность вектора наблюдений, то есть всего 1, если одновременно обрабатывается только одно новое наблюдение. Это значительно ускоряет расчеты фильтра в реальном времени.
^Макс А. Вудбери, Обращение модифицированных матриц, Memorandum Rept. 42, Группа статистических исследований, Принстонский университет, Принстон, Нью-Джерси, 1950, 4 стр. МИСТЕР38136
^Курт С. Ридель, "Тождество Шермана – Моррисона – Вудбери для матриц, увеличивающих ранг, с применением к центрированию", Журнал SIAM по матричному анализу и приложениям, 13 (1992)659-662, Дои:10.1137/0613040препринтМИСТЕР1152773
Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, BP (2007), «Раздел 2.7.3. Формула Вудбери», Числовые рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Издательство Кембриджского университета, ISBN978-0-521-88068-8
![{ 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f9188a55ebfb78625ce03beb899b67c010612cc)
![{ displaystyle { begin {align} { 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)} конец {выровнено}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd80a045fa9157c9185e1805320cacf91ce7b40e)
![{ displaystyle { begin {align} { 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)} конец {выровнено}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70dd74f08ea4769fe59dc5765fa134270b371d60)
