Konjugerad gradientmetod (för SLAE-lösning)

Den konjugerade gradientmetoden är en numerisk metod för att lösa system av linjära algebraiska ekvationer , är en iterativ metod av Krylov-typ .

Förklaring av problemet

Låt systemet med linjära ekvationer ges: . Dessutom är systemets matris en verklig matris , som har följande egenskaper: , det vill säga det är en symmetrisk positiv-definitiv matris . Sedan kan processen för att lösa SLAE representeras som en minimering av följande funktionella: $yxa = b$ $A = A^T > 0$

$(Ax,x)-2(b,x)\rightarrow min$

Bakom är den skalära produkten . Genom att minimera denna funktion med hjälp av Krylov-underrymden får vi algoritmen för den konjugerade gradientmetoden. $(\cdot, \cdot)$

Algoritm

Förberedelse inför den iterativa processen

Vi väljer en initial uppskattning $x^0$
$r^0 = b - Ax^0$
$z^0 = r^0$

k

-te iterationen av metoden [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}$

Stoppkriterier

Eftersom den funktion som ska minimeras är kvadratisk måste processen ge ett svar på the iterationen, men när metoden implementeras på en dator finns det ett fel i representationen av reella tal, som ett resultat av vilket fler iterationer kan vara nödvändig. Du kan också utvärdera noggrannheten genom den relativa avvikelsen och stoppa den iterativa processen när avvikelsen blir mindre än ett givet tal. $n$ $\frac{||r^k||}{||b||}$

Algoritm för ett förkonditionerat system

Låt det förkonditionerade systemet ha formen: , då kan algoritmen för metoden för ett sådant system skrivas enligt följande: $SAQx=Sb$

Förberedelse inför den iterativa processen

Vi väljer en initial uppskattning $x^0$
$r^0 = Q(b - SAx^0)$
$z^0 = r^0$
$\widetilde{x}^0 = Qx^0$

k

-th metoden iteration

$\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}$

Efter den iterativa processen

$x^* = Q^{-1} \widetilde{x}^m$ , där är den ungefärliga lösningen för systemet, är det totala antalet iterationer av metoden. $x^{*}$ $m$

Stoppkriterier

I det här fallet kan du använda samma stoppkriterier som för ett konventionellt system, endast med hänsyn tagen till förkonditionering. Till exempel kommer den relativa avvikelsen att beräknas som: , men du kan också använda avvikelsen för det ursprungliga systemet, som beräknas enligt följande: $\frac{||\widetilde{r}^k||}{||Sb||}$ $\frac{||r^k||}{||b||} = \frac{||Q^{-1}\widetilde{r}^k||}{||b||}$

Funktioner och generaliseringar

Liksom alla metoder på Krylov-underrymden kräver den konjugerade gradientmetoden från en matris endast förmågan att multiplicera den med en vektor, vilket leder till möjligheten att använda speciella matrislagringsformat (som sparse) och spara minne för matrislagring.
Metoden används ofta för att lösa finita element SLAE.
Metoden har generaliseringar: metoden för bikonjugerade gradienter , för att arbeta med icke-symmetriska matriser. Och den komplexa konjugerade gradientmetoden, där matrisen kan innehålla komplexa tal, men måste uppfylla villkoret: , det vill säga vara en självadjoint positiv bestämd matris. $A$ $A = A^* > 0$

Anteckningar

↑ Henk A. van der Vorst. Iterativa Krylov-metoder för stora linjära system. - Cambridge University Press, 2003. - 221 sid. — ISBN 9780521818285 .

Metoder för att lösa SLAE
Direkta metoder	Matrismetod Gauss metod Gauss-Jordan-metoden Cramer metod LU-nedbrytning Cholesky nedbrytning Sopa metod
Iterativa metoder	Jacobi metod Gauss-Seidel-metoden Iterationsmetod Avslappningsmetod Konjugerad gradientmetod Bikonjugerad gradientmetod Stabiliserad bikonjugatgradientmetod
Allmän	invers matris Projektionsmetoder för att lösa SLAE Förkonditionering