hrvatski

Iterativne metode za rješavanje linearnih sustava

Ovaj rad bavi se problemom rješavanja linearnog sustava $Ax=b$ pomoću iterativnih metoda, zbog mnogih pogodnosti koje one nude. Iterativne metode pogodne su za rješavanje sustava kod kojih je matrica zadana preko procedure, koja računa njeno djelovanje na vektor, i za rijetko popunjene matrice, kod kojih množenje sa vektorom nije jako skupo. One se sastoje od iteracija, koje u svakom svojem koraku nastoje, na neki način, aproksimaciju rješenja približiti samom rješenju. Budući da se rješenje svakog sustava nalazi u Krylovljevom potprostoru $\mathcal{K}_{n}(A, b)$, većina iterativnih metoda pokušava naći aproksimaciju rješenja u rastućem nizu Krylovljevih potprostora. Nažalost, ne postoji univerzalna metoda koja je jednako djelotvorna za sve sustave. Stoga su konstruirane različite metode, koje rješavaju različite tipove sustava. Od metoda koje aproksimiraju rješenje pomoću Krylovljevih potprostora CG metoda se primjenjuje za hermitske pozitivno definitne matrice, a Orthomin(2) i MINRES za hermitske indefinitne matrice. Za rješavanje nehermitskih sustava stoji nam na raspolaganju veći broj metoda, od kojih svaka ima prednost kod jedne klase sustava, a nedostatak kod druge. Standardna metoda za ovakve sustave je GMRES, ali su se razvile još i metode koje su zadovoljile i mnoga dodatna svojstva, kao što su BCG, QMR, CGS i BICGSTAB. Postoje još metode koje se temelje na CG metodi primijenjenoj na normalni sustav sa matricom $A^{*}A$ ili $AA^{*}$. Kod svih tih metoda, konvergencija najviše ovisi o svojstvima matrice, pri čemu je konvergencija to bolja, što je matrica "bliža" identiteti. Iz tog razloga uvedeno je prekondicioniranje, kod kojeg se cijeli sustav množi sa matricom prekondicioniranja $M^{-1}$, uz nastojanje da matrica prekondicioniranog sustava $M^{-1}A$ bude još "bliža" identiteti. Odabir same matrice prekondicioniranja ovisi o sustavu i iterativnoj metodi koju primjenjujemo. Sve ove metode primjenjuju se na linearne sustave za koje nije važno na koji način su dobivene. Međutim, razvile su se specijalizirane metode, koje rješavaju linearne sustave dobivene iz diskretizacije određenih diferencijalnih jednadžbi. Takve metode su multigrid i metode kompozicije domene. Općenito, kako se sve te iterativne metode izvode na računalu, napravljena je i analiza numeričke stabilnosti metoda. Pokazalo se da mnoga dobra svojstva tih metoda, koja su pokazana da vrijede u egzaktnoj aritmetici, vrijede i u aritmetici konačne preciznosti.

linearni sustav; iterativne metode; Krylovljevi potprostori

nije evidentirano