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

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

Предположим, что p , q — неотрицательные целые числа такие, что p + q > 0 , и предположим, что A , B , C , D — соответственно p × p , p × q , q × p и q × q матрицы комплексных чисел. Позволять $M=\left[{\begin{matrix}A&B\\C&D\end{matrix}}\right]$ так что M — матрица ( p + q ) × ( p + q ).

Если D обратим, то дополнение Шура к блоку D матрицы M представляет собой матрицу p × p , определяемую формулой $M/D:=A-BD^{-1}C.$ Если A обратим, дополнение Шура к блоку A матрицы M представляет собой матрицу q × q , определяемую формулой $M/A:=D-CA^{-1}B.$ В случае, когда , замена обратных для A или D сингулярны M обобщенным / A и M/D обратным дает обобщенное дополнение Шура .

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

Фон

Дополнение Шура возникает при выполнении блочного исключения Гаусса на матрице M . Чтобы исключить элементы ниже диагонали блока, матрицу M умножают на блочную нижнюю треугольную матрицу справа следующим образом: ${\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 обозначает p × p единичную матрицу размера . В результате дополнение Шура $M/D=A-BD^{-1}C$ появляется в верхнем левом блоке p × p .

Продолжая процесс исключения за этой точкой (т. е. выполняя блок исключения Гаусса–Жордана ), ${\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-разложению M читается , которое ${\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}}$ Таким образом, обратное к M может быть выражено с использованием D ⁻¹ и обратное дополнение Шура, если оно существует, как ${\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 ⁻¹ и М/Д . роли A и D. Эквивалентный вывод можно сделать , поменяв местами Приравнивая выражения для M ⁻¹ Полученные этими двумя разными способами, можно установить лемму об обращении матрицы , которая связывает два дополнения Шура к M : M/D и M/A (см. «Вывод из разложения LDU» в матричном тождестве Вудбери § Альтернативные доказательства ).

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

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

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

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

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

{\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 определяется выражением

\det(M)=\det(A)\det \left(D-CA^{-1}B\right)

, соответственно

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

{\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}}.

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

{\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}}.

В частности, мы видим, что дополнение Шура является обратным дополнению Шура. $2,2$ заблокировать ввод обратного значения $M$ .

На практике нужно $A$ быть хорошо обусловленным , чтобы этот алгоритм был численно точным.

Этот метод полезен в электротехнике для уменьшения размерности уравнений сети. Это особенно полезно, когда элементы выходного вектора равны нулю. Например, когда $u$ или $v$ равно нулю, мы можем исключить соответствующие строки матрицы коэффициентов без каких-либо изменений в остальной части выходного вектора. Если $v$ равно нулю, то приведенное выше уравнение для $x$ сводится к $x=\left(A^{-1}+A^{-1}BS^{-1}CA^{-1}\right)u$ , тем самым уменьшая размерность матрицы коэффициентов, оставляя $u$ неизмененный. Это используется с успехом в электротехнике, где это называется устранением узла или уменьшением Крона .

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

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

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

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

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

{\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}}

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

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

Пусть X — симметричная матрица действительных чисел, заданная формулой $X=\left[{\begin{matrix}A&B\\B^{\mathrm {T} }&C\end{matrix}}\right].$ Затем

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

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

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

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

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

{\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 положительно полуопределено:

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

Первое и третье утверждения можно вывести ^[7] рассматривая минимизатор величины $u^{\mathrm {T} }Au+2v^{\mathrm {T} }B^{\mathrm {T} }u+v^{\mathrm {T} }Cv,\,$ как функция v (при фиксированном u ).

Кроме того, поскольку $\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 в терминах обобщенного дополнения Шура. ^[2] Именно так,

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

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

См. также

Ссылки

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

[1] Шур, Дж. (1917). «О степенных рядах, ограниченных внутри единичного круга» . Ж. Чистая и прикладная математика . 147 : 205–232. дои : 10.1515/crll.1917.147.205 .

[Zhang_2005-2] Перейти обратно: Перейти обратно: ^а ^б ^с ^д Чжан, Фучжэнь (2005). Чжан, Фучжэнь (ред.). Дополнение Шура и его приложения . Численные методы и алгоритмы. Том. 4. Спрингер. дои : 10.1007/b105056 . ISBN 0-387-24271-6 .

[3] Хейнсворт, Э.В., «О дополнении Шура», Базельские математические заметки , # BNB 20, 17 страниц, июнь 1968 г.

[4] Фешбах, Герман (1958). «Единая теория ядерных реакций». Анналы физики . 5 (4): 357–390. дои : 10.1016/0003-4916(58)90007-1 .

[5] Крэбтри, Дуглас Э.; Хейнсворт, Эмили В. (1969). «Тождество для дополнения Шура матрицы» . Труды Американского математического общества . 22 (2): 364–366. дои : 10.1090/S0002-9939-1969-0255573-1 . ISSN 0002-9939 . S2CID 122868483 .

[6] Девриендт, Карел (2022). «Эффективное сопротивление — это больше, чем расстояние: лапласианцы, симплики и дополнение Шура» . Линейная алгебра и ее приложения . 639 : 24–49. arXiv : 2010.04521 . дои : 10.1016/j.laa.2022.01.002 . S2CID 222272289 .

[Boyd_2004-7] Перейти обратно: Перейти обратно: ^а ^б Бойд С. и Ванденбергхе Л. (2004), «Выпуклая оптимизация», Cambridge University Press (Приложение A.5.5)

[von_Mises_1964-8] фон Мизес, Рихард (1964). «Глава VIII.9.3». Математическая теория вероятностей и статистика . Академическая пресса. ISBN 978-1483255385 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]