Factorizaci N QR
Páginas: 12 (2833 palabras)
Publicado: 18 de mayo de 2015
Factorización QR
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 QR utilizado para el cálculo de los vectores y valores propios de una matriz.
Definición
La descomposición QR de una matriz cuadrada real A es
donde Q esuna matriz ortogonal (QTQ = I ) y R es una matriz triangular superior.
Cálculo de la descomposición QR
Mediante el método de ortogonalización de Gram-Schmidt
Recurriendo al método de ortogonalización de Gram-Schmidt, con las columnas de A como los vectores a procesar.
. Entonces
Naturalmente, utilizamos los ais de A para obtener:
Ahora estas ecuaciones pueden ser escritas en forma matricial deesta manera:
:::::::::
El producto de cada fila con cada columna de las matrices de arriba, nos da la respectiva columna de A con la que comenzamos y, por tanto, dada la matriz A, la hemos factorizado en una matriz ortogonal Q (la matriz de eks), aplicando el proceso de Gram-Schmidt, y la matriz resultante triangular superior es R.
Alternativamente, la matriz puede calcularse de la siguientemanera:
Recordemos que: Entonces, tenemos
Note que y , entonces .
Ejemplo
Si se considera la descomposición de
Se busca la matriz ortogonal tal que
Por lo que calculamos mediante Gram-Schmidt como sigue:
Por lo tanto, tenemos
Mediante el uso de reflexiones de Householder
Una transformación de Householder o reflexión de Householder es una transformación que refleja el espacio con respecto aun plano determinado. Esta propiedad se puede utilizar para realizar la transformación QR de una matriz si tenemos en cuenta que es posible elegir la matriz de Householder de manera que un vector elegido quede con una única componente no nula tras ser transformado (es decir, premultiplicando por la matriz de Householder). Gráficamente, esto significa que es posible reflejar el vector elegidorespecto de un plano de forma que el reflejo quede sobre uno de los ejes de la base cartesiana.
La manera de elegir el plano de reflexión y formar la matriz de Householder asociada es el siguiente:
Sea un vector columna arbitrario m-dimensional tal que |||| = |α|, donde α es un escalar; (si el algoritmo se implementa utilizando aritmética de coma flotante, entonces α debe adoptar el signo contrarioque 1para evitar pérdida de precisión).
Entonces, siendo el vector (1,0,...,0)T, y ||·|| la norma euclídea, se define:
es un vector unitario perpendicular al plano de reflexión elegido. es una matriz de Householder asociada a dicho plano.
Esta propiedad se puede usar para transformar gradualmente los vectores columna de una matriz A de dimensiones m por n en una matriz triangular superior. Enprimer lugar se multiplica A con la matriz de Householder Q1 que obtenemos al elegir como vector la primera columna de la matriz. Esto proporciona una matriz QA con ceros en la primera columna (excepto el elemento de la primera fila).
el procedimiento se puede repetir para A′ (que se obtiene de A eliminando la primera fila y columna), obteniendo así una matriz de Householder Q′2. Hay que tener encuenta que Q′2 es menor que Q1. Para conseguir que esta matriz opere con Q1A en lugar de A′ es necesario expandirla hacia arriba a la izquierda, completando con un uno en la diagonal, o en general:
Tras repetir el proceso veces, donde ,
es una matriz triangular superior. De forma que tomando
es una descomposición QR de la matriz .
Este método tiene una estabilidad numérica mayor que la delmétodo de Gram-Schmidt descrito arriba.
Una pequeña variación de este método se utiliza para obtener matrices semejantes con la forma de Hessenberg, muy útiles en el cálculo de autovalores por acelerar la convergencia del algoritmo QR reduciendo así enormemente su coste computacional.
Ejemplo
Vamos a calcular la descomposición de la matriz
En primer lugar necesitamos encontrar una reflexión...
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 QR utilizado para el cálculo de los vectores y valores propios de una matriz.
Definición
La descomposición QR de una matriz cuadrada real A es
donde Q esuna matriz ortogonal (QTQ = I ) y R es una matriz triangular superior.
Cálculo de la descomposición QR
Mediante el método de ortogonalización de Gram-Schmidt
Recurriendo al método de ortogonalización de Gram-Schmidt, con las columnas de A como los vectores a procesar.
. Entonces
Naturalmente, utilizamos los ais de A para obtener:
Ahora estas ecuaciones pueden ser escritas en forma matricial deesta manera:
:::::::::
El producto de cada fila con cada columna de las matrices de arriba, nos da la respectiva columna de A con la que comenzamos y, por tanto, dada la matriz A, la hemos factorizado en una matriz ortogonal Q (la matriz de eks), aplicando el proceso de Gram-Schmidt, y la matriz resultante triangular superior es R.
Alternativamente, la matriz puede calcularse de la siguientemanera:
Recordemos que: Entonces, tenemos
Note que y , entonces .
Ejemplo
Si se considera la descomposición de
Se busca la matriz ortogonal tal que
Por lo que calculamos mediante Gram-Schmidt como sigue:
Por lo tanto, tenemos
Mediante el uso de reflexiones de Householder
Una transformación de Householder o reflexión de Householder es una transformación que refleja el espacio con respecto aun plano determinado. Esta propiedad se puede utilizar para realizar la transformación QR de una matriz si tenemos en cuenta que es posible elegir la matriz de Householder de manera que un vector elegido quede con una única componente no nula tras ser transformado (es decir, premultiplicando por la matriz de Householder). Gráficamente, esto significa que es posible reflejar el vector elegidorespecto de un plano de forma que el reflejo quede sobre uno de los ejes de la base cartesiana.
La manera de elegir el plano de reflexión y formar la matriz de Householder asociada es el siguiente:
Sea un vector columna arbitrario m-dimensional tal que |||| = |α|, donde α es un escalar; (si el algoritmo se implementa utilizando aritmética de coma flotante, entonces α debe adoptar el signo contrarioque 1para evitar pérdida de precisión).
Entonces, siendo el vector (1,0,...,0)T, y ||·|| la norma euclídea, se define:
es un vector unitario perpendicular al plano de reflexión elegido. es una matriz de Householder asociada a dicho plano.
Esta propiedad se puede usar para transformar gradualmente los vectores columna de una matriz A de dimensiones m por n en una matriz triangular superior. Enprimer lugar se multiplica A con la matriz de Householder Q1 que obtenemos al elegir como vector la primera columna de la matriz. Esto proporciona una matriz QA con ceros en la primera columna (excepto el elemento de la primera fila).
el procedimiento se puede repetir para A′ (que se obtiene de A eliminando la primera fila y columna), obteniendo así una matriz de Householder Q′2. Hay que tener encuenta que Q′2 es menor que Q1. Para conseguir que esta matriz opere con Q1A en lugar de A′ es necesario expandirla hacia arriba a la izquierda, completando con un uno en la diagonal, o en general:
Tras repetir el proceso veces, donde ,
es una matriz triangular superior. De forma que tomando
es una descomposición QR de la matriz .
Este método tiene una estabilidad numérica mayor que la delmétodo de Gram-Schmidt descrito arriba.
Una pequeña variación de este método se utiliza para obtener matrices semejantes con la forma de Hessenberg, muy útiles en el cálculo de autovalores por acelerar la convergencia del algoritmo QR reduciendo así enormemente su coste computacional.
Ejemplo
Vamos a calcular la descomposición de la matriz
En primer lugar necesitamos encontrar una reflexión...
Leer documento completo
Regístrate para leer el documento completo.