Navegación

Clase 6: Iteración simultánea y algoritmo de QR

Bibliografía de la Clase:

  • Numerical Linear Algebra.L.N. Trefethen. Chapter 5: Lecture 28 QR Algorithm without Shifts
  • Guía profesor Luis Salinas

Iteración Simultánea

El método de iteración de potencia (visto en la clase Clase 2) sólo permite encontrar un valor propio de la matriz \mathbf{A}.

El método de iteración simultánea (o método de iteración de potencia por bloques) extiende el método de iteración de potencia para poder encontrar los n vectores propios (\mathbf{v_1,\dots,v_n}) asociados a los n valores propios de mayor valor absoluto (\lambda_1,\dots,\lambda_n). La idea consiste en aplicar el método de iteración de potencia a varios vectores a la vez.

Inicialmente ahora se cuenta con un set de n vectores linealmente independientes {\mathbf{v}_1^{(0)},\dots,\mathbf{v}_n^{(0)}}.

Si los agrupamos matricialmente se tiene:

\mathbf{V^{(0)}} = \left[ \begin{array}{c|c|c} \, & \, & \, \\ \mathbf{v}_1^{(0)} & \cdots & \mathbf{v}_n^{(0)} \\ \, & \, & \, \end{array} \right]

Al ir multiplicando sucesivamente por \mathbf{A} se tiene que en la iteración k usando el método de iteración de potencia se tendrá:

\mathbf{V}^{(k)} = \mathbf{A^k V^{(0)}} = \left[ \begin{array}{c|c|c} \, & \, & \, \\ \mathbf{v}_1^{(k)} & \cdots & \mathbf{v}_n^{(k)} \\ \, & \, & \, \end{array} \right]

Si expandimos los vectores \mathbf{v}_j^{(0)} y \mathbf{v}_j^{(k)} en los valores propios de \mathbf{A} se tiene:

\mathbf{v}_j^{(0)} = \alpha_{1j} \mathbf{q}_1 + \dots + \alpha_mj \mathbf{q}_m \\ \mathbf{v}_j^{(j)} = \lambda_1^k \alpha_{1j} \mathbf{q}_1 + \dots + \lambda_m^k \alpha_mj \mathbf{q}_m \\

Lo que se espera de este procedimiento es que todas las columnas de \mathbf{V}^{(k)} tiendan a \mathbf{q}_1 (vector propio asociado al valor propio de mayor valor). Para evitar esto, se fuerza a que los vectores {\mathbf{v}_1^{(k)},\dots,\mathbf{v}_n^{(k)}} sean ortonormales en cada iteración (originalmente en el algoritmo de iteración de potencia se normalizaban los vectores encontrados). La ortonormalización se realiza usando la descomposición QR de las matrices \mathbf{V}^{(k)}.

Nota

La matriz \mathbf{A} debe ser real y simétrica.

El algoritmo de la iteración simultánea es el siguiente:

\boxed{ \begin{array}{ll} \text{Elegir vectores base arbitrarios: } {\mathbf{v}_1^{(0)},\dots,\mathbf{v}_n^{(0)}} \\ \text{Construir: } \mathbf{V}^{(0)} \\ \text{Ortonormalizar la base: } \mathbf{Q}^{(0)} \mathbf{R}^{(0)} = \text{qr}(\mathbf{V}^{(0)}) \\ \textbf{for} \; k=1,2,\dots \\ \quad \mathbf{Z} = \mathbf{A Q^{(k-1)}} \\ \quad \mathbf{Q}^{(k)} \mathbf{R}^{(k)} = \text{qr}(\mathbf{Z}) \end{array} }

Una pequeña modificación del algoritmo corresponde a:

\boxed{ \begin{array}{ll} \mathbf{Q}^{(0)} = \mathbb{I} \\ \textbf{for} \; k=1,2,\dots \\ 1: \quad \mathbf{Z} = \mathbf{A} \underline{\mathbf{Q}}^{(k-1)} \\ 2: \quad \underline{\mathbf{Q}}^{(k)} \mathbf{R}^{(k)} = \text{qr}(\mathbf{Z}) \\ 3: \quad \mathbf{A}^{(k)} = (\underline{\mathbf{Q}}^{(k)})^T \mathbf{A} \underline{\mathbf{Q}}^{(k)}\\ 4: \quad \underline{\mathbf{R}}^{(k)} = \mathbf{R}^{(k)} \dots \mathbf{R}^{(1)} \end{array}}

Los cambios realizados son:

  • Se reemplazó \mathbf{Q}^{(k)} por \underline{\mathbf{Q}}^{(k)} para poder diferenciar las matrices \mathbf{Q} generadas por el algoritmo de iteración simultánea.
  • Se definieron las matrices \mathbf{A}^{(k)} y \underline{\mathbf{R}}^{(k)} (líneas 3 y 4) para poder compararlo posteriormente con el algoritmo de QR.

Condiciones

La convergencia del algoritmo depende de dos condiciones:

  • La matriz \mathbf{A} tiene n vectores propios ortogonales \mathbf{q_1,\dots,q_n} con los correspondientes valores propios |\lambda_1| > \dots > |\lambda_n|
  • Todos los menores principales de \mathbf{\hat{Q}^T} \mathbf{V}^{(0)} son no singulares. Los menores principales corresponden a las submatrices cuadradas izquierdas superiores de dimensiones 1 \times 1, 2 \times 2, etc.

Nota

Notar que la matriz \mathbf{\hat{Q}^T} \mathbf{V}^{(0)} corresponde a los coeficientes \alpha_ij.

Ejercicio propuesto

  • Probar que la matriz \mathbf{\hat{Q}^T} \mathbf{V}^{(0)} corresponde a la matriz de los coeficientes \alpha_ij.

Este método, aunque funciona, no es usado generalmente en la práctica ya que existe un algoritmo que realiza las mismas operaciones de una forma más elegante que el método de iteración simultánea, el algoritmo QR.

Primera versión: Algoritmo QR

El algoritmo QR es usado para poder construir una matriz triangular superior a partir de una matriz \mathbf{A} (Fase 2 vista en la Clase 3). El algoritmo mejora su tasa de convergencia si recibe como entrada una matriz de Hessenberg \mathbf{H}.

El algoritmo QR puede ser utilizado para encontrar la matriz diagonal superior de la descomposición de Schur. De la Clase 3 vimos que si queremos obtener ceros bajo la diagonal usando el siguiente procedimiento:

\mathbf{T} \leftarrow \mathbf{Q^* A Q}

resultaba que al postmultiplicar por la matriz \mathbf{Q} se destruían los ceros formados.

Sin embargo, el procedimiento anterior resulta ser efectivo cuando se realiza iterativamente:

\boxed{ \begin{array}{ll} \mathbf{A}^{(0)} =& \mathbf{A} \\ \textbf{for} \; &k=1,2,\dots \\ 1: \quad & \mathbf{Q}^{(k)} \mathbf{R}^{(k)} = \textbf{qr}(\mathbf{A}^{(k-1)})\\ 2: \quad & \mathbf{A}^{(k)} = \mathbf{R}^{(k)} \mathbf{Q}^{(k)} \\ 3: \quad & \underline{\mathbf{Q}}^{(k)} = \mathbf{Q}^{(1)} \dots \mathbf{Q}^{(k)} \\ 4: \quad & \underline{\mathbf{R}}^{(k)} = \mathbf{R}^{(k)} \dots \mathbf{R}^{(1)} \end{array} }

La idea del algoritmo es ir obteniendo una matriz diagonal superior en dos pasos:

  • Primero se calcula \mathbf{R}^{(k)}= (\mathbf{Q}^{(k)})^T \mathbf{A}^{(k-1)} (línea 1),
  • Y luego se obtiene \mathbf{A}^{(k)} = \mathbf{R}^{(k)} \mathbf{Q}^{(k)} (línea 2) que equivale a \mathbf{A}^{(k)} = (\mathbf{Q}^{(k)})^T \mathbf{A}^{(k-1)} \mathbf{Q}^{(k)}, es decir se está pre y post multiplicando sucesivamente por matrices ortonormales.

Nota

De lo anterior resulta que \mathbf{A}^{(k)} es similar a \mathbf{A}^{(k-1)} y por lo tanto a \mathbf{A}, es decir, todas ellas tienen los mismos valores propios.

Para poder comparar el algoritmo QR con el método de iteración simultánea se han definido dos matrices adicionales que no afectan el algoritmo: \underline{\mathbf{Q}}^{(k)} y \underline{\mathbf{R}}^{(k)} (líneas 3 y 4).

Contenidos

Tema anterior

Clase 5: Método de Iteración Inversa

Próximo tema

Clase 7: Algoritmos de QR iterativos

Esta página

Navegación

© Copyright 2012, CTI-HPC. Creado con Sphinx 1.1.3.