Álgebra lineal

Álgebra lineal numérica

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 siguientes tipos de factorizaciones:

Resolución de sistemas de ecuaciones lineales

Las siguientes factorizaciones se utilizan en la resolución de sistemas de ecuaciones lineales, cálculo de determinantes e inversión de matrices.

Factorización LU

• Aplicable a: una matriz cuadrada A
• Factorización: ${\displaystyle A=LU}$, donde L es una matriz triangular inferior y U es una matriz triangular superior
• Notas: La factorización LU expresa el método de Gauss en forma matricial. En efecto, PA = LU donde P es una matriz de permutación. Los elementos de la diagonal principal de L son todos iguales a 1. Una condición suficiente de que exista la factorización es que la matriz A sea invertible.
• Resolución del sistema de ecuaciones lineales Ax = b: primero se resuelve el sistema de ecuaciones Ly = b y después Ux = y.
• Existencia: Una condición necesaria y suficiente es que todos los menores principales de A sean distintos de cero.¹
• Métodos de cálculo: método de Crout que obtiene una matriz U cuyos elementos de la diagonal son todos 1. El método de Doolittle es una modificación del mismo.

Factorización ${\displaystyle LDL^{T}}$

• Aplicable a: una matriz simétrica A.
• Factorización: ${\displaystyle A=LDL^{T}}$ donde L es una matriz triangular inferior con unos en la diagonal y ${\displaystyle L^{T}}$ denota su matriz traspuesta. La factorización es única.
• Existencia: Una condición suficiente es que todos los menores principales de A sean distintos de cero.
• Notas: Si la matriz es definida positiva la factorización existe y es única siendo los elementos de la diagonal positivos.

Factorización de Cholesky

• Aplicable a: una matriz simétrica definida positiva A
• Factorización: ${\displaystyle A=LL^{T}}$, donde L es una matriz triangular inferior con entradas en la diagonal positivas.
• Notas: La factorización siempre existe y es única.

Factorización QR o triangularización ortogonal

• Aplicable a: una matriz A m por n.
• Factorización: ${\displaystyle A=QR}$ donde Q es una matriz ortogonal m por m, y R es una matriz triangular superior m por n.
• Métodos de cálculo: La factorización QR puede calcularse mediante el proceso de ortogonalización de Gram-Schmidt aplicado a las columnas de A, mediante el uso de transformaciones de Householder y mediante transformaciones de Givens.
• Notas: La factorización QR puede utilizarse para "resolver" el sistema de ecuaciones lineales Ax = b cuando el número de ecuaciones es distinto al de incógnitas.

Descomposición en valores singulares

• Aplicable a: una matriz A m-por-n.
• Factorización: ${\displaystyle A=U\Sigma V^{T}}$, donde Σ es una matriz diagonal mxn, y U y V son matrices ortogonales mxm y nxn respectivamente, siendo ${\displaystyle V^{T}}$ la traspuesta de V. Los elementos de la diagonal de Σ son los valores singulares de A y son mayores o iguales a cero.
• Notas: a la matriz ${\displaystyle V\Sigma ^{+}U^{T}}$, donde ${\displaystyle \Sigma ^{+}}$ es igual a la matriz Σ reemplazando los valores singulares por sus recíprocos, se le llama pseudoinversa de A.

Otros tipos de factorizaciones

Diagonalización de una matriz

• Aplicable a: una matriz cuadrada A
• Factorización: A = CDC^-1
• Existencia:

Forma canónica de Jordan

• Aplicable a: una matriz cuadrada B
• Factorización:

Factorización de rango

• Aplicable a: una matriz A de dimensiones ${\displaystyle m\times n}$
• Factorización: ${\displaystyle A=CF}$, donde ${\displaystyle C}$ es una matriz ${\displaystyle m\times r}$ y ${\displaystyle F}$ es una matriz ${\displaystyle r\times n}$

Factorización de Schur

• Aplicable a: una matriz cuadrada A
• Factorización:

Tridiagonalización

• Aplicable a: una matriz cuadrada simétrica A

La factorización LU

Supongamos que A se puede factorizar como el producto de una matriz triangular inferior L con una matriz triangular superior U:

 

A = LU

(51)

En este caso, el sistema de ecuaciones dado por (44) podría representarse en la forma:

 

LUx=b

(52)

Si denominamos z a la matriz columna de n filas resultado del producto de las matrices Ux, tenemos que la ecuación (52) se puede reescribir del siguiente modo:

 

Lz=b

(53)

A partir de las ecuaciones (52) y (53), es posible plantear un algoritmo para resolver el sistema de ecuaciones empleando dos etapas:

• Primero obtenemos z aplicando el algoritmo de sustitución progresiva en la ecuación (53).
• Posteriormente obtenemos los valores de x aplicando el algoritmo de sustitución regresiva a la ecuación
  
  
  Ux = z
  
  

El análisis anterior nos muestra lo fácil que es resolver estos dos sistemas de ecuaciones triangulares y lo útil que resultaría disponer de un método que nos permitiera llevar a cabo la factorización A=LU. Si disponemos de una matriz A de , estamos interesados en encontrar aquellas matrices:

tales que cumplan la ecuación (51). Cuando esto es posible, decimos que A tiene una descomposición LU. Se puede ver que las ecuación anterior no determina de forma única a Ly a U. De hecho, para cada ipodemos asignar un valor distinto de cero a l_ii o u_ii (aunque no ambos). Por ejemplo, una elección simple es fijar l_ii=1 para  haciendo de esto modo que L sea una matriz triangular inferior unitaria. Otra elección es hacer U una matriz triangular superior unitaria (tomando u_ii=1 para cada i).Para deducir un algoritmo que nos permita la factorización LU de Apartiremos de la fórmula para la multiplicación de matrices:

(54)

en donde nos hemos valido del hecho de que l_is=0 para s >i y u_sj=0 para s>j.En este proceso, cada paso determina una nueva fila de U y una nueva columna de L. En el paso k, podemos suponer que ya se calcularon las filas  de U, al igual que las columnas de L. Haciendo i=j=k en la ecuación (54) obtenemos

(55)

Si especificamos un valor para l_kk (o para u_kk), a partir de la ecuación (55) es posible determinar un valor para el otro término. Conocidas u_kk y l_kk y a partir de la ecuación (54) podemos escribir las expresiones para la k-ésima fila (i=k) y para la k-ésima columna (j=k), respectivamente:

 

			(56)
			(57)

Es decir, las ecuaciones (57) se pueden emplear para encontrar los elementos u_kj y l_ik.El algoritmo basado en el análisis anterior se denomina factorización de Doolittle cuando se toman los términos l_ii = 1 para  (L triangular inferior unitaria) y factorización de Crout cuando se toman los términos u_ii=1 (U triangular superior unitaria).
Una implementación en pseudocódigo del algoritmo para llevar a cabo la factorización LU se muestra en la figura (11).

  

Figure: Implementación del algoritmo de la factorización LU.

Es interesante notar que los bucles que permiten el cómputo de la k-ésima fila de U y de la k-ésima columna de L se pueden llevar a cabo en paralelo, es decir, pueden evaluarse simultáneamente sobre dos procesadores, lo que redunda en un importante ahorro del tiempo de cálculo.
Ejemplo: Encuentre las factorizaciones de Doolittle y Crout de la matriz:

La factorización de Doolittle es, a partir del algoritmo:

En vez de calcular la factorización de Crout directamente, la podemos obtener a partir de la factorización de Doolittle que acabamos de ver. Efectivamente, si tenemos en cuenta que la matriz A es simétrica, es posible comprobar que se cumple la relación:

A = LU = U^TL^T

por lo que la factorización de Crout resulta ser:

factorización o descomposición de Cholesky toma su nombre del matemático André-Louis Cholesky, quien encontró que una matriz simétricadefinida positiva puede ser descompuesta como el producto de una matriz triangular inferior y la traspuesta de la matriz triangular inferior. La matriz triangular inferior es el triángulo de Cholesky de la matriz original positiva definida. El resultado de Cholesky ha sido extendido a matrices con entradas complejas. Es una manera de resolver sistemas de ecuaciones matriciales y se deriva de la factorización LU con una pequeña variación.

Cualquier matriz cuadrada A con pivotes no nulos puede ser escrita como el producto de una matriz triangular inferior L y una matriz triangular superior U; esto recibe el nombre de factorización LU. Sin embargo, si A es simétrica y definida positiva, se pueden escoger los factores tales que U es la transpuesta de L, y esto se llama la descomposición o factorización de Cholesky. Tanto la descomposición LU como la descomposición de Cholesky son usadas para resolver sistemas de ecuaciones lineales. Cuando es aplicable, la descomposición de Cholesky es dos veces más eficiente que la descomposición LU.

Definición

En general, si A es Hermitiana y definida positiva, entonces A puede ser descompuesta como

${\displaystyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*},}$

donde L es una matriz triangular inferior con entradas diagonales estrictamente positivas y L^* representa la conjugada traspuesta de L. Esta es la descomposición de Cholesky.

La descomposición de Cholesky es única: dada una matriz Hermitiana positiva definida A, hay una única matriz triangular inferior L con entradas diagonales estrictamente positivas tales que A = LL^*. El recíproco se tiene trivialmente: si A se puede escribir como LL^* para alguna matriz invertible L, triangular inferior o no, entonces A es Hermitiana y definida positiva.

El requisito de que L tenga entradas diagonales estrictamente positivas puede extenderse para el caso de la descomposición en el caso de ser semidefinida positiva. La proposición se lee ahora: una matriz cuadrada A tiene una descomposición de Cholesky si y sólo si A es Hermitiana y semidefinida positiva. Las factorizaciones de Cholesky para matrices semidefinidas positivas no son únicas en general.

En el caso especial que A es una matriz simétrica definida positiva con entradas reales, L se puede asumir también con entradas reales. Una Matriz D diagonal con entradas positivas en la diagonal (valores propios de A), es factorizable como ${\displaystyle D={\sqrt {D}}{\sqrt {D}}}$, donde ${\displaystyle {\sqrt {D}}}$ es matriz cuya diagonal consiste en la raíz cuadrada de cada elemento de D, que tomamos como positivos. Así:

${\displaystyle A=LU=LDU_{0}=LDL^{t}=L({\sqrt {D}}{\sqrt {D}})L^{t}=(L{\sqrt {D}})({\sqrt {D}}L^{t})=(L{\sqrt {D}})(L{\sqrt {D}})^{t}=KK^{t}}$

La factorización puede ser calculada directamente a través de las siguientes fórmulas (en este caso realizamos la factorizacón superior ${\displaystyle A=U^{T}*U}$):
${\displaystyle u_{ii}^{2}=a_{ii}-\sum _{k=1}^{i-1}u_{ik}^{2}}$ para los elementos de la diagonal principal, y:

${\displaystyle u_{ij}={\frac {a_{ij}-\sum _{k=1}^{j-1}u_{ik}u_{jk}}{u_{jj}}}}$ para el resto de los elementos. Donde ${\displaystyle u_{ij}}$ son los elementos de la matriz U.

Aplicaciones

La descomposición de Cholesky se usa principalmente para hallar la solución numérica de ecuaciones lineales Ax = b. Si A es simétrica y positiva definida, entonces se puede solucionar Ax = b calculando primero la descomposición de Cholesky A = LL^T, luego resolviendo Ly = b para y, y finalmente resolviendo L^Tx = y para x.

Mínimos cuadrados lineales

Sistemas de la forma Ax = b con A simétrica y definida positiva aparecen a menudo en la práctica. Por ejemplo, las ecuaciones normales en problemas de mínimos cuadrados lineales son problemas de esta forma. Podría ocurrir que la matriz A proviene de un funcional de energía el cual debe ser positivo bajo consideraciones físicas; esto ocurre frecuentemente en la solución numérica de ecuaciones diferenciales parciales.

Simulación de Montecarlo

La descomposición de Cholesky se usa comúnmente en el método de Montecarlo para simular sistemas con variables múltiples correlacionadas: la matriz de correlaciónentre variables es descompuesta, para obtener la triangular inferior L. Aplicando ésta a un vector de ruidos simulados incorrelacionados, u produce un vector Lu con las propiedades de covarianza del sistema a ser modelado.

Filtro de Kalman

Los filtros de Kalman usan frecuentemente la descomposición de Cholesky para escoger un conjunto de puntos sigma. El filtro de Kalman sigue el estado promedio de un sistema como un vector x de longitud n y covarianza dada por una matriz P de tamaño nxn. La matriz P es siempre semidefinida positiva y puede descomponerse como LL^T. Las columnas de L puede ser adicionadas y restadas de la media x para formar un conjunto de 2N vectores llamados los puntos sigma. Estos puntos sigma capturan la media y la covarianza del estado del sistema.

Factorización de Cholesky

Una matriz A simétrica y positiva definida puede ser factorizada de manera eficiente por medio de una matrz triangular infereior y una matriz triangular superior. 
Para una matriz no singular la descomposición LU nos lleva a considerar una descomposición de tal tipo A = LU; dadas las condiciones de A, simétrica y definida positiva, no es necesario hacer pivoteo, por lo que ésta factorización se hace eficientemente y en un número de operaciones la mitad de LU tomando la forma  , donde L (la cual podemos "verla" como la raíz cuadrada de A) es una matriz triangular inferior donde los elementos de la diagonal son positivos.

Para resolver un sistema lineal Ax = b con A simétrica definida positiva y dada su factorizaciòn de Cholesky , primero debemos resolver Ly = b y entonces resolver  para lograr x.

Una variante de la factorización de Cholesky es de la forma  , donde R es una matriz triangular superior, en algunas aplicaciones se desea ver la matriz en esa forma y no de otra.

Para encontrar la factorización  , bastaría ver la forma de L y observar las ecuaciones que el producto derecho nos conduce al igualar elementos:

así obtendríamos que:

a11 = l112
a21 = l21l11
a22=l212 + l222
a32=l31l21+l32l22		l32=(a32-l31l21)/l22, etc.

y de manera general, para  y :

Ahora bien, ya que A es simétrica y definida positiva, podemos asegurar que los elementos sobre la diagonal de L son positivos y los restantes elementos reales desde luego.

Una de las aplicaciones de la factorización de Cholesky es resolver las ecuaciones normales de un problema de cuadrados mínimos, esas ecuaciones son:  , en la que  es simétrica y definida positiva.