数学 、特に線形代数 において、マックス・A・ウッドベリー にちなんで名付けられたウッドベリー行列恒等式 [ 1 ] [ 2 ] 行列のランク k 補正の逆行列は、元の行列の逆行列にランクk 補正を施すことによって計算できることを示しています。この公式の別名としては、行列反転補題 、シャーマン・モリソン・ウッドベリー公式 、または単にウッドベリー公式 などがあります。ただし、この恒等式はウッドベリー報告以前にもいくつかの論文に登場していました。[ 3 ] [ 4 ]
ウッドベリー行列の恒等式は[ 5 ]である。 （ A + U C V ） − 1 = A − 1 − A − 1 U （ C − 1 + V A − 1 U ） − 1 V A − 1 、 {\displaystyle \left(A+UCV\right)^{-1}=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1},}
ここで、 A 、U 、C 、Vは 適合行列 であり、A はn × n 、C はk × k 、U はn × k 、V はk × nである。これは ブロック単位の行列反転 を用いて導出できる。
この恒等式は主に行列で使用されますが、一般的な環 やAb 圏 でも成り立ちます。
ウッドベリー行列恒等式は、逆行列や線形方程式の解を安価に計算することを可能にする。しかし、この式の数値的安定性 についてはほとんど知られていない。誤差範囲に関する公表された結果はない。逸話的な証拠[ 6 ] は、一見無害な例（元の行列と修正された行列の両方が良好な条件数 である場合）でも発散する可能性があることを示唆している。
議論 この結果を証明するために、まずより簡単な結果を証明してみましょう。AとCを単位行列Iに置き換えると、 もう少し 簡単な 別 の恒等式が得られます。 （ 私 + U V ） − 1 = 私 − U （ 私 + V U ） − 1 V 。 {\displaystyle \left(I+UV\right)^{-1}=IU\left(I+VU\right)^{-1}V.} 簡略化された恒等式 から元の式を復元するには、U {\displaystyle U} A − 1 U {\displaystyle A^{-1}U} V {\displaystyle V} C V {\displaystyle CV}
この恒等式自体は、2つのより単純な恒等式の組み合わせと見なすことができます。最初の恒等式は、 私 = （ 私 + P ） − 1 （ 私 + P ） = （ 私 + P ） − 1 + （ 私 + P ） − 1 P 、 {\displaystyle I=(I+P)^{-1}(I+P)=(I+P)^{-1}+(I+P)^{-1}P,} （ 私 + P ） − 1 = 私 − （ 私 + P ） − 1 P 、 {\displaystyle (I+P)^{-1}=I-(I+P)^{-1}P,} （ 私 + P ） − 1 = 私 − P （ 私 + P ） − 1 。 {\displaystyle (I+P)^{-1}=IP(I+P)^{-1}.} プッシュスルー・アイデンティティである [ 7 ] （ 私 + U V ） − 1 U = U （ 私 + V U ） − 1 {\displaystyle (I+UV)^{-1}U=U(I+VU)^{-1}} U （ 私 + V U ） = （ 私 + U V ） U {\displaystyle U(I+VU)=(I+UV)U} （ 私 + V U ） − 1 {\displaystyle (I+VU)^{-1}} （ 私 + U V ） − 1 {\displaystyle (I+UV)^{-1}}
すべてをまとめると、 （ 私 + U V ） − 1 = 私 − U V （ 私 + U V ） − 1 = 私 − U （ 私 + V U ） − 1 V 。 {\displaystyle \left(I+UV\right)^{-1}=I-UV\left(I+UV\right)^{-1}=IU\left(I+VU\right)^{-1}V.}
特別なケース いつV 、 U {\displaystyle V,U} はベクトル であり、この恒等式はシャーマン・モリソン公式 に帰着する。
スカラー の場合、簡略化されたバージョンは単純に 1 1 + u v = 1 − u v 1 + v u 。 {\displaystyle {\frac {1}{1+uv}}=1-{\frac {uv}{1+vu}}.}
和の逆数 n = k かつU = V = I n
（ A + B ） − 1 = A − 1 − A − 1 （ B − 1 + A − 1 ） − 1 A − 1 = A − 1 − A − 1 （ A B − 1 + 私 ） − 1 。 {\displaystyle {\begin{aligned}\left(A+B\right)^{-1}&=A^{-1}-A^{-1}\left(B^{-1}+A^{-1}\right)^{-1}A^{-1}\\[1ex]&=A^{-1}-A^{-1}\left(AB^{-1}+{I}\right)^{-1}.\end{aligned}}}
上記の式の右辺の項を統合し続けると、華恒等式が得られる。 （ A + B ） − 1 = A − 1 − （ A + A B − 1 A ） − 1 。 {\displaystyle \left({A}+{B}\right)^{-1}={A}^{-1}-\left({A}+{A}{B}^{-1}{A}\right)^{-1}.}
同じアイデンティティのもう1つの有用な形式は （ A − B ） − 1 = A − 1 + A − 1 B （ A − B ） − 1 、 {\displaystyle \left({A}-{B}\right)^{-1}={A}^{-1}+{A}^{-1}{B}\left({A}-{B}\right)^{-1},}
これは、上記とは異なり、B {\displaystyle B} 単数 であり、再帰的な構造を持ち、 （ A − B ） − 1 = ∑ k = 0 ∞ （ A − 1 B ） k A − 1 {\displaystyle \left({A}-{B}\right)^{-1}=\sum _{k=0}^{\infty }\left({A}^{-1}{B}\right)^{k}{A}^{-1}} 半径 がA − 1 B {\displaystyle A^{-1}B} （ A − B ） − 1 {\displaystyle (A-B)^{-1}}
この形式は、 Bが A の摂動である場合の摂動展開で使用できます。
バリエーション
二項逆定理 A 、B 、U 、V がそれぞれ n × n 、k × k 、n × k 、k × n のサイズの行列である場合、（ A + U B V ） − 1 = A − 1 − A − 1 U B （ B + B V A − 1 U B ） − 1 B V A − 1 {\displaystyle \left(A+UBV\right)^{-1}=A^{-1}-A^{-1}UB\left(B+BVA^{-1}UB\right)^{-1}BVA^{-1}}
ただし、A とB + BVA −1 UB は 非特異である。後者の非特異性は、B −1 が存在することを要求する。なぜなら、 B −1 はB ( I + VA −1 UB )B のランクを超えることができないからである。[ 7 ]
B は可逆であるため、右辺の括弧内の逆数を挟む2 つのB項は ( B −1 ) −1 に置き換えることができ、 元のウッドベリー恒等式が得られます。
B が特異行列で、場合によっては非平方行列である場合のバリエーション： [ 7 ] （ A + U B V ） − 1 = A − 1 − A − 1 U （ 私 + B V A − 1 U ） − 1 B V A − 1 。 {\displaystyle (A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}BVA^{-1}.}
A が特異な場合についても公式が存在する。[ 8 ]
派生
直接的な証拠 この公式は、以下の点を確認することで証明できる。（ A + U C V ） {\displaystyle (A+UCV)} （ A + U C V ） [ A − 1 − A − 1 U （ C − 1 + V A − 1 U ） − 1 V A − 1 ] = { 私 − U （ C − 1 + V A − 1 U ） − 1 V A − 1 } + { U C V A − 1 − U C V A − 1 U （ C − 1 + V A − 1 U ） − 1 V A − 1 } = { 私 + U C V A − 1 } − { U （ C − 1 + V A − 1 U ） − 1 V A − 1 + U C V A − 1 U （ C − 1 + V A − 1 U ） − 1 V A − 1 } = 私 + U C V A − 1 − （ U + U C V A − 1 U ） （ C − 1 + V A − 1 U ） − 1 V A − 1 = 私 + U C V A − 1 − U C （ C − 1 + V A − 1 U ） （ C − 1 + V A − 1 U ） − 1 V A − 1 = 私 + U C V A − 1 − U C V A − 1 = 私 。 {\displaystyle {\begin{aligned}&\left(A+UCV\right)\left[A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right]\\={}&\left\{I-U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}+\left\{UCVA^{-1}-UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&\left\{I+UCVA^{-1}\right\}-\left\{U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}+UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&I+UCVA^{-1}-\left(U+UCVA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UC\left(C^{-1}+VA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UCVA^{-1}\\={}&I.\end{aligned}}}
アプリケーション この恒等式は、A − 1が既に計算されていて、( A + UCV ) − 1 を計算したい特定 の数値計算で役立ちます。A の逆行列が利用可能な場合、恒等式の右辺を使用して結果を得るには、C −1 + VA −1 U の逆行列を見つけるだけで済みます。C の次元が A よりはるかに小さい場合、これはA + UCV を 直接逆行列にするよりも効率的です。一般的なケースは、 A の低ランク更新A + UCV の逆行列を見つけること( U は数列、V は 数行しかない場合)、または、行列B が低ランク行列 UCV で近似できる場合の行列 A + B の逆 行列の近似を見つけることです。たとえば、特異値分解 を使用します。
これは、例えばカルマンフィルタ や再帰的最小二乗 法において、状態ベクトルサイズの行列の逆行列計算を必要とするパラメトリック解を 、条件方程式に基づく解に置き換えるために用いられます。カルマンフィルタの場合、この行列の次元は観測ベクトルの次元と同じであり、一度に1つの新しい観測値しか処理しない場合は、最小で1となります。これにより、フィルタのリアルタイム計算が大幅に高速化されます。
C が単位行列I の場合、行列私 + V A − 1 U {\displaystyle I+VA^{-1}U} 数値線形代数 および数値偏微分方程式では、 容量行列 として知られています。[ 4 ]
注記 ↑ Max A. Woodbury、「修正行列の逆行列計算」 、メモランダムレポート42、統計研究グループ、プリンストン大学、プリンストン、ニュージャージー州、1950年、4ページ、 MR 0038136 ↑ Max A. Woodbury、『入力行列の安定性』 、シカゴ、イリノイ州、1949年、5ページ、 MR 0032564 ↑ Guttmann, Louis (1946). "逆行列を計算するための拡大法" . Ann. Math. Statist . 17 (3): 336– 343. doi : 10.1214/aoms/1177730946 . 1 2 Hager, William W. (1989). "行列の逆行列の更新". SIAM Review . 31 (2): 221– 239. doi : 10.1137/1031049 . JSTOR 2030425 . MR 0997457 . ↑ Higham, Nicholas ( 2002). 数値アルゴリズムの精度と安定性 （第2 版）. SIAM . p. 258. ISBN 978-0-89871-521-7 . MR 1927606 . ↑ 「 MathOverflow の議論」 。MathOverflow 。 1 2 3 Henderson, HV; Searle, SR (1981). "行列の和の逆行列の導出について" (PDF) . SIAM Review . 23 (1): 53– 60. doi : 10.1137/1023004 . hdl : 1813/32749 . JSTOR 2029838 . ↑ Kurt S. Riedel、「中心化への応用を伴うランク増加行列のシャーマン・モリソン・ウッドベリー恒等式」、 SIAM Journal on Matrix Analysis and Applications 、13 (1992)659-662、 doi : 10.1137/0613040プレプリントMR 1152773 ↑ バーンスタイン、デニス S. (2018). スカラー、ベクトル、行列の数学：理論、事実、公式 （改訂増補 版）. プリンストン：プリンストン大学出版局. p. 638. ISBN 9780691151205 。↑ Schott, James R. (2017). 統計学のための行列解析 （第3 版）. ホーボーケン、ニュージャージー州：John Wiley & Sons, Inc. p. 219. ISBN 9781119092483 。Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「セクション 2.7.3. ウッドベリーの公式」、Numerical Recipes: The Art of Scientific Computing (第 3 版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-8 
![{\displaystyle {\begin{aligned}\left(A+B\right)^{-1}&=A^{-1}-A^{-1}\left(B^{-1}+A^{-1}\right)^{-1}A^{-1}\\[1ex]&=A^{-1}-A^{-1}\left(AB^{-1}+{I}\right)^{-1}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da6474384e0a95c513b2250c5a36638881482b4b)
![{\displaystyle {\begin{aligned}&\left(A+UCV\right)\left[A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right]\\={}&\left\{IU\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}+\left\{UCVA^{-1}-UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&\left\{I+UCVA^{-1}\right\}-\left\{U\left(C^{-1}+VA^{-1 }U\right)^{-1}VA^{-1}+UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&I+UCVA^{-1}-\left(U+UCVA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UC\left(C^{-1}+VA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UCVA^{-1}\\={}&I.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f9188a55ebfb78625ce03beb899b67c010612cc)
