Projekční metody pro řešení SLAE

Projekční metody pro řešení SLAE jsou třídou iteračních metod, ve kterých je problém promítání neznámého vektoru do určitého prostoru řešen optimálně vzhledem k nějakému jinému prostoru.

Prohlášení o problému

Uvažujme SLAE kde je čtvercová matice dimenze Nechť a být dvourozměrné podprostory prostoru Je potřeba najít takový vektor , aby tzn. byla splněna podmínka: $Ax=b,$ $A$ $n.$ $K$ $L$ $m$ $R^{n}.$ $\tilde{x} \in K$ $bA\tilde{x} \perp L,$

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

nazval Petrov-Galyorkinův stav.

Pokud je známa počáteční aproximace , pak je třeba řešení promítnout do afinního prostoru Reprezentujme a označme nesrovnalost počáteční aproximace jako $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 .$

Pak lze konstatování problému formulovat takto: Je třeba najít takové , že tzn. byla splněna podmínka: $\delta\v 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$

Obecný přístup ke konstrukci promítacích metod

Zaveďme základy matic v prostorech a $K$ $L:$

$V=[v_{1},v_{2},...,v_{m}]$ - velikostní matice složená z prostorových sloupcových vektorů - velikostní matice složená z prostorových sloupcových vektorů $n \krát m$ $K.$ $W=[w_{1},w_{2},...,w_{m}]$ $n \krát m$ $L.$

Potom může být vektor řešení také zapsán: $\delta\ = Vy$ $\tilde{x}$

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

kde je vektor koeficientů. ${\displaystyle y\in R^{m))$

Poté lze výraz přepsat jako: $(r_0-A \delta\,l)=0$

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

odkud a ${\displaystyle W^{T}AVy=W^{T}r_{0))$

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

Řešení by tedy mělo být upřesněno podle vzorce:

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

Obecný pohled na jakoukoli metodu třídy projekce:

Dělejte to, dokud nenajdete řešení.

Vyberte dvojici podprostorů a $K$ $L.$
Konstrukce pro a základny a $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.$

Volba prostorů a způsob konstrukce bází pro ně zcela určují výpočtové schéma metody. $K$ $L$

Volba podprostorů K a L

Případ jednorozměrných podprostorů K a L

V případě, kdy jsou prostory a jednorozměrné, jejich maticovými základy jsou vektory: a výraz lze přepsat jako $K$ $L$ $V=[v]$ $W=[w]$ $\tilde{x} = x_0 + Vy,$

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

kde je neznámý koeficient, který lze snadno zjistit z podmínky ortogonality $\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},$

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

Metody s výběrem jednorozměrných podprostorů a : $K$ $L$

Metoda nejstrmějšího sestupu
Nejrychlejší metoda redukce zbytků
Gauss-Seidelova metoda
Metody třídy ABS

V praktických úlohách metody, které používají jednorozměrné prostory a mají spíše pomalou konvergenci. $K$ $L$

Metody Krylovského typu

Metody Krylovova typu (nebo metody Krylovova podprostoru ) jsou metody, pro které je jako podprostor vybrán Krylovův podprostor: $K$

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

kde je nesoulad počáteční aproximace. Různé verze metod Krylova podprostoru jsou podmíněny volbou podprostoru ${\displaystyle r_{0}=b-Ax_{0))$ $L.$

Z hlediska teorie aproximace mají aproximace získané v metodách Krylovova podprostoru tvar $\tilde{x},$

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

kde je polynom stupně Pokud dáme , pak ${\displaystyle q_{m-1))$ $m-1.$ $x_{0}=0,$

$A^{-1}b\přibližně q_{m-1}(A)b.$

Jinými slovy, přibližuje se $A^{-1}b$ $q_{m-1}(A)b.$

Přestože volba podprostoru neovlivňuje typ polynomiální aproximace, má významný vliv na efektivitu metody. K dnešnímu dni existují 2 způsoby, jak vybrat podprostor, které poskytují nejúčinnější výsledky: $L$ $L,$

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

L=K

L=AK

Věta .
Je-li matice A symetrická a pozitivně definitní, pak problém návrhu SLAEna jakýkoli podprostorortogonálně k podprostoruje ekvivalentní problému minimalizace funkcionálu

sekera=b

K

L=K

$\Phi_1(x) = \paralelní x- \tilde{x} \paralelní_A^2,$

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

Důkaz

Díky pozitivní definitivnosti matice dosahuje funkcionál svého minima při a je přísně konvexní. V čem $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}.

Vzhledem k symetrii matice je to pravda a funkcionál je roven $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}.

Podle hypotézy věty je tedy funkcionál přísně konvexní. Problém minimalizace formulovaný v podmínce se tak redukuje na nalezení $K=L,$ $V=W.$ $\Phi _{1}(x)$

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

Zvažme tento problém. Vzhledem ke konvexnosti postačí najít stacionární bod funkčního tzn. vyřešit systém $\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}}.

Gradient tohoto funkcionálu se rovná nule ${\mathcal {r}}\Psi _{1}(y)=2V^{T}AVy-2V^{T}r_{0}.$

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

což je úplně stejné jako výraz , pokud do něj vložíme $y=(W^{T}AV)^{-1}W^{T}r_{0},$ $V=W.$

Věta .
Pokud je matice A nedegenerovaná, pak problém návrhu SLAEna jakýkoli podprostorortogonálně k podprostoruje ekvivalentní problému minimalizace funkcionálu.

sekera=b

K

L=AK

$\Phi_2(x) = \paralelní r_x \paralelní_2^2.$

Důkaz

Dosazením vztahu pro báze do vzorce dostaneme: ${\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}.

To znamená, že uvažovaná situace je ekvivalentní volbě pro symetrický systém $L=K$ $A^{T}Ax=A^{T}b.$

Vzhledem k poměru

\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

a použitím předchozí věty na takový systém získáme tvrzení formulované v podmínce.

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

Ke konstrukci každého nového vektoru vyžaduje Arnoldiho ortogonalizační algoritmus nalezení vnitřních součinů a stejný počet lineárních kombinačních operací. $v_{k}$ $(k-1)$

Literatura

Saad Y. Iterační metody pro řídké lineární systémy. — 2. vydání. - SIAM Society for Industrial & Applied Mathematics, 2003. - S. 477. -ISBN 0898715342.
Balandin M.Yu., Shurina E.P. Metody řešení vysokorozměrných SLAE. - Novosibirsk: NSTU, 2000. - S. 70.
Golub J., Van Lone C. Matrix Computing. - Moskva: Mir, 1999.
Ilyin V.P. Neúplné faktorizační metody pro řešení lineárních soustav. - Moskva: Fizmatlit, 1995.

Metody řešení SLAE
Přímé metody	Maticová metoda Gaussova metoda Gauss-Jordanova metoda Cramerova metoda LU rozklad Choleský rozklad Metoda zametání
Iterační metody	Jacobiho metoda Gauss-Seidelova metoda Iterační metoda Relaxační metoda Metoda konjugovaného gradientu Metoda bikonjugovaného gradientu Metoda stabilizovaného bikonjugátového gradientu
Všeobecné	inverzní matice Projekční metody pro řešení SLAE Předběžná úprava