Arnoldijev algoritam za nelinearne probleme svojstvenih vrijednosti

master's thesis

• Author: Ivana Šain
• Mentor: Zlatko Drmač (mentor)
• Committee member: Zlatko Drmač (predsjednik povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2014-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovo radu smo proučavali kvadratični svojstveni problem (QEP - Quadratic Eigenvalue Problem). Točnije, zanimalo nas je kako naći skalar $\lambda \in \mathbb{C}$ i vektor $z \in \mathbb{C}^n$ tako da za zadane matrice $M, C$ i $K$, reda $n$ vrijedi $(\lambda^2 M + \lambda C + K)z=0$. U zadnjem poglavlju smo vidjeli neke primjere iz primjene koje rješava ovaj problem. Predložili smo dvije metode za rješavanje ovakvog problema. Prva metoda se svodi na to da nelinearni problem... More lineariziramo, tj. svedemo ga na standardni problem svojstvenih vrijednosti, te novodefinirani problem riješimo Arnoldijevim algoritmom. Ovdje nastaje problem, jer se dimenzija problem linearizacijom udvostručuje pa nam se povećavaju zahtjevi za memorijom prilikom implementacije programa. Arnoldijev algoritam nalazi određen broj svojstvenih vrijednosti i najčešće se koristi kada imamo velike rijetke matrice $S$ . On računa ortgonalnu bazu $Q$ za Krilovljev potprostor zadane dimenzije, te Hessenbergovu matricu $H$ čije svojstvene vrijednosti aproksimiraju svojstvene vrijednosti matrice $S$. Naveli smo teorem koji kaže da rezidual u Arnoldijevom algoritmu ovisi o početnom vektoru, u smislu da je rezidual manji što je početni vektor bliži svojstvenom vektoru tražene svojstvene vrijednosti. Tu činjenicu smo iskoristili kako bi opisali implicitno restartani Arnoldijev algoritam. U tom algoritmu dozvoljavamo više iteracija nego što nam je potrebno. Nakon $k$ iteracija imamo $k$ aproksimacija za svojstvene vrijednosti. Izdvojimo $m$ svojstvenih vrijednosti koje su nam od interesa. Ostale svojstvene vrijednosti koristimo kako bi napravile pomake u matrici $H$, te time prigušili doprinos svojstvenih vrijednosti, koje nam nisu od interesa, u početnom vektoru. Taj postupak smo napravili implicitno, tj. Arnoldijev algoritam ne pokrećemo ponovno od prvog koraka, već od $m$-tog. Razradili smo metode lockinga odnosno zaključavanja svojstvenih vrijednosti koje su nam od interesa a iskonvergirale su ranije, te purginga odnosno izbacivanja svojstvenih vrijednosti koje su iskonvergirale a nisu nam od interesa. Mana metode linearizacije je u tome što se problem udupla, te se izgubi početna struktura problema. Kako bi očuvali tu strukturu moramo raditi direktno sa matricama $M,C$ i $K$. Zbog toga smo opisali SOAR (Second Order Arnoldi Method) metodu. Ta metoda projicira početni QEP velike dimenzije, na QEP puno manje zadane dimenzije koji ima istu strukturu, a lakše je izračunati njegove svojstvene vrijednosti. Vidjeli smo da postoji veza izmedu SOAR-a i Arnoldija. Naime, do deflacije dolazi u istom koraku algoritama. Kako bi razvili algoritam koji koristi istu ideju kao implicitno restartani Arnoldijev algoritam, bilo je potrebno modificirati SOAR metodu. Definirali smo generaliziranu SOAR metodu (GSOAR) te na njoj proveli implicitno restartanje. Problem nastaje kod odabira pomaka. Naime, kvadratični problem ima $2n$ svojstvenih vrijednosti, pa prema tome i $2n$ svojstvenih vektora. To znači da skup svih svojstvenih vektora nije linearno nezavisan. Prema tome, postoje svojstvene vrijednosti koje su možda različite, a imaju iste svojstvene vektore. To znači da nakon $k$ koraka GSOAR algoritma imamo $2k$ aproksimacija za svojstvene vektore. Ako tražimo $m$ svojstvenih vrijednosti imamo $2k-m$ kandidata za pomake. Među tih $2k-m$ kandidata može se desiti da postoje svojstveni vektori koji odgovaraju svojstvenim vektorima nekih od $m$ traženih svojstvenih vrijednosti. Ako te vrijednosti iskoristimo za pomake, izgubit ćemo informaciju o željenoj svojstvenoj vrijednosti. Predložili smo način na koji se taj problem rješava. Na kraju smo dali nekoliko primjera iz primjene i na njima proveli opisane metode. GSOAR se pokazao kao bolji rješavač, jer za mali broj pomaka daje jako dobre rezultate. Kod Arnoldijevog algoritma smo imali primjer u kojem metoda nije konvergirala za prvih 200 restartanja. Less

Abstract (english)

This thesis presents numerical methods for solving quadratic eigenvalue problem (QEP): find scalar $\lambda \in \mathbb{C}$and vector $z \in \mathbb{C}^n$so that, for given matrices $M, C$ and $K$ $(\lambda^2 M + \lambda C + K)z=0$ In last chapter we saw few examples in which we apply this problem. Two methods are presented for solving this problem. First method finds linearization for nonlinear problem. That linearization defines standard eigenvalue problem which is solved... More using Arnoldi algorithm. The problem is that new linearized problem has double dimension. Arnoldi algorithm finds a specifed number of eigenvalues and is used for large, sparse matrices $S$. It computes an orthogonal basis $Q$ for Krylov subspaces $K$ of given dimension, and Hessenberg matrix $H$ which represents projection of $S$ onto $K$. The eigenvalues of $H$ are approximate eigenvalues of $S$. The residual is smaller if the initial vector is closer to eigenspace for wanted eigenvalues. That fact is used to describe implicitly restarted Arnoldi algorithm. That algorithm has more iterations than needed. After $k$ iterations we have $k$ approximations for eigenvalues. We define $m$ wanted eigenvalues. The remaining eigenvalues are used for shifts that define polynomial filter in implicit restart. The algorithm is implicit, which means that Arnoldi iterations start from step $m$ and not from first step. Locking and purging are described. Linearization doubles the dimension of initial problem, and the initial structure of problem is lost. If we want to preserve the structure of the problem, we use matrices $M, C$ and $K$ and project them onto the search subspace, which is the key idea of the SOAR procedure. Because of that, SOAR method is introduced. This method projects initial QEP (of large dimension) onto smaller QEP so we can easier find its eigenvalues. It is shown that there exists a connection between Arnoldi and SOAR procedure, meaning they deflate at same step. If we want to develop idea of implicit restarting as in Arnoldi procedure we need to define generalized SOAR. The problem in restarting is choosing the shifts. Because there are two eigenvalues, that can be different, and have the same eigenvector. After $k$ steps of GSOAR we have $2k$ approximations of eigenvalues. If we need $m$ eigenvalues, than we have $2k-m$ candidates for shifts. It is discussed how to choose the shifts and not use the one with eigenvector for one of the wanted eigenvalues. We used selected numerical examples to illustrate performances of the described methods. GSOAR has good results, even for small number of shifts. There is example for which Arnoldi iterations did not converge in first 200 restarts. Less

• Keywords: kvadratični svojstveni problem; Arnoldijev algoritam; Krilovljev potprostor; metoda linearizacije; Hessenbergova matrica; SOAR (Second Order Arnoldi Method) metoda; generalizirana SOAR metoda
• Keywords (english): quadratic eigenvalue problem; Arnoldi algorithm; Krylov subspaces; linearization method; Hessenberg matrix; Second Order Arnoldi Method; generalized SOAR method
• Language: croatian
• URN:NBN: urn:nbn:hr:217:860637
• 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: 2019-02-08 12:10:00