Uzupełnienie Schura

W algebrze liniowej i teorii macierzy dopełnienie Schura macierzy blokowej definiuje się następująco.

Załóżmy, że p , q są nieujemnymi liczbami całkowitymi i przypuśćmy, że A , B , C , D są odpowiednio macierzami p × p , p × q , q × p i q × q liczb zespolonych. Pozwalać

{\ Displaystyle M = \ lewo [{\ rozpocząć {macierz} A & B \\ C & D \ koniec {macierz}} \ prawo]}

tak że M jest macierzą ( p + q ) × ( p + q ).

Jeśli D jest odwracalne, to uzupełnieniem Schura bloku D macierzy M jest macierz p × p zdefiniowana przez

{\ Displaystyle M / D: = A-BD ^ {-1} C.}

Jeśli A jest odwracalne, uzupełnieniem Schura bloku A macierzy M jest macierz q × q zdefiniowana przez

{\ Displaystyle M / A: = D-CA ^ {- 1} B.}

W przypadku, gdy A lub D jest liczbą pojedynczą , zastąpienie uogólnionej odwrotności odwrotnościami M/A i M/D daje uogólnione dopełnienie Schura .

Dopełnienie Schura zostało nazwane na cześć Issaia Schura , który użył go do udowodnienia lematu Schura , chociaż był używany wcześniej. Emilie Virginia Haynsworth jako pierwsza nazwała to uzupełnieniem Schura . Uzupełnienie Schura jest kluczowym narzędziem w dziedzinie analizy numerycznej, statystyki i analizy macierzowej.

Tło

Dopełnienie Schura powstaje podczas wykonywania blokowej eliminacji Gaussa na macierzy M . Aby wyeliminować elementy poniżej przekątnej bloku, mnoży się macierz M przez dolną trójkątną macierz bloku po prawej stronie w następujący sposób:

{\ Displaystyle {\ rozpocząć {wyrównane} & M = {\ rozpocząć {bmatrix} A & B \\ C & D \ koniec {bmatrix}} \ quad \ do \ quad {\ rozpocząć {bmatrix} A & B \\ C & D \ koniec {bmatrix}}} \begin{bmatrix}I_{p}&0\\-D^{-1}C&I_{q}\end{bmatrix}}={\begin{bmatrix}A-BD^{-1}C&B\\0&D\end {bmacierz}},\end{wyrównane}}}

gdzie I _p oznacza macierz identyczności p × p . $_$ rezultacie w górnym _ _ _

Kontynuując proces eliminacji poza ten punkt (tj. wykonując blokową eliminację Gaussa-Jordana ),

{\ Displaystyle {\ rozpocząć {wyrównane} i {\ rozpocząć {bmatrix} A-BD ^ {-1} C&B \\ 0 i D \ koniec {bmatrix}} \ quad \ do \ quad {\ rozpocząć {bmatrix} I_ {p} &-BD^{-1}\\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{bmacierz}},\end{wyrównane}}}

prowadzi do rozkładu LDU M , który brzmi

{\ Displaystyle {\ rozpocząć {wyrównane} M & = {\ rozpocząć {bmatrix} A & B \\ C i D \ koniec {bmatrix}} = {\ rozpocząć {bmatrix} I_ {p} i BD ^ {-1} \\ 0 i I_ {q} \end{bmatrix}}{\begin{bmatrix}A-BD^{-1}C&0\\0&D\end{bmatrix}}{\begin{bmatrix}I_{p}&0\\D^{-1}C&I_ {q}\end{bmacierz}}.\end{wyrównane}}}

Zatem odwrotność M można wyrazić z udziałem D ^-1 i odwrotności dopełnienia Schura, zakładając, że istnieje, ponieważ

{\ Displaystyle {\ rozpocząć {wyrównane} M ^ {-1} = {\ rozpocząć {bmatrix} A & B \\ C i D \ koniec {bmatrix}} ^ {-1} = {} & \ lewo ({\ rozpocząć {bmatrix} I_{p}&BD^{-1}\\0&I_{q}\end{bmatrix}}{\begin{bmatrix}A-BD^{-1}C&0\\0&D\end{bmatrix}}{\begin{ bmatrix}I_{p}&0\\D^{-1}C&I_{q}\end{bmatrix}}\right)^{-1}\\={}&{\begin{bmatrix}I_{p}&0 \\-D^{-1}C&I_{q}\end{bmatrix}}{\begin{bmatrix}\left(A-BD^{-1}C\right)^{-1}&0\\0&D^ {-1}\end{bmatrix}}{\begin{bmatrix}I_{p}&-BD^{-1}\\0&I_{q}\end{bmatrix}}\\[4pt]={}&{ \begin{bmatrix}\left(A-BD^{-1}C\right)^{-1}&-\left(A-BD^{-1}C\right)^{-1}BD^{ -1}\\-D^{-1}C\lewo(A-BD^{-1}C\prawo)^{-1}&D^{-1}+D^{-1}C\lewo( A-BD^{-1}C\right)^{-1}BD^{-1}\end{bmatrix}}\\[4pt]={}&{\begin{bmatrix}\left(M/D \right)^{-1}&-\left(M/D\right)^{-1}BD^{-1}\\-D^{-1}C\left(M/D\right)^ {-1}&D^{-1}+D^{-1}C\left(M/D\right)^{-1}BD^{-1}\end{bmacierz}}.\end{wyrównane} }}

Powyższa zależność pochodzi z operacji eliminacji, które obejmują D ⁻¹ i M/D . Równoważne wyprowadzenie można wykonać, zamieniając role A i D. Zrównując wyrażenia dla M ⁻¹ otrzymane na te dwa różne sposoby, można ustanowić lemat o odwróceniu macierzy , który odnosi się do dwóch uzupełnień Schura M : M / D i M / A (patrz „Wyprowadzenie z rozkładu LDU” w Tożsamość macierzy Woodbury'ego § Dowody alternatywne ).

Nieruchomości

Jeśli p i q są równe 1 (tj. A , B , C i D są skalarami), otrzymujemy znany wzór na odwrotność macierzy 2 na 2:

\ Displaystyle M ^ {-1} = {\ Frac {1} {AD-BC}} \ lewo [{\ rozpocząć {macierz} D&-B \\ - C&A \ koniec {macierz} }\right]}

pod warunkiem, że AD − BC jest różny od zera.

Ogólnie, jeśli A jest odwracalne, to

{\ Displaystyle {\ rozpocząć {wyrównane} M & = {\ rozpocząć {bmatrix} A & B \\ C i D \ koniec {bmatrix}} = {\ rozpocząć {bmatrix} I_ {p} i 0 \\ CA ^ {-1} i I_ {q }\end{bmatrix}}{\begin{bmatrix}A&0\\0&D-CA^{-1}B\end{bmatrix}}{\begin{bmatrix}I_{p}&A^{-1}B\\ 0&I_{q}\end{bmacierz}},\\[4pt]M^{-1}&={\begin{bmacierz}A^{-1}+A^{-1}B(M/A)^ {-1}CA^{-1}&-A^{-1}B(M/A)^{-1}\\-(M/A)^{-1}CA^{-1}&( M/A)^{-1}\end{bmatrix}}\end{aligned}}}

ilekroć istnieje ta odwrotność.

(Wzór Schura) Gdy odpowiednio A , odpowiednio D , jest odwracalne, wyznacznik M jest również wyraźnie określony przez

{\ Displaystyle \ det (M) = \ det (A) \ det \ lewo (D-CA ^ {-1} B \ prawo)}

, odpowiednio

{\ Displaystyle \ det (M) = \ det (D) \ det \ lewo (A-BD ^ {- 1} C \

,

co uogólnia wzór na wyznacznik dla macierzy 2 × 2.

M (Formuła addytywności rang Guttmana) Jeśli D jest odwracalny, to ranga M jest określona przez

\ Displaystyle \ operatorname {ranga} (M)=\nazwaoperatora {stopień} (D)+\nazwaoperatora {stopień} \left(A-BD^{-1}C\right)}

( Wzór addytywności bezwładności Haynswortha ) Jeśli A jest odwracalny, to bezwładność macierzy blokowej M jest równa bezwładności A plus bezwładność M / A .
(Tożsamość ilorazowa) ${\ Displaystyle A/B = ((A/C) / (B/C))}$ .
Dopełnienie Schura macierzy Laplace'a jest również macierzą Laplaca.

Zastosowanie do rozwiązywania równań liniowych

Dopełnienie Schura powstaje naturalnie przy rozwiązywaniu układu równań liniowych, takich jak

${\ Displaystyle {\ rozpocząć {bmatrix} A & B \\ C & D \ koniec {bmatrix}} {\ rozpocząć {bmatrix} x \\ y \ koniec {bmatrix}} ={\begin{bmatrix}u\\v\end{bmatrix}}}$ .

$,$ że podmacierz jest $odwracalna$ , możemy wyeliminować równań w następujący sposób

${\ Displaystyle x = A ^ {- 1} (u-By)}$ .

Podstawienie tego wyrażenia do drugiego równania daje

{\ Displaystyle \ lewo (D-CA ^ {-1} B \ prawej) y = v-CA ^ {- 1} u

.

Nazywamy to równaniem $zredukowanym$ uzyskanym przez wyeliminowanie pierwotnego równania. Macierz występująca w równaniu zredukowanym nazywana jest dopełnieniem Schura pierwszego bloku ${\ displaystyle A}$ w: ${\ displaystyle M$ }

{\ Displaystyle S \ {\ overset {\ underset {\ operatorname {def}} {}} {=}} \ D-CA ^ {- 1} B

.

Rozwiązując zredukowane równanie, otrzymujemy

{\ Displaystyle y = S ^ {- 1} \ lewo (v-CA ^ {- 1} u \ prawej)}

.

Podstawienie tego do pierwszego równania daje wyniki

{\ Displaystyle x = \ lewo (A ^ {- 1} + A ^ {- 1} BS^{-1}CA^{-1}\right)uA^{-1}BS^{-1}v}

.

Powyższe dwa równania możemy wyrazić jako:

{\ Displaystyle {\ rozpocząć {bmatrix} x \\ y \ koniec {bmatrix}} = {\ rozpocząć {bmatrix} A ^ {-1} + A ^ {-1} BS ^ {-1} CA ^ {-1 }&-A^{-1}BS^{-1}\\-S^{-1}CA^{-1}&S^{-1}\end{bmatrix}}{\begin{bmatrix}u\ \v\end{bmacierz}}}

.

Dlatego formuła odwrotności macierzy blokowej to:

\ Displaystyle {\ rozpocząć {bmatrix} A&B \\ C&D \ koniec {bmatrix}} ^ {- 1} = {\ początek{bmacierz}A^{-1}+A^{-1}BS^{-1}CA^{-1}&-A^{-1}BS^{-1}\\-S^{- 1}CA^{-1}&S^{-1}\end{bmatrix}}={\begin{bmatrix}I_{p}&-A^{-1}B\\&I_{q}\end{bmatrix }}{\begin{bmatrix}A^{-1}&\\&S^{-1}\end{bmatrix}}{\begin{bmatrix}I_{p}&\\-CA^{-1}&I_ {q}\end{bmacierz}}}

.

$, że dopełnienie$ odwrotnością wpisu blokowego odwrotności ${\ displaystyle M}$

W praktyce trzeba $,$ dobrze uwarunkowanym aby ten algorytm był liczbowo dokładny.

W elektrotechnice jest to często określane jako eliminacja węzłów lub redukcja Krona .

Zastosowania w teorii prawdopodobieństwa i statystyce

Załóżmy, że losowe wektory kolumnowe X , Y żyją odpowiednio w R ⁿ i R ^m , a wektor ( X , Y ) w R ^{n + m} ma wielowymiarowy rozkład normalny , którego kowariancja jest symetryczną dodatnio określoną macierzą

{\ Displaystyle \ Sigma = \ lewo [{\ rozpocząć {macierz} A & B \\ B ^ {\ mathsf {T}} i C \ koniec {macierzy}} \ prawej],}

gdzie ${\ textstyle A \ in \ mathbb {R} ^ {n \ razy n}}$ jest macierzą kowariancji X , ${\ textstyle C \ in \ mathbb {R} ^{m\times m}}$ to macierz kowariancji Y i ${\textstyle B\in \mathbb {R} ^{n\times m}}$ to macierz kowariancji między X a Y .

Wtedy warunkowa kowariancja X przy danym Y jest dopełnieniem Schura C w $textstyle \ Sigma}$ \ :

{\ Displaystyle {\ rozpocząć {wyrównane} \ operatorname {Cov} (X \ mid Y) & = A-BC ^ {-1} B ^ {\ mathsf {T}} \\\ operatorname {E} (X \ mid Y)&=\nazwa_operatora {E} (X)+BC^{-1}(Y-\nazwa_operatora {E} (Y))\end{wyrównane}}}

Jeśli przyjmiemy, że powyższa macierz $to$ jest kowariancją losowego wektora, ale kowariancją próbki , może ona mieć rozkład Wisharta . W takim przypadku uzupełnienie Schura $rozkład$ w ma również Wisharta. ^{[ potrzebne źródło ]}

Warunki pozytywnej określoności i półokreśloności

Niech X będzie symetryczną macierzą liczb rzeczywistych danych przez

{\ Displaystyle X = \ lewo [{\ rozpocząć {macierz} A & B \\ B ^ {\ mathsf {T}} i C \ koniec {macierz}} \ prawo].}

Następnie

Jeśli A jest odwracalne, to X jest dodatnio określone wtedy i tylko wtedy, gdy A i jego dopełnienie X / A są dodatnio określone:
${\ Displaystyle X\succ 0\Leftrightarrow A\succ 0,X/A=CB^{\mathsf {T}}A^{-1}B\succ 0.}$
Jeśli C jest odwracalne, to X jest dodatnio określone wtedy i tylko wtedy, gdy C i jego dopełnienie X / C są dodatnio określone:
${\ displaystyle X\succ 0\Leftrightarrow C\succ 0,X/C=A-BC^{-1}B^{\mathsf {T}}\succ 0.}$
Jeśli A jest dodatnio określone, to X jest dodatnio określone wtedy i tylko wtedy, gdy dopełnienie X/A jest dodatnio określone:
${\text{If }}A\succ 0,{\text{ then }}X\succeq 0\Leftrightarrow X/A=C-B^{\mathsf {T}}A^{-1}B\succeq 0.$
Jeśli C jest dodatnio określone, to X jest dodatnio określone wtedy i tylko wtedy, gdy dopełnienie X/C jest dodatnio określone:
${\text{If }}C\succ 0,{\text{ then }}X\succeq 0\Leftrightarrow X/C=A-BC^{-1}B^{\mathsf {T}}\succeq 0.$

Pierwsze i trzecie stwierdzenie można wyprowadzić, biorąc pod uwagę minimalizator ilości

{\ Displaystyle u ^ {\ mathsf {T}} Au + 2v ^ {\ mathsf {T}} B ^ {\ mathsf {T}} u +v^{\mathsf {T}}Cv,\,}

jako funkcja v (dla ustalonego u ).

Ponadto, ponieważ

{\ Displaystyle \ lewo [{\ rozpocząć {macierz} A & B \\ B ^ {\ mathsf {T}} i C \ koniec {macierzy}} \

i podobnie w przypadku dodatnich półokreślonych macierzy, drugie (odpowiednio czwarte) stwierdzenie jest natychmiastowe po pierwszym (odpowiednio trzecim) stwierdzeniu.

Istnieje również wystarczający i konieczny warunek pozytywnej półokreśloności X w kategoriach uogólnionego dopełnienia Schura. Dokładnie,

$\ Displaystyle X \ succeq 0 \ strzałka w lewo A \ succeq 0, CB ^ {\ mathsf {T}} A ^ { g}B\succeq 0,\left(I-AA^{g}\right)B=0\,}$ i
$^ { \mathsf {T}}\succeq 0,\left(I-CC^{g}\right)B^{\mathsf {T}}=0,}$

gdzie oznacza uogólnioną odwrotność ZA sol ${\ displaystyle A}$ $}$ .

Zobacz też