**************************************************************
Clase 3: Reducción de Hessenberg
**************************************************************


.. topic:: Bibliografía de la Clase:

    * Numerical Linear Algebra.L.N. Trefethen. Chapter 5: Lecture 26 ``Reduction of Hessenberg or Tridiagonal Form``
    * Guía profesor Luis Salinas


Matriz de Hessenberg
####################

La matriz de Hessenberg de una matriz `\mathbf{A}` tiene la siguiente forma:

.. math::

        \mathop{\left[ \begin{array}{c c c c c} \times & \times  &
        \times & \times & \times \\ \times & \times  & \times & \times
        & \times \\ \, & \times  & \times & \times & \times \\ \, & \,
        & \times & \times & \times \\ \, & \,  & \, & \times & \times
        \\ \end{array} \right]}_{\mathbf{H}}

Esta matriz se define como:

.. math::

        \mathbf{H} = \mathbf{Q^* A Q}

donde `\mathbf{Q}` es una matriz unitaria y `\mathbf{H}` es la matriz
de Hessenberg.

.. note::

        Recordar que la matriz de Hessenberg se obtiene como un paso
        intermedio para obtener la factorización de Schur que revela
        los valores propios de `\mathbf{A}`.



La estrategia para construir la matriz de Hessenberg `\mathbf{H}`
es introducir ceros bajo la subdiagonal:


.. math::
        \mathop{\left[ \begin{array}{ccccc}
        \times & \times  & \times & \times & \times \\
        \times & \times  & \times & \times & \times  \\
        \times & \times  & \times & \times & \times \\
        \times & \times  & \times & \times & \times \\
        \times & \times  & \times & \times & \times \\
        \end{array} \right]}_{\mathbf{A}}
        \mathop{\xrightarrow{\hspace*{1cm}}}^{\mathbf{Q}_1^* \cdot}
        \mathop{\left[ \begin{array}{c c c c c}
        \times & \times  & \times & \times & \times \\
        \ast & \ast  & \ast & \ast & \ast  \\
        0 & \ast  & \ast & \ast & \ast \\
        0 & \ast  & \ast & \ast & \ast \\
        0 & \ast  & \ast & \ast & \ast \\
        \end{array} \right]}_{\mathbf{Q_1^* A}}
        \mathop{\xrightarrow{\hspace*{1cm}}}^{\cdot \mathbf{Q}_1}
        \mathop{\left[ \begin{array}{c c c c c}
        \times & \diamond  & \diamond & \diamond & \diamond \\
        \ast & \diamond  & \diamond & \diamond & \diamond  \\
        0 & \diamond  & \diamond & \diamond & \diamond \\
        0 & \diamond  & \diamond & \diamond & \diamond \\
        0 & \diamond  & \diamond & \diamond & \diamond \\
        \end{array} \right]}_{\mathbf{Q_1^* A Q_1}}

Se debe encontrar una matriz `\mathbf{Q}_1^*` que cuyo efecto al
multiplicar a la matriz `\mathbf{A}` sea crear ceros bajo la
subdiagonal y que este resultado al premultiplicarse por
`\mathbf{Q}_1` mantenga los ceros creados. Este proceso debe repitirse
`m-2` veces. Finalmente se obtendrá la matriz de Hessenberg como:

.. math::

        \mathbf{Q^*_{m-2} \dots Q^*_2 Q^*_1 A Q_1
        Q_2 \dots Q_{m-2} = Q^* A Q}


Reducción de Householder
########################


La construcción de las matrices `\mathbf{Q}_i, i=1:m-2` está basada en
la idea de los reflectores de Householder (Ver `Clase Householder <http://www.hpc.cl/cc1/clase14-RP.html>`_):


.. math::

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

donde,

 * `\mathbb{I}` es la matriz identidad de dimensión `k \times k`.
 * `\mathbf{F}` es el **Reflector de Householder** de dimensión `(m-k) \times (m-k)`, y es una matriz unitaria.
 * `\mathbf{Q}_k` tiene dimensión `m \times m`

.. note::

        Recuerde que el reflector de Householder `\mathbf{F}` se obtiene como
        `\mathbf{F}=\mathbb{I} - 2 \mathbf{\frac{v v^*}{v^* v}}` y su
        efecto sobre un vector `\mathbf{x}` es `\mathbf{F x = \pm \| x \|
        e_1}`. 

El algoritmo que resume el procedimiento es el siguiente:

.. math::
        \boxed{\begin{array}{ll} 
        \textbf{for} \; &k=1 \; \textbf{to} \; m-2 \\
        \quad & \mathbf{x} = \mathbf{A}_{k+1:m,k} \\
        \quad & \mathbf{v}_k = \text{sign}(x_1) \|x\|_2 \mathbf{e}_1 +
        \mathbf{x} \\
        \quad & \mathbf{v}_k = \frac{\mathbf{v}_k}{\|\mathbf{v}_k\|_2} \\
        \quad & \mathbf{A}_{k+1:m,k:m} = \mathbf{A}_{k+1:m,k:m} - 2
        \mathbf{v}_k(\mathbf{v}_k^* \mathbf{A}_{k+1:m,k:m})\\
        \quad & \mathbf{A}_{1:m,k+1:m} = \mathbf{A}_{1:m,k+1:m} -
        2(\mathbf{A}_{1:m,k+1:m} \mathbf{v}_k) \mathbf{v}_k^*
        \end{array} }

En el algoritmo puede apreciarse que nunca se calculan explícitamente
las matrices `\mathbf{Q}_k` pero éstas pueden ser obtenidas a partir
de los `\mathbf{v}_k`.

Ejercicio en clases
===================

Demostrar gráficamente que `\mathbf{Q^*_{m-2} \dots Q^*_2 Q^*_1 A Q_1
Q_2 \dots Q_{m-2}}` tiene forma tridiagonal.


Ejercicio propuesto
===================

Explique cuál es la relación de las matrices `\mathbf{Q}_k` usadas
para encontrar la matriz de Hessenberg con respecto a las usadas en la
triangularización de Householder. Hint: Leer introducción Lecture 26 y
Lecture 10 del texto guía Numerical Linear Algebra, Trefethen.