Arnoldijev algoritam za nelinearne probleme svojstvenih vrijednosti

Šain, Ivana (2014) Arnoldijev algoritam za nelinearne probleme svojstvenih vrijednosti. Diploma thesis, Faculty of Science > Department of Mathematics.

 Preview
PDF
Language: Croatian

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 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.