Computación de la matriz inversa cuando cambia un elemento

Question

Dado un $ n times n $ matrix $ mathbf {a} $. Deje que la matriz inversa de $ mathbf {a} $ $ mathbf {a}^{-1} $ (es decir, $ mathbf {a} mathbf {a}^{-1} = mathbf {i ps Suponga que se cambia un elemento en $ mathbf {a} $ (digamos $ a _ {ij} $ a $ a '_ {ij} $). El objetivo es encontrar $ mathbf {a}^{-1} $ después de este cambio. ¿Existe un método para encontrar este objetivo que sea más eficiente que volver a calcular la matriz inversa desde cero?

Answer 1

los Fórmula de Sherman-Morrison podría ayudar:

$$ (a + uv^t)^{-1} = a^{-1}- frac {a^{-1} uv^ta^{-1}} {1 + v^ta^{-1 } u}. $$

Sea $ u = (a '_ {ij} -a_ {ij}) e_i $ y $ v = e_j $, donde $ e_i $ es el vector de columna de base estándar. Puede verificar que si la matriz actualizada es $ a '$, entonces $$ a^{ prime -1} = a^{ -1} - frac {(a' _ {ij} -a_ {ij}) a^ {-1} _ {i rectarrow} a^{-1t} _ { downarrow j}} {1 + (a '_ {ij} -a_ {ij}) a^{-1} _ {ij}} . $$

Answer 2

Un cambio de elemento único, dado $ A $ con $ A^{-1} $, puede rastrearse con una actualización de rango uno. Entonces, sí, absolutamente, hay una mejor manera que recalcular el inverso desde cero.

Deje que $ delta = a_ {ij} ' - a_ {ij} $ sea el cambio del elemento $ a_ {ij} $. Usando $ e_i $ como el vector de columna de la unidad de uno en la posición $ i $ y cero en otro lugar, tenemos $$ (a + e_i delta e_j^ top) a^{-1} = i + e_i delta e_j^^ top a^{-1} $$

$ e_i delta e_j^ top $ es la matriz cero, excepto el valor de $ delta $ en la posición $ ij $. ¿Puede ver aquí cómo un apropiado rango de una multiplicación correcta con $ a^{-1} $ puede dar el nuevo inverso deseado? (O equivalentemente, operaciones de columna elemental en $ a^{-1} $.)

O si desea hacer operaciones de fila en su lugar, puede usar $$ A^{-1} (A + E_I delta E_J^ top) = i + A^{-1} E_I Delta E_J^ Top $$

En el primer caso tenemos la identidad con una fila agregada. Esto es fácil de hacer de las operaciones de columna para que la identidad vuelva nuevamente. Haga estas operaciones en $ a^{-1} $ y el resultado es el nuevo inverso, como se desea. El segundo caso es la identidad con una columna agregada. En ese caso, puede hacer operaciones de fila en su lugar. Puede elegir el que sea más conveniente.