30 votos

¿La eliminación gaussiana es sólo Gram-Schmidt con un cambio en el símbolo del producto interior?

En algún momento me di cuenta de que si se toma el algoritmo de Gram-Schmidt para tomar la descomposición QR de una matriz, y se cambia el significado del símbolo del producto interior $\langle \mathbf u, \mathbf v \rangle$ (donde $\mathbf u, \mathbf v \in \mathbb R^n$ ) a:

$u_i v_i$ para el más pequeño $i \in \{1,2,\dotsc,n\}$ para lo cual $u_i \neq 0$ o $v_i \neq 0$ ,

entonces el algoritmo Gram-Schmidt cambia a eliminación gaussiana. Nótese que ya no es un producto interior. Incluso es discontinuo, curiosamente. Observe que si introducimos pivotar a Gram-Schmidt, entonces el Gram-Schmidt pivotado cambia a eliminación gaussiana pivotada. Observe también que la definición de una matriz ortogonal ( $\langle T\mathbf e_i, T\mathbf e_j \rangle = \langle \mathbf e_i, \mathbf e_j \rangle$ para la base estándar $\{e_1,e_2,\dotsc,e_n\}$ ) pasa a ser una matriz triangular inferior cuyas entradas diagonales son $\pm 1$ (seguido de la permutación de columnas), lo que da lugar a que la descomposición QR cambie a la descomposición LR.

¿Hay alguna razón conceptual para ello?

8voto

Matt S Puntos 4279

No estoy seguro de que esto responda a la pregunta "¿por qué ocurre esto?". Pero espero que proporcione una visión más geométrica/abstracta de esto.

Me parece que tanto la eliminación Gram-Schmidt como la Gaussiana pueden describirse como llevar una base dada a una base especial. El proceso Gram-Schmidt produce una base ortonormal, mientras que la eliminación gaussiana produce una base que es estándar respecto a una bandera fija (con algunos problemas potenciales de degeneración).

Por una bandera, me refiero a una cadena de subespacios $V_1\leq V_2 \leq \dotsb \leq V_{n-1} \leq V_n = \mathbb{F}^n$ . Una base $v_1,\dotsc v_n$ estándar a esta bandera tiene la propiedad $\langle v_1,\dotsc, v_k \rangle = V_k$ . Si nuestra bandera viene dada por $V_k = \langle e_1,\dotsc, e_k \rangle$ donde $e_i$ son las bases en las que escribimos nuestras matrices, entonces la matriz que tiene como columnas cualquier otra base estándar es triangular superior.

Nota: al considerar sólo las bases nos hemos centrado realmente en el caso de que nuestras matrices sean invertibles, pero estas ideas podrían extenderse al caso singular.

Fijando una base $e_i$ también obtenemos una bandera complementaria libre con subespacios $W_{n-k} = \langle e_{k+1},\dotsc, e_n \rangle$ para que $V_k \oplus W_{n-k} = \mathbb{F}^n$ para cada $k$ . Una matriz con columnas normalizadas con respecto a esta bandera es triangular inferior. Podría haber empezado sólo con esta bandera, pero el par opuesto será útil.

Ahora observamos que el paso de proyección de su proceso Gram-Schmidt alterado es precisamente (en el paso $k+1$ ) a lo largo de $V_k$ en $W_{n-k}$ y luego normalizar (en el paso $1$ simplemente normalizamos). Debemos tener cuidado aquí porque esto sólo funciona si nuestra base elegida $u_1,\dots,u_n$ tiene la propiedad: $u_k$ proyectado sobre $W_{n-k+1}$ no está en $W_{n-k}$ ya (es decir, su componente en el $e_k$ es distinto de cero).

De hecho, su $(u,v)$ podría considerarse exactamente el artilugio para conseguirlo sin tener que seguir $k$ alrededor.

Tenga en cuenta que puede adaptarlo fácilmente para asegurarse de que el número de la diagonal es exactamente $1$ y no sólo $\pm 1$ . Obviamente, algunas elecciones de base original causarán problemas, pero por lo demás esto llevará una base arbitraria a una norma con respecto a nuestra segunda bandera.

Correspondientemente, toma una matriz arbitraria (con salvedades) en una triangular inferior y obtenemos la descomposición LR en lugar de la descomposición QR.

Una cosa más a tener en cuenta es que hemos encontrado que la matriz triangular inferior con todos los $1$ en la diagonal. En particular, esto la hace unipotente y, de hecho, el conjunto de todas las matrices de este tipo es el radical unipotente $U^-$ del grupo de matrices triangulares inferiores invertibles $B^-$ . Así que lo que hemos redescubierto es que $U^-B$ cubre gran parte de $GL(\mathbb{F}^n)$ . En efecto, se trata de un subconjunto denso denominado "célula grande" de la descomposición de Bruhat; véase Caracterización de la célula grande de Bruhat de los grupos universales de Chevalley sobre $\mathbb C$ .

En este lenguaje de grupos de Lie (centrándonos en el caso invertible), lo que has encontrado es una forma de moverse entre la descomposición de Iwasawa y la descomposición de Bruhat (no estoy seguro de cómo se generalizaría esto a otros grupos de Lie semisimples/reductivos, pero creo que podría).

1voto

Idan K Puntos 10037

Comenzamos con el $2 \times 2$ en el que obtenemos algunas ideas sobre el caso general. Nos encontramos con que tenemos que inventar una nueva noción para reemplazar las formas cuadráticas con el fin de generalizar estas ideas a la $n \times n$ caso.

Consideremos las matrices diagonales $D_P = \begin{pmatrix}1 & 0 \\ 0 & 0 \end{pmatrix}$ y $D_S = \begin{pmatrix}1 & 0 \\ 0 & 1 \end{pmatrix}$ donde $P$ y $S$ sugestivamente significan PLANO y ESFERA. Cada una de ellas determina una forma cuadrática. Una matriz $Q$ es ortogonal con respecto a $D_S$ como forma cuadrática si $Q$ es ortogonal en el sentido habitual. Consideremos ahora cuándo $Q$ es ortogonal con respecto a $D_P$ : $$Q D_P Q^T = D_P \implies Q=LP$$ donde $L$ es una matriz triangular inferior y $P$ es una matriz de permutación.

Obsérvese ahora que los factores de la $QR$ son ortogonales con respecto a $D_S$ y $D_P$ respectivamente. Los factores de la $LU$ son ortogonales con respecto a $D_P$ y $\operatorname{adj}(D_P)$ respectivamente (donde hemos utilizado la matriz adjunta).

Así que esto sugiere cuál podría ser el caso general:

  1. Una matriz $M$ puede (¿a menudo?) escribirse como el producto $Q'Q$ donde $Q'$ es ortogonal con respecto a una forma cuadrática, y $Q$ es ortogonal con respecto a otra. Es posible que se necesiten algunos factores adicionales de la matriz de permutación.

  2. La triangularidad con permutación de columnas (o filas) tiene algo que ver con las formas cuadráticas degeneradas.

Nos basamos en el punto 2. Si intentamos generalizar la observación anterior a $3 \times 3$ matrices, no se sostiene, porque la teoría de las formas cuadráticas degeneradas se vuelve demasiado, errrr, degenerada.

Propuesta de una noción alternativa a una forma cuadrática degenerada

Definimos un Forma cuadrática con compensación degenerativa en $\mathbb R^n$ como una secuencia de formas cuadráticas $(Q_1, Q_2, \dotsc)$ donde $\forall i, \forall j > i, Q_i(\mathbf v) \neq 0 \implies Q_j(\mathbf v) = 0$ . Esto se asemeja a un complejo en cadena.

Ahora bien, una matriz triangular superior permutada por columnas es una matriz que es ortogonal con respecto a la forma cuadrática compensada por degeneraciones en la que cada $Q_i$ tiene rango $1$ .

Definimos la "forma hermitiana" correspondiente por: $$\langle \mathbf u, \mathbf v \rangle = \langle \mathbf u, \mathbf v \rangle_{Q_i},$$ donde $i$ es el mayor índice para el que todos los $j < i$ tienen $Q_j(\mathbf u) = Q_j(\mathbf v) = 0$ .

La generalización obvia de Gram-Schmidt incluye la eliminación gaussiana. Esto sugiere que la noción podría ser natural.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X