Matriz ortogonal

BeneficiosEditar

El análisis numérico aprovecha muchas de las propiedades de las matrices ortogonales para el álgebra lineal numérica, y surgen de forma natural. Por ejemplo, a menudo es deseable calcular una base ortonormal para un espacio, o un cambio ortogonal de bases; ambos toman la forma de matrices ortogonales. Tener el determinante ±1 y todos los valores propios de magnitud 1 es muy beneficioso para la estabilidad numérica. Una implicación es que el número de condición es 1 (que es el mínimo), por lo que los errores no se magnifican al multiplicar con una matriz ortogonal. Muchos algoritmos utilizan matrices ortogonales como las reflexiones de Householder y las rotaciones de Givens por esta razón. También es útil que, no sólo una matriz ortogonal es invertible, sino que su inversa está disponible esencialmente gratis, mediante el intercambio de índices.

Las permutaciones son esenciales para el éxito de muchos algoritmos, incluyendo el caballo de batalla de la eliminación de Gauss con pivote parcial (donde las permutaciones hacen el pivote). Sin embargo, rara vez aparecen explícitamente como matrices; su forma especial permite una representación más eficiente, como una lista de n índices.

Así mismo, los algoritmos que utilizan matrices de Householder y Givens suelen utilizar métodos especializados de multiplicación y almacenamiento. Por ejemplo, una rotación de Givens afecta sólo a dos filas de una matriz que multiplica, cambiando una multiplicación completa de orden n3 a una mucho más eficiente de orden n. Cuando los usos de estas reflexiones y rotaciones introducen ceros en una matriz, el espacio desocupado es suficiente para almacenar datos suficientes para reproducir la transformación, y hacerlo de forma robusta. (Siguiendo a Stewart (1976), no almacenamos un ángulo de rotación, que es caro y se comporta mal.)

DescomposicionesEditar

Una serie de descomposiciones matriciales importantes (Golub & Van Loan 1996) implican matrices ortogonales, incluyendo especialmente:

Descomposición QR M = QR, Q ortogonal, R triangular superior Descomposición del valor singular M = UΣVT, U y V ortogonales, Σ matriz diagonal Eigendecomposición de una matriz simétrica (descomposición según el teorema espectral) S = QΛQT, S simétrica, Q ortogonal, Λ diagonal Descomposición polar M = QS, Q ortogonal, S simétrica positiva-semidefinida

EjemplosEditar

Considere un sistema de ecuaciones lineales sobredeterminado, como podría ocurrir con las mediciones repetidas de un fenómeno físico para compensar los errores experimentales. Escribe Ax = b, donde A es m × n, m > n.Una descomposición QR reduce A a R triangular superior. Por ejemplo, si A es 5 × 3 entonces R tiene la forma

R = . {\displaystyle R={begin{bmatrix}\cdot &\cdot &\cdot &\cdot&0&\cdot \\0&&&&0\end{bmatrix}}.}

El problema lineal de mínimos cuadrados consiste en encontrar la x que minimiza ||Ax – b||, lo que equivale a proyectar b al subespacio abarcado por las columnas de A. Suponiendo que las columnas de A (y por tanto R) son independientes, la solución de proyección se encuentra a partir de ATAx = ATb. Ahora ATA es cuadrado (n × n) e invertible, y también es igual a RTR. Pero las filas inferiores de ceros de R son superfluas en el producto, que por tanto ya está en forma factorizada triangular inferior-triangular superior, como en la eliminación gaussiana (descomposición de Cholesky). Aquí la ortogonalidad es importante no sólo para reducir ATA = (RTQT)QR a RTR, sino también para permitir la solución sin magnificar los problemas numéricos.

En el caso de un sistema lineal que está subdeterminado, o una matriz no invertible de otra manera, la descomposición del valor singular (SVD) es igualmente útil. Con A factorizado como UΣVT, una solución satisfactoria utiliza la pseudoinversa de Moore-Penrose, VΣ+UT, donde Σ+ simplemente sustituye cada entrada diagonal no nula por su recíproco. Fijar x en VΣ+UTb.

El caso de una matriz cuadrada invertible también tiene interés. Supongamos, por ejemplo, que A es una matriz de rotación de 3 × 3 que se ha calculado como la composición de numerosos giros y vueltas. El punto flotante no coincide con el ideal matemático de los números reales, por lo que A ha ido perdiendo su verdadera ortogonalidad. Un proceso de Gram-Schmidt podría ortogonalizar las columnas, pero no es el método más fiable, ni el más eficiente, ni el más invariable. La descomposición polar convierte una matriz en un par, uno de los cuales es la única matriz ortogonal más cercana a la matriz dada, o una de las más cercanas si la matriz dada es singular. (La cercanía puede medirse por cualquier norma de matriz invariante bajo un cambio de base ortogonal, como la norma espectral o la norma de Frobenius). Para una matriz casi ortogonal, la convergencia rápida al factor ortogonal puede lograrse mediante un enfoque de «método de Newton» debido a Higham (1986) (1990), promediando repetidamente la matriz con su transposición inversa. Dubrulle (1994) harvtxt error: sin objetivo: CITEREFDubrulle1994 (help) ha publicado un método acelerado con una conveniente prueba de convergencia.

Por ejemplo, consideremos una matriz no ortogonal para la que el algoritmo de promediación simple tarda siete pasos

→ → ⋯ → {\displaystyle {\begin{bmatrix}3&1\b7&5\end{bmatrix}}rightarrow {\begin{bmatrix}1.8125&&2.6875{end{bmatrix}{rightarrow}{cdots}{rightarrow} {\begin{bmatrix}0.8&&0.8\end{bmatrix}}}

y cuya aceleración se recorta a dos pasos (con γ = 0,353553, 0,565685).

→ → {\año}&1\año7&5\año}

.06066\\1.06066&1.41421\end{bmatrix}}\rightarrow {\begin{bmatrix}0.8&&0.8\end{bmatrix}}}

Gram-Schmidt arroja una solución inferior, mostrada por una distancia de Frobenius de 8.28659 en lugar del mínimo de 8,12404.

→ {\displaystyle {\begin{bmatrix}3&1\b7&5\bend{bmatrix}rightarrow {\begin{bmatrix}0.393919&&0.393919\end{bmatrix}}}

Aleatorización

Algunas aplicaciones numéricas, como los métodos de Monte Carlo y la exploración de espacios de datos de alta dimensión, requieren la generación de matrices ortogonales aleatorias uniformemente distribuidas. En este contexto, «uniforme» se define en términos de la medida de Haar, que esencialmente requiere que la distribución no cambie si se multiplica por cualquier matriz ortogonal elegida libremente. Ortogonalizar matrices con entradas aleatorias independientes distribuidas uniformemente no da lugar a matrices ortogonales distribuidas uniformemente, pero la descomposición QR de entradas aleatorias independientes distribuidas normalmente sí lo hace, siempre que la diagonal de R contenga sólo entradas positivas (Mezzadri 2006). Stewart (1980) reemplazó esto con una idea más eficiente que Diaconis & Shahshahani (1987) generalizó más tarde como el «algoritmo de subgrupo» (en cuya forma funciona igual de bien para permutaciones y rotaciones). Para generar una matriz ortogonal (n + 1) × (n + 1), tome una n × n y un vector unitario uniformemente distribuido de dimensión n + 1. Construya una reflexión de Householder a partir del vector, y luego aplíquela a la matriz más pequeña (incrustada en la de mayor dimensión con un 1 en la esquina inferior derecha).

Matriz ortogonal más cercanaEditar

El problema de encontrar la matriz ortogonal Q más cercana a una matriz dada M está relacionado con el problema de Procrustes Ortogonal. Hay varias formas diferentes de obtener la solución única, la más sencilla es tomar la descomposición del valor singular de M y sustituir los valores singulares por unos. Otro método expresa la R explícitamente pero requiere el uso de una raíz cuadrada matricial:

Q = M ( M T M ) – 1 2 {\displaystyle Q=M\left(M^{\mathrm {T} }M\right)^-{\frac {1}{2}}}}

Esto puede combinarse con el método babilónico para extraer la raíz cuadrada de una matriz para dar una recurrencia que converge a una matriz ortogonal cuadráticamente:

Q n + 1 = 2 M ( Q n – 1 M + M T Q n ) – 1 {\displaystyle Q_{n+1}=2M\left(Q_{n}^{-1}M+M^{\\mathrm {T} }Q_{n}\right)^{-1}