Дополнение Шура - Schur complement

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

Предположим, что 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]}$

так что M - матрица размера ( p + q ) × ( p + q ).

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

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

Если A обратимо, дополнение Шура блока A матрицы M - это матрица q × q, определенная формулой

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

В том случае, или D является сингулярным , заменив обобщенный обратную для обратных на M / A и M / D , получает обобщенные дополнения Шуру .

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

Фон

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

${\ displaystyle {\ begin {align} & 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 {выравнивается}}}$

где I _p обозначает единичную матрицу размера p × p . В результате дополнение Шура появляется в верхнем левом блоке p × p . ${\ Displaystyle M / D = A-BD ^ {- 1} C}$

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

${\ displaystyle {\ begin {align} & {\ 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 {align}}}$

приводит к разложению LDU из М , в котором говорится

${\ displaystyle {\ begin {align} 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 {align}}}$

Таким образом, обратное к M может быть выражено с использованием D ⁻¹ и обратного дополнения Шура, если оно существует, как

${\ displaystyle {\ begin {align} 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 {выравнивается} }}$

Выше отношения происходят от операций ликвидации , которые включают D ^-1 и M / D . Эквивалентное вывод можно сделать с ролями A и D взаимозаменяемыми. Приравнивая выражения для M ^−1, полученные этими двумя разными способами, можно установить лемму об обращении матриц , которая связывает два дополнения Шура к M : M / D и M / A (см. «Вывод из разложения LDU» в матрице Вудбери идентичность § Альтернативные доказательства ).

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

Приложение для решения линейных уравнений

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

${\ 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 х = А ^ {- 1} (н-по)}$.

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

${\ 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 у = S ^ {- 1} \ влево (v-CA ^ {- 1} и \ вправо)}$.

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

${\ displaystyle x = \ left (A ^ {- 1} + A ^ {- 1} BS ^ {- 1} CA ^ {- 1} \ right) uA ^ {- 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}}}$.

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

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

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

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

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

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

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

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

${\ displaystyle {\ begin {align} \ operatorname {Cov} (X \ mid Y) & = A-BC ^ {- 1} B ^ {\ mathsf {T}} \\\ operatorname {E} (X \ mid Y) & = \ operatorname {E} (X) + BC ^ {- 1} (Y- \ operatorname {E} (Y)) \ end {выровнено}}}$

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

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

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

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

потом

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

  ${\ displaystyle X \ succ 0 \ Leftrightarrow A \ succ 0, X / A = CB ^ {\ mathsf {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 ^ {\ mathsf {T}} \ succ 0.}$

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

  ${\ displaystyle {\ text {If}} A \ succ 0, {\ text {then}} X \ successq 0 \ Leftrightarrow X / A = CB ^ {\ mathsf {T}} A ^ {- 1} B \ successq 0.}$

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

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

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

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

как функция от v (при фиксированном u ).

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

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

и аналогично для положительных полуопределенных матриц второе (соответственно четвертое) утверждение непосредственно из первого (соответственно третьего) утверждения.

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

• ${\ Displaystyle X \ successq 0 \ Leftrightarrow A \ successq 0, CB ^ {\ mathsf {T}} A ^ {g} B \ successq 0, \ left (I-AA ^ {g} \ right) B = 0 \ ,}$ а также
• ${\ displaystyle X \ successq 0 \ Leftrightarrow C \ successq 0, A-BC ^ {g} B ^ {\ mathsf {T}} \ successq 0, \ left (I-CC ^ {g} \ right) B ^ { \ mathsf {T}} = 0,}$

где обозначает обобщенное обратное к . ${\ displaystyle A ^ {g}}$${\ displaystyle A}$

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

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

использованная литература