NumMod 1 het 4

date: 2024.03.04

Megjegyzesek:

1. A ${\Delta }_j\ne 0,\forall j=1,\dots ,m$ teljesul, ha $A$ szimmetrikus pozitiv definit matrix (szpd).
2. A ${\Delta }_j\ne 0,\forall j=1,\dots ,m$ teljesul, ha $A$ szigoruan dominans foatloju, tehat $\forall i=1,\dots ,n$ -re $2|a_{ii}|>{\sum }_{j=1}^m|a_{ij}|$.
3. Ha $\det A\ne 0$, akkor mindig $\exists P\in {\mathbb{R}}^{n\times m}$ permutalo matrix, hogy $PA$-nak $\exists$ LU-felbontasa.
4. Ha $A$ szimmetrikus pozitiv definit matrix, akkor $\exists$ egy masik felbontasa is: $A=G\cdot G^T$, ahol $G$ also haromszog matrix, pozitiv foatloval. (Cholesky-felbontas)

Foelem-kivalasztas (pivoting)

Gauss elim $j$-edik lepese:

$$\left[\begin{array}{ccc}1& \dots & \dots \\ ⋮& ⋮& ⋮\\ 0& a_{jj}^{(j)}& \dots \\ ⋮& ⋮& ⋮\\ 0& 0& 1\end{array}\right]$$

A $a_{jj}^{(j)}$ szammal elosztjuk a $j$-edik sort.
Nem elonyos, ha $|a_{jj}^{(j)}|$ nagyon kicsi, mert akkor a kerekitesi hiba nagy lesz.

1. Reszleges foelem kivalasztas: Sorcserevel a foatloba hozzuk az $a_{jj}^{(j)}$ alatti legnagyobb absz erteku elemet.
2. Teljes foelem kivalasztas: Sorcserevel es oszlop cserevel az $A[j:n,j:n]$ jobb also reszmatrix legnagyobb absz erteku elemet visszuk a foatloba. (Itt figyelni kell arra, hogy oszlop cserenel az $x$ elemeit is csereljuk.)

Iteracios modszerek

1. Klasszikus iteracios modszerek

Emlek:
Def.: Amh. az $x^{\ast }\in {\mathbb{R}}^n$ az $f:{\mathbb{R}}^n\to {\mathbb{R}}^n$ fixpontja, ha $f(x^{\ast })=x^{\ast }$.
Def.: Amh. az $f:{\mathbb{R}}^m\to {\mathbb{R}}^m$ fuggveny kontrakci az $||\cdot ||$ ${\mathbb{R}}^n$-beli normaban, ha $\exists q\in [0,1]$-melyre:

$$||f(x)-f(y)||\le q\cdot ||x-y||\forall x,y\in D(f)$$

Tetel: Ha $f:{\mathbb{R}}^n\to {\mathbb{R}}^n$ az egesz ${\mathbb{R}}^n$-en ertelmezett kontrakcio ($q$-val), akkor:

1. $f$-nek $\exists !x^{\ast }$ fixpontja.
2. Tetszoleges $x^0\in {\mathbb{R}}^n$ vektorbol inditva $x^{n+1}=f(x^n)$ rekurzioval felepitett $(x{)}_n$ sorozat konvergens, es $x_n\to x^{\ast }$.
3. $||x^n-x^{\ast }||\le \frac{q^n}{1-q}||x^1-x^0||$

Q.: Hogyan alkalmazhatjuk ezt a tetel lin.a.e.r. megoldasara?

(1) $Ax=b,A\in {\mathbb{R}}^{m\times m},\det A\ne 0,b\in {\mathbb{R}}^m$
Tfh (1) atirhato a kovetkezo alakra
(2) $x=Qx+r$, ahol $Q\in {\mathbb{R}}^{m\times m},r\in {\mathbb{R}}^m$
Ekkor az $f(x):=Qx+r$ jelolessel a feladat megoldasa az $f:{\mathbb{R}}^m\to {\mathbb{R}}^m$ fuggveny fixpontja. Ezt a fixpontot keressuk.

Q.: Mikor lesz $f$ kontrakcio?

$$x,y\in {\mathbb{R}}^m,f(x)-f(y)=Qx+r-Qy-r=Q(x-y)$$ $$||f(x)-f(y)|{|}_{{\mathbb{R}}^m}=||Q(x-y)|{|}_{{\mathbb{R}}^m}\le ||Q||\cdot ||x-y|{|}_{{\mathbb{R}}^m}$$

Tehat be kell latni, hogy $||Q||<1$, akkor $f$ kontrakcio es $q=||Q||$.
Tetel $⟹$ ekkor az $x^{n+1}=Q{x}^n+r$ rekurzioval definialt sorozat konverges (barmelyik ${\mathbb{R}}^m$-beli vektornormaban), es $x_n\to x^{\ast }$, mely (1)-nek a megoldasa.

Q.:

1. Hogyan irjuk at (1)-et (2) alakura?
2. Mikor fog teljesulni, hogy $||Q||<1$ valamelyik indukalt matrix norma szerint?

Jacobi-iteracio

$$Ax=b$$ $$A=L+D+U$$ $$(L+D+U)x=b$$ $$Dx=-(L+U)x+b$$ $$x=D^{-1}(b-(L+U)x)=-D^{-1}(L+U)x+D^{-1}b$$ $$Q_J=-D^{-1}(L+U)r_J=D^{-1}b$$

Fixpont iteracio:
$x^0\in {\mathbb{R}}^m$-t rogzitjuk
$x^{n+1}=-D^{-1}(L+U)x^n+D^{-1}b$

All.: $||Q_j|{|}_{\infty }<1⟺A\text{ szigoruan dominans foatloju}$.

Kov.: Ha $A$ szigoruan dominans foatloju, akkor a Jacobi-iteracio konvergens.

Gauss-Seidel-iteracio

$$Ax=b$$ $$A=L+D+U$$ $$(L+D+U)x=b$$ $$(L+D)x=-Ux+b$$ $$x=-(L+D{)}^{-1}Ux+(L+D{)}^{-1}b$$ $$Q_{GS}=-(L+D{)}^{-1}U,r_{GS}=(L+D{)}^{-1}b$$

Stacionarius-iteracio

Eszrevetel: A Jacobi-iteracio atirhato:

$$x^{n+1}=-D^{-1}(L+U)x^n+D^{-1}b$$ $$D{x}^{n+1}=-(L+U)x^n+b$$ $$D{x}^{n+1}=-(A-D)x^n+b$$ $$D(x^{n+1}-x^n)+A{x}^n=b$$

(Jacobi-iteracio kanonikus alakja)

Gauss-Seidel-iteracio atirva:

$$(D+L)(x^{n+1}-x^n)+A{x}^n=b(\text{SI})$$

(Gauss-Seidel kanonikus alakja)

Def.: Legyen $B\in {\mathbb{R}}^{m\times m}$, es $\tau >0$ szam. A

$$B\cdot \frac{x^{n+1}-x^n}{\tau }+A{x}^n=b$$

iteraciot stacionarius-iteracionak nevezzuk.

Megj.:
Jacobi: $B=D,\tau =1$
Gauss-Seidel: $B=D+L,\tau =1$
(Meg altalanosabb: $B\leftrightarrow B_n,\tau \leftrightarrow {\tau }_n$)

Egy fontos stacionarius iteracio (Tulrelaxacios modeszer / Successive overrelaxation method - SOR-modszer):

$$B=D+\omega L,\tau =\omega ,\text{ ahol }\omega >0\text{ adott parameter}$$ $$(D+\omega L)\cdot \frac{x^{n+1}-x^n}{\omega }+A{x}^n=b$$

Megfigyeles: $\omega =1$-re visszakapjuk a Gauss-Seidel-iteraciot.

related: NumMod 1