Lanczosova i Arnoldijeva metoda

master's thesis

• Title (english): Lanzzo's and Arnold's method
• Author: Dolores Jandrić
• Mentor: Nela Bosner (mentor)
• Committee member: Nela Bosner (predsjednik povjerenstva)
• Committee member: Vedran Čačić (član povjerenstva)
• Committee member: Pavle Pandžić (član povjerenstva)
• Committee member: Matija Bašić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2022-03-03, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom diplomskom radu smo proučavali Lanczosovu i Arnoldijevu metodu koje predstavljaju tehniku za računanje nekoliko najvećih ili najmanjih (ekstremnih) svojstvenih vrijednosti za velike rijetko popunjene (ne)simetrične matrice. U prvom poglavlju smo uveli notaciju i ponovili osnovna svojstva matrice i svojstvenih vektora i njima pridružene svojstvene vrijednosti. U drugom poglavlju detaljno razrađujemo Lanczosovu metodu. Prvo se uvodi pojam Krylovljevog potrpostora, odnosno kako dolazimo do ortonormirane baze, zatim dolazimo do tridijagonalne matrice čije svojstvene vrijednosti aproksimiraju svojstvene vrijednosti naše početne simetrične matrice. Dolazimo do izvoda Lanczosove iteracije, nakon čega opisujemo pogreške i konvergenciju metode. Implementacijom u aritmetici računala uočavamo gubitak ortogonalnosti Lanczosovih vektora zbog čega se daje opis Lanczosa s potpunom ortogonalizacijom koja popravlja gubitak ortogonalnosti. Spominjemo još selektivnu ortogonalizaciju i problem tzv. duhova svojstvenih vektora. Treće poglavlje daje nam uvid u Arnoldijev algoritam koja se temelji na Hessenbergovu dekompoziciju, restartani Arnoldi i nesimetričnu Lanczosovu tridijagonalizaciju. U zadnjem poglavlju, prikazano je nekoliko primjera u kojima primjenjujemo Lanczosov algoritam za simetričnu matricu.

Abstract (english)

This thesis presents the Lanzos and Arnold method, which represents a technique for calculating several largest or smallest (extreme) eigenvalues of large sparse symmetric matrices, or a set of eigenvalues of non-symmetric matrix. In the first chapter, we introduced notation and displayed the basic properties of the matrix, eigenvectors and their associated eigenvalues. In the second chapter, we elaborate on Lanczo’s method. First, we introduce the notion of Krylov’s subspace and how we compute the orthonormal base. That brings us to a tridiagonal matrix whose eigenvalues approximate the eigenvalues of our initial symmetric matrix. The next step includes a derivation of the Lanczos iteration, after which we describe the errors and convergence of the method. When implemented in computer arithmetic we notice a loss of orthogonality of Lanczos vectors, and therefore we describe Lanczos with complete orthogonalization that corrects the loss of orthogonality. We also mention the selective orthogonalization and the problem of the so-called ghost eigenvalue. The third chapter gives us an insight into Arnold’s algorithm based on Hessenberg’s decomposition, restarted Arnoldi, and asymmetric Lanczos tridiagonalization. In the last chapter, we present a few examples in which we apply the Lanczos algorithm for symmetric matrix.

• Keywords: (ne)simetrične matrice; Krylovljevo potrpostor; tridijagonalna matrica; ortogonalnost
• Keywords (english): non-symmetric matrix; Krylov's subspace; tridiagonal matrix; orthogonality
• Language: croatian
• URN:NBN: urn:nbn:hr:217:671041
• Study programme: Title: Applied Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2022-03-28 10:37:14