дополнение Шура

Инструмент линейной алгебры и матричного анализа

В линейной алгебре и теории матриц дополнение Шура блочной матрицы определяется следующим образом.

Предположим, что p , q — неотрицательные целые числа, и предположим, что A , B , C , D — это соответственно p × p , p × q , q × p и q × q матрицы комплексных чисел. Позволять

$${\displaystyle M=\left[{\begin{matrix}A&B\\C&D\end{matrix}}\right]}$$

Mpqpq

Если D обратим, то дополнение Шура к блоку D матрицы M представляет собой матрицу размера p × p , определяемую формулой

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

Aдополнение ШураAMqq

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

A или D сингулярны ,обратныхAM/D обобщеннымобобщенное дополнение Шура

Дополнение Шура названо в честь Иссая Шура , который использовал его для доказательства леммы Шура , хотя оно использовалось и ранее. ^[1] Эмили Вирджиния Хейнсворт была первой, кто назвал это дополнением Шура . ^[2] Дополнение Шура является ключевым инструментом в области численного анализа, статистики и матричного анализа.

Фон

Дополнение Шура возникает при выполнении блочного исключения Гаусса на матрице M . Чтобы исключить элементы ниже диагонали блока, матрицу M умножают на блочную нижнюю треугольную матрицу справа следующим образом:

$${\displaystyle {\begin{aligned}&M={\begin{bmatrix}A&B\\C&D\end{bmatrix}}\quad \to \quad {\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}},\end{aligned}}}$$

I _pединичную матрицу размера pppp ${\displaystyle M/D=A-BD^{-1}C}$

Продолжая процесс исключения за этой точкой (т. е. выполняя блок исключения Гаусса–Жордана ),

$${\displaystyle {\begin{aligned}&{\begin{bmatrix}A-BD^{-1}C&B\\0&D\end{bmatrix}}\quad \to \quad {\begin{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{bmatrix}},\end{aligned}}}$$

LDU-разложению,

$${\displaystyle {\begin{aligned}M&={\begin{bmatrix}A&B\\C&D\end{bmatrix}}={\begin{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}}.\end{aligned}}}$$

MD ^-1

$${\displaystyle {\begin{aligned}M^{-1}={\begin{bmatrix}A&B\\C&D\end{bmatrix}}^{-1}={}&\left({\begin{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\left(A-BD^{-1}C\right)^{-1}&D^{-1}+D^{-1}C\left(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{bmatrix}}.\end{aligned}}}$$

D ⁻¹M/DAD.M ^-1об обращении матрицыMM/DM/A«Вывод из разложения LDU»матрице Вудбери) . тождество § Альтернативные доказательства

Характеристики

• Если p и q оба равны 1 (т. е. A , B , C и D являются скалярами), мы получаем знакомую формулу для обратной матрицы 2х2:

${\displaystyle M^{-1}={\frac {1}{AD-BC}}\left[{\begin{matrix}D&-B\\-C&A\end{matrix}}\right]}$

при условии, что AD  −  BC не равно нулю.

• В общем случае, если A обратимо, то

${\displaystyle {\begin{aligned}M&={\begin{bmatrix}A&B\\C&D\end{bmatrix}}={\begin{bmatrix}I_{p}&0\\CA^{-1}&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{bmatrix}},\\[4pt]M^{-1}&={\begin{bmatrix}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}}}$

всякий раз, когда это обратное существует.

• (Формула Шура) Когда A , соответственно D , обратимы, также ясно видно, что определитель M определяется выражением

${\displaystyle \det(M)=\det(A)\det \left(D-CA^{-1}B\right)}$, соответственно

${\displaystyle \det(M)=\det(D)\det \left(A-BD^{-1}C\right)}$,

которая обобщает определительную формулу для матриц 2 × 2.

• (Формула аддитивности ранга Гуттмана) Если D обратим, то ранг M определяется выражением

${\displaystyle \operatorname {rank} (M)=\operatorname {rank} (D)+\operatorname {rank} \left(A-BD^{-1}C\right)}$

• ( Формула аддитивности инерции Хейнсворта ) Если A обратима, то инерция блочной матрицы M равна инерции A плюс инерция M / A .
• (Факторное тождество) . ^[3] ${\displaystyle A/B=((A/C)/(B/C))}$
• Дополнение Шура к матрице Лапласа также является матрицей Лапласа. ^[4]

Приложение к решению линейных уравнений

Дополнение Шура естественным образом возникает при решении системы линейных уравнений типа ^[5]

${\displaystyle {\begin{bmatrix}A&B\\C&D\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}={\begin{bmatrix}u\\v\end{bmatrix}}}$.

Предполагая, что подматрица обратима, мы можем исключить ее из уравнений следующим образом. ${\displaystyle A}$ ${\displaystyle x}$

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

Подставив это выражение во второе уравнение, получим

${\displaystyle \left(D-CA^{-1}B\right)y=v-CA^{-1}u}$.

Мы называем это сокращенным уравнением , полученным путем исключения из исходного уравнения. Матрица, появляющаяся в сокращенном уравнении, называется дополнением Шура первого блока в : ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle M}$

${\displaystyle S\ {\overset {\underset {\mathrm {def} }{}}{=}}\ D-CA^{-1}B}$.

Решая приведенное уравнение, получаем

${\displaystyle y=S^{-1}\left(v-CA^{-1}u\right)}$.

Подставив это в первое уравнение, получим

${\displaystyle x=\left(A^{-1}+A^{-1}BS^{-1}CA^{-1}\right)u-A^{-1}BS^{-1}v}$.

Мы можем выразить два приведенных выше уравнения как:

${\displaystyle {\begin{bmatrix}x\\y\end{bmatrix}}={\begin{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{bmatrix}}}$.

Следовательно, формулировка обратной блочной матрицы такова:

${\displaystyle {\begin{bmatrix}A&B\\C&D\end{bmatrix}}^{-1}={\begin{bmatrix}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{bmatrix}}}$.

В частности, мы видим, что дополнение Шура является инверсией блочной записи обратного . ${\displaystyle 2,2}$ ${\displaystyle M}$

На практике для того, чтобы этот алгоритм был численно точным, необходимо быть хорошо подготовленным . ${\displaystyle A}$

В электротехнике это часто называют устранением узла или уменьшением Крона .

Приложения к теории вероятностей и статистике

Предположим, что случайные векторы-столбцы ^X , Y живут в Rn и Rm соответственно, а вектор ( X , Y ⁾ в Rn ^{+ m} имеет многомерное нормальное распределение , ковариация которого представляет собой симметричную положительно определенную матрицу ^.

${\displaystyle \Sigma =\left[{\begin{matrix}A&B\\B^{\mathrm {T} }&C\end{matrix}}\right],}$

где — ковариационная матрица X , — ковариационная матрица Y и — ковариационная матрица между X и Y. ${\textstyle A\in \mathbb {R} ^{n\times n}}$ ${\textstyle C\in \mathbb {R} ^{m\times m}}$ ${\textstyle B\in \mathbb {R} ^{n\times m}}$

Тогда условная ковариация X при условии Y является дополнением Шура к C в : [ ^6] ${\textstyle \Sigma }$

${\displaystyle {\begin{aligned}\operatorname {Cov} (X\mid Y)&=A-BC^{-1}B^{\mathrm {T} }\\\operatorname {E} (X\mid Y)&=\operatorname {E} (X)+BC^{-1}(Y-\operatorname {E} (Y))\end{aligned}}}$

Если мы возьмем приведенную выше матрицу не как ковариацию случайного вектора, а как выборочную ковариацию, то она может иметь распределение Уишарта . В этом случае дополнение Шура к C in также имеет распределение Уишарта. ^{[ нужна цитата ]} ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$

Условия положительной определенности и полуопределенности.

Пусть X — симметричная матрица действительных чисел, заданная формулой

$${\displaystyle X=\left[{\begin{matrix}A&B\\B^{\mathrm {T} }&C\end{matrix}}\right].}$$

• Если A обратим, то X положительно определен тогда и только тогда, когда A и его дополнение X/A положительно определены: ^{[1] : 34}

$${\displaystyle X\succ 0\Leftrightarrow A\succ 0,X/A=C-B^{\mathrm {T} }A^{-1}B\succ 0.}$$

• Если C обратим, то X положительно определен тогда и только тогда, когда C и его дополнение X/C оба положительно определены:

$${\displaystyle X\succ 0\Leftrightarrow C\succ 0,X/C=A-BC^{-1}B^{\mathrm {T} }\succ 0.}$$

• Если A положительно определен, то X положительно полуопределенен тогда и только тогда, когда дополнение X/A положительно полуопределено: ^{[1] : 34}

$${\displaystyle {\text{If }}A\succ 0,{\text{ then }}X\succeq 0\Leftrightarrow X/A=C-B^{\mathrm {T} }A^{-1}B\succeq 0.}$$

• Если C положительно определен, то X положительно полуопределенен тогда и только тогда, когда дополнение X/C положительно полуопределено:

$${\displaystyle {\text{If }}C\succ 0,{\text{ then }}X\succeq 0\Leftrightarrow X/C=A-BC^{-1}B^{\mathrm {T} }\succeq 0.}$$

Первое и третье утверждения можно получить ^[5] , рассматривая минимизатор величины

$${\displaystyle u^{\mathrm {T} }Au+2v^{\mathrm {T} }B^{\mathrm {T} }u+v^{\mathrm {T} }Cv,\,}$$

vu

Кроме того, поскольку

$${\displaystyle \left[{\begin{matrix}A&B\\B^{\mathrm {T} }&C\end{matrix}}\right]\succ 0\Longleftrightarrow \left[{\begin{matrix}C&B^{\mathrm {T} }\\B&A\end{matrix}}\right]\succ 0}$$

Существует также достаточное и необходимое условие положительной полуопределенности X в терминах обобщенного дополнения Шура. ^[1] Именно,

• ${\displaystyle X\succeq 0\Leftrightarrow A\succeq 0,C-B^{\mathrm {T} }A^{g}B\succeq 0,\left(I-AA^{g}\right)B=0\,}$и
• ${\displaystyle X\succeq 0\Leftrightarrow C\succeq 0,A-BC^{g}B^{\mathrm {T} }\succeq 0,\left(I-CC^{g}\right)B^{\mathrm {T} }=0,}$

где обозначает обобщенную обратную величину . ${\displaystyle A^{g}}$ ${\displaystyle A}$

Смотрите также

• Матричное тождество Вудбери
• Квазиньютоновский метод
• Формула аддитивности инерции Хейнсворта
• Гауссов процесс
• Всего наименьших квадратов

Рекомендации

1. Чжан, Фучжэнь (2005). Чжан, Фучжэнь (ред.). Дополнение Шура и его приложения . Численные методы и алгоритмы. Том. 4. Спрингер. дои : 10.1007/b105056. ISBN 0-387-24271-6.
2. Хейнсворт, Э.В., «О дополнении Шура», Базельские математические заметки , # BNB 20, 17 страниц, июнь 1968 г.
3. Крэбтри, Дуглас Э.; Хейнсворт, Эмили В. (1969). «Тождество для дополнения Шура матрицы». Труды Американского математического общества . 22 (2): 364–366. дои : 10.1090/S0002-9939-1969-0255573-1 . ISSN  0002-9939. S2CID  122868483.
4. Девриендт, Карел (2022). «Эффективное сопротивление - это больше, чем расстояние: лапласианцы, симплики и дополнение Шура». Линейная алгебра и ее приложения . 639 : 24–49. arXiv : 2010.04521 . дои : 10.1016/j.laa.2022.01.002. S2CID  222272289.
5. Бойд С. и Ванденбергхе Л. (2004), «Выпуклая оптимизация», Cambridge University Press (Приложение A.5.5)
6. фон Мизес, Ричард (1964). «Глава VIII.9.3». Математическая теория вероятностей и статистика . Академическая пресса. ISBN 978-1483255385.