Factorización LU

Factorización LU

Factorización LU

En el álgebra lineal, la factorización o descomposición LU es una forma de factorización de una matriz como el producto de una matriz triangular inferior y una superior. Debido a la inestabilidad de éste método, por ejemplo si un elemento de la diagonal es cero, es necesario premultiplicar la matriz por una matriz de permutación. Método llamado factorización PA = LU o LU con pivote.

Esta descomposición se usa en el análisis numérico para resolver sistemas de ecuaciones (más eficientemente) o encontrar las matrices inversas.

Contenido

Definiciones

A una matriz no singular (si lo fuera, entonces la descomposición podría no ser única)

 A = LU, \,

donde L y U son matrices inferiores y superiores triangulares.

Para matrices 3 \times 3 , esto es:

 
        \begin{pmatrix}
           a_{11} & a_{12} & a_{13} \\
           a_{21} & a_{22} & a_{23} \\
           a_{31} & a_{32} & a_{33} \\
        \end{pmatrix} =
      \begin{pmatrix}
           1 & 0 & 0 \\
           l_{21} & 1 & 0 \\
           l_{31} & l_{32} & 1 \\
        \end{pmatrix}
        \begin{pmatrix}
           u_{11} & u_{12} & u_{13} \\
           0 & u_{22} & u_{23} \\
           0 & 0 & u_{33} \\
        \end{pmatrix}

Por otro lado la descomposición PLU tiene esta forma:

Lm − 1Pm − 1...L2P2L1P1A = U

Con Lm − 1...L1 matrices triangulares inferiores, Pm − 1...P1 matrices de permutacion y U una matriz triangular superior.

Para determinar L:

L = (L'm − 1 * ... * L'2 * L'1) − 1

y cada L'k está dado por:

L'k = {P}_{m-1}*...*{P}_{k+1}*{L}_{k}*{P^{-1}}_{k+1}*...*{P^{-1}}_{m-1}

Esto se debe a que L'k es igual a Lk, pero con los elementos de la subdiagonal permutados.

Otra forma de ver éste tipo de factorización es: A = PTLU Recordando que las matrices de permutación matriz permutación son invertibles y su inversa es su traspuesta


Unicidad

Las matrices L y U son únicas, si la matriz no es singular. En caso contrario pueden no ser únicas.

Demostración:

Dada la matriz A ∈ Rmxn


A = L1U1 y A = L2U2

Recordemos que L1,U1,L2,U2 son invertibles por tener el determinante distinto de cero entonces:

L1U1 = L2U2


{L_{2}}^{-1}L_{1}=U_{2}{U_{1}}^{-1}


Entonces {L_{2}}^{-1}L_{1} es una matriz triangular inferior, con unos en la diagonal y U_{2}{U_{1}}^{-1} es triangular superior, con unos en la diagonal (recordando que el producto matricial de triangulares superiores/inferiores es triangular superior/inferior). La única matriz que cumple estas dos propiedades es la identidad. Por lo tanto:

{L_{2}}^{-1}L_{1}=I y U_{2}{U_{1}}^{-1}=I

Con lo cual:

L1 = L2 y U1 = U2

Algoritmos

La factorización LU es básicamente una forma modificada de la eliminación gaussiana. Transformamos la matriz A en una triangular superior U anulando los elementos debajo de la diagonal.

E1 * E2 * ... * En * A = U

Donde E1,E2,...,En son matrices elementales, que representan los distintos pasos de la eliminación. Luego recordando que la inversa de una matriz elemental, es otra matriz elemental:

A = E^{-1}_{1}*E^{-1}_{2}*...*E^{-1}_{n}*U

Llamamos L a E^{-1}_{1}*E^{-1}_{2}*...*E^{-1}_{n} una matriz triangular inferior.


Aplicaciones

Resolviendo sistemas de álgebra lineal

Dada la ecuación matricial

Ax = LUx = b

Queremos la solución para un determinando A y b. Los pasos son los siguientes:

  1. Primero, resolvemos Ly = b para y
  2. Segundo, resolvemos Ux = y para x.

Nótese que ya tenemos las matrices L y U. La ventaja de este método es que es computacionalmente eficiente, porque podemos elegir el vector b que nos parezca y no tenemos que volver a hacer la eliminación de Gauss cada vez.

Factorización L-U con pivotación: Al utilizar la técnica de triangulación de Gauss para obtener la descomposición L-U de una matriz A podemos encontrarnos con el mismo problema de encontrar un coeficiente en la diagonal que sea 0 o un mal condicionamiento. Podemos entonces utilizar la misma técnica de pivotación : buscar el siguiente elemento en la columna que sea distinto de 0 o , mejor aún , el de mayor valor absoluto.

Pero una vez obtenida la descomposición L-U, si queremos aplicarla a resolver un sistema de ecuaciones , tendremos que tener en cuenta la “historia” o registro de las pivotaciones efectuadas para aplicar al vector de términos independientes.

Esto se realiza mediante la matriz de permutación P , que consiste en efectuar sobre la matriz identidad , las mismas permutaciones de filas que se vayan efectuando sobre la matriz que se está triangulando por Gauss.

Al mismo tiempo se efectúan las mismas permutaciones sobre los elementos subdiagonal de la matriz L.

Así , si tenemos , por ejemplo , el sistema:

AX=B


y L y U son las matrices obtenidas de la matriz A como descomposición L-U por triangulación de Gauss con pivotaciones recogidas en la matriz de permutación P, es fácil comprobar que :

LU=PA (LU)X=P(AX)=PB=NUEVOB


Por tanto los procesos de sustitución descendente y ascendente los aplicamos a : LD=NUEVOB UX=D

Matriz Inversa

Las matrices L y U pueden ser usadas para calcular la matriz inversa mediante:

A − 1 = U − 1L − 1

Algunas implementaciones que invierten matrices usan este método.

Determinante de una matriz

Las matrices L y U pueden ser usadas para calcular el determinante de la matriz A muy eficientemente porque det(A) = det(L)det(U) y los determinantes de matrices triangulares son simplemente el producto de los elementos de sus diagonales. En particular, si L es una matriz triangular en cuya diagonal todos los elementos son uno, entonces:

 \det(A) = \det(L) \det(U) = \det(U) = \prod_{i=1}^n u_{ii}.

La misma aproximación al problema puede ser usada para factorizaciones LUP en las que aparece matrices de permutación, pues el determinante de una matriz de permutación P es (−1)S, donde S es el número de permutaciones de filas en la descomposición.

Obtenido de "Factorizaci%C3%B3n LU"

Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Factorización — Saltar a navegación, búsqueda En álgebra, la factorización es expresar un objeto o número (por ejemplo, un número compuesto, una matriz o un polinomio) como producto de otros objetos más pequeños (factores), (en el caso de números debemos… …   Wikipedia Español

  • Factorización QR — Saltar a navegación, búsqueda En álgebra lineal, la descomposición o factorización QR de una matriz es una descomposición de la misma como producto de una matriz ortogonal por una triangular superior. La descomposición QR es la base del algoritmo …   Wikipedia Español

  • Factorización — En matemáticas, factorización es la descomposición de un objeto en una lista de objetos más pequeños (factores), que al multiplicarlos todos resulta el objeto original. Por ejemplo, el número 15 se factoriza en números primos 3 × 5; y el… …   Enciclopedia Universal

  • Factorización de matrices — Saltar a navegación, búsqueda En álgebra lineal la factorización de una matriz es la descomposición de la misma como producto de dos o más matrices según una forma canónica. Según las aplicaciones de la factorización podemos distinguir los… …   Wikipedia Español

  • Factorización de enteros — Saltar a navegación, búsqueda En teoría de números, el problema de la factorización de enteros consiste en encontrar un divisor no trivial de un número compuesto; Por ejemplo dado el número 91, el reto es encontrar un número tal como el 7 que lo… …   Wikipedia Español

  • Factorización de Cholesky — Saltar a navegación, búsqueda En matemáticas, la factorización o descomposición de Cholesky toma su nombre del matemático André Louis Cholesky, quien encontró que una matriz simétrica definida positiva puede ser descompuesta como el producto de… …   Wikipedia Español

  • Factorización de rango — Saltar a navegación, búsqueda Dada una matriz A, de dimensiones y de rango r, una descomposición de rango de A es un producto A = CF, donde C es una matriz y F es una matriz …   Wikipedia Español

  • Factorización de Schur — Saltar a navegación, búsqueda En álgebra lineal, la descomposición de Schur o triangulación de Schur es una importante descomposición matricial. Definición Si A es una matriz cuadrada sobre números complejos, entonces A puede descomponerse como… …   Wikipedia Español

  • Método de factorización de Euler — El método de factorización de Euler es un método de factorización basado en la representación de un entero positivo N como la suma de dos cuadrados de dos maneras distintas: N = a2 + b2 = c2 + d2 Aunque la factorización algebraica de números… …   Wikipedia Español

  • Teorema de factorización de Weierstrass — En matemática, concretamente en análisis complejo, el teorema de factorización de Weierstrass, llamado así en honor a Karl Weierstrass, asegura que las funciones enteras pueden ser representadas mediante un producto que envuelve sus ceros. Además …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”