Konjugeret gradientmetode (til SLAE-opløsning)

Den konjugerede gradientmetode er en numerisk metode til løsning af systemer af lineære algebraiske ligninger , er en iterativ metode af Krylov-typen .

Udtalelse af problemet

Lad systemet af lineære ligninger være givet :. Desuden er systemets matrix en reel matrix , som har følgende egenskaber: , det vil sige, det er en symmetrisk positiv-bestemt matrix . Så kan processen med at løse SLAE repræsenteres som en minimering af følgende funktionelle: $økse = b$ $A = A^T > 0$

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

Bagved er det skalære produkt . Ved at minimere denne funktionalitet ved hjælp af Krylov-underrummene opnår vi algoritmen for den konjugerede gradientmetode. $(\cdot, \cdot)$

Algoritme

Forberedelse før den iterative proces

Vi vælger en indledende tilnærmelse $x^0$
$r^0 = b - Ax^0$
$z^0 = r^0$

k

-te iteration af 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}$

Stopkriterier

Da den funktionelle, der skal minimeres, er kvadratisk, skal processen give et svar på the iteration, men når metoden implementeres på en computer , er der en fejl i repræsentationen af reelle tal, som et resultat af, at flere iterationer kan være påkrævet. Du kan også evaluere nøjagtigheden ud fra den relative uoverensstemmelse og stoppe den iterative proces, når uoverensstemmelsen bliver mindre end et givet tal. $n$ $\frac{||r^k||}{||b||}$

Algoritme for et forudkonditioneret system

Lad det prækonditionerede system have formen: , så kan algoritmen for metoden for et sådant system skrives som følger: $SAQx=Sb$

Forberedelse før den iterative proces

Vi vælger en indledende tilnærmelse $x^0$
$r^0 = Q(b - SAx^0)$
$z^0 = r^0$
$\widetilde{x}^0 = Qx^0$

k

-th metode 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 iterative proces

$x^* = Q^{-1} \widetilde{x}^m$ , hvor er systemets omtrentlige løsning, er det samlede antal iterationer af metoden. $x^{*}$ $m$

Stopkriterier

I dette tilfælde kan du bruge de samme stopkriterier som for et konventionelt system, kun med forkonditionering taget i betragtning. For eksempel vil den relative afvigelse blive beregnet som: , men du kan også bruge afvigelsen fra det oprindelige system, som beregnes som følger: $\frac{||\widetilde{r}^k||}{||Sb||}$ $\frac{||r^k||}{||b||} = \frac{||Q^{-1}\widetilde{r}^k||}{||b||}$

Funktioner og generaliseringer

Som alle metoder på Krylov-underrum kræver den konjugerede gradientmetode fra en matrix kun evnen til at gange den med en vektor, hvilket fører til muligheden for at bruge specielle matrixlagerformater (såsom sparse) og gemme hukommelse til matrixlagring.
Metoden bruges ofte til at løse finite element SLAE'er.
Metoden har generaliseringer: metoden med bikonjugerede gradienter , til at arbejde med ikke-symmetriske matricer. Og den komplekse konjugerede gradientmetode, hvor matricen kan indeholde komplekse tal, men skal opfylde betingelsen: , altså være en selvadjoint positiv bestemt matrix. $EN$ $A = A^* > 0$

Noter

↑ Henk A. van der Vorst. Iterative Krylov-metoder for stort lineært system. - Cambridge University Press, 2003. - 221 s. — ISBN 9780521818285 .

Metoder til løsning af SLAE
Direkte metoder	Matrix metode Gauss metode Gauss-Jordan metode Cramer metode LU nedbrydning Kolesky nedbrydning Feje metode
Iterative metoder	Jacobi metode Gauss-Seidel metode Iterationsmetode Afslapningsmetode Konjugeret gradientmetode Bikonjugeret gradientmetode Stabiliseret bikonjugat gradientmetode
Generel	omvendt matrix Projektionsmetoder til løsning af SLAE Forkonditionering