Main Content

Factorizaciones

Introducción

Las tres factorizaciones de matrices que se analizan en esta sección utilizan matrices triangulares, donde todos los elementos ubicados por encima o por debajo de la diagonal son cero. Los sistemas de ecuaciones lineales que incluyen matrices triangulares se resuelven fácil y rápidamente a través de la sustitución hacia adelante o hacia atrás.

Factorización de Cholesky

La factorización de Cholesky expresa una matriz simétrica como el producto de una matriz triangular y su matriz traspuesta.

A = RR,

donde R es una matriz triangular superior.

No todas las matrices simétricas se pueden factorizar de esta manera. Las matrices que tienen dicha factorización se califican como definidas positivas. Esto implica que todos los elementos diagonales de A son positivos y que los elementos fuera de la diagonal “no son demasiado grandes”. Las matrices de Pascal proporcionan un ejemplo interesante. A lo largo de este capítulo, la matriz de ejemplo A ha sido la matriz de Pascal de 3 por 3. Por un momento, considere la matriz de 6 por 6:

A = pascal(6)

A =
       1     1     1     1     1     1
       1     2     3     4     5     6
       1     3     6    10    15    21
       1     4    10    20    35    56
       1     5    15    35    70   126
       1     6    21    56   126   252

Los elementos de A son coeficientes binomiales. Cada elemento es la suma de sus vecinos del norte y el oeste. La factorización de Cholesky es la siguiente:

R = chol(A)

R =
     1     1     1     1     1     1
     0     1     2     3     4     5
     0     0     1     3     6    10
     0     0     0     1     4    10
     0     0     0     0     1     5
     0     0     0     0     0     1

Los elementos son, nuevamente, coeficientes binomiales. El hecho de que R'*R es igual a A demuestra una identidad que incluye las sumas de productos de coeficientes binomiales.

Nota

La factorización de Cholesky también se aplica a matrices complejas. Cualquier matriz compleja que tiene una factorización de Cholesky satisface la condición

A′ = A

y se califica como definida positiva hermítica.

La factorización de Cholesky permite que el sistema lineal

Ax = b

sea reemplazado por

RRx = b.

Debido a que el operador barra invertida reconoce sistemas triangulares, este sistema puede resolverse fácilmente en el entorno de MATLAB® con la siguiente operación:

x = R\(R'\b)

Si A es n por n, la complejidad computacional de chol(A) es O(n3), pero la complejidad de las soluciones de barra invertida subsiguientes es solo O(n2).

Factorización LU

La factorización LU, o eliminación gaussiana, expresa cualquier matriz cuadrada A como el producto de una permutación de una matriz triangular inferior y una matriz triangular superior:

A = LU,

donde L es una permutación de una matriz triangular inferior con unos en su diagonal y U es una matriz triangular superior.

Las permutaciones son necesarias por motivos tanto teóricos como computacionales. La matriz

[0110]

no se puede expresar como el producto de matrices triangulares sin intercambiar sus dos filas. Aunque la matriz

[ε110]

se puede expresar como el producto de matrices triangulares, cuando ε es pequeño, los elementos de los factores son grandes y amplían los errores. Por lo tanto, aunque las permutaciones no son estrictamente necesarias, resultan convenientes. El pivoteo parcial asegura que los elementos de L están acotados por uno en magnitud y que los elementos de U no son mucho más grandes que los de A.

Por ejemplo:

[L,U] = lu(B)

L =
    1.0000         0         0
    0.3750    0.5441    1.0000
    0.5000    1.0000         0

U =
    8.0000    1.0000    6.0000
         0    8.5000   -1.0000
         0         0    5.2941

La factorización LU de A permite que el sistema lineal

A*x = b

se resuelva rápidamente de la siguiente manera:

x = U\(L\b)

Los determinantes y las inversas se calculan a partir de la factorización LU con la fórmula

det(A) = det(L)*det(U)

e

inv(A) = inv(U)*inv(L)

También es posible calcular los determinantes con det(A) = prod(diag(U)), aunque los signos de los determinantes podrían invertirse.

Factorización QR

Una matriz ortogonal, o matriz con columnas ortogonales, es una matriz real cuyas columnas tienen longitud uno y son perpendiculares entre sí. Si Q es ortogonal, entonces

QTQ = I,

donde I es la matriz de identidad.

Las matrices ortogonales más simples son las rotaciones de coordenadas bidimensionales:

[cos(θ)sin(θ)sin(θ)cos(θ)].

En el caso de las matrices complejas, el término correspondiente es unitaria. Las matrices ortogonales y unitarias son convenientes para el cálculo numérico porque mantienen la longitud, conservan los ángulos y no amplían los errores.

La factorización ortogonal, o QR, expresa cualquier matriz rectangular como el producto de una matriz ortogonal o unitaria y una matriz triangular superior. También podría incluir una permutación de columnas:

A = QR

o

AP = QR,

donde Q es ortogonal o unitaria, R es triangular superior y P es una permutación.

Existen cuatro variantes de la factorización QR: de tamaño total o parcial, y con permutación de columnas o sin ella.

Los sistemas lineales sobredeterminados incluyen una matriz rectangular con más filas que columnas, es decir, m por n con m > n. La factorización QR de tamaño total produce una matriz cuadrada ortogonal Q de m por m y una matriz rectangular triangular superior R de m por n:

C=gallery('uniformdata',[5 4], 0);
[Q,R] = qr(C)

Q =

    0.6191    0.1406   -0.1899   -0.5058    0.5522
    0.1506    0.4084    0.5034    0.5974    0.4475
    0.3954   -0.5564    0.6869   -0.1478   -0.2008
    0.3167    0.6676    0.1351   -0.1729   -0.6370
    0.5808   -0.2410   -0.4695    0.5792   -0.2207


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648
         0         0         0         0

En muchos casos, las últimas m – n columnas de Q no son necesarias, ya que se multiplican por los ceros de la parte inferior de R. Por lo tanto, la factorización QR de tamaño parcial produce una matriz rectangular Q de m por n con columnas ortonormales y una matriz cuadrada triangular superior R de n por n. Para el ejemplo de 5 por 4, el ahorro no es tan significativo, pero para matrices más grandes y altamente rectangulares, el ahorro tanto de tiempo como de memoria puede ser bastante importante:

[Q,R] = qr(C,0)	
Q =

    0.6191    0.1406   -0.1899   -0.5058
    0.1506    0.4084    0.5034    0.5974
    0.3954   -0.5564    0.6869   -0.1478
    0.3167    0.6676    0.1351   -0.1729
    0.5808   -0.2410   -0.4695    0.5792


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648

En contraste con la factorización LU, la factorización QR no requiere pivoteo ni permutaciones. Sin embargo, es de utilidad una permutación de columnas opcional, activada por la presencia de un tercer argumento de salida, para poder detectar singularidad o deficiencia de rango. En cada paso de la factorización, se usa como base la columna con la norma más grande de la matriz restante sin factorizar. Esto asegura que los elementos diagonales de R aparezcan en orden descendente y que cualquier dependencia lineal entre las columnas se pueda revelar, casi con toda certeza, al observar estos elementos. Para el pequeño ejemplo que se muestra aquí, la segunda columna de C tiene una norma más grande que la primera, por lo que las dos columnas se intercambian:

[Q,R,P] = qr(C)

Q =
   -0.3522    0.8398   -0.4131
   -0.7044   -0.5285   -0.4739
   -0.6163    0.1241    0.7777

R =
  -11.3578   -8.2762
         0    7.2460
         0         0

P =
     0     1
     1     0

Cuando se combinan el tamaño parcial y las permutaciones de columna, el tercer argumento de salida es un vector de permutación, y no una matriz de permutación:

[Q,R,p] = qr(C,0)

Q =
   -0.3522    0.8398
   -0.7044   -0.5285
   -0.6163    0.1241

R =
  -11.3578   -8.2762
         0    7.2460


p =
     2     1

La factorización QR transforma un sistema lineal sobredeterminado en un sistema triangular equivalente. La expresión

norm(A*x - b)

es igual a

norm(Q*R*x - b)

La multiplicación por matrices ortogonales conserva la norma euclidiana, de manera que esta expresión también es igual a

norm(R*x - y)

donde y = Q'*b. Dado que las últimas filas m-n de R son cero, esta expresión se divide en dos partes:

norm(R(1:n,1:n)*x - y(1:n))

y

norm(y(n+1:m))

Cuando A tiene rango completo, es posible despejar la x de manera que la primera de estas expresiones sea igual a cero. Entonces, la segunda expresión devuelve la norma del residuo. Cuando A no tiene rango completo, la estructura triangular de R permite hallar una solución básica para el problema de mínimos cuadrados.

Uso de multiprocesos para factorización

El software de MATLAB admite multiprocesos computacionales para varias funciones de álgebra lineal y funciones numéricas que actúan elemento por elemento. Estas funciones se ejecutan automáticamente en varios procesos. Para que una función o expresión se ejecute más rápido en varias CPU, se deben cumplir una serie de condiciones:

  1. La función debe realizar operaciones que se dividan fácilmente en secciones ejecutadas de manera simultánea. Estas secciones se deben poder ejecutar con poca comunicación entre los procesos. Además, estas deben requerir pocas operaciones secuenciales.

  2. El tamaño de los datos debe ser lo suficientemente grande para que cualquier ventaja propia de la ejecución simultánea justifique el tiempo que se requiere para dividir los datos y administrar procesos de ejecución separados. Por ejemplo, la mayoría de las funciones se acelera solo cuando el arreglo contiene varios miles de elementos o más.

  3. La operación no debe estar limitada por la memoria; el tiempo de procesamiento no debe estar dominado por el tiempo de acceso de la memoria. Como regla general, las funciones complicadas se aceleran más que las funciones simples.

Las funciones lu y qr muestran un importante incremento de la velocidad en arreglos de precisión doble de gran tamaño (del orden de diez mil elementos).

Consulte también

| |

Temas relacionados