当前位置：网站首页>schur completement

schur completement

2022-07-30 07:49:00 【sunset stained ramp】

目的：Study the derivation of some formulas,schur Complement formulas are often encountered in matrix multiplication,So write down the derivation formula to deepen your understanding

舒尔补(schur completement)定义
in linear algebra or matrix theory,Schur complement Written in matrix block form,表示如下：
M = [ A B C D ] M = \begin{bmatrix} A&B\\C&D \end{bmatrix} M=[AC​BD​]
其中 A , B , C , D A, B, C, D A,B,C,D分别表示 p × p , p × q , q × p , q × q p × p, p × q, q × p, q × q p×p,p×q,q×p,q×q 维度的矩阵, p , q p,q p,qare two non-negative integers.因此可以看到 M M M为 ( p + q ) × ( p + q ) (p+q) \times (p+q) (p+q)×(p+q)的方正.
如果 D D D是可逆(invertible),then the matrix block Schur completement 被定义为:
M / D : = A − B D − 1 C M/D:=A-BD^{-1}C M/D:=A−BD−1C
如果 A A A是可逆(invertible),then the matrix block Schur completement 被定义为:
M / A : = D − C A − 1 B M/A:=D-CA^{-1}B M/A:=D−CA−1B
A B C D ABCD ABCD: 它都是顺时针方向.
作用
1）将 M M M The matrix becomes upper triangular or lower triangular, respectively.
M = [ A B C D ] = [ I p B D − 1 0 I q ]   [ A − B D − 1 C 0 0 D ]   [ I p 0 D − 1 C I q ] M=\begin{bmatrix} A&B\\C&D \end{bmatrix}=\begin{bmatrix} I_p&BD^{-1}\\0&I_q \end{bmatrix} \space \begin{bmatrix} A-BD^{-1}C&0\\0&D \end{bmatrix} \space \begin{bmatrix} I_p&0\\D^{-1}C&I_q \end{bmatrix} M=[AC​BD​]=[Ip​0​BD−1Iq​​] [A−BD−1C0​0D​] [Ip​D−1C​0Iq​​]

证明一：
If you want to get the diagonal matrix,First use Gaussian elimination,消去 C C C,Obtained using the formula（It is multiplied by the right,Indicates row elimination,这样 B D BD BD不变）

[ A B C D ] [ I p 0 X I q ] = [ A ∗ B 0 D ] \begin{bmatrix} A&B\\C&D \end{bmatrix} \begin{bmatrix} I_p&0\\X&I_q \end{bmatrix}= \begin{bmatrix} A^*&B\\0&D \end{bmatrix} [AC​BD​][Ip​X​0Iq​​]=[A∗0​BD​]

The obtained equation is as follows
C + D X = 0 = > X = − D − 1 C C+DX=0=>X=-D^{-1}C C+DX=0=>X=−D−1C

将 X X XBring in the formula for the matrix above A ∗ = A + B X A^*=A+BX A∗=A+BX得到：

[ A B C D ] [ I p 0 − D − 1 C I q ] = [ A − B D − 1 C B 0 D ] \begin{bmatrix} A&B\\C&D \end{bmatrix} \begin{bmatrix} I_p&0\\-D^{-1}C&I_q \end{bmatrix}= \begin{bmatrix} A-BD^{-1}C&B\\0&D \end{bmatrix} [AC​BD​][Ip​−D−1C​0Iq​​]=[A−BD−1C0​BD​]

Now use the elimination method to eliminate B B B,Use row elimination.In the formula it is left multiplication.
[ I p X 0 I q ] [ A − B D − 1 C B 0 D ] = [ A − B D − 1 C 0 0 D ] \begin{bmatrix} I_p&X\\0&I_q \end{bmatrix} \begin{bmatrix} A-BD^{-1}C&B\\0&D \end{bmatrix}=\begin{bmatrix} A-BD^{-1}C&0\\0&D \end{bmatrix} [Ip​0​XIq​​][A−BD−1C0​BD​]=[A−BD−1C0​0D​]
The obtained equation is as follows：
B + D X = 0 = > X = − D − 1 B B+DX=0=>X=-D^{-1}B B+DX=0=>X=−D−1B

将 X X Xinto the equation to get
[ I p − D − 1 B 0 I q ] [ A − B D − 1 C B 0 D ] = [ A − B D − 1 C 0 0 D ] \begin{bmatrix} I_p&-D^{-1}B\\0&I_q \end{bmatrix} \begin{bmatrix} A-BD^{-1}C&B\\0&D \end{bmatrix}=\begin{bmatrix} A-BD^{-1}C&0\\0&D \end{bmatrix} [Ip​0​−D−1BIq​​][A−BD−1C0​BD​]=[A−BD−1C0​0D​]

Summarizing the two formulas can be obtained：

M = [ A B C D ] = [ I p B D − 1 0 I q ]   [ A − B D − 1 C 0 0 D ]   [ I p 0 D − 1 C I q ] M=\begin{bmatrix} A&B\\C&D \end{bmatrix}=\begin{bmatrix} I_p&BD^{-1}\\0&I_q \end{bmatrix} \space \begin{bmatrix} A-BD^{-1}C&0\\0&D \end{bmatrix} \space \begin{bmatrix} I_p&0\\D^{-1}C&I_q \end{bmatrix} M=[AC​BD​]=[Ip​0​BD−1Iq​​] [A−BD−1C0​0D​] [Ip​D−1C​0Iq​​]

证明二：
Use the algebra of linear systems to find
[ A B C D ] [ X p X q ] = [ Y p Y q ] \begin{bmatrix} A&B\\C&D \end{bmatrix}\begin{bmatrix} X_p\\X_q \end{bmatrix}=\begin{bmatrix} Y_p\\Y_q \end{bmatrix} [AC​BD​][Xp​Xq​​]=[Yp​Yq​​]

因为 [ Y p Y q ] = ( [ A B C D ] ) − 1 [ X p X q ] \begin{bmatrix} Y_p\\Y_q \end{bmatrix}=(\begin{bmatrix} A&B\\C&D \end{bmatrix})^{-1}\begin{bmatrix} X_p\\X_q \end{bmatrix} [Yp​Yq​​]=([AC​BD​])−1[Xp​Xq​​]
因为 D D D可逆,得到下面公式
X q = Y q − D − 1 C X p X_q=Y_q-D^{-1}CX_p Xq​=Yq​−D−1CXp​
Bring in A X p + B X q = Y p AX_p+BX_q=Y_p AXp​+BXq​=Yp​得到 X p X_p Xp​
X p = ( A − B D − 1 C ) − 1 ( Y p − B Y q ) X_p=(A-BD^{-1}C)^{-1}(Y_p-BY_q) Xp​=(A−BD−1C)−1(Yp​−BYq​)
在将 X p X_p Xp​带入 X q = Y q − D − 1 C X p X_q=Y_q-D^{-1}CX_p Xq​=Yq​−D−1CXp​:
X q = Y q − D − 1 C ( A − B D − 1 C ) − 1 ( Y p − B Y q ) X_q=Y_q-D^{-1}C(A-BD^{-1}C)^{-1}(Y_p-BY_q) Xq​=Yq​−D−1C(A−BD−1C)−1(Yp​−BYq​)
After converting the above into vector form,in converting to a matrix.

2）Quickly find matrices M M M的逆.
M − 1 = [ A B C D ] − 1 = ( [ I p B D − 1 0 I q ]   [ A − B D − 1 C 0 0 D ]   [ I p 0 D − 1 C I q ] ) − 1 = [ I p 0 − D − 1 C I q ]   [ ( A − B D − 1 C ) − 1 0 0 D − 1 ]   [ I p − B D − 1 0 I q ]   = [ ( A − B D − 1 C ) − 1 − ( A − B D − 1 C ) − 1 B D − 1 − D − 1 C ( A − B D − 1 C ) − 1 D − 1 C ( A − B D − 1 C ) − 1 B D − 1 + D − 1 ] = [ ( M / D ) − 1 − ( M / D ) − 1 B D − 1 − D − 1 C ( M / D ) − 1 D − 1 + D − 1 C ( M / D ) − 1 B D − 1 ] M^{-1} =\begin{bmatrix} A&B\\C&D \end{bmatrix} ^{-1}= (\begin{bmatrix} I_p&BD^{-1}\\0&I_q \end{bmatrix} \space \begin{bmatrix} A-BD^{-1}C&0\\0&D \end{bmatrix} \space \begin{bmatrix} I_p&0\\D^{-1}C&I_q \end{bmatrix})^{-1} \\ \\ \\ =\begin{bmatrix} I_p&0\\-D^{-1}C&I_q \end{bmatrix}\space \begin{bmatrix} (A-BD^{-1}C)^{-1}&0\\0&D^{-1} \end{bmatrix} \space \begin{bmatrix} I_p&-BD^{-1}\\0&I_q \end{bmatrix} \space \\ \\ \\ =\begin{bmatrix} (A-BD^{-1}C)^{-1}& -(A-BD^{-1}C)^{-1}BD^{-1}\\-D^{-1}C (A-BD^{-1}C)^{-1}&D^{-1}C(A-BD^{-1}C)^{-1}BD^{-1} + D^{-1} \end{bmatrix} \\ \\ \\ =\begin{bmatrix} (M/D)^{-1}&-(M/D)^{-1}BD^{-1}\\-D^{-1}C(M/D)^{-1}&D^{-1} + D^{-1}C(M/D)^{-1}BD^{-1} \end{bmatrix} M−1=[AC​BD​]−1=([Ip​0​BD−1Iq​​] [A−BD−1C0​0D​] [Ip​D−1C​0Iq​​])−1=[Ip​−D−1C​0Iq​​] [(A−BD−1C)−10​0D−1​] [Ip​0​−BD−1Iq​​] =[(A−BD−1C)−1−D−1C(A−BD−1C)−1​−(A−BD−1C)−1BD−1D−1C(A−BD−1C)−1BD−1+D−1​]=[(M/D)−1−D−1C(M/D)−1​−(M/D)−1BD−1D−1+D−1C(M/D)−1BD−1​]
Known from the formula,when finding the inverse of a matrix,可以通过先获取 ( M / D ) (M/D) (M/D),Then get its inverse.

原网站

版权声明
本文为[sunset stained ramp]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/211/202207300542270637.html

边栏推荐

猜你喜欢

随机推荐