Projektionsmetoder för att lösa SLAE

Projektionsmetoder för att lösa SLAE är en klass av iterativa metoder där problemet med att projicera en okänd vektor på ett visst utrymme löses optimalt med avseende på något annat utrymme.

Förklaring av problemet

Låt oss betrakta SLAE där är en kvadratisk matris av dimension Låta och vara tvådimensionella delrum av rummet Det är nödvändigt att hitta en sådan vektor som d.v.s. villkoret uppfylldes: $Ax=b,$ $A$ $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),$

kallas Petrov-Galyorkin-tillståndet.

Om den initiala approximationen är känd , måste lösningen projiceras på ett affint utrymme. Låt oss representera och beteckna avvikelsen i den initiala approximationen 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 .$

Då kan problemformuleringen formuleras på följande sätt: Det är nödvändigt att hitta sådana att d.v.s. villkoret uppfylldes: $\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$

Allmänt tillvägagångssätt för konstruktion av projektionsmetoder

Låt oss introducera matrisbaser i utrymmena och $K$ $L:$

$V=[v_{1},v_{2},...,v_{m}]$ - storleksmatris sammansatt av rymdbaskolumnvektorer - storleksmatris sammansatt av rymdbaskolumnvektorer $n \ gånger m$ $K.$ $W=[w_{1},w_{2},...,w_{m}]$ $n \ gånger m$ $L.$

Då kan lösningsvektorn också skrivas: $\delta\ = Vy$ $\tilde{x}$

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

var är vektorn av koefficienter. ${\displaystyle y\in R^{m))$

Då kan uttrycket skrivas om som: $(r_0-A \delta\ ,l)=0$

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

varifrån och ${\displaystyle W^{T}AVy=W^{T}r_{0))$

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

Sålunda bör lösningen förfinas i enlighet med formeln:

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

Allmän översikt över alla projektionsklassmetoder:

Gör det tills en lösning hittas.

Välj ett par underutrymmen och $K$ $L.$
Konstruktion för och baser och $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.$

Valet av utrymmen och metoden för att konstruera baser för dem bestämmer helt beräkningsschemat för metoden. $K$ $L$

Val av delrum K och L

Fallet med endimensionella delrum K och L

I det fall då utrymmena och är endimensionella är deras matrisbaser vektorer: och och uttrycket kan skrivas om som $K$ $L$ $V=[v]$ $W=[w]$ $\tilde{x} = x_0 + Vy,$

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

var är en okänd koefficient, som lätt kan hittas från ortogonalitetsvillkoret $\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},$

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

Metoder med val av endimensionella delrum och : $K$ $L$

Brantaste nedstigningsmetod
Snabbaste metod för restreduktion
Gauss-Seidel-metoden
ABS klass metoder

I praktiska problem, metoder som använder endimensionella rum och har ganska långsam konvergens. $K$ $L$

Krylovsky typ metoder

Metoder av Krylov-typ (eller Krylov-underrymdsmetoder ) är metoder för vilka Krylov-underrymden är vald som ett underrum: $K$

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

var är avvikelsen för den initiala uppskattningen. Olika versioner av Krylovs underrumsmetoder är betingade av valet av underrummet $r_{0}=b-Ax_{0}$ $L.$

Ur approximationsteoris synvinkel har de approximationer som erhålls i Krylov subrymdmetoder formen $\tilde{x},$

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

var är ett gradpolynom Om vi sätter , då ${\displaystyle q_{m-1))$ $m-1.$ $x_{0}=0,$

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

Det är med andra ord ungefärligt $A^{-1}b$ $q_{m-1}(A)b.$

Även om valet av delrum inte påverkar typen av polynomapproximation, har det en betydande inverkan på metodens effektivitet. Hittills finns det två sätt att välja ett underutrymme som ger de mest effektiva resultaten: $L$ $L,$

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

L=K

och

L=AK

Teorem .
Om matrisen A är symmetrisk och positiv bestämd, då är problemet med att designa en SLAEpå vilketmot delrummetekvivalent med problemet med att minimera det funktionella

ax=b

K

L=K

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

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

Bevis

På grund av matrisens positiva bestämdhet når den funktionella sitt minimum vid och är strikt konvex. Vart i $A$ $\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 av matrisens symmetri är det sant och det funktionella är lika med $A$ ${\tilde {x}}^{T}Ax=b^{T}A(A^{-1})x=b^{T}x,$

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

Enligt satsens hypotes är funktionalen därför strikt konvex. Det i villkoret formulerade minimeringsproblemet reduceras alltså till att finna $K=L,$ $V=W.$ $\Phi _{1}(x)$

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

Låt oss överväga detta problem. På grund av konvexiteten räcker det att hitta en stationär punkt hos det funktionella d.v.s. lösa 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 för denna funktion är att likställa den med noll, får vi ${\mathcal {r}}\Psi _{1}(y)=2V^{T}AVy-2V^{T}r_{0}.$

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

vilket är exakt samma som uttrycket om vi lägger in det $y=(W^{T}AV)^{-1}W^{T}r_{0},$ $V=W.$

Teorem .
Om matrisen A är icke degenererad, då är problemet med att designa en SLAEpå vilketortogonalt mot delrummetekvivalent med problemet med att minimera det funktionella

ax=b

K

L=AK

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

Bevis

Genom att ersätta relationen med baserna i formeln 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}.

Detta innebär att den aktuella situationen är likvärdig med valet för det symmetriska systemet $L=K$ $A^{T}Ax=A^{T}b.$

Med tanke på förhållandet

\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

och genom att tillämpa föregående sats på ett sådant system får vi påståendet formulerat i villkoret.

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

För att konstruera varje ny vektor kräver Arnoldi-ortogonaliseringsalgoritmen att man hittar inre produkter och samma antal linjära kombinationsoperationer. $v_{k}$ $(k-1)$

Litteratur

Saad Y. Iterativa metoder för glesa linjära system. — 2:a upplagan. - SIAM Society for Industrial & Applied Mathematics, 2003. - P. 477. -ISBN 0898715342.
Balandin M.Yu., Shurina E.P. Metoder för att lösa högdimensionella SLAE. - Novosibirsk: NSTU, 2000. - S. 70.
Golub J., Van Lone C. Matrix Computing. - Moskva: Mir, 1999.
Ilyin V.P. Ofullständiga faktoriseringsmetoder för att lösa linjära system. - Moskva: Fizmatlit, 1995.

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