Convergence Analysis of an Inexact Truncated RQ Iteration

Abstract

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 \in C(k, k) (k eigenvalues, k \leq 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 {u_j} 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 requires 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 hermitian and the convergence rate of the inexact TRQ is at least linear with a small convergence factor.