Title Konvergencija blok Jacobijevih metoda Title (english) Convergence of block Jacobi methods Author Erna Begović Kovač Mentor Vjeran Hari (mentor)Committee member Sanja Singer (predsjednik povjerenstva)Committee member Vjeran Hari (član povjerenstva)Committee member Nela Bosner (član povjerenstva)Granter University of Zagreb Defense date and country 2014-12-17, Croatia Scientific / art field, NATURAL SCIENCES Universal decimal classificationUDC ) 51 - Mathematics Abstract Jacobijeve metode su iterativne metode za računanje spektralne i singularne dekompozicije matrice. Temelje se na transformacijama matrice pomoću dvostranih ravninskih (tzv. Jacobijevih) rotacija koje su birane tako da se izvandijagonalni dio matrice reducira u nekoj mjeri, s ciljem da iterirana matrica postaje sve više dijagonalna. Da bi niz dobivenih matrica konvergirao prema dijagonalnoj matrici, niz izvandijagonalnih normi tih matrica mora konvergirati prema nuli. Teorija perturbacija za dani problem tada daje informaciju koliko dobro dijagonalni elementi iterirane matrice aproksimiraju svojstvene vrijednosti polazne matrice. Isto vrijedi za svojstvene vektore koji su aproksimirani stupcima matrica akumuliranih rotacija. Problem singularne dekompozicije može se interpretirati kao svojstveni problem jer su ova dva problema usko povezana. Blok Jacobijeve metode koriste blok strukturu iterirane matrice što rezultira povećanjem efikasnosti algoritma. U ovom radu proučava se globalna konvergencija blok Jacobijevih metoda, posebno za simetrične i hermitske matrice, te globalna konvergencija opće blok metode Jacobijevog tipa. Blok metode se u specijalnom slučaju svode na obične Jacobijeve metode, po elementima. Disertacija se bavi globalnom konvergencijom blok Jacobijevih metoda za široku klasu cikličkih i kvazi-cikličkih pivotnih strategija. Naglasak je na cikličkim strategijama koje su izvedene iz serijalnih strategija na način da se pivotni indeksi uzimaju redom po stupcima ili retcima, s tim da se unutar svakog stupca, odnosno retka, pivotni indeksi biraju u proizvoljnom poretku. Tako se dobivaju četiri nove klase pivotnih strategija koje se koriste u Jacobijevoj metodi po elementima i po blokovima. Za te strategije dokazuje se konvergencija iterirane matrice prema dijagonalnoj formi. Ove se klase strategija dodatno proširuju korištenjem nekoliko relacija ekvivalencije, a potom se iz njih izvode i posebne kvazi-cikličke strategije. Posebno, dokazano je da su sve cikličke Jacobijeve metode na simetričnim (hermitskim) matricama reda tri i četiri konvergentne. Opisan je novi alat za proučavanje blok metoda Jacobijevog tipa – teorija blok Jacobijevih anihilatora i operatora. Pomoću njih se dokazuju novi rezultati o globalnoj konvergenciji, a pokazuje se i kako se mogu koristiti za proučavanje meto da sličnih Jacobijevoj, ali za druge tip ove matrica i druge matrične probleme.
Abstract (english) 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.
Keywords
globalna konvergencija
Jacobijeva metoda
pivotne strategije
singularne vrijednosti
svojstvene vrijednosti
Keywords (english)
eigenvalues
global convergence
Jacobi method
pivot strategies
singular values
Language croatian URN:NBN urn:nbn:hr:217:243565 Study programme Title: Mathematics Type of resource Text Extent vii, 242 str. File origin Born digital Access conditions Closed access Terms of use Created on 2019-03-07 10:35:59
