NumMod 1 het 5

date: 2024.03.11.

Stacionarius iteracio konvergenciaja

emlek:

$$B\frac{x^{n+1}-x^n}{\tau }+A\cdot x^n=b\text{(SI)}$$ $$Ax=b\text{(1)}$$

tfh. $A$ szpd, tehat $A=A^T$, $x^{T}Ax>0,\text{ha }x\ne 0$
maskeppen: $\exists \delta >0:(Ax,x)\ge \delta \cdot ||x|{|}^2$

jelolje $x^{\ast }$ az (1) egyenelet megoldasat, azaz $A{x}^{\ast }=b$
jelolje $e_n:=x^n-x^{\ast }$ (az $n$-edik iteracio hibaja)

Def.: Azt mondjuk hogy a stacionarius iteracio (SI) konvergens, ha $\exists \lim x_n$ és $x_n\to x^{\ast }$, azaz ${\lim }_{n\to \infty }{e}_n=0$.

All.: Tegyuk fol, hogy $A$ szpd. Ha $\exists B^{-1}$, es $\tau >0$ parameter olyan, hogy $B-0.5\tau A$ szpd, akkor a stacionarius iteracio konvergens.
Biz.:

$$x^n=e_n+x^{\ast },x^{n+1}=e_{n+1}+x^{\ast }⇝\text{ (SI)-be beirva}$$ $$B\frac{e_{n+1}+x^{\ast }-e_n-x^{\ast }}{\tau }+A{e}_n+A{x}^{\ast }=b$$ $$B\frac{e_{n+1}-e_n}{\tau }+A{e}_n=0\text{(3) hibaegyenlet}$$

Fejezzuk ki $e_{n+1}$-el

$$B{e}_{n+1}=(B-\tau A)e_n$$ $$e_{n+1}=(I-\tau B^{-1}A)e_n$$ $$A{e}_{n+1}=(A-\tau A{B}^{-1}A)e_n$$ $$⟹(A{e}_{n+1},e_{n+1})=(A{e}_n-\tau A{B}^{-1}A{e}_n,e_n-\tau B^{-1}A{e}_n)$$ $$=(A{e}_n,e_n)-\tau (A{B}^{-1}A{e}_n,e_n)-\tau (A{e}_n,B^{-1}A{e}_n)+{\tau }^2(A{B}^{-1}A{e}_n,B^{-1}A{e}_n)$$

Tudjuk, hogy

$$(A{B}^{-1}A{e}_n,e_n)=(B^{-1}A{e}_n,A^T{e}_n)=(B^{-1}A{e}_n,A{e}_n)=(A{e}_n,B^{-1}A{e}_n)$$

Tehat

$$(A{e}_{n+1},e_{n+1})=(A{e}_n,e_n)-2\tau (A{B}^{-1}A{e}_n,e_n)+{\tau }^2(A{B}^{-1}A{e}_n,B^{-1}A{e}_n)$$

Jelolje $J_n=(A{e}_n,e_n)$. Ezzel

$$J_{n+1}=J_n-2\tau (A{e}_n,B^{-1}A{e}_n)+{\tau }^2(A{B}^{-1}A{e}_n,\stackrel{y_n}{\overbrace{B^{-1}A{e}_n}})$$

Ezzel $B{y}_n=A{e}_n$

$$=J_n-2\tau (B{y}_n,y_n)+{\tau }^2(A{y}_n,y_n)=J_n-2\tau \left((B{y}_n,y_n)-\frac{\tau }{2}(A{y}_n,y_n)\right)$$ $$⇝J_{n+1}=J_n-2\tau ((B-0.5\tau A)y_n,y_n)\text{(4)}$$ $$⟹J_{n+1}\le J_n$$

Mert feltetel szerint $\tau >0$ es $(B-0.5\tau A)$ szpd, tehat pozitiv szor pozitiv tagot vonunk ki, tehat egy pozitiv szamot vonunk ki. Ezert a jobb oldal kisebb mint $J_n$.
Igy a $(J_n)$ sorozat monoton csokkeno, es $J_n\ge 0$, (mert $J_n=(A{e}_n,e_n)$ ), tehat ez a sorozat alulrol korlatos.
Tehat $(J_n)$ konvergens, jeloles $J^{\ast }:={\lim }_{n\to \infty }{J}_n$

(4)-ben vegyunk limeszt $⇝$

$$J^{\ast }=J^{\ast }-2\tau \underset{n\to \infty }{\lim }((B-0.5\tau A)y_n,y_n)$$ $$⟹\underset{n\to \infty }{\lim }((B-0.5\tau A)y_n,y_n)=0$$

Mivel $B-0.5\tau A$ szpd, ezert $\exists \delta >0:((B-0.5\tau A)y_n,y_n)\ge \delta \cdot ||y_n|{|}^2$.
Rendorelv:

$$((B-0.5\tau A)y_n,y_n)\ge \delta \cdot ||y_n|{|}^2\ge 0$$ $$\underset{n\to \infty }{\lim }((B-0.5\tau A)y_n,y_n)\ge \underset{n\to \infty }{\lim }\delta \cdot ||y_n|{|}^2\ge 0$$ $$⟹0\ge \underset{n\to \infty }{\lim }\delta \cdot ||y_n|{|}^2\ge 0⟹\underset{n\to \infty }{\lim }\delta \cdot ||y_n|{|}^2=0$$

Mivel $y_n=B^{-1}A{e}_n$ $⇝e_n=A^{-1}B{y}_n$

$$0\le ||e_n||=||A^{-1}B{y}_n||\le ||A^{-1}B||\cdot ||y_n||\to 0⟹||e_n||\to 0⟹e_n\to 0$$

Sor modszer konvergenciaja

Kulcskerdes: $\omega$ megvalasztasa.
Fugg $A$-tol!

Nehany allitas:
1.) Tetszoleges $A\in {\mathbb{R}}^{n\times m}$ eseten a SOR-modszer konvergenciajahoz szukseges, hogy $\omega \in (0,2)$.
2.) Ha $A$ szpd, akkor $\omega \in (0,2)$ elegseges is a konvergenciahoz.
$⟹$ Ha $A$ szpd, akkor a Gauss-Seidel iteracio konvergens, mert a GS-it pont a SOR-modszer $\omega =1$-el.

Gradiens alapu modszerek

$$Ax=b\text{(1)}$$

Tegyuk fel, hogy $A$ szpd.

Def.: $\varphi :{\mathbb{R}}^m\to \mathbb{R}$ fv-t:

$$\varphi (x):=\frac{1}{2}(x,Ax)-(x,b)$$

ez differencialhato ${\mathbb{R}}^m$-en.
Derivaljuk!

$${\varphi }^{\prime }(x)=\nabla \varphi (x)=Ax-b\text{(szamolassal ellenorizheto)}$$

$Ax-b$ az $r:=b-Ax$ maradekvektor $-1$ szerese!

Hol $0$ a gradiens?

$${\varphi }^{\prime }(x)=Ax-b=0⇝x=A^{-1}b\text{ ez eppen az (1) megoldasa}$$ $${\varphi }^{\prime \prime }(x)=A$$

Mivel feltettuk, hogy $A$ szpd, ezert ${\varphi }^{\prime \prime }(x)$ potiv definit, tehat ahol a gradiens nulla ott lokalis minimum hely van.
$⟹x^{\ast }$ az egyetlen lokalis minimum hely / globalis minimum helye $\varphi$-nek.

Q.: Hogy nez ki a $\varphi$ fuggveny? Tekintsunk egy ket dimenzios peldat:

$$\begin{array}{rl}2x_1& =4\\ 8x_2& =8\end{array}$$

Megoldas: $x_1^{\ast }=2,x_2^{\ast }=1$

$$A=\left[\begin{array}{cc}2& 0\\ 0& 8\end{array}\right],b=\left[\begin{array}{c}4\\ 8\end{array}\right]$$ $$\varphi (x)=\frac{1}{2}(x,Ax)-(x,b)$$ $$\varphi (x)=\frac{1}{2}\left(\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right],\left[\begin{array}{c}2x_1\\ 8x_2\end{array}\right]\right)-\left(\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right],\left[\begin{array}{c}4\\ 8\end{array}\right]\right)=\frac{1}{2}{x}_{1}2x_1+\frac{1}{2}{x}_{2}8x_2-4x_1-8x_2=(x_1-2{)}^2+4(x_2-1{)}^2-8$$

Szintvonalak?
$Ac=0$-hoz tartozo

$$(x_1-2{)}^2+4(x_2-1{)}^2-8=0$$ $$\frac{(x_1-2{)}^2}{8}+\frac{(x_2-1{)}^2}{2}=1$$

Ez egy $(2,1)$ kozeppontu ellipszis $\sqrt{8},\sqrt{2}$ fotengelyekkel. Tehat $(2,1)$ a megoldas.

Tehat a fuggveny szintvonalai koncentrikus hiperellipszoidok!

Eloszor gondoljuk meg, hogy egy $x\in {\mathbb{R}}^m$ pontot es egy $p\ne 0$ vektort rogzitve $p$ irany menten hol veszi fel a $\varphi$ a legkisebb erteket?

Jel.: $g(\alpha ):=\varphi (x+\alpha p)$
Q.: Mely $\alpha$-ra lesz $g(\alpha )$ fuggveny erteke minimalis?

All.: A $g(\alpha )=\varphi (x+\alpha p)$ fuggveny egyertelmu minimumat az

$$\alpha =\frac{(p,r)}{(p,Ap)}$$

megvalasztas eseten veszi fol!

Biz.: Farago jegyzet 83. oldal

Q.: Hogyan valasszuk meg $p_1,p_2,\dots$ keresesi iranyokat?

Gradiens modszer

Tudjuk: A $\nabla \varphi$ -vel ellentetes iranyban a legmeredekebb a lejtes.

$x_i$ pontban $p_{i+1}$-el jelolve a keresesi iranyt:

$$p_{i+1}:=-\nabla \varphi (x_i)$$ $$\nabla \varphi (x)=Ax-b=-r$$ $$⟹p_{i+1}:=-\nabla \varphi (x_i)=b-A{x}_i=r_i$$

ami eppen az $x_i$ pontbeli maradekvektor.

$$x_i⇝x_{i+1}=x_i+\alpha \cdot p_{i+1}=x_i+\frac{(p_{i+1},r_i)}{(p_{i+1},A{p}_{i+1})}\cdot p_{i+1}=x_i+\frac{(r_i,r_i)}{(r_i,A{r}_i)}\cdot r_i$$

Mi lesz $x_{i+1}$-ben a maradekvektor?

$$r_{i+1}=b-A{x}_{i+1}=b-A\cdot \left(x_i+\frac{(r_i,r_i)}{(r_i,A{r}_i)}\cdot r_i\right)$$

Vegyuk eszre: $r_i\perp r_{i+1}$, mert addig megyunk $p_i$ iranyban ameddig nem erintjuk a kovetkezo szintvonalat, amire a kovetkezo gradiens meroleges.

related: NumMod 1