Convergence of block Jacobi methods

Begović, Erna (2014) Convergence of block Jacobi methods. Doctoral thesis, Faculty of Science > Department of Mathematics.

[img] PDF
Restricted to Repository staff only
Language: Croatian

Download (1MB) | Request a copy

Abstract

Jacobi methods are iterative methods for computing the spectral and singular decomposition of the matrix. They are based on the matrix transformations using plane (i.e. Jacobi) rotations. These rotations are chosen to reduce the off-diagonal part of the matrix in order to make the iterated matrix more diagonal. To get the convergence of the iterated matrix sequence to the diagonal form, one must establish that the sequence of off-norms converges to zero. Then the perturbation theory for a specific problem gives the bounds on how far diagonal elements of the iterated matrix are from the eigenvalues of the initial matrix. The same is true for the eigenvectors, which are approximated by columns of the accumulated rotation matrices. SVD problem can be interpreted as eigenvalue problem since the two problems are closely related. Block Jacobi methods use the block structure of the iterated matrix in order to gain a more efficient algorithm. In this thesis the global convergence of the block Jacobi methods is studied. The results for the symmetric and Hermitian matrices are given and, using those results, the results for the general Jacobi type process are proven. Special case of the block methods are element-wise methods. Here, the global convergence of the block Jacobi methods defined by a large class of cyclic and quasi-cyclic strategies is studied. The main focus is on the cyclic strategies derived from the serial strategies such that pivot indices are taken by columns (rows), but inside each column (row) pivot indices are chosen in an arbitrary ordering. Four new classes of the pivot strategies are gained this way. Those strategies are used in the Jacobi method, element-wise and block-wise, and the convergence of the iterated matrix to the diagonal form is proven. Moreover, using several equivalence relations on the set of pivot orderings, even bigger classes of strategies are gained. Further on, quasi-cyclic strategies are built from these cyclic ones. In particular, it is proven that the Jacobi method on the symmetric (Hermitian) matrix of order three or four converges using any cyclic pivot ordering. The new tool for studying the block Jacobi-type methods is described – the theory of the block Jacobi annihilators and operators. They play important role in proving the new results on the global convergence. It is also discussed how they can be used in studying general Jacobi-type methods for different types of matrices and matrix problems.

Item Type: Thesis (Doctoral thesis)
Keywords: eigenvalues, global convergence, Jacobi method, pivot strategies, singular values
Supervisor: Hari, Vjeran
Date: 2014
Number of Pages: 242
Subjects: NATURAL SCIENCES > Mathematics
NATURAL SCIENCES > Mathematics > Numerical Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 28 Apr 2015 07:34
Last Modified: 02 Jun 2015 09:08
URI: http://digre.pmf.unizg.hr/id/eprint/3877

Actions (login required)

View Item View Item