Álgebra lineal: ¿Cuál es la motivación detrás de la definición del complemento Schur de una matriz?

Answer 1

Primero, daré un resumen rápido de la importancia. Luego trataré de explicar en términos simples cómo el complemento Schur surge naturalmente de los problemas de física y cómo puede mejorar significativamente el tiempo que lleva resolverlos.

Visión de conjunto
En PDE numéricos, el complemento Schur puede ahorrar mucho tiempo, ya que en muchos casos permite eliminar muchas variables de la solución y resolver las necesarias.

Esta técnica en la comunidad de elementos finitos se llamaba originalmente “condensación estática”, porque se consideraba principalmente como un truco para acelerar el sistema resultante de ecuaciones lineales.

Sin embargo, un artículo reciente de Cockburn et al:
Hibridación unificada de los métodos Galerkin discontinuo, mixto y Galerkin continuo para problemas elípticos de segundo orden

han explicado que, de hecho, físicamente las variables que ha eliminado de la solución son en realidad las que contienen la ” menor” información. Proporcionan una técnica general para producir un sistema que puede complementarse con Schur de tal manera que solo resuelva las variables “importantes” . Este enfoque más poderoso se conoció como “Hibridación”. Es una técnica extremadamente importante ahora, ya que ha hecho que los problemas de otra manera intratables (por ejemplo, propagación de ondas de muy alta frecuencia en dominios grandes) sean completamente posibles. Cuando digo que, por lo demás, eran intratables, quiero decir que, literalmente, las computadoras modernas simplemente no podían manejarlas.

¿De dónde viene?

Cuando resuelve una PDE con motivación física como la ecuación de onda o la ecuación de Helmholtz, debe recurrir a una aproximación con frecuencia. La forma en que esto se hace en los métodos de tipo de elemento finito es que el dominio se “discretiza” en formas simples (por ejemplo, triángulo), y luego la física se resuelve en cada forma; determinar la física en formas simples resulta mucho más fácil que en formas complicadas.

ver, por ejemplo, las figuras de wikipedia de una geometría discreta
Archivo: Ejemplo de malla 2D.png

y la geometría no discreta
Archivo: ejemplo FEM de solución 2D.png

Entonces surge la pregunta de que, dado que queremos saber qué está sucediendo físicamente en todo el dominio, ¿cómo comunicamos la información de la física que ocurre en un triángulo a la física que sucede en otro? (ya que pueden depender el uno del otro).

Sin entrar en muchos detalles, podemos llamar a esta comunicación de información física de un triángulo a otro ” apretón de manos”. Imagine que está trabajando en paralelo en algunos libros de cuentas con un amigo. Ustedes dos realizan sus cálculos, luego alcanzan una etapa donde los cálculos mutuos son necesarios para que cada uno continúe. Pasas un día haciendo tus cálculos, luego te encuentras para almorzar e intercambias algunos resultados para que puedas continuar nuevamente al día siguiente. Este es un apretón de manos.

Lo que hace la hibridación es ignorar por completo los cálculos que usted y su amigo hicieron de forma independiente, y pasar directamente al apretón de manos. A partir de esta información, puede reconstruir los cálculos independientes, aunque a veces no es necesario, y ahí es donde entra el poder. El tiempo que lleva resolver el apretón de manos a menudo es significativamente menor que el tiempo combinado de los cálculos independientes + apretón de manos. Sin embargo, el hecho más sorprendente sobre esto es que en los problemas de física: ¡ las variables de apretón de manos a menudo son aproximaciones significativamente más precisas que las variables de no apretón de manos! ¡Así que no solo trabajaste menos, sino que trabajaste menos para obtener la mayor cantidad de información! Ese es el poder del Complemento Schur cuando se manejan ciertos tipos de física.

Answer 2

Wow, ¿cómo me perdí esta pregunta?

La pregunta es: ¿cuál es la motivación detrás de la definición del complemento Schur? Primero voy a responder la pregunta: ¿por qué se llama el complemento Schur? ¿Por qué lo llamamos un complemento ? Tan pronto como respondo a esta pregunta, la motivación detrás de la definición del complemento Schur se vuelve más clara.

Entonces, lo primero es lo primero.

Comenzamos con una matriz no singular [matemática] M [/ matemática] dividida en una matriz de bloque [matemática] 2 \ veces 2 [/ matemática]

[matemáticas] M = \ begin {pmatrix} A y B \\ C & D \ end {pmatrix}. [/ math]

Claramente, podemos particionar [math] M ^ {- 1} [/ math] en una matriz de bloques [math] 2 \ times 2 [/ math] también, digamos en

[matemáticas] M ^ {- 1} = \ begin {pmatrix} W & X \\ Y & Z \ end {pmatrix}. [/ math]

Aquí es donde entra la palabra complemento: Las matrices [matemáticas] A [/ matemáticas] y [matemáticas] Z [/ matemáticas] se llaman bloques complementarios . En la misma línea, las matrices [matemáticas] D [/ matemáticas] y [matemáticas] W [/ matemáticas] también son bloques complementarios . Así que ahora sabes de dónde viene la palabra ‘ complemento ‘.

Entonces, ¿por qué usamos la palabra ‘ complemento ‘ para los complementos de Schur ?

Aquí está la razón.

Hay un teorema poco conocido (aunque extremadamente poderoso) que simplemente dice: los bloques complementarios tienen la misma nulidad . Ahora resulta que lo siguiente es cierto:

Si [matemática] A [/ matemática] es invertible, entonces (según el teorema anterior, [matemática] Z [/ matemática] es invertible y) [matemática] Z ^ {- 1} = D – CA ^ {- 1} B [/matemáticas].

Si [matemática] D [/ matemática] es invertible, entonces (según el teorema anterior, [matemática] W [/ matemática] es invertible y) [matemática] W ^ {- 1} = A – BD ^ {- 1} C [/matemáticas].

En otras palabras, el bloque complementario de [matemáticas] A [/ matemáticas] es el inverso de la matriz [matemáticas] D – CA ^ {- 1} B [/ matemáticas]. Del mismo modo, el bloque complementario de [matemáticas] D [/ matemáticas] es el inverso de la matriz [matemáticas] A – BD ^ {- 1} C [/ matemáticas].

Entonces, es por eso que llamamos a la matriz [matemáticas] D – CA ^ {- 1} B [/ matemáticas] el complemento Schur de [matemáticas] M [/ matemáticas] con respecto a [matemáticas] A [/ matemáticas], y llame a la matriz [matemáticas] A – BD ^ {- 1} C [/ matemáticas] el complemento de Schur de [matemáticas] M [/ matemáticas] con respecto a [matemáticas] D [/ matemáticas]. Esencialmente, ahora podemos decir que:

Si [math] A [/ math] es invertible, entonces su bloque complementario [math] Z [/ math] es el inverso del complemento Schur de [math] M [/ math] con respecto a [math] A [/ math ]

Si [math] D [/ math] es invertible, entonces su bloque complementario [math] W [/ math] es el inverso del complemento Schur de [math] M [/ math] con respecto a [math] D [/ math ]

Un uso obvio de los complementos de Schur, por lo tanto, es obtener inversos de matrices particionadas. Pero hay más. También es el caso de que, si [matemática] A [/ matemática] es invertible, entonces el determinante de [matemática] M [/ matemática] puede encontrarse mediante la siguiente ecuación:

[matemáticas] | M | = | A | \, | D-CA ^ {- 1} B |. [/ Math]

Del mismo modo, si [math] D [/ math] es invertible, entonces

[matemáticas] | M | = | D | \, | A-BD ^ {- 1} C |. [/ Matemáticas]

Podemos repetir esto de la siguiente manera: el determinante de una matriz particionada [matemática] M [/ matemática] es igual al producto del determinante de [matemática] A [/ matemática] (o [matemática] D [/ matemática]) y el determinante del complemento de Schur de [matemáticas] M [/ matemáticas] con respecto a [matemáticas] A [/ matemáticas] (o [matemáticas] D [/ matemáticas]). Esta es la razón por la cual el complemento de Schur generalmente se denota por [matemáticas] (M / A) [/ matemáticas] o [matemáticas] (M / D) [/ matemáticas] – la notación se vuelve bastante atractiva en el contexto de los determinantes:

[matemáticas] | M | = | A | \, | (M / A) |. [/ Matemáticas]

[matemáticas] | M | = | D | \, | (M / D) |. [/ Matemáticas]

Por lo tanto, los complementos de Schur también son extremadamente útiles para encontrar el determinante de una matriz en términos de uno de sus submatrices principales no singulares.

¿Es esto importante en las aplicaciones? Permítanme ilustrar solo una aplicación. Si [math] A [/ math] es la matriz de adyacencia de un gráfico [math] G [/ math], entonces [math] | xI – A | [/ math] es su polinomio característico. Cualquier submatriz principal de [math] A [/ math] es la matriz de adyacencia de una subgrafía inducida particular de [math] G [/ math]. A partir de la fórmula anterior, podemos encontrar una expresión para el polinomio característico de este subgrafo inducido (y, por lo tanto, su espectro) utilizando la del gráfico original y un determinante del complemento Schur particular.

Answer 3

El cumplido de Schur de una matriz cuadrada [math] \ mathbf {A} [/ math] surge como la matriz de coeficientes de un nuevo conjunto de ecuaciones cuando separamos [math] \ mathbf {Ax = b} [/ math] en bloque formar y sustituir la solución de un conjunto en los coeficientes del otro. Para ilustrar esto, escribamos nuestro sistema como:

[matemáticas] \ begin {eqnarray *} \ begin {bmatrix} \ mathbf {A} _ {11} y \ mathbf {A} _ {12} \\ \ mathbf {A} _ {21} y \ mathbf {A} _ {22} \ end {bmatrix} \ begin {bmatrix} \ mathbf {x} _ {1} \\ \ mathbf {x} _ {2} \ end {bmatrix} & = & \ begin {bmatrix} \ mathbf { b} _ {1} \\ \ mathbf {b} _ {2} \ end {bmatrix} \ end {eqnarray *} [/ math]

Luego, comprenda lo que implica la fila superior: [math] \ mathbf {A} _ {11} \ mathbf {x} _ {1} + \ mathbf {A} _ {12} \ mathbf {x} _ {2} = \ mathbf {b} _ {1} \ implica \ mathbf {x} _ {1} = \ mathbf {A} _ {11} ^ {- 1} (\ mathbf {b} _ {1} – \ mathbf {A} _ {12} \ mathbf {x} _ {2}) [/ math].

Si sustituimos esto en la fila inferior, estamos codificando la relación completa [math] \ mathbf {Ax} = \ mathbf {b} [/ math] con menos ecuaciones. Tenemos:

[matemática] \ begin {eqnarray *} \ mathbf {b} _ {2} & = & \ mathbf {A} _ {21} \ mathbf {x} _ {1} + \ mathbf {A} _ {22} \ mathbf {x} _ {2} \\ & = & \ mathbf {A} _ {21} \ big (\ mathbf {A} _ {11} ^ {- 1} (\ mathbf {b} _ {1} – \ mathbf {A} _ {12} \ mathbf {x} _ {2}) \ big) + \ mathbf {A} _ {22} \ mathbf {x} _ {2} \\ & = & \ mathbf {A } _ {21} \ mathbf {A} _ {11} ^ {- 1} \ mathbf {b} _ {1} – \ mathbf {A} _ {21} \ mathbf {A} _ {11} ^ {- 1} \ mathbf {A} _ {12} \ mathbf {x} _ {2} + \ mathbf {A} _ {22} \ mathbf {x} _ {2} \\ & = & \ mathbf {A} _ {21} \ mathbf {A} _ {11} ^ {- 1} \ mathbf {b} _ {1} + \ big (\ mathbf {A} _ {22} – \ mathbf {A} _ {21} \ mathbf {A} _ {11} ^ {- 1} \ mathbf {A} _ {12} \ big) \ mathbf {x} _ {2} \ end {eqnarray *} [/ math]

Que se puede reorganizar como:

[matemáticas] \ begin {eqnarray *} \ big (\ mathbf {A} _ {22} – \ mathbf {A} _ {21} \ mathbf {A} _ {11} ^ {- 1} \ mathbf {A} _ {12} \ big) \ mathbf {x} _ {2} & = & \ mathbf {b} _ {2} – \ mathbf {A} _ {21} \ mathbf {A} _ {11} ^ {- 1} \ mathbf {b} _ {1} \\ \ mathbf {A} ‘\ mathbf {x} _ {2} & = & \ mathbf {b}’ \ end {eqnarray *} [/ math]

donde [math] \ mathbf {A} ‘[/ math] es nuestro complemento Schur. Si [math] \ mathbf {A} [/ math] es denso, entonces este enfoque no ofrece ventajas. Sin embargo, si [math] \ mathbf {A} _ {11} [/ math] se invierte fácilmente (por ejemplo, porque es diagonal, en bandas, escaso o incluso simétrico), este enfoque ofrece un medio más rápido para resolver el conjunto original de ecuaciones

Answer 4

La intuición detrás del complemento Schur es la siguiente.

Una matriz describe cómo se relacionan un montón de puntos entre sí, por ejemplo, especifica fuerzas en cada punto de una estructura física, digamos un puente, y la matriz le indica qué tan lejos se dobla cada punto: la matriz describe cómo se unen y Entonces, ¿cómo la fuerza sobre uno influye en la flexión de otro? (Esta historia de describir objetos físicos por un conjunto de puntos se detalla en la respuesta de Reid Atcheson al Álgebra Lineal: ¿Cuál es la motivación detrás de la definición del complemento Schur de una matriz?)

El complemento de Schur es la matriz que describe la misma influencia en ese objeto físico, pero en un subconjunto de los puntos.

Esto es un poco sutil. ¿Por qué esa descripción de un subconjunto de puntos no es simplemente la submatriz de esos puntos? Bueno, eso es porque si i y j están en ese subconjunto yk no, el punto i influye en j directamente, pero también a través de k. El complemento Schur es una descripción que tiene en cuenta las conexiones a través de los puntos que ha excluido. (Y sí, lo hace mediante la reducción de filas como se describe en la respuesta de Daniel McLaury al Álgebra Lineal: ¿Cuál es la motivación detrás de la definición del complemento Schur de una matriz?)

Answer 5

El complemento de Schur es básicamente la eliminación guasiana para matrices de bloques. En lugar de hacer la eliminación gaussiana en una sola variable, lo haces en un vector de variables. A menudo se usa en la descomposición del dominio porque puede usarlo de manera independiente (es decir, puede hacer esto en paralelo) para encontrar soluciones aproximadas en múltiples subdominios (son aproximadas porque una vez que resuelve un problema en un subdominio de forma aislada , pierde toda la información sobre cómo un subdominio se une a otro).

Una vez que haga eso, puede usarlos para construir un problema reducido que capture toda la dinámica entre subdominios. El problema reducido puede ser, en ciertos casos, mucho más fácil de resolver que el problema original. Y además, debido a que la eliminación gaussiana es exacta en aritmética exacta, puede recuperar la solución en todo el dominio (aunque en general, no tiene garantías de que la solución que recupere sea la correcta porque la eliminación gaussiana es inestable sin pivotar y el complemento Schur que haces no impone pivotar, al menos en la matriz global)

Answer 6

Esto es mucho más simple que las otras respuestas. No necesitas saber nada de física o estadística ni nada más que álgebra matricial básica como la que enseñan en una clase avanzada de álgebra de secundaria.

Si reduce en fila una matriz de bloques, obtendrá cero en la esquina inferior izquierda, las mismas cosas que ya tenía en el lado derecho y un nuevo bloque en la esquina superior derecha. Este nuevo bloque se llama el complemento de Schur del bloque inferior izquierdo, porque juntos forman la diagonal del bloque de una matriz triangular superior del bloque similar a la matriz original. Esto se describe en detalle en la página de Wikipedia:

Complemento Schur

Si comprende por qué desea reducir una matriz en filas y por qué desea trabajar con matrices de bloques, entonces esto debería responder a su pregunta por completo. Si no, su problema no es con los complementos de Schur sino con uno o ambos de esos conceptos.

Answer 7

Un problema que conozco es en el cálculo de condicionales en gaussianos dadas las distribuciones conjuntas.

Además, de alguna manera, los resultados de los complementos de Schur se pueden usar de alguna manera para aumentar la eficiencia computacional. Fórmula Sherman – Morrison – Woodbury para la inversión matricial. alguna forma de teorema de inversión a partir de resultados intermedios de complementos de schur durante la derivación de condicionales o algo así.