haku: @supervisor Eirola, Timo / yhteensä: 16
viite: 6 / 16
| Tekijä: | Perämäki, Allan |
| Työn nimi: | Reaalilineaaristen yhtälöryhmien iteratiiviset menetelmät |
| Iterative methods for real-linear systems of equations | |
| Julkaisutyyppi: | Diplomityö |
| Julkaisuvuosi: | 2009 |
| Sivut: | 84 Kieli: fin |
| Koulu/Laitos/Osasto: | Matematiikan ja systeemianalyysin laitos |
| Oppiaine: | Matematiikka (Mat-1) |
| Valvoja: | Eirola, Timo |
| Ohjaaja: | Huhtanen, Marko |
| Digitoitu julkaisu: | https://aaltodoc.aalto.fi/handle/123456789/97043 |
| OEVS: | Digitoitu arkistokappale on julkaistu Aaltodocissa
|
| Sijainti: | P1 Ark T80 | Arkisto |
| Avainsanat: | real-linear Krylov iteration Galerkin GMRES preconditioning ILU impedance tomography reaalilineaarinen Krylov iteraatio Galerkin GMRES pohjustus ILU impedanssitomografia |
| Tiivistelmä (fin): | Työssä esitellään ratkaisumenetelmiä yhtälöille muotoa Mz + M#z = b, missä M ja M# ovat kompleksisia n x n-matriiseja, b annettu vektori ja z ratkaistava vektori. Tällainen yhtälö voitaisiin ratkaista muuttamalla se ensiksi reaaliseksi 2n x 2n-kokoiseksi lineaariseksi yhtälöksi Ax = f, mutta tässä työssä menetelmät perustuvat alkuperäiseen muotoon. Reaalilineaariset operaattorit ovat kuvauksia z- Mz + M#. Tässä työssä nämä esitetään taulukkomuodossa matriisien tapaan ja niille annetaan lähteen [1] mukainen reaalilineaarinen LU-hajotelma, Householderin muunnos ja QR-hajotelma. Householderin muunnoksen laskenta-algoritmi annetaan numeerista stabiiliutta parantavalla muutoksella. Lähteessä [1] mainitun LU-hajotelman tukialkion singulaarisuuden ongelman ratkaisuksi ehdotetaan uutta menetelmää. Matriisien Krylovin aliavaruudet ja näihin perustuvia lineaaristen yhtälöryhmien iteratiivisia ratkaisumenetelmiä esitellään lähdettä [8] noudatellen. Lähteen [1] mukainen reaalilineaarinen GMRES-menetelmä yhtälölle kz + M#z= b, missä k on kompleksiluku, käydään läpi ja lisäksi tapauksille MT# = (-)M# tuodaan esiin Lanczos-tyyppiseen iterointiin perustuvat menetelmät. Ensiksi mainitussa menetelmässä tarvittavan Householderin muunnoksen tilalle tarjotaan uutena mahdollisuutena käyttää reaalilineaarisia Givens-rotaatioita. Yleisille reaalilineaarisille yhtälöille ei saada GMRESia, mutta joitakin Galerkinin menetelmään perustuvia iteratiivisia menetelmiä kokeillaan mukaanlukien lähteessä [1] mainittu. Matriisien epätäydelliset LU-hajotelmat (ILU) pohjustusmenetelminä yleistetään reaalilineaarisille operaattoreille. Näistä esimerkkeinä annetaan ILU(0)- ja ILUT-menetelmät. Numeerisia kokeita varten diskretoidaan sähköisessä impedanssitomografiassa esiintyvää alpha- yhtälöä vastaava integraaliyhtälö päätyen yhtälöön z + M#z= 1 lähdettä [5] noudattaen. MATLABilla suoritetut laskennat osoittavat reaalilineaariset ratkaisumenetelmät tehokkaammiksi kuin GMRES vastaavalle reaaliselle 2n x 2n-yhtälöryhmälle. Aikaisemmin ei ole suoraan mainittu edellä olevan yhtälö muuttamista C-lineaariseen muotoon (I - M#M)z = 1 - M#1. Matriisin M# ollessa peräisin edellä mainitun integraaliyhtälön diskretoinnista, on numeeristen kokeiden perusteella ratkaisu tästä muodosta suositeltavaa. Lukijalta edellytetään lineaarialgebran alkeiden hallintaa. Liite A sisältää matriisien osalta käytetyt määritelmät. |
| Tiivistelmä (eng): | This thesis presents solution methods for equations of the form Mz + M#z = b, where M and M# are complex n x n-matrices, b a given vector and z the vector to he solved. Such an equation could he solved by first rewriting it as a real 2n x 2n system of linear equations Ax = f, hut the methods in this thesis are based on the original formulation. Real-linear operators are mappings z - Mz + M#z. These can he represented in a table form not unlike matrices and real-linear LU-decomposition, Householder transformation and QR-decomposition are defined following [1]. The Householder transformation is modified to improve numerical stability. A new strategy to avoid the breakdown mentioned in [1] in the real-linear LU-decomposition is suggested. The Krylov subspaces of matrices and some solutions methods based on these are introduced roughly following [8]. The real-linear GMRES method given in [1] for the equation kz + M#z = b where k is a complex number, is reconsidered and additionally methods for the cases MT# = (-) M# based on Lanczos-type iteration is presented. New real-linear Givens rotations provide an alternative to using Householder transformations during computations of the real-linear GMRES. There's no GMRES for real-linear equations of the general form, but some iterative Galerkin methods are tried including the one mentioned in [1]. The incomplete LU-decompositions (ILU) for matrices as preconditioning methods are generalized to real-linear operators. ILU(0) and ILUT methods are given as examples. Following [5], the integral equation corresponding to the alpha-equation arising in electrical impedance tomography is discretized resulting in the equation z + M#z = 1. Computations with MÄTLAB provide evidence of the effectiveness for real-linear methods in comparison to the corresponding real 2n x 2n system with GMRES. Previously, there's no direct mention of transforming to the C-linearized equation (I - M#M#) z = 1 - M#1. When the matrix M# arises from the discretization of the mentioned integral equation numerical experiments suggest that using this formulation is recommended. The thesis is self-contained requiring only the basics of linear algebra. Appendix A contains the required definitions concerning matrices. |
| ED: | 2010-01-21 |
INSSI tietueen numero: 38788
+ lisää koriin
INSSI