Вычисление обратной матрицы при изменении элемента

Question

Учитывая $ n times n $ matrix $ mathbf {a} $. Пусть обратная матрица $ mathbf {a} $ be $ mathbf {a}^{-1} $ (то есть $ mathbf {a} mathbf {a}^{-1} = mathbf {i } $). Предположим, что один элемент в $ mathbf {a} $ изменен (скажем, $ a _ {ij} $ to $ a '_ {ij} $). Цель состоит в том, чтобы найти $ mathbf {a}^{-1} $ после этого изменения. Существует ли метод для поиска этой цели, которая более эффективна, чем повторная калиляция обратной матрицы с нуля.

Answer 1

А Шерман-Моррисон Формула может помочь:

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

Пусть $ u = (a '_ {ij} -a_ {ij}) e_i $ и $ v = e_j $, где $ e_i $ является стандартным базовым вектором. Вы можете проверить, что если обновленная матрица равно $ a '$, тогда $$ a^{ prime -1} = a^{ -1} - frac {(a' _ {ij} -a_ {ij}) a^^ {-1} _ {i rightarrow} a^{-1t} _ { Down-arrow j}} {1 + (a '_ {ij} -a_ {ij}) a^{-1} _ {ij}}}}} . $$

Answer 2

Единственное изменение элемента, данное $ a $ с $ a^{-1} $, может быть отслеживается с обновлением первого ранга. Так что да, абсолютно, есть лучший способ, чем пересматривать обратную с нуля.

Пусть $ delta = a_ {ij} ' - a_ {ij} $ будет изменением элемента $ a_ {ij} $. Используя $ e_i $ в качестве вектора столбца единицы одного в позиции $ i $ и нулей в другом месте, у нас есть $$ (a + e_i delta e_j^ top) a^{-1} = i + e_i delta e_j^ top a^{-1} $$

$ e_i delta e_j^ top $ - это нулевая матрица, за исключением стоимости $ delta $ в позиции $ ij $. Можете ли вы увидеть здесь, как соответствующий ранг правого умножения с $ a^{-1} $ может дать желаемую новую обратную? (Или эквивалентно, элементарные операции столбца на $ a^{-1} $.)

Или если вам нравится выполнять операции строк, вы можете использовать $$ a^{-1} (a + e_i delta e_j^ top) = i + a^{-1} e_i delta e_j^ top $$

В первом случае у нас есть личность с добавленной строкой. Это легко выполнить операции столбцов, чтобы вернуть личность снова. Сделайте эти операции на $ a^{-1} $, и результат является новым обратным, по желанию. Второй случай - это личность с добавленной колонкой. В этом случае вы можете выполнять операции по строкам вместо этого. Вы можете выбрать то, что удобнее.