Análisis de convergencia de una iteración inexacta RQ truncada

Abstract

Este trabajo presenta una iteración inexacta RQ truncada y su análisis de convergencia. El presente algoritmo sirve para encontrar los autovalores (k autovalores, k ≤ n) de una matriz A ϵ C (k, k) que puede ser esparza o densa, está dirigido principalmente para matrices de gran tamaño por ejemplo de orden 200. Parte de la iteración RQ por Givens que es semejante a la QR. Con el fin de evitar el número de cálculos se reduce la matriz a la forma Héssenberg (H) y a esta matriz reducida se le aplica la iteración RQ para producir una sucesión de transformaciones ortogonales hasta llevar a H a una triangular superior, donde los elementos expuestos en su diagonal son los autovalores. Para acelerar la convergencia se elige determinados desplazamientos { uj } y se procede como el anterior. Para matrices de gran tamaño es casi imposible hacer tantas iteraciones y factorizaciones RQ. Para ello después de un número considerable de iteraciones se procede a truncar en un k paso, de tal forma que se siga actualizando la porción principal, aquí surge unas ecuaciones lineales que deben solucionarse, el análisis se centra en encontrar estas soluciones, buscando un método directo apropiado (iteración TRQ), luego se soluciona estas ecuaciones con un método iterativo precondicionado (iteración ITRQ). Finalmente se hace un análisis de su convergencia, llegando a mostrar que la TRQ es cuadrática y es cúbica si la matriz A es hermitiana. Y la iteración ITRQ es lineal.

In this work, present an inexact truncated RQ iteration and its convergence analysis. This iteration can be used to find eigenvalues of a matrix A ϵ C(k, k) (k eigenvalues, k < n) where the matrix A is large sparse or dense, for example the dimension of the matrix is 200 x 200. It begins with RQ Givens algorithm that is similar to the familiar QR algorithm. In order, reduction the calculates the algorithm begins with a complete reduction of A to upper Hessenberg form (H), the RQ iteration in the applied to H to produce a sequence of orthogonal transformations which eventually drives H into an upper triangular form with eigenvalues exposed on the diagonal. To acceleration convergence a set of shifts selected { uj } to acceleration the convergence and again proceeds as above. For large scale matrix is not possible do many iterations RQ. It would be desirable to truncate this update procedure after k . steps to maintain and update only the leading portion of the factorizations occurring in this sequence. Here emerge a set of linear equations that requieres solving. When these equations can be solved accurately by a direct solver, its called Truncated RQ iteration (TRQ) and whether the equations are solved iteratively with some error its called inexact TRQ iteration. We analyze the convergence of an inexact TRQ iteration. We will view to TRQ, the convergence of each eigenvalue is quadratic in general and cubic is A is hermitiana and the convergence rate of the inexact TRQ is at least linear with a small convergence factor.