| Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW) |
TW 436
Raf Vandebril, Ellen Van Camp, Marc Van Barel, Nicola Mastronardi
On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form
Abstract
In this paper, we will compare the convergence properties of three basic reduction methods. It covers the reduction to tridiagonal, semiseparable and semiseparable plus diagonal form. These reductions are often used as the first step in the computation of the eigenvalues and/or eigenvectors of arbitrary matrices. In this way the calculation of the eigenvalues using, for example, the QR-algorithm reduces in complexity.
First we will investigate the convergence properties of these three reduction algorithms. It will be shown that for the partially reduced matrices at step k of any of these reduction algorithms, the lower right k x k (already reduced) sub-block will have the Lanczos-Ritz values, w.r.t. a certain starting vector. It will also be shown that the reductions to semiseparable and to semiseparable plus diagonal form have an extra convergence behavior: a special type of subspace iteration is performed on the lower right k x k submatrix, which contains these Ritz-values.
Secondly we look in more detail at the behavior of the involved subspace iteration. It will be shown that the reduction method can be intepreted as a nested type of multishift iteration. Theoretical results will be presented, making it possible to predict the convergence behavior of these reduction algorithms.
Finally we illustrate by means of numerical examples, how it is possible to tune the convergence behavior such that it becomes a powerful tool for certain applications.
report.pdf (594K) / mailto: M. Van Barel