Konjugaattigradienttimenetelmä (SLAE-liuokselle)

Konjugaattigradienttimenetelmä on numeerinen menetelmä lineaaristen algebrallisten yhtälöiden ratkaisemiseksi , se on Krylov-tyyppinen iteratiivinen menetelmä .

Ongelman selvitys

Olkoon lineaarinen yhtälöjärjestelmä annettu: . Lisäksi järjestelmän matriisi on reaalimatriisi , jolla on seuraavat ominaisuudet: , eli se on symmetrinen positiivinen-määräinen matriisi . Sitten SLAE:n ratkaisuprosessi voidaan esittää seuraavien toimintojen minimoimisena: $kirves = b$ $A = A^T > 0$

${\näyttötyyli (Ax,x)-2(b,x)\rightarrow min}$

Takana on skalaaritulo . Minimoimalla tämän funktion käyttämällä Krylov-aliavaruuksia , saamme konjugaattigradienttimenetelmän algoritmin. $(\cdot, \cdot)$

Algoritmi

Valmistelu ennen iteratiivista prosessia

Valitsemme alustavan likiarvon $x^0$
$r^0 = b - Ax^0$
$z^0 = r^0$

k

- menetelmän iteraatio [1]

$\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(Az^{k-1}, z^{k-1})}$
$x^k = x^{k-1} + \alpha_k z^{k-1}$
$r^k = r^{k-1} - \alpha_k A z^{k-1}$
$\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$

Pysäytyskriteerit

Koska minimoitava funktio on neliöllinen, prosessin on annettava vastaus th iteraatioon, mutta menetelmää tietokoneella toteutettaessa tapahtuu reaalilukujen esittämisessä virhe, jonka seurauksena iteraatioita voi tulla lisää. vaaditaan. Voit myös arvioida tarkkuuden suhteellisella erolla ja lopettaa iteratiivisen prosessin, kun ero on pienempi kuin annettu luku. $n$ $\frac{||r^k||}{||b||}$

Esiehdotetun järjestelmän algoritmi

Olkoon esiehdotulla järjestelmällä muoto: , niin menetelmän algoritmi tällaiselle järjestelmälle voidaan kirjoittaa seuraavasti: $SAQx=Sb$

Valmistelu ennen iteratiivista prosessia

Valitsemme alustavan likiarvon $x^0$
$r^0 = Q(b - SAx^0)$
$z^0 = r^0$
$\widetilde{x}^0 = Qx^0$

k

-th menetelmä iteraatio

$\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(SAQz^{k-1}, z^{k-1})}$
$\widetilde{x}^k = \widetilde{x}^{k-1} + \alpha_k z^{k-1}$
$r^k = r^{k-1} - \alpha_k SAQ z^{k-1}$
$\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$

Iteratiivisen prosessin jälkeen

$x^* = Q^{-1} \widetilde{x}^m$ , jossa on järjestelmän likimääräinen ratkaisu, on menetelmän iteraatioiden kokonaismäärä. $x^{*}$ $m$

Pysäytyskriteerit

Tässä tapauksessa voit käyttää samoja pysäytyskriteerejä kuin perinteisessä järjestelmässä, vain esikäsittely huomioiden. Suhteellinen poikkeama lasketaan esimerkiksi seuraavasti: Voit kuitenkin käyttää myös alkuperäisen järjestelmän poikkeamaa, joka lasketaan seuraavasti: $\frac{||\widetilde{r}^k||}{||Sb||}$ $\frac{||r^k||}{||b||} = \frac{||Q^{-1}\widetilde{r}^k||}{||b||}$

Ominaisuudet ja yleistykset

Kuten kaikki Krylov-aliavaruuksien menetelmät, konjugaattigradienttimenetelmä matriisista vaatii vain kyvyn kertoa se vektorilla, mikä johtaa kykyyn käyttää erityisiä matriisitallennusmuotoja (kuten harvaa) ja säästää muistia matriisin tallennusta varten.
Menetelmää käytetään usein elementtien SLAE:n ratkaisemiseen.
Menetelmässä on yleistyksiä: bikonjugaattigradienttien menetelmä epäsymmetristen matriisien kanssa työskentelyyn. Ja kompleksikonjugaattigradienttimenetelmä, jossa matriisi voi sisältää kompleksilukuja, mutta sen täytyy täyttää ehto: , eli olla itseadjungoitu positiivinen määrätty matriisi. $A$ $A = A^* > 0$

Muistiinpanot

↑ Henk A. van der Vorst. Iteratiiviset Krylov-menetelmät suurelle lineaariselle järjestelmälle. - Cambridge University Press, 2003. - 221 s. — ISBN 9780521818285 .

Menetelmät SLAE :n ratkaisemiseksi
Suorat menetelmät	Matriisimenetelmä Gaussin menetelmä Gauss-Jordan menetelmä Cramer menetelmä LU:n hajoaminen Cholesky-hajoaminen Lakaisumenetelmä
Iteratiiviset menetelmät	Jacobin menetelmä Gauss-Seidelin menetelmä Iterointimenetelmä Rentoutumismenetelmä Konjugaattigradienttimenetelmä Bikonjugaattigradienttimenetelmä Stabiloitu bikonjugaattigradienttimenetelmä
Kenraali	käänteinen matriisi Projektiomenetelmät SLAE:n ratkaisemiseen Esikäsittely