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に小さな乱れperturbationuvT\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 ↩︎