Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Factorizaciones

Introducción

Las tres factorizaciones de matriz discutidas en esta sección hacen uso de matrices, donde todos los elementos, ya sea por encima o por debajo de la diagonal son cero.triangular Los sistemas de ecuaciones lineales que implican matrices triangulares se resuelven fácil y rápidamente usando cualquiera o.forwardback substitution

Factorización Cholesky

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

= ′,ARR

donde hay una matriz triangular superior.R

No todas las matrices simétricas se pueden Factoriza de esta manera; las matrices que tienen tal factorización se dice que son positivos definitivos. Esto implica que todos los elementos diagonales de son positivos y que los elementos fuera de la diagonal son "no demasiado grande."A Las matrices Pascal proporcionan un ejemplo interesante. A lo largo de este capítulo, la matriz de ejemplo ha sido la matriz de Pascal 3 por 3.A Cambie temporalmente al 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 son Coeficientes binomiales.A Cada elemento es la suma de sus vecinos del norte y del oeste. La factorización de Cholesky es

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 de nuevo Coeficientes binomiales. El hecho de que es igual a demuestra una identidad que implica sumas de productos de Coeficientes binomiales.R'*RA

Nota

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

=A′A

y se dice que es.Hermitian positive definite

La factorización Cholesky permite que el sistema lineal

=Axb

para ser reemplazado por

=.RRxb

Dado que el operador de barra diagonal inversa reconoce sistemas triangulares, esto se puede resolver rápidamente en el entorno conMATLAB®

x = R\(R'\b)

Si es-por-, la complejidad computacional de es O (Annchol(A)n3), pero la complejidad de las siguientes soluciones de barra diagonal inversa es solo O (n2).

LU Factorization

La factorización de LU, o la eliminación Gaussiana, expresa cualquier matriz cuadrada como el producto de una permutación de una matriz triangular inferior y una matriz triangular superiorA

= ,ALU

donde se encuentra una permutación de una matriz triangular inferior con unos en su diagonal y es una matriz triangular superior.LU

Las permutaciones son necesarias tanto por razones teóricas como computacionales. La matriz

[0110]

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

[ε110]

puede expresarse como el producto de matrices triangulares, cuando es pequeño, los elementos en los factores son grandes y magnificar errores, por lo que aunque las permutaciones no son estrictamente necesarias, son deseables.ε La pivotante parcial asegura que los elementos de están delimitados por uno en magnitud y que los elementos de no son mucho más grandes que los de.LUA

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 de LU permite que el sistema linealA

A*x = b

para ser resuelto rápidamente con

x = U\(L\b)

Los determinantes y las inversas se calculan a partir de la factorización LU utilizando

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

Y

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

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

La factorización de QR

Una matriz, o una matriz con columnas conjunto ortonormal, es una matriz real cuyas columnas tienen una longitud de unidad y son perpendiculares entre sí.orthogonal Si es ortogonal, entoncesQ

′ = 1.QQ

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

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

Para matrices complejas, el término correspondiente es.unitary Las matrices ortogonales y unitarias son deseables para el cálculo numérico porque preservan la longitud, preservan los ángulos y no magnifican 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. Una permutación de columna también podría estar implicada:

=AQR

O

= ,APQR

donde es ortogonal o unitaria, es triangular superior, y es una permutación.QRP

Hay cuatro variantes de la factorización de QR: tamaño completo o económico, y con o sin permutación de columna.

Los sistemas lineales sobredeterminados implican una matriz rectangular con más filas que columnas, que es-por-con >.mnmn La factorización QR de tamaño completo produce un triángulo cuadrado,-por-ortogonal y rectangular-por-superior:mmQmnR

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 columnas de no son necesarias porque se multiplican por los ceros en la parte inferior de.m – nQR Por lo tanto, la factorización QR de tamaño económico produce una rectangular,-por-con columnas conjunto ortonormal y un triángulo cuadrado-por-superior.mnQnnR Para el ejemplo 5-por-4, esto no es mucho de un ahorro, pero para matrices más grandes, altamente rectangulares, el ahorro en el tiempo y la memoria puede ser muy 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 de LU, la factorización de QR no requiere ninguna pivotante o permutaciones. Pero una permutación de columna opcional, provocada por la presencia de un tercer argumento de salida, es útil para detectar la singularidad o deficiencia de rango. En cada paso de la factorización, la columna de la matriz no factorizada restante con la norma más grande se utiliza como la base para ese paso. Esto garantiza que los elementos diagonales se produzcan en orden decreciente y que cualquier dependencia lineal entre las columnas se revele casi con certeza examinando estos elementos.R Para el pequeño ejemplo dado aquí, la segunda columna de tiene una norma más grande que la primera, por lo que se intercambian las dos columnas:C

[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 las permutaciones de tamaño y columna de la economía, el tercer argumento de salida es un vector de permutación, en lugar de 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)

Iguales

norm(Q*R*x - b)

La multiplicación por matrices ortogonales preserva la norma euclidiana, por lo que esta expresión también es igual a

norm(R*x - y)

Dónde.y = Q'*b Dado que las últimas filas de son cero, esta expresión se divide en dos partes:mnR

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

Y

norm(y(n+1:m))

Cuando tiene rango completo, es posible resolver para que la primera de estas expresiones sea cero.Ax Entonces la segunda expresión da la norma del residuo. Cuando no tiene rango completo, la estructura triangular de hace posible encontrar una solución básica para el problema de mínimos cuadrados.AR

Uso de cálculo multiproceso para factorización

software es compatible con el cálculo multiproceso para un número de álgebra lineal y funciones numéricas de elementos.MATLAB Estas funciones se ejecutan automáticamente en varios subprocesos. Para que una función o expresión se ejecute más rápido en varias CPU, deben ser verdaderas algunas condiciones:

  1. La función realiza operaciones que se particionan fácilmente en secciones que se ejecutan simultáneamente. Estas secciones deben ser capaces de ejecutarse con poca comunicación entre los procesos. Deben requerir pocas operaciones secuenciales.

  2. El tamaño de los datos es lo suficientemente grande como para que las ventajas de la ejecución simultánea superen el tiempo necesario para particionar los datos y administrar subprocesos de ejecución independientes. Por ejemplo, la mayoría de las funciones aceleran solo cuando la matriz contiene varios miles de elementos o más.

  3. La operación no está enlazada a memoria; tiempo de procesamiento no está dominado por el tiempo de acceso de memoria. Como regla general, las funciones complicadas aceleran más que las funciones simples.

y muestran un aumento significativo de la velocidad en matrices de doble precisión (en orden de 10.000 elementos).luqr

Consulte también

| |

Temas relacionados