Projektionsmetoder til løsning af SLAE

Projektionsmetoder til løsning af SLAE er en klasse af iterative metoder, hvor problemet med at projicere en ukendt vektor på et bestemt rum løses optimalt i forhold til et andet rum.

Udtalelse af problemet

Lad os betragte SLAE hvor er en kvadratisk matrix af dimension Lad og være todimensionelle underrum af rummet Det er nødvendigt at finde en sådan vektor , der dvs. betingelse var opfyldt: $Ax=b,$ $EN$ $n.$ $K$ $L$ $m$ $R^{n}.$ $\tilde{x} \i K$ $bA\tilde{x} \perp L,$

$\forall l\in L: (A\tilde{x} ,l)=(b,l),$

kaldet Petrov-Galyorkin tilstand.

Hvis den oprindelige tilnærmelse er kendt , skal løsningen projiceres på et affint rum . Lad os repræsentere og betegne uoverensstemmelsen i den indledende tilnærmelse som $x_{0}$ $x_{0}+K.$ $\tilde{x} =x_0+ \delta$ $r_{0}=b-Ax_{0}.$

$bA{\tilde {x}}=bA(x_{0}+\delta )=b-Ax_{0}-A\delta =(b-Ax_{0})-A\delta =r_{0 }-A\delta .$

Derefter kan problemformuleringen formuleres således: Det er nødvendigt at finde sådan , at dvs. betingelse var opfyldt: $\delta\i K,$ $r_0 -A \delta \perp L ,$

${\tilde {x}}=x_{0}+\delta ,\ \delta \in K$

$\forall l\in L:(r_0-A \delta ,l)=0$

Generel tilgang til konstruktion af projektionsmetoder

Lad os introducere matrixbaser i mellemrummene og $K$ $L:$

$V=[v_{1},v_{2},...,v_{m}]$ - størrelsesmatrix sammensat af space basis kolonnevektorer - størrelsesmatrix sammensat af space basis kolonnevektorer $n \ gange m$ $K.$ $W=[w_{1},w_{2},...,w_{m}]$ $n \ gange m$ $L.$

Så kan løsningsvektoren også skrives: $\delta\ = Vy$ $\tilde{x}$

$\tilde{x} = x_0 + Vy,$

hvor er vektoren af koefficienter. ${\displaystyle y\in R^{m))$

Så kan udtrykket omskrives som: $(r_0-A \delta\,l)=0$

$W^T (r_0-A \delta\ )= \bar{0},$

hvorfra og ${\displaystyle W^{T}AVy=W^{T}r_{0))$

$y=(W^{T}AV)^{-1}W^{T}r_{0},$

Derfor skal opløsningen raffineres i overensstemmelse med formlen:

$x_{1}=x_{0}+V(W^{T}AV)^{-1}W^{T}r_{0},$

Generel visning af enhver projektionsklassemetode:

Gør det indtil en løsning er fundet.

Vælg et par underrum og $K$ $L.$
Konstruktion for og baser og $K$ $L$ $V=[v_{1},v_{2},...,v_{m}]$ $W=[w_{1},w_{2},...,w_{m}].$
$r_{0}=b-Ax_{0}.$
$y=(W^{T}AV)^{-1}W^{T}r_{0}.$
$x_{1}=x_{0}+Vy.$

Valget af rum og metoden til at konstruere baser for dem bestemmer fuldstændigt metodens beregningsskema. $K$ $L$

Valg af underrum K og L

Tilfældet med endimensionelle underrum K og L

I det tilfælde, hvor mellemrummene og er endimensionelle, er deres matrixbaser vektorer: og og udtrykket kan omskrives som $K$ $L$ $V=[v]$ $W=[w]$ $\tilde{x} = x_0 + Vy,$

$x_{k+1} = x_k + \gamma_k\ v_k,$

hvor er en ukendt koefficient , som let findes ud fra ortogonalitetsbetingelsen $\gamma_k\$ $r_k - A( \gamma_k\ v_k ) \perp w_k :$

$(r_k - \gamma_k\ Av_k,w_k) =(r_k, w_k) - \gamma_k\ (Av_k,w_k)= \bar{0},$

hvor $\gamma_k\ = \frac {(r_k, w_k)}{(Av_k,w_k)}.$

Metoder med valg af endimensionelle underrum og : $K$ $L$

Stejleste nedstigningsmetode
Hurtigste metode til restreduktion
Gauss-Seidel metode
ABS klasse metoder

I praktiske problemer, metoder, der bruger endimensionelle rum og har ret langsom konvergens. $K$ $L$

Krylovsky type metoder

Krylov-typemetoder (eller Krylov-underrumsmetoder ) er metoder, hvor Krylov-underrummet er valgt som et underrum: $K$

${\mathcal {K}}_{m}(r_{0},A)=span\{r_{0},Ar_{0},A^{2}r_{0},..., A^{m-1}r_{0}\},$

hvor er uoverensstemmelsen i den oprindelige tilnærmelse. Forskellige versioner af Krylovs underrumsmetoder er betinget af valget af underrummet $r_{0}=b-Ax_{0}$ $L.$

Fra tilnærmelsesteoriens synspunkt har tilnærmelserne opnået i Krylov-underrumsmetoderne formen $\tilde{x},$

$A^{-1}b\approx {\tilde {x}}=x_{0}+q_{m-1}(A)r_{0},$

hvor er et gradspolynomium Hvis vi sætter , så ${\displaystyle q_{m-1))$ $m-1.$ $x_{0}=0,$

$A^{-1}b\approx q_{m-1}(A)b.$

Det er med andre ord omtrentligt $A^{-1}b$ $q_{m-1}(A)b.$

Selvom valget af underrum ikke påvirker typen af polynomietilnærmelse, har det en væsentlig indflydelse på metodens effektivitet. Til dato er der 2 måder at vælge et underrum på, der giver de mest effektive resultater: $L$ $L,$

$L=K$ og $L=AK$
$L={\mathcal {K}}_{m}({\tilde {r}}_{0},A^{T})$

L=K

L=AK

Sætning .
Hvis matricen A er symmetrisk og positiv bestemt, så svarer problemet med at designe en SLAEpå et hvilket som helst underrumortogonalt til underrummettil problemet med at minimere det funktionelle

akse=b

K

L=K

$\Phi_1(x) = \parallel x- \tilde{x} \parallel_A^2,$

hvor $\parallel x \parallel_A^2 = (Ax,x).$

Bevis

I kraft af den positive bestemthed af matrixen når den funktionelle sit minimum ved og er strengt konveks. Hvori $EN$ $\Phi _{1}(x)$ $x= \tilde{x}$

\Phi_1(x)=(A(x- \tilde{x}),x- \tilde{x})= (Ax,x)-(A \tilde{x},x)-(Ax, \tilde{ x})+(A \tilde{x},\tilde{x})=

=(Ax,x)-(Ax,\tilde{x})-(b,x)+(b,\tilde{x})= x^TAx-\tilde{x}^TAx-b^Tx+b ^T\tilde{x}.

På grund af symmetrien af matrixen er det sandt, og det funktionelle er lig med $EN$ ${\tilde {x}}^{T}Ax=b^{T}A(A^{-1})x=b^{T}x,$

\Phi_1(x)=x^TAx-2b^Tx+b^T\tilde{x}.

Ved sætningens hypotese er den funktionelle derfor strengt konveks. Det i betingelsen formulerede minimeringsproblem reduceres således til at finde $K=L,$ $V=W.$ $\Phi _{1}(x)$

y=\arg \min _{y}\Phi _{1}(x_{0}+Vy).

Lad os overveje dette problem. På grund af konveksiteten er det tilstrækkeligt at finde et stationært punkt af det funktionelle dvs. løse systemet $\Psi (y)=\Phi _{1}(x_{0}+Vy),$ ${\mathcal {r}}\Psi (y)=0.$

\Psi (y)=(x_{0}+Vy)^{T}A(x_{0}+Vy)-2b^{T}(x_{0}+Vy)+b^{T} {\tilde {x}}=

=(x_{0}^{T}Ab^{T})x_{0}-b^{T}x_{0}+2(x_{0}^{T}Ab^{T}) Vy+y^{T}(V^{T}AV)y+b^{T}{\tilde {x}}=

=y^{T}(V^{T}AV)y-r_{0}^{T}x_{0}-b^{T}x_{0}-2r_{0}^{T} Vy+b^{T}{\tilde {x}}.

Gradienten af denne funktion er at ligne den med nul, får vi ${\mathcal {r}}\Psi _{1}(y)=2V^{T}AVy-2V^{T}r_{0}.$

y=(V^{T}AV)^{-1}V^{T}r_{0},

hvilket er nøjagtigt det samme som udtrykket, hvis vi lægger i det $y=(W^{T}AV)^{-1}W^{T}r_{0},$ $V=W.$

Sætning .
Hvis matricen A er ikke-degenereret, så svarer problemet med at designe en SLAEpå et hvilket som helst underrumortogonalt til underrummettil problemet med at minimere det funktionelle

akse=b

K

L=AK

$\Phi_2(x) = \parallel r_x \parallel_2^2.$

Bevis

Ved at erstatte relationen for baserne i formlen får vi: ${\displaystyle y=(W^{T}AV)^{-1}W^{T}r_{0))$ $W=AV,$

y=(V^{T}A^{T}AV)^{-1}V^{T}A^{T}r_{0}.

Det betyder, at den betragtede situation svarer til valget for det symmetriserede system $L=K$ $A^{T}Ax=A^{T}b.$

I betragtning af forholdet

\parallel x- \tilde{x} \parallel_{A^TA}^2 = (A^TA (x- \tilde{x}),(x- \tilde{x}))_2=(A(x- \tilde{x}),A(x- \tilde{x} ))_2=(r_x,r_x)_2= \parallel r_x \parallel_2^2

og anvender den foregående sætning på et sådant system, får vi den påstand, der er formuleret i betingelsen.

L={\mathcal {K}}_{m}({\tilde {r}}_{0},A^{T})

For at konstruere hver ny vektor kræver Arnoldi-ortogonaliseringsalgoritmen at finde indre produkter og det samme antal lineære kombinationsoperationer. $v_{k}$ $(k-1)$

Litteratur

Saad Y. Iterative metoder til sparsomme lineære systemer. — 2. udgave. - SIAM Society for Industrial & Applied Mathematics, 2003. - S. 477. -ISBN 0898715342.
Balandin M.Yu., Shurina E.P. Metoder til løsning af højdimensionelle SLAE'er. - Novosibirsk: NSTU, 2000. - S. 70.
Golub J., Van Lone C. Matrix Computing. - Moskva: Mir, 1999.
Ilyin V.P. Ufuldstændige faktoriseringsmetoder til løsning af lineære systemer. - Moskva: Fizmatlit, 1995.

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