logo

셔먼-모리슨 공식 유도 📂행렬대수

셔먼-모리슨 공식 유도

정리

가역행렬 A∈Rn×nA \in \mathbb{R}^{n \times n} 과 u,v∈Rn\mathbf{u} , \mathbf{v} \in \mathbb{R}^{n} 에 대해 다음이 성립한다. 1+vTA−1u≠0  ⟺  ∃:(A+uvT)−1 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \ne 0 \iff \exists : \left( A + \mathbf{u} \mathbf{v}^{T} \right)^{-1}

셔먼-모리슨 공식

(A+uvT)−1\left( A + \mathbf{u} \mathbf{v}^{T} \right)^{-1} 이 존재할 때, 그 구체적인 공식은 다음과 같다. (A+uvT)−1=A−1−A−1uvTA−11+vTA−1u \left( A + \mathbf{u} \mathbf{v}^{T} \right)^{-1} = A^{-1} - {{ A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }}

설명

셔먼-모리슨 공식의 용도 자체야 통계학에서 피어슨 정리를 증명하는 등에 쓰이는 등 얼마든지 있겠지만, 존재성 증명 자체만 보았을 때 당장 써먹을 수 있는 한가지 방법은 AA 에 작은 요동perturbation uvT\mathbf{u} \mathbf{v}^{T} 이 가해지거나, 특정한 행이나 열을 더하거나 뺐을때 여전히 역행렬이 존재하는지 쉽게 확인하는 것이다.

셔먼-모리슨 공식 자체는 기존에 구해놓은 A−1A^{-1} 를 통해 새로이 역행렬을 구하는 과정을 생략하고 행렬과 상수배, 덧셈과 뺼셈, 곱셈만으로 새로운 역행렬을 찾을 수 있음을 보여주고 있다. 역행렬을 처음부터 계산하는 수고에 비하면 이 정도는 계산이라고 할 수도 없을 정도로 효율적이다.

증명 1

존재성

행렬식 보조정리: 가역행렬 A∈Rn×nA \in \mathbb{R}^{n \times n} 과 u,v∈Rn\mathbf{u} , \mathbf{v} \in \mathbb{R}^{n} 에 대해 다음이 성립한다. det⁡(A+uvT)=(1+vTA−1u)det⁡A \det \left( A + \mathbf{u} \mathbf{v}^{T} \right) = \left( 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \right) \det A

행렬식 보조정리에 따라 det⁡(A+uvT)=(1+vTA−1u)det⁡A \det \left( A + \mathbf{u} \mathbf{v}^{T} \right) = \left( 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \right) \det A 인데 AA 는 가역행렬이라 가정했으므로 det⁡A≠0\det A \ne 0 이고, det⁡(A+uvT)=0\det \left( A + \mathbf{u} \mathbf{v}^{T} \right) = 0 이 성립하는 필요충분조건은 (1+vTA−1u)=0\left( 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \right) = 0 이다.

■

공식

그냥 (A+uvT)\left( A + \mathbf{u} \mathbf{v}^{T} \right) 과 (A−1−A−1uvTA−11+vTA−1u)\left( A^{-1} - {{ A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \right) 을 곱해서 항등행렬 II 인지 확인하는 것으로 충분하다. (A+uvT)(A−1−A−1uvTA−11+vTA−1u)=AA−1+uvTA−1−AA−1uvTA−1+uvTA−1uvTA−11+vTA−1u=I+uvTA−1−uvTA−1+uvTA−1uvTA−11+vTA−1u=I+uvTA−1−u(1+vTA−1u)vTA−11+vTA−1u=I+uvTA−1−uvTA−1=I \begin{align*} & \left( A + \mathbf{u} \mathbf{v}^{T} \right) \left( A^{-1} - {{ A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \right) \\ =& A A^{-1} + \mathbf{u} \mathbf{v}^{T} A^{-1} - {{ A A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} + \mathbf{u} \mathbf{v}^{T} A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \\ =& I + \mathbf{u} \mathbf{v}^{T} A^{-1} - {{ \mathbf{u} \mathbf{v}^{T} A^{-1} + \mathbf{u} \mathbf{v}^{T} A^{-1} \mathbf{u} \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \\ =& I + \mathbf{u} \mathbf{v}^{T} A^{-1} - {{ \mathbf{u} \left( 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} \right) \mathbf{v}^{T} A^{-1} } \over { 1 + \mathbf{v}^{T} A^{-1} \mathbf{u} }} \\ =& I + \mathbf{u} \mathbf{v}^{T} A^{-1} - \mathbf{u} \mathbf{v}^{T} A^{-1} \\ =& I \end{align*} 곱셈의 좌우가 바뀌어도 똑같은데, 이는 생략한다.

■

  1. https://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula ↩︎