Формула Шермана-Моррисона

В линейной алгебре формула Шермана -Моррисона , названная в честь Джека Шермана и Уинифред Дж. Моррисон , вычисляет обратную « обновление ранга -1» к матрице , обратная которой была вычислена ранее. То есть, учитывая обратимую матрицу $A$ и внешний продукт $uv^{\textsf {T}}$ векторов ​ $u$ и $v,$ формула дешево вычисляет обновленную обратную матрицу ${\textstyle \left(A+uv^{\textsf {T}}\right){\vphantom {)}}^{\!-1}.}$

Формула Шермана-Моррисона является частным случаем формулы Вудбери . Хотя оно названо в честь Шермана и Моррисона, оно уже появлялось в более ранних публикациях.

Заявление

Предполагать $A\in \mathbb {R} ^{n\times n}$ является обратимой квадратной матрицей и $u,v\in \mathbb {R} ^{n}$ являются векторами-столбцами . Затем $A+uv^{\textsf {T}}$ обратим тогда и только тогда, когда $1+v^{\textsf {T}}A^{-1}u\neq 0$. В этом случае,

$\left(A+uv^{\textsf {T}}\right)^{-1}=A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}.$

Здесь, $uv^{\textsf {T}}$ является внешним произведением двух векторов $u$ и $v$. Показанная здесь общая форма опубликована Бартлеттом.

Доказательство

( $\Leftarrow$) Доказать, что обратное направление $1+v^{\textsf {T}}A^{-1}u\neq 0\Rightarrow A+uv^{\textsf {T}}$ обратимо с обратным, заданным выше) верно, мы проверяем свойства обратного. Матрица $Y$ (в данном случае правая часть формулы Шермана–Моррисона) является обратной матрицей $X$ (в этом случае $A+uv^{\textsf {T}}$) тогда и только тогда, когда $XY=YX=I$.

Сначала проверим, что правая часть ( $Y$) удовлетворяет $XY=I$.

${\begin{aligned}XY&=\left(A+uv^{\textsf {T}}\right)\left(A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\right)\\[6pt]&=AA^{-1}+uv^{\textsf {T}}A^{-1}-{AA^{-1}uv^{\textsf {T}}A^{-1}+uv^{\textsf {T}}A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\[6pt]&=I+uv^{\textsf {T}}A^{-1}-{uv^{\textsf {T}}A^{-1}+uv^{\textsf {T}}A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\[6pt]&=I+uv^{\textsf {T}}A^{-1}-{u\left(1+v^{\textsf {T}}A^{-1}u\right)v^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\[6pt]&=I+uv^{\textsf {T}}A^{-1}-uv^{\textsf {T}}A^{-1}\\[6pt]&=I\end{aligned}}$

Чтобы закончить доказательство этого направления, нам нужно показать, что $YX=I$ аналогично предыдущему:

$YX=\left(A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\right)(A+uv^{\textsf {T}})=I.$

(На самом деле, последнего шага можно избежать, поскольку для квадратных матриц $X$ и $Y$, $XY=I$ эквивалентно $YX=I$.)

( $\Rightarrow$) Взаимно, если $1+v^{\textsf {T}}A^{-1}u=0$, то по лемме об определителе матрицы , $\det \!\left(A+uv^{\textsf {T}}\right)=(1+v^{\textsf {T}}A^{-1}u)\det(A)=0$, так $\left(A+uv^{\textsf {T}}\right)$ не является обратимым.

Приложение

Если обратное $A$ уже известна, формула обеспечивает численный дешевый способ вычисления обратной величины $A$ исправлено по матрице $uv^{\textsf {T}}$ (в зависимости от точки зрения коррекцию можно рассматривать как возмущение или обновление ранга -1). Вычисления относительно дешевы, поскольку обратное $A+uv^{\textsf {T}}$ не нужно вычислять с нуля (что, как правило, дорого), но можно вычислить, исправив (или возмутив) $A^{-1}$.

Использование единичных столбцов (столбцов из единичной матрицы ) для $u$ или $v$, отдельные столбцы или строки $A$ Таким образом, можно манипулировать и соответственно обновлять инверсию относительно дешево. В общем случае, когда $A^{-1}$ это $n$-к- $n$ матрица и $u$ и $v$ — произвольные векторы размерности $n$, вся матрица обновляется и расчет занимает $3n^{2}$ скалярные умножения. Если $u$ является единичным столбцом, вычисление занимает всего $2n^{2}$ скалярные умножения. То же самое происходит, если $v$ представляет собой единичный столбец. Если оба $u$ и $v$ являются единичными столбцами, вычисление занимает всего $n^{2}$ скалярные умножения.

Эта формула также имеет применение в теоретической физике. А именно, в квантовой теории поля эта формула используется для расчета пропагатора поля со спином 1. Обратный распространитель (как он появляется в лагранжиане) имеет вид $A+uv^{\textsf {T}}$. Формула Шермана-Моррисона используется для расчета обратного (удовлетворяющего определенным граничным условиям временного порядка) обратного пропагатора - или просто (фейнмановского) пропагатора - который необходим для выполнения любых пертурбативных вычислений. с участием поля спина 1.

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

Альтернативная проверка

Ниже приводится альтернативная проверка формулы Шермана – Моррисона с использованием легко проверяемого тождества.

$\left(I+wv^{\textsf {T}}\right)^{-1}=I-{\frac {wv^{\textsf {T}}}{1+v^{\textsf {T}}w}}$.

Позволять

$u=Aw,\quad {\text{and}}\quad A+uv^{\textsf {T}}=A\left(I+wv^{\textsf {T}}\right),$

затем

$\left(A+uv^{\textsf {T}}\right)^{-1}=\left(I+wv^{\textsf {T}}\right)^{-1}A^{-1}=\left(I-{\frac {wv^{\textsf {T}}}{1+v^{\textsf {T}}w}}\right)A^{-1}$.

Замена $w=A^{-1}u$ дает

$\left(A+uv^{\textsf {T}}\right)^{-1}=\left(I-{\frac {A^{-1}uv^{\textsf {T}}}{1+v^{\textsf {T}}A^{-1}u}}\right)A^{-1}=A^{-1}-{\frac {A^{-1}uv^{\textsf {T}}A^{-1}}{1+v^{\textsf {T}}A^{-1}u}}$

Обобщение ( матричное тождество Вудбери )

Учитывая квадрат обратимый $n\times n$ матрица $A$, $n\times k$ матрица $U$и $k\times n$ матрица $V$, позволять $B$ быть $n\times n$ матрица такая, что $B=A+UV$. Тогда, предполагая $\left(I_{k}+VA^{-1}U\right)$ обратимо, мы имеем

$B^{-1}=A^{-1}-A^{-1}U\left(I_{k}+VA^{-1}U\right)^{-1}VA^{-1}.$

См. также

• Лемма об определителе матрицы выполняет обновление определителя ранга 1 .
• Матричное тождество Вудбери
• Квазиньютоновский метод
• Биномиальная обратная теорема
• Формула Банча – Нильсена – Соренсена
• Тензор напряжений Максвелла содержит применение формулы Шермана – Моррисона.

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

• Вайсштейн, Эрик В. «Формула Шермана – Моррисона» . Математический мир .