2015/03/02

逆行列の補助定理(Woodburyの恒等式)

分野: 線形代数  レベル: 大学数学

行列 $A,B,C,D$ に対して
$(A+BDC)^{-1}=A^{-1}-A^{-1}B(D^{-1}+CA^{-1}B)^{-1}CA^{-1}$
(ただし,行列の積が定義できるような適切なサイズ,および $A$ などの逆行列の存在を仮定します)

特に $D=I$ のとき,
$(A+BC)^{-1}=A^{-1}-A^{-1}B(I+CA^{-1}B)^{-1}CA^{-1}$

逆行列の補助定理,Sherman–Morrison–Woodburyの公式,Woodburyの恒等式,シャーマンモリソン公式などいろいろな呼び方があります。

一見複雑な形をしていますが,非常に美しい行列恒等式です。

なぜ嬉しいのか

「行列の積が定義できるような適切なサイズ」というのは,
$A:n\times n$
$B:n\times k$
$C:k\times n$
$D:k\times k$
となります。

Woodburyの恒等式が活躍する3つの条件

  • $A$ の逆行列は既に求まっている
  • $(A+BDC)^{-1}$ を求めたい
  • $k$ が $n$ よりもはるかに小さい($C$ が横長,$B$ が縦長行列)

このとき,$(A+BDC)^{-1}$ を直接計算するよりもWoodburyの恒等式の右辺を計算する方が楽(計算量が少ない)というのが最大の恩恵です。

Sherman–Morrisonの公式

特に極端な例として $k=1$ の場合を考えてみます($k=1$ の場合を特にSherman–Morrisonの公式と言います)。

すると,$B,C$ はベクトル,$D$ はただのスカラーとなり,$BDC^{-1}$ はランク1の行列になります。
そこで,$A$ にランク1の行列を足すことを「少し変化させる」と言うことにすると,Woodburyの恒等式の効果を以下のように表現できます。

$A$ の逆行列が分かっていれば「 $A$ を少しだけ変化させたときの行列」の逆行列も簡単に計算できる。

こう表現するとけっこう役立ちそうですね。自分はこのあたりの話に詳しい訳ではありませんが,カルマンフィルタの勉強をしていたときにいきなり登場してきて驚きました。

証明

最後にSherman–Morrison–Woodburyの公式を証明します!

証明はただ計算するのみです。「$(A+BDC)$ 」と「Woodburyの恒等式の右辺」の積が単位行列 $I$ と一致することを確認すればよいだけです。

証明

$(A+BDC)\{A^{-1}-A^{-1}B(D^{-1}+CA^{-1}B)^{-1}CA^{-1}\}\\
=I+BDCA^{-1}\\
-B(D^{-1}+CA^{-1}B)^{-1}CA^{-1}\\
-BDCA^{-1}B(D^{-1}+CA^{-1}B)^{-1}CA^{-1}\\
=I+BDCA^{-1}\\
-BD(D^{-1}+CA^{-1}B)(D^{-1}+CA^{-1}B)^{-1}CA^{-1}\\
=I+BDCA^{-1}-BDCA^{-1}=I$

なお,ブロック行列とかを持ちだして証明することもできます。

「シャーマンモリソンウッドベリーの公式」。僕は長い名前の定理がけっこう好きです。

Tag: 数学の定理No.1決定戦

分野: 線形代数  レベル: 大学数学