행렬 순위 정리
수학 (특히 선형 대수학 )에서는 Max A의 이름을 딴 Woodbury 매트릭스 아이덴티티 가 있다.우드베리는 일부 행렬 의 순위-k 수정의 역행위는 원래 행렬의 역행위로 순위-k 보정을 수행하여 계산할 수 있다고 말한다.[1] [2] 이 공식의 대체 이름은 매트릭스 반전 보조정리 인 셔먼-모리슨- 우드베리 공식 이나 그냥 우드베리 공식 .그러나 그 정체는 우드베리 보고서 이전에 여러 신문에 실렸다.[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}{-1}VA^{-1}VA^{-1},} 여기 서 A, U , C 및 V 는 준수 가능한 행렬 이다.A 는 n ×n , C 는 k ×k , U 는 n ×k , V 는 k ×n 이다.이는 블럭화 행렬 역순 을 사용하여 도출할 수 있다.
그 정체성은 주로 행렬에 사용되지만, 그것은 일반 링이나 Ab-category 에서 사용된다.
토론 이 결과를 증명하기 위해, 우리는 더 단순한 것을 증명하는 것으로 시작할 것이다. A 와 C 를 ID 매트릭스 I 로 대체하면 좀 더 간단한 또 다른 ID를 얻을 수 있다.
( I + U V ) − 1 = I − U ( I + V U ) − 1 V . 왼쪽(I+) UV\오른쪽)^{-1}=I-U\왼쪽(I+VU\오른쪽)^{-1} 이 축소된 ID 에서 원래 방정식을 복구하려면 U 1 X {\displaystyle U=A^{-1} X } C {\displaystyle V=CY} .
이 정체성 자체는 두 가지 단순한 정체성의 결합으로 볼 수 있다. 우리는 로부터 첫 번째 신원을 얻는다.
I I 1 I P P I 1 P {\displaystyle I=(I+P)^{-1}(I+P)=(I+P)^{-1}+(I+P)^{-1 }},},},},} 그러므로
( I P 1 I P P {\displaystyle (I+P)^{-1}=I-(I+P)^{-1 마찬가지로
( I + P ) − 1 = I − P ( I + P ) − 1 . {\displaystyle (I+P)^{-1}=I-P(I+P)^{-1}. } 두 번째 정체성은 이른바 푸시스루 [6]
( I + U V ) − 1 U = U ( I + V U ) − 1 {\displaystyle (I+UV)^{-1}U=U(I+VU)^{-1} 우리가 얻은 것
U ( I + V U ) = ( I + U V ) U {\displaystyle U(I+VU)=(I+UV) U} (I V U - 오른쪽 {\ displaystyle (I+ )^{- 1}, 1 {\ displaystyle (I+UV)^{-1}
특례 V U {\displaystyle V,U} 셔먼-모리슨 공식 으로 감소한다.
스칼라 케이스에서는 간단히 (축소된 버전)
1 1 + u v = 1 − u v 1 + u v . {\displaystyle {\frac {1}{1+uv}=1-{\frac {uv}{1+uv}}. } 합의 역 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 + I ) − 1 . {\displaystyle {\begin}\왼쪽({A}+{B}\오른쪽)^{-1}&=A^{-1}-A^{-1}(B^{-1}+A^{-1})^{-1A^{-1}^{-1}-1}A^{-1}\&={{-1} A}^{-1}-{A}^{-1}\왼쪽({A}{B}^{-1}+{A}) I}\right)^{-1} \end{정렬}}} 위 방정식의 맨 오른쪽의 용어를 계속 합치면 화의 정체성 이 나타난다.
( A + B ) − 1 = A − 1 − ( A + A B − 1 A ) − 1 . {\displaystyle \left({A}+{B}\right)^{-1}={A}^{1}-\reft({A}+{A}{A}}}{{A}}}{}}}{A}}}}}} B}^{-1}{A}\오른쪽)^{-1}. } 동일한 정체성의 또 다른 유용한 형태는
( A − B ) − 1 = A − 1 + A − 1 B ( A − B ) − 1 , {\displaystyle \left({A}-{B}\right)^{-1}={A}^{-1}+{A}^{B}\reft({A}-{B}\right)^{1}, {-1} 재귀적 구조를 가진
( A − B ) − 1 = ∑ k = 0 ∞ ( A − 1 B ) k A − 1 . {\displaystyle \left({A}-{B}\right)^{-1}=\sum _{k=0}^{\ft{A}^{1}{B}\right) ^{k}{A}^{-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+B) VA^{-1}UB\right)^{-1}BVA^{-1} 단, A 와 B + BVAUB 는−1 비경상적이다. 후자의 비논리성은 B(I + VAUB −1 )등급 은 B의 등급을 초과할 수 없으므로 −1 B가 존재할 것을 요구한다.[6]
B 는 수정이 불가능하기 때문에 오른쪽의 모체 수량을 역행하는 두 개 의 B 용어는 (B −1 )로 대체될 수 있으며,−1 이는 원래의 우드베리 아이덴티티로 귀결된다.
B 가 단수일 때, 심지어 제곱이 아닐 수도 있는 경우에 대한 변동:[6]
( A + U B V ) − 1 = A − 1 − A − 1 U ( I + B V A − 1 U ) − 1 B V A − 1 . {\displaystyle (A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}{-1}BVA^{-1}. } A 가 단수인 특정 사례에 대해서도 수식이 존재한다.[7]
파생어 직접증거 이 공식은 U V {\displaystyle (A+UCV)}
( A + U C V ) [ A − 1 − A − 1 U ( C − 1 + V A − 1 U ) − 1 V A − 1 ] = { I − 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 } = { I + 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 } = I + U C V A − 1 − ( U + U C V A − 1 U ) ( C − 1 + V A − 1 U ) − 1 V A − 1 = I + U C V A − 1 − U C ( C − 1 + V A − 1 U ) ( C − 1 + V A − 1 U ) − 1 V A − 1 = I + U C V A − 1 − U C V A − 1 = I . {\displaystyle {\begin{aigned}&\좌측(A+UCV\우측)\좌측[A^{-1}-A^{-1}U\좌측(C^{-1}+VA^{-1}우측)^{-1}VA^{-1}{-1}\우측] \={}&\왼쪽\{I-U\왼쪽(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}{-1}VA^{-1}{-1}{-1}{-1}{-1}{-1}{-1}VA^{-1}-1}\right\\\{{{{{}}}}}}}}}}} UCVA^{-1}-UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}{-1}{-1}VA^{-1}\}\={}&\왼쪽\) {I+UCVA^{-1}\우측\}-\좌측\{ U\왼쪽(C^{-1}+VA^{-1}U\오른쪽)^{-1}VA^{-1}VA^{-1}+ UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}{-1}\right\}\={} &I+UCVA^{-1}-\좌측(U+UCVA^{-1}U\우측)\좌측(C^{-1}+VA^{-1}+VA^{-1}우측)^{-1}VA^{-1}{-1}VA^{-1}\={} &I+UCVA^{-1}-UC\왼쪽(C^{-1}+VA^{-1}U\오른쪽)\왼쪽(C^{-1}+VA^{-1}+VA^{-1}U\오른쪽)^{-1}VA^{-1}{-1}VA^{-1}\={} &I+UCVA^{-1}-UCVA^{-1}\={}&I. \end{정렬}}} 대체 교정쇄 대수적 증명
먼저 이런 유용한 정체성을 생각해봐
U + U C V A − 1 U = U C ( C − 1 + V A − 1 U ) = ( A + U C V ) A − 1 U ( A + U C V ) − 1 U C = A − 1 U ( C − 1 + V A − 1 U ) − 1 {\displaystyle {\begin}U+UCVA^{-1}U&= UC\왼쪽(C^{-1}+VA^{-1}U\오른쪽)=\왼쪽(A+UCV\오른쪽) A^{-1}U\\\좌측(A+UCV\우측)^{-1}U&=A^{-1}U\좌측(C^{-1}+VA^{-1}우측)^{-1}{-1}{-1}U\우측)^{-1}{1}{정렬}}}}}}}} 자, 이제.
A − 1 = ( A + U C V ) − 1 ( A + U C V ) A − 1 = ( A + U C V ) − 1 ( I + U C V A − 1 ) = ( A + U C V ) − 1 + ( A + U C V ) − 1 U C V A − 1 = ( A + U C V ) − 1 + A − 1 U ( C − 1 + V A − 1 U ) − 1 V A − 1 . {\displaystyle {\reasoned} A^{-1}&=\왼쪽(A+UCV\오른쪽)^{-1}\왼쪽(A+UCV\오른쪽) A^{-1}\&=\왼쪽(A+UCV\오른쪽)^{-1}\왼쪽(I+UCVA^{-1}\오른쪽) \\&=\left(A+UCV\right)^{-1}+\left(A+UCV\right)^{-1}UCVA^{-1}\\&=\left(A+UCV\right)^{-1}+A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}. \end{정렬}}}
LDU 분해에서 파생
매트릭스부터 시작해
[ A U V C ] {\displaystyle {\bmatrix} A&U\\V&C\end{bmatrix}} A 에 의거한 입력을 제거함으로써 (A 가 불가항력임을 감안하여) 우리는 A에 의거한 입력을 제거하게 된다.
[ I 0 − V A − 1 I ] [ A U V C ] = [ A U 0 C − V A − 1 U ] {\displaystyle {\bmatrix} I&0\\-VA^{-1}& I\end{bmatrix}{\begin{bmatrix} A&U\\V&C\end{bmatrix}={\begin{bmatrix} A&U\\0&C-VA^{-1}U\end{bmatrix}} 마찬가지 로, C 위의 항목을 제거하면
[ A U V C ] [ I − A − 1 U 0 I ] = [ A 0 V C − V A − 1 U ] {\displaystyle {\bmatrix} A&U\\V&C\end{bmatrix}{\begin{bmatrix} I&-A^{-1}U\\0& I\end{bmatrix}={\begin{bmatrix} A&0\\V&C-VA^{-1}U\end{bmatrix}} 이제 위의 두 가지를 합치면
[ I 0 − V A − 1 I ] [ A U V C ] [ I − A − 1 U 0 I ] = [ A 0 0 C − V A − 1 U ] {\displaystyle {\bmatrix} I&0\\-VA^{-1}& I\end{bmatrix}{\begin{bmatrix} A&U\\V&C\end{bmatrix}{\begin{bmatrix} I&-A^{-1}U\\0& I\end{bmatrix}={\begin{bmatrix} A&0\\0&C-VA^{-1}U\end{bmatrix}} 오른쪽으로 이동하면 힘이 난다.
[ A U V C ] = [ I 0 V A − 1 I ] [ A 0 0 C − V A − 1 U ] [ I A − 1 U 0 I ] {\displaystyle {\bmatrix} A&U\\V&C\end{bmatrix}={\begin{bmatrix} I&0\\VA^{-1}& I\end{bmatrix}{\begin{bmatrix} A&0\\0&C-VA^{-1}U\end{bmatrix}{\begin{bmatrix} I&A^{-1}U\\0& I\end{bmatrix}} 즉, 블록 행렬을 위쪽 삼각형, 대각선 및 아래쪽 삼각형 행렬로 분해하는 것이다.
이제 양쪽을 뒤집으면
[ A U V C ] − 1 = [ I A − 1 U 0 I ] − 1 [ A 0 0 C − V A − 1 U ] − 1 [ I 0 V A − 1 I ] − 1 = [ I − A − 1 U 0 I ] [ A − 1 0 0 ( C − V A − 1 U ) − 1 ] [ I 0 − V A − 1 I ] = [ A − 1 + A − 1 U ( C − V A − 1 U ) − 1 V A − 1 − A − 1 U ( C − V A − 1 U ) − 1 − ( C − V A − 1 U ) − 1 V A − 1 ( C − V A − 1 U ) − 1 ] ( 1 ) {\displaystyle {\displaysty}{bmatrix} A&U\\V&C\end{bmatrix}^{-1}={\begin{bmatrix} I&A^{-1}U\\0& I\end{bmatrix}^{-1}{\begin{bmatrix} A&0\\0&C-VA^{-1}U\end{bmatrix}^{-1}{\begin{bmatrix} I&0\\VA^{-1}& I\end{bmatrix}^{-1}\[8pt]&={\begin{bmatrix} I&-A^{-1}U\\0& I\end{bmatrix}{\begin{bmatrix}A^{-1}&0\\\\\좌측(C-VA^{-1}U\우측)^{-1}\end{bmatrix}}{\bgin{bmatrix}} I&0\\-VA^{-1}& I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}A^{-1}+A^{-1}U\left(C-VA^{-1}U\right)^{-1}VA^{-1}&-A^{-1}U\left(C-VA^{-1}U\right)^{-1}\\-\left(C-VA^{-1}U\right)^{-1}VA^{-1}&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}\qquad \mathrm {(1)} \end{aligned}}} 우리는 다른 방법으로도 똑같이 잘 할 수 있었다. 즉, C 가 되돌릴 수 없다면)
[ A U V C ] = [ I U C − 1 0 I ] [ A − U C − 1 V 0 0 C ] [ I 0 C − 1 V I ] {\displaystyle {\bmatrix} A&U\\V&C\end{bmatrix}={\begin{bmatrix} I&UC^{-1}\\0& I\end{bmatrix}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}{\begin{bmatrix}} I&0\\C^{-1}V& I\end{bmatrix}} 다시 양쪽을 뒤집으면
[ A U V C ] − 1 = [ I 0 C − 1 V I ] − 1 [ A − U C − 1 V 0 0 C ] − 1 [ I U C − 1 0 I ] − 1 = [ I 0 − C − 1 V I ] [ ( A − U C − 1 V ) − 1 0 0 C − 1 ] [ I − U C − 1 0 I ] = [ ( A − U C − 1 V ) − 1 − ( A − U C − 1 V ) − 1 U C − 1 − C − 1 V ( A − U C − 1 V ) − 1 C − 1 + C − 1 V ( A − U C − 1 V ) − 1 U C − 1 ] ( 2 ) {\displaystyle {\displaysty}{bmatrix} A&U\\V&C\end{bmatrix}^{-1}={\begin{bmatrix} I&0\\C^{-1}V& I\end{bmatrix}:{-1}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}^{-1}{\begin{bmatrix} I&UC^{-1}\\0& I\end{bmatrix}^{-1}\[8pt]&={\begin{bmatrix} I&0\\-C^{-1}V& I\end{bmatrix}{\begin{bmatrix}\왼쪽(A-UC^{-1}V\right)^{-1}&0\C^{-1}\end{bmatrix}}{\bmatrix}} I&-UC^{-1}\\0& I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}\left(A-UC^{-1}V\right)^{-1}&-\left(A-UC^{-1}V\right)^{-1}UC^{-1}\\-C^{-1}V\left(A-UC^{-1}V\right)^{-1}&C^{-1}+C^{-1}V\left(A-UC^{-1}V\right)^{-1}UC^{-1}\end{bmatrix}}\qquad \mathrm {(2)} \end{aligned}}} 이제 위의 (1)과 (2)의 RHS의 원소(1, 1)를 비교하면 우드베리 공식이 주어진다.
( A − U C − 1 V ) − 1 = A − 1 + A − 1 U ( C − V A − 1 U ) − 1 V A − 1 . {\displaystyle \left(A-UC^{-1}V\right)^{-1}=A^{-1}+A^{-1}U\left(C-VA^{-1}U\right)^{-1}{-1}VA^{-1}. }
적용들 이 ID는 A 가−1 이미 계산되었고 계산하기를 원하는 특정 수치 계산에 유용하다(A + UCV ).−1 A 의 역수를 이용할 수 있는 상태에서, ID의 우측을 이용하여 결과를 얻기 위해서는 C −1 + VAU 의−1 역행만 찾으면 된다.C 가 A 보다 훨씬 작은 치수를 가지고 있다면 이 는 A + UCV 를 직접 뒤집는 것보다 효율적이다.일반적인 경우는 A 의 낮은 순위 업데이트 A + UCV (U 가 몇 열만 있고 V 가 몇 행만 있는 경우)의 역순을 찾거나, 행렬 B 가 낮은 순위 매트릭스 UCV 로 근사치를 구할 수 있는 매트릭스 A + B 의 역순에 대한 근사치를 구하는 것이다(예: 단수 값 분해 사용 ).
이는 예를 들어 Kalman 필터 와 재귀 최소 제곱법 에서 적용되며, 상태 벡터 크기 매트릭스의 역전이 필요한 파라메트릭 용액 을 조건 방정식 기반 용액으로 대체한다. Kalman 필터의 경우 이 행렬은 관측치의 벡터 치수를 가지고 있다. 즉, 한 번에 하나의 새로운 관측치만 처리되는 경우 1만큼 작다. 이것은 필터의 종종 실시간 계산을 현저하게 가속화한다.
C 가 아이덴티티 매트릭스 I인 경우, 행렬 V A 1 U {\displaystyle I+VA^{-1}U} 숫자 선형 대수 와 숫자 부분 미분 방정식 에서 캐패시턴스 매트릭스 로 알려져[4]
참고 항목 메모들 ^ Max A. Woodbury, 개조된 행렬 뒤집기 , 비망록 파충류. 42, 프린스턴 대학교, 프린스턴 대학교, NJ, 1950, 4pp MR 38136 ^ Max A. Woodbury, The Stability of Out-Input Matrice . 1949년 시카고, 일리노이 주, 5 페이지 MR 32564 ^ Guttmann, Louis (1946). "Enlargement methods for computing the inverse matrix" . Ann. Math. Statist . 17 (3): 336–343. doi :10.1214/aoms/1177730946 ^ a b Hager, William W. (1989). "Updating the inverse of a matrix". SIAM Review . 31 (2): 221–239. doi :10.1137/1031049 . JSTOR 2030425 . MR 0997457 . ^ Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms SIAM . p. 258 . ISBN 978-0-89871-521-7 MR 1927606 .^ a b c Henderson, H. V.; Searle, S. R. (1981). "On deriving the inverse of a sum of matrices" (PDF) . SIAM Review . 23 (1): 53–60. doi :10.1137/1023004 . hdl :1813/32749 JSTOR 2029838 . ^ 커트 S. 리델 "셔먼-모리슨- MR1152773 사전 인쇄 MR11537/0613040 , 13 (1992 )659-662, 도이:10 1137/ 0613040 매트릭스 분석 및 응용을 통한 순위 증강을 위한 우드베리 아이덴티티티티", 매트릭스 분석 및 응용에 관한 SIAM 저널 "Matrix를 위한 등급 식별" 외부 링크 
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f9188a55ebfb78625ce03beb899b67c010612cc)
![{\displaystyle {\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix}}^{-1}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}^{-1}{\begin{bmatrix}I&0\\VA^{-1}&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}{\begin{bmatrix}A^{-1}&0\\0&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}{\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}A^{-1}+A^{-1}U\left(C-VA^{-1}U\right)^{-1}VA^{-1}&-A^{-1}U\left(C-VA^{-1}U\right)^{-1}\\-\left(C-VA^{-1}U\right)^{-1}VA^{-1}&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}\qquad \mathrm {(1)} \end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd80a045fa9157c9185e1805320cacf91ce7b40e)
![{\displaystyle {\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&0\\C^{-1}V&I\end{bmatrix}}^{-1}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}^{-1}{\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&0\\-C^{-1}V&I\end{bmatrix}}{\begin{bmatrix}\left(A-UC^{-1}V\right)^{-1}&0\\0&C^{-1}\end{bmatrix}}{\begin{bmatrix}I&-UC^{-1}\\0&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}\left(A-UC^{-1}V\right)^{-1}&-\left(A-UC^{-1}V\right)^{-1}UC^{-1}\\-C^{-1}V\left(A-UC^{-1}V\right)^{-1}&C^{-1}+C^{-1}V\left(A-UC^{-1}V\right)^{-1}UC^{-1}\end{bmatrix}}\qquad \mathrm {(2)} \end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70dd74f08ea4769fe59dc5765fa134270b371d60)
