Fórmula de Sherman-Morrison

Fórmula para calcular la inversa de la suma de una matriz y el producto externo de dos vectores

En álgebra lineal , la fórmula Sherman-Morrison , llamada así por Jack Sherman y Winifred J. Morrison, calcula la inversa de una " actualización de rango -1" de una matriz cuya inversa se ha calculado previamente. ^{[1] [2] [3]} Es decir, dada una matriz invertible y el producto externo de vectores y la fórmula calcula de manera económica una matriz inversa actualizada ${\displaystyle A}$ ${\displaystyle uv^{\textsf {T}}}$ ${\displaystyle u}$ ${\displaystyle v,}$ ${\textstyle \left(A+uv^{\textsf {T}}\right){\vphantom {)}}^{\!-1}.}$

La fórmula de Sherman-Morrison es un caso especial de la fórmula de Woodbury . Aunque lleva el nombre de Sherman y Morrison, ya aparecía en publicaciones anteriores. ^[4]

Declaración

Supongamos que es una matriz cuadrada invertible y son vectores columna . Entonces es invertible si y solo si . En este caso, ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ ${\displaystyle u,v\in \mathbb {R} ^{n}}$ ${\displaystyle A+uv^{\textsf {T}}}$ ${\displaystyle 1+v^{\textsf {T}}A^{-1}u\neq 0}$

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

Aquí, es el producto externo de dos vectores y . La forma general que se muestra aquí es la publicada por Bartlett. ^[5] ${\displaystyle uv^{\textsf {T}}}$ ${\displaystyle u}$ ${\displaystyle v}$

Prueba

( ) Para demostrar que la dirección inversa es invertible con la inversa dada como se indicó anteriormente) es verdadera, verificamos las propiedades de la inversa. Una matriz (en este caso, el lado derecho de la fórmula de Sherman-Morrison) es la inversa de una matriz (en este caso ) si y solo si . ${\displaystyle \Leftarrow }$ ${\displaystyle 1+v^{\textsf {T}}A^{-1}u\neq 0\Rightarrow A+uv^{\textsf {T}}}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle A+uv^{\textsf {T}}}$ ${\displaystyle XY=YX=I}$

Primero verificamos que el lado derecho ( ) satisface . ${\displaystyle Y}$ ${\displaystyle XY=I}$

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

Para finalizar la prueba de esta dirección, necesitamos demostrar que de manera similar a la anterior: ${\displaystyle YX=I}$

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

(De hecho, el último paso se puede evitar ya que para matrices cuadradas y , es equivalente a .) ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle XY=I}$ ${\displaystyle YX=I}$

( ) Recíprocamente, si , entonces a través del lema del determinante matricial , , por lo que no es invertible. ${\displaystyle \Rightarrow }$ ${\displaystyle 1+v^{\textsf {T}}A^{-1}u=0}$ ${\displaystyle \det \!\left(A+uv^{\textsf {T}}\right)=(1+v^{\textsf {T}}A^{-1}u)\det(A)=0}$ ${\displaystyle \left(A+uv^{\textsf {T}}\right)}$

Solicitud

Si ya se conoce la inversa de , la fórmula proporciona una forma numéricamente barata de calcular la inversa de corregida por la matriz (según el punto de vista, la corrección puede verse como una perturbación o como una actualización de rango 1). El cálculo es relativamente barato porque la inversa de no tiene que calcularse desde cero (lo que en general es costoso), sino que se puede calcular corrigiendo (o perturbando) . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle uv^{\textsf {T}}}$ ${\displaystyle A+uv^{\textsf {T}}}$ ${\displaystyle A^{-1}}$

Usando columnas unitarias (columnas de la matriz identidad ) para o , se pueden manipular columnas o filas individuales de y calcular de manera relativamente económica una inversa actualizada correspondiente. ^[6] En el caso general, donde es una matriz -por- y y son vectores arbitrarios de dimensión , se actualiza toda la matriz ^[5] y el cálculo toma multiplicaciones escalares. ^[7] Si es una columna unitaria, el cálculo toma solo multiplicaciones escalares. Lo mismo ocurre si es una columna unitaria. Si tanto y son columnas unitarias, el cálculo toma solo multiplicaciones escalares. ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle A}$ ${\displaystyle A^{-1}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle n}$ ${\displaystyle 3n^{2}}$ ${\displaystyle u}$ ${\displaystyle 2n^{2}}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle n^{2}}$

Esta fórmula también tiene aplicación en física teórica . Es decir, en la teoría cuántica de campos , se utiliza esta fórmula para calcular el propagador de un campo de espín 1. ^{[8] [ referencia circular ]} El propagador inverso (tal como aparece en el lagrangiano) tiene la forma . Se utiliza la fórmula de Sherman-Morrison para calcular el inverso (que satisface ciertas condiciones de contorno de ordenación temporal) del propagador inverso, o simplemente el propagador (de Feynman), que se necesita para realizar cualquier cálculo perturbativo ^[9] que involucre al campo de espín 1. ${\displaystyle A+uv^{\textsf {T}}}$

Uno de los problemas de la fórmula es que se sabe poco sobre su estabilidad numérica. No hay resultados publicados sobre sus límites de error. La evidencia anecdótica ^[10] sugiere que la identidad de la matriz de Woodbury (una generalización de la fórmula de Sherman-Morrison) puede divergir incluso en ejemplos aparentemente benignos (cuando tanto la matriz original como la modificada están bien condicionadas ).

Verificación alternativa

A continuación se muestra una verificación alternativa de la fórmula de Sherman-Morrison utilizando la identidad fácilmente verificable

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

Dejar

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

entonces

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

Sustituyendo se obtiene ${\displaystyle w=A^{-1}u}$

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

Generalización (Identidad matricial de Woodbury)

Dada una matriz cuadrada invertible , una matriz , y una matriz , sea una matriz tal que . Entonces, suponiendo que es invertible, tenemos ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle n\times k}$ ${\displaystyle U}$ ${\displaystyle k\times n}$ ${\displaystyle V}$ ${\displaystyle B}$ ${\displaystyle n\times n}$ ${\displaystyle B=A+UV}$ ${\displaystyle \left(I_{k}+VA^{-1}U\right)}$

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

Véase también

• El lema del determinante matricial realiza una actualización de rango 1 a un determinante .
• Identidad matricial de Woodbury
• Método de cuasi-Newton
• Teorema del inverso del binomio
• Fórmula Bunch-Nielsen-Sorensen
• El tensor de tensión de Maxwell contiene una aplicación de la fórmula de Sherman-Morrison.

Referencias

1. Sherman, Jack; Morrison, Winifred J. (1949). "Ajuste de una matriz inversa correspondiente a cambios en los elementos de una columna dada o una fila dada de la matriz original (resumen)". Annals of Mathematical Statistics . 20 : 621. doi : 10.1214/aoms/1177729959 .
2. Sherman, Jack; Morrison, Winifred J. (1950). "Ajuste de una matriz inversa correspondiente a un cambio en un elemento de una matriz dada". Anales de estadística matemática . 21 (1): 124–127. doi : 10.1214/aoms/1177729893 . MR  0035118. Zbl  0037.00901.
3. Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007), "Sección 2.7.1 Fórmula de Sherman-Morrison", Recetas numéricas: el arte de la computación científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-85-0-312-0 978-0-521-88068-8, archivado desde el original el 19-03-2012 , consultado el 8-08-2011
4. Hager, William W. (1989). "Actualización de la inversa de una matriz". SIAM Review . 31 (2): 221–239. doi :10.1137/1031049. JSTOR  2030425. MR  0997457. S2CID  7967459.
5. Bartlett, Maurice S. (1951). "Un ajuste de matriz inversa que surge en el análisis discriminante". Anales de estadística matemática . 22 (1): 107–111. doi : 10.1214/aoms/1177729698 . MR  0040068. Zbl  0042.38203.
6. Langville, Amy N. y Meyer, Carl D.; "El PageRank de Google y más allá: la ciencia de las clasificaciones en los motores de búsqueda", Princeton University Press, 2006, pág. 156
7. Actualización de la matriz inversa por la fórmula de Sherman-Morrison
8. Propagador#Spin 1
9. "Teoría cuántica de campos perturbativa".
10. "Discusión de MathOverflow". MathOverflow .

Enlaces externos

• Weisstein, Eric W. "Fórmula de Sherman-Morrison". MathWorld .