Convergence of block Jacobi methods

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

 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) eigenvalues, global convergence, Jacobi method, pivot strategies, singular values Hari, Vjeran 2014 242 NATURAL SCIENCES > MathematicsNATURAL SCIENCES > Mathematics > Numerical Mathematics Faculty of Science > Department of Mathematics Iva Prah 28 Apr 2015 07:34 02 Jun 2015 09:08 http://digre.pmf.unizg.hr/id/eprint/3877