Clase 14: Triangularización de Householder¶

Bibliografía de la Clase

Numerical Linear Algebra. L.N. Trefethen. Chapter 1: Lecture 10 Householder Triangularization

Guía profesor Luis Salinas

Gram-Schmidt como Ortogonalización Triangular¶

Si se recuerda el algoritmo Gram-Schmidt Modificado , en forma matricial se tiene lo siguiente:

(i=1)

$\left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ v_1 & v_2 & \cdots & v_n \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] \mathop{ \left[ \begin{array}{c|c|c|c|c} 1/r_{11} & -r_{12}/r_{11} &-r_{13}/r_{11} &\cdots & -r_{1n}/r_{11} \\ 0 & 1 & 0 &\cdots & 0 \\ 0 & 0 &1 & \cdots & 0 \\ \vdots & \vdots & \vdots & & \vdots\\ 0 & 0 & 0 & \cdots & 1 \end{array} \right]}_{R_1}= \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ q_1 & v_2^{(1)} & \cdots & v_n^{(1)} \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right]$

Para obtener $q_1$ :

$\left[ \begin{array}{c} \\ \\ q_1 \\ \\ \\ \end{array} \right]= \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ v_1 & v_2 & \cdots & v_n \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] \left[ \begin{array}{c} \\ \\ r_1 \\ \\ \\ \end{array} \right]= v_1 \frac{1}{r_{11}}$

Para obtener $v_2^{(1)}$ :

$\left[ \begin{array}{c} \\ \\ v_2^{(1)} \\ \\ \\ \end{array} \right]= \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ v_1 & v_2 & \cdots & v_n \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] \left[ \begin{array}{c} \\ \\ r_2 \\ \\ \\ \end{array} \right]= v_1 -\frac{r_{12}}{r_{11}} + v_2 \ 1 + v_3 \ 0 + \ldots= v_2 - r_{12} q_1$

Para obtener $v_3^{(1)}$ :

$\left[ \begin{array}{c} \\ \\ v_3^{(1)} \\ \\ \\ \end{array} \right]= \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ v_1 & v_2 & \cdots & v_n \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] \left[ \begin{array}{c} \\ \\ r_3 \\ \\ \\ \end{array} \right]= v_1 -\frac{r_{13}}{r_{11}} + v_2 \ 0 + v_3 \ 1 + \ldots= v_3 - r_{13} q_1 \ldots$

(i=2)

$\left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ q_1 & v_2^{(2)} & \cdots & v_n^{(2)} \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] \left[ \begin{array}{c|c|c|c|c} 1 & 0 &0 &\cdots & 0 \\ 0 & 1/r_{22} & -r_{23}/r_{22} &\cdots & -r_{2n}/r_{22} \\ 0 & 0 &1 & \cdots & 0 \\ \vdots & \vdots & \vdots & & \vdots\\ 0 & 0 & 0 & \cdots & 1 \end{array} \right]= \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ q_1 & q_2 & \cdots & v_n^{(2)} \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right]$

Para obtener $q_2$ :

$\left[ \begin{array}{c} \\ \\ q_2 \\ \\ \\ \end{array} \right]= \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ v_1 & v_2 & \cdots & v_n \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] \left[ \begin{array}{c} \\ \\ r_1 \\ \\ \\ \end{array} \right]= v_2 \frac{1}{r_{22}}$

Para obtener $v_3^{(2)}$ :

$\left[ \begin{array}{c} \\ \\ v_3^{(2)} \\ \\ \\ \end{array} \right]= \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ v_1 & v_2 & \cdots & v_n \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] \left[ \begin{array}{c} \\ \\ r_2 \\ \\ \\ \end{array} \right]= v_2^{(1)} -\frac{r_{23}}{r_{22}} + v_3^{(1)} \ldots$

Idea

Mediante las iteraciones del método de Gram-Schmidt se aplica una sucesión de matrices triangulares superiores $R_{k}$ por la derecha de la matriz $A$ (aunque en la práctica no formamos las matrices $R_k$ ):

$A R_1 R_2 \ldots R_n =\hat{Q} R_1 R_2 \ldots R_n = \hat{R}^{-1}$

y la matriz resultante, $\hat{Q}$ tiene columnas ortonormales. El producto $\hat{R}^{-1}= R_1 R_2 \ldots R_n$ 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 $Q_k$ por la izquierda de A:

$Q_n \ldots Q_2 Q_1 A = R Q_n \ldots Q_2 Q_1 = Q^{*} Q = Q_1^{*} Q_2^{*} \ldots Q_n^{*}$

y la matriz resultante $R$ , es una matriz triangular superior. El producto $Q^{*}=Q_{1}^{*} Q_{2}^{*} \ldots Q_{n}^{*}$ es también una matriz unitaria, por lo que se obtiene la factorización QR completa de $A$ .

Resumen:

Por lo tanto, ambos métodos pueden resumirse de la sgte. manera:

Gram-Schmidt: Ortogonalización triangular

Householder: Triangularización ortogonal.

Método de Householder:¶

Este método fue propuesto por Alston Householder en el año 1958, y es una forma ingeniosa de diseñar matrices unitarias $Q_k$ , que realicen las siguientes operaciones:

$\mathop{\left[ \begin{array}{c c c} x &x & x \\ x &x & x \\ x &x & x \\ x &x & x \\ x &x & x \\ \end{array} \right]}_{A} \mathop{\longrightarrow}^{Q_1} \mathop{\left[ \begin{array}{c c c} * &* & * \\ 0 &* & * \\ 0 &* & * \\ 0 &* & * \\ 0 &* & * \\ \end{array} \right]}_{Q_1 A} \mathop{\longrightarrow}^{Q_2} \mathop{ \left[ \begin{array}{c c c} x &x & x \\ 0 &* & * \\ 0 &0 & * \\ 0 &0 & * \\ 0 &0 & * \\ \end{array} \right]}_{Q_2 Q_1 A} \mathop{\longrightarrow}^{Q_3} \mathop{\left[ \begin{array}{c c c} x &x & x \\ 0 &x & x \\ 0 &0 & * \\ 0 &0 & 0 \\ 0 &0 & 0 \\ \end{array} \right]}_{Q_3 Q_2 Q_1 A}$

$x \rightarrow$ elemento de la matriz, no necesariamente cero.

$* \rightarrow$ elemento que se ha modificado recientemente.

En general, $Q_k$ opera sobre las filas $k, \ldots , m$ .

Reflectores de Householder¶

La matriz $Q_k$ tiene la siguiente forma:

$Q_k = \begin{bmatrix} I & 0 \\ 0 &F\end{bmatrix}$

$I$ es la matriz identidad y tiene dimensión $(k-1) \times (k-1)$ .

$F$ es el Reflector de Householder y tiene dimensión $(m-k+1) \times (m-k+1)$ , y es una matriz unitaria.

$Q_k$ tiene dimensión $m \times m$

En la iteración $k$ se transforma el vector $x \in \mathbb{C}^{m-k+1}$ . El reflector de Householder realiza la siguiente transformación:

$x \mathop{\longrightarrow}^{F} Fx = \begin{bmatrix} ||x|| \\ 0 \\ \vdots \\ 0 \end{bmatrix} = ||x|| e_1 , \ \ \ \ \ \ e_1= \begin{bmatrix}1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$

Reflexión de Householder:

El reflector $F$ va a reflejar el espacio $\mathbb{C}^{m-k+1}$ (o $\mathbb{R}^{m-k+1}$ , más fácil de “visualizar”) a través del hiperplano $H$ que es ortogonal a $v=||x||e_1 - x$ .
En general un hiperplano se caracteriza por un conjunto de puntos ortogonal a un vector fijo distinto de cero, y en este caso $v$ , corresponde a este vector.

La fórmula de la reflexión se puede derivar de la siguiente forma:

$\text{ Para algún } y \in \mathbb{C}^{m}: Py = \left ( I - \frac{vv^*}{v^*v} \right ) y = y - v \left ( \frac{v^* y}{v^*v} \right ) \rightarrow \text{Proy. de } y \text{ sobre } H$

¡Pero es necesario reflejar! Por lo tanto se debe detener en el punto anterior, sino que avanzar dos veces en la misma dirección:

$Fy= \left ( I - 2 \frac{vv^*}{v^*v} \right ) y = y -2v \left ( \frac{v^* y}{v^*v} \right )$

Ejercicio en Clases

Demostrar, geométricamente, que el reflector de Householder es $F=\left ( I - 2 \frac{vv^*}{v^*v} \right )$ .

¿Cuál es la proyección de $x$ sobre $H$ ?
¿Cuál es la proyección de $x$ sobre $v$ ?
¿Cuál es la reflexión de $x$ sobre $H$ ?

Posibles Reflectores¶

Existen varios reflectores de Householder: $||x||e_1$ como $-||x||e_1$ .

El vector $x$ puede ser reflejado a $z ||x|| e_1$ , donde $z$ es escalar con $|z|=1$ . Si $z \in \mathbb{C} \Rightarrow$ circunferencia con posibles reflexiones, si $z \in \mathbb{R} \Rightarrow$ 2 posibles reflexiones, correspondientes al hiperplano $H^+$ y $H^-$ .

Matemáticamente, ambas transformaciones son correctas, pero para un $x$ dado, se busca estabilidad numérica, para lo cual se escoge la reflexión más lejana a $x$ .

Para lograr esto se escoge:

$z=-sign(x_1), \ \ \ x_1: \text{primer componente de } x v= -sign(x_1)||x|| e_1 - x v = sign(x_1)||x|| e_1 + x \ \ \ \ (sign(x_1) = 1 \text{ si } x_1 = 0)$

Recordar:

Si $x_1 \in \mathbb{R}$ :

$sign(x_1)=\begin{cases} 1, & \mbox{si } x_1 \geq 0\\ -1, & \mbox{si } x_1 < 0\end{cases}$

Recordar:

Si $x_1 \in \mathbb{C}$ :

$sign(x_1)=\frac{x_1}{| x_1 | } x_1=a+ib | x_1| =\sqrt{a^2 + b^2}$

Algoritmo de Householder¶

Ejemplo

Iteración 1:

.

$\mathop{\left[ \begin{array}{c c c} x_1 &* &* \\ x_2 &* &* \\ x_3 &* &* \\ x_4 &* &* \\ x_5 &* &* \\ \end{array} \right]}_{A} \rightarrow x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} \in \mathbb{C}^{5}, \ \ \ e_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \in \mathbb{C}^{5} v_1=sing(x_1) ||x|| e_1 + x \vspace{0.5cm} P=\frac{v_1 v_1^*}{v_1^* v} \vspace{0.5cm} \text{dim}(I) = (k-1) \times (k-1) = 0 \times 0 \text{dim}(F) = (m-k+1) \times (m-k+1) = 5 \times 5 \vspace{1cm} Q_1= F_1= \left[ \begin{array}{c c c c c} F &F &F &F &F \\ F &F &F &F &F \\ F &F &F &F &F \\ F &F &F &F &F \\ F &F &F &F &F \\ \end{array} \right]_{5\times 5} = I-2\frac{v_1 v_1^*}{v_1^* v}$

Iteración 2:

.

$\mathop{\left[ \begin{array}{c c c} R &R &R \\ 0 &x_1 &* \\ 0 &x_2 &* \\ 0 &x_3 &* \\ 0 &x_4 &* \\ \end{array} \right]}_{A} \rightarrow x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} \in \mathbb{C}^{4}, \ \ \ e_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} \in \mathbb{C}^{4} v_2=sing(x_1) ||x|| e_1 + x \vspace{0.5cm} P=\frac{v_2 v_2^*}{v_2^* v_2} \vspace{0.5cm} \text{dim}(I) = (k-1) \times (k-1) = 1 \times 1 \text{dim}(F) = (m-k+1) \times (m-k+1) = 4 \times 4 \vspace{1cm} Q_2= F_2= \left[ \begin{array}{c c c c c} 1 &0 &0 &0 &0 \\ 0 &F &F &F &F \\ 0 &F &F &F &F \\ 0 &F &F &F &F \\ 0 &F &F &F &F \\ \end{array} \right]_{5\times 5} = I-2\frac{v_2 v_2^*}{v_2^* v_2}$

Iteración 3:

.

$\mathop{\left[ \begin{array}{c c c} R &R &R \\ 0 &R &R \\ 0 &0 &x_1 \\ 0 &0 &x_2 \\ 0 &0 &x_3 \\ \end{array} \right]}_{A} \rightarrow x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \in \mathbb{C}^{3}, \ \ \ e_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \in \mathbb{C}^{3} v_3=sing(x_1) ||x|| e_1 + x \vspace{0.5cm} P=\frac{v_3 v_3^*}{v_3^* v_3} \vspace{0.5cm} \text{dim}(I) = (k-1) \times (k-1) = 2 \times 2 \text{dim}(F) = (m-k+1) \times (m-k+1) = 3 \times 3 \vspace{1cm} Q_3= F_3= \left[ \begin{array}{c c c c c} 1 &0 &0 &0 &0 \\ 0 &1 &0 &0 &0 \\ 0 &0 &F &F &F \\ 0 &0 &F &F &F \\ 0 &0 &F &F &F \\ \end{array} \right]_{5\times 5} = I-2\frac{v_3 v_3^*}{v_3^* v_3} \Rightarrow \left[ \begin{array}{c c c} R &R &R \\ 0 &R &R \\ 0 &0 &R \\ 0 &0 &0 \\ 0 &0 &0 \\ \end{array} \right]$

Ejercicio:

Obtener la factorización QR de la matriz $A$ , utilizando la triangularización de Houselder:

$A=\begin{bmatrix} i &-i &2i \\ 1 &-1 &0 \\ -i &i &0 \\ 1 &-1 &-6 \end{bmatrix}$

Contenidos

Tema anterior

Próximo tema

Esta página

Clase 14: Triangularización de Householder¶

Gram-Schmidt como Ortogonalización Triangular¶

Método de Householder:¶

Reflectores de Householder¶

Posibles Reflectores¶

Algoritmo de Householder¶

Navegación

Contenidos

Tema anterior

Próximo tema

Esta página

Búsqueda rápida

Clase 14: Triangularización de Householder¶

Gram-Schmidt como Ortogonalización Triangular¶

Método de Householder:¶

Reflectores de Householder¶

Posibles Reflectores¶

Algoritmo de Householder¶

Navegación