Title: On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form
Authors: Vandebril, Raf ×
Van Camp, Ellen
Van Barel, Marc
Mastronardi, Nicola #
Issue Date: Aug-2006
Publisher: Springer
Series Title: Numerische Mathematik vol:104 issue:2 pages:205-239
Abstract: In this paper, we will compare the convergence properties of three basic reduction methods, by placing them in a general framework. 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 interpreted as a nested type of multi-shift iteration. Theoretical results will be presented, making it possible to predict the convergence behavior of these reduction algorithms. Also a theoretical bound on the convergence rate is presented. Finally we illustrate by means of numerical examples, how it is possible to tune the convergence behavior such that it can become a powerful tool for certain applications.
ISSN: 0029-599X
Publication status: published
KU Leuven publication type: IT
Appears in Collections:NUMA, Numerical Analysis and Applied Mathematics Section
× corresponding author
# (joint) last author

Files in This Item:
File Status SizeFormat
Vandebril_VanCamp_VanBarel_Mastronardi_2006.pdf Published 716KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science