Bibliografía de la Clase
- Numerical Linear Algebra. L.N. Trefethen. Chapter 1: Lecture 10 Householder Triangularization
- Guía profesor Luis Salinas
Si se recuerda el algoritmo Gram-Schmidt Modificado , en forma matricial se tiene lo siguiente:
(i=1)
Para obtener :
Para obtener :
Para obtener :
(i=2)
Para obtener :
Para obtener :
Idea
Mediante las iteraciones del método de Gram-Schmidt se aplica una sucesión de matrices triangulares superiores por la derecha de la matriz (aunque en la práctica no formamos las matrices ):
y la matriz resultante, tiene columnas ortonormales. El producto es una matriz triangular superior, obteniendo así la factorización QR reducida de A.
Por otro lado, el método de Householder aplica una sucesión de matrices unitarias por la izquierda de A:
y la matriz resultante , es una matriz triangular superior. El producto es también una matriz unitaria, por lo que se obtiene la factorización QR completa de .
Resumen:
Por lo tanto, ambos métodos pueden resumirse de la sgte. manera:
Gram-Schmidt: Ortogonalización triangular
Householder: Triangularización ortogonal.
Este método fue propuesto por Alston Householder en el año 1958, y es una forma ingeniosa de diseñar matrices unitarias , que realicen las siguientes operaciones:
elemento de la matriz, no necesariamente cero.
elemento que se ha modificado recientemente.
En general, opera sobre las filas .
La matriz tiene la siguiente forma:
es la matriz identidad y tiene dimensión .
es el Reflector de Householder y tiene dimensión , y es una matriz unitaria.
tiene dimensión
En la iteración se transforma el vector . El reflector de Householder realiza la siguiente transformación:
Reflexión de Householder:
La fórmula de la reflexión se puede derivar de la siguiente forma:
¡Pero es necesario reflejar! Por lo tanto se debe detener en el punto anterior, sino que avanzar dos veces en la misma dirección:
Ejercicio en Clases
Demostrar, geométricamente, que el reflector de Householder es .
Existen varios reflectores de Householder: como .
El vector puede ser reflejado a , donde es escalar con . Si circunferencia con posibles reflexiones, si 2 posibles reflexiones, correspondientes al hiperplano y .
Matemáticamente, ambas transformaciones son correctas, pero para un dado, se busca estabilidad numérica, para lo cual se escoge la reflexión más lejana a .
Para lograr esto se escoge:
Recordar:
Si :
Recordar:
Si :
Ejemplo
Iteración 1:
.
Iteración 2:
.
Iteración 3:
.
Ejercicio: