He intentado buscar alguna referencia en la red pero no he encontrado ninguna buena. ¿Cuál es la ventaja de pivotar en la descomposición LU sobre la descomposición LU normal? ¿Tiene algo que ver con la matriz singular o no?
Respuestas
¿Demasiados anuncios?
Para generalizar aún más la respuesta de Rahul, cualquier matriz que tenga un bloque principal singular no puede tener una descomposición LU. Permitiendo el pivoteo (o en términos de factorización matricial, permitiendo la multiplicación de su matriz original por una matriz de permutación apropiada), todas las matrices admiten una descomposición LU. Esta es la explicación del pivoteo en la aritmética exacta.
En la aritmética inexacta, la condición "singular" de la explicación anterior se sustituye por el término "mal condicionado". Cada matriz tiene un número de condición asociado, que se define como el producto de la norma de la matriz y la norma de su inversa. Al intentar proceder a la descomposición LU de una matriz con un bloque principal mal condicionado, se llegará a un punto en el que hay que dividir por un número pequeño (resultando en un número que puede ser mucho mayor en magnitud que las entradas originales de la matriz), lo que provoca todo tipo de problemas en las sumas/restas sucesivas que hay que hacer para terminar la descomposición LU.
Al pivotar, evitamos (o al menos retrasamos) la aparición de números mucho mayores que las entradas de la matriz original, que es una de las formas en que se pierde precisión en las operaciones.
Por supuesto, se podría objetar que los coeficientes están mal escalados: por ejemplo, si se tienen dos ecuaciones en dos incógnitas, y se multiplican ambos lados de cualquiera de las dos ecuaciones por un número mucho menor o mucho mayor que los coeficientes originales, la solución del sistema sigue siendo la misma, pero intentar realizar la descomposición LU en el sistema transformado puede ser desastroso. Aquí es donde entran en juego conceptos como el "pivotaje a escala", en el que se tienen en cuenta las magnitudes relativas en lugar de las absolutas a la hora de seleccionar los pivotes.
Además, hay aplicaciones en las que el "pivotaje parcial" (intercambio de filas) no es suficiente; la determinación del rango de una matriz, por ejemplo, requiere un "pivotaje completo" (intercambio de filas y columnas).
En resumen, la descomposición LU se comporta mucho mejor con el pivote.
(He sido intencionadamente vago en algunas partes; harías bien en leer Golub y Van Loan, como ya recomendó jmoy, o los libros "Matrix Decompositions" de Stewart o "Applied Numerical Linear Algebra" de Demmel para versiones más rigurosas de mi explicación).
theog
Puntos
585
Eric Goodwin
Puntos
1497
La mayoría de las matrices cuadradas invertibles admiten una $LU$ descomposición con $L$ una matriz triangular inferior con 1 en la diagonal y $U$ es una matriz triangular superior (con entradas diagonales arbitrarias no nulas). Se ve fácilmente que tal expresión es única. El conjunto de matrices invertibles que admiten la descomposición es abierto y denso en el grupo de matrices invertibles de n por n $GL(n)$ . Una matriz pertenece a este conjunto si y sólo si todos sus menores principales son distintos de cero como se menciona en el Página de Wikipedia ) Si la matriz no pertenece a este conjunto aún admite un $LU$ descomposición con pivote $A = wLU$ con $L$ y $U$ como antes y $w$ es una matriz de permutación.
El origen geométrico de estas construcciones viene dado por el Descomposición celular de Bruhat de $GL(n)$
$GL(n) = \coprod_{w \in W} BwB$
donde $B$ es el subgrupo de las matrices triangulares superiores invertidas, $W$ es el grupo simétrico, y $w$ es una matriz de permutación.
Cuando $w=w_0$ es el elemento más largo del grupo simétrico, dado por una matriz antidiagonal con una antidiagonal unidad, entonces: $ B w_0 = w_0 w_0^{-1} B w_0 = w_0 N $ , donde $N$ es el grupo de las matrices triangulares superiores. Así, el conjunto de matrices que admiten la descomposición LU regular se identifica con la celda correspondiente al elemento más largo. Esta celda que es densa en $GL(n)$ se denomina célula grande (Schubert).
Cuando, la matriz pertenece a la celda grande , pero algunos de los principales menores son muy pequeños con respecto a otros, entonces el $LU$ La descomposición dará como resultado elementos matriciales grandes, porque los determinantes de los menores principales aparecen en los denominadores de los elementos matriciales de la $LU$ descomposición. En este caso, es habitual realizar un pivotaje para trasladar esta matriz a otra celda, para reducir la diferencia de escala entre los principales menores y ganar estabilidad numérica.
