NumMod 1 het 3

date: 2024.02.26

Linearis algebrai egyenletrendszerek (l.a.e.r) megoldasa

1. Direkt modszerek

Pontosan szamolva veges sok lepesben a pontos megoldasokat adjak.
peladul:

• Cramer-szabaly
  nagyon muveletigenyes
• Gauss-eliminacio

2. Iteracio modszerek

Egy, a pontos megoldashoz tarto vektorsorozatot generalnak.

Gauss eliminacio

Megoldando: $Ax=b,A\in {\mathbb{R}}^{m\times m},\det A\ne 0⟹\exists !\text{m.o.},b\in {\mathbb{R}}^m$.
Azaz:

\begin{array} aa_{11}x_{1} + a_{12}x_{2} + \dots + a_{1m}x_{m} & = b_{1} \\ \vdots \\ a_{m 1}x_{1} + a_{m 2}x_{2} + \dots + a_{m m}x_{m} & = b_{m} \end{array}

I. alakban: Atalakitjuk az e.r.-t felso haromszog matrixuva. A foatloban legyenek egyesek

1. lepes: Tfh $a_{11}\ne 0$ ekkor (1)
   $x_1+\frac{a_{12}}{a_{11}}{x}_2+\frac{a_{13}}{a_{11}}{x}_3+\frac{a_{1m}}{a_{11}}{x}_m=\frac{b_1}{a_{11}}=y_1$
2. lepes: (1)’ segitsegevel a (2) - (m) egyenletekbol eliminaljuk $x_1$-et, kivonva beloluk az (1)‘-nek az $a_{i1}$-szereset.

\begin{array} xx_{1} & + \frac{a_{12}}{a_{11}}x_{2} & + \frac{a_{13}}{a_{11}}x_{3} & + \frac{a_{1m}}{a_{11}}x_{m} & = & \frac{b_{1}}{a_{11}} = y_{1} \\ \\ & a_{22}^{(1)}x_{2} & + \dots & & = & y_{2}\\ & & & &\vdots &\\ & a_{m 2}^{(1)}x_{2} & + \dots &+ a_{m m}^{(1)}x_{m} & = & b_{m} \end{array}

3. lepes: nem irom le mert mindenki tud Gauss-eliminalni…

Mikor hajthato vegre a Gauss-elim?

I. szakaszban $Ax=b⟹Ux=y$

Q.: Mi a kapcsolat $y$ es $b$ kozott?
$b_1=a_{11}{y}_1$
$b_2=a_{21}{y}_1+a_{22}^{(1)}{y}_2$
…
es igy tovabb
$b_j=l_{j1}{y}_1+l_{j2}{y}_2+\cdots +l_{jj}{y}_j,j=1,\dots ,m,\text{ ahol }{l}_{jj}=a_{jj}^{(j-1)}$

$$\left[\begin{array}{cccc}{a}_{11}& 0& \dots & 0\\ a_{21}& a_{22}^{(1)}& \dots & 0\\ & & \dots & a_{mm}^{(m-1)}\end{array}\right]\cdot \left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_m\end{array}\right]\le \left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right]$$

Ha a Gauss-elim elvegezheto akkor a fenti matrix invertalhato, azaz a foatloban nincs $0$, tehat $\exists L^{-1}$, ahol $L$ a fenti also haromszog matrix.

Tehat $Ly=b⟹y=L^{-1}b⟹Ux=L^{-1}b⟹LUx=b$

Ebbol adodik egy uj modszer

1. Felirjuk az $A$-t $A=LU$ alakban, ahol $L$ invertalhato also haromszog matrix es $U$ olyan felso haromszog matrix melynek a foatlojaban csak egyesek vannak.
2. Megoldjuk az $Ly=b$ egyenletrendszert $⟹y$
3. Megoldjuk az $Ux=y$ egyenletrendszert $⟹x$

Elnevezes: LU-felbontas modszere
Belathato, hogy 1. - 2. ekvivalens a Gauss-elim elso szakaszaval es 3. ekvivalens a Gauss-elim masodik szakaszaval. Tehat ez a modszer a Gauss-elim modositott algoritmusa.

Tehat a kerdesunk mashogy: Mikor letezik az LU-felbontas? Pontosan ekkor hajthato vegre a Gauss-eliminacio.

Legyen

$${\Delta }_1:=a_{11},,{\Delta }_2:=\det \left[\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right],\dots ,{\Delta }_m:=\det A$$

All.: Ha ${\Delta }_j\ne 0$, $j=1,\dots ,m$, akkor $\exists$ LU-felbontassa $A$-nak, es az egyertelmu.
Biz.:

1. Letezes
   Itt csak az $A\in {\mathbb{R}}^{2\times 2}$ esetre mutatjuk meg

$$A=L\cdot U=\left[\begin{array}{cc}{l}_{11}& 0\\ l_{21}& l_{22}\end{array}\right]\cdot \left[\begin{array}{cc}1& u_{12}\\ 0& 1\end{array}\right]\text{ felbontas letezik}⟺\text{letezik }{l}_{11},l_{21},l_{22},u_{12}\text{ ismeretlenekre nezve megoldasa a kovetkezo e.r.-nek}$$ $$l_{11}=a_{11}$$ $$l_{11}{u}_{12}=a_{12}$$ $$l_{21}=a_{21}$$ $$l_{21}{u}_{12}+l_{22}=a_{22}$$

es a kovetkezo $L$ matrixnak letezzen inverze

$$L=\left[\begin{array}{cc}{l}_{11}& 0\\ l_{21}& l_{22}\end{array}\right]$$

tehat $l_{11}\ne 0,l_{22}\ne 0$.

Ha $a_{11}\ne 0$, akkor lathato, hogy ennek az egyenletrendszernek $\exists !$ megoldasa:

$$l_{11}=a_{11},u_{12}=\frac{a_{12}}{a_{11}},l_{21}=a_{21},l_{22}=a_{22}-a_{21}\frac{a_{12}}{a_{11}}$$

Tovabba $l_{11}\ne 0$, mert $a_{11}\ne 0$ es $l_{22}\ne 0$, mert $l_{22}=\frac{\det A}{a_{11}}$ $⟹\exists L^{-1}$

Megjegyzes: $m>2$-re teljes indukcioval kovetkezik az allitas.

2. Egyertelmuseg
   tfh $A=L_1{U}_1=L_2{U}_2$

$$L_2^{-1}{L}_1{U}_1=U_2$$ $$L_2^{-1}{L}_1=U_2{U}_1^{-1}$$

Mivel az alsoharomszog matrixok es a felso haromszog matrixok is egy-egy csoportot alkotnak, ezert a fenti csak akkor igaz, ha $L_2^{-1}{L}_1$ es $U_2{U}_1^{-1}$ is diagonalis. Tovabba $U_{1,2}$-nek a foatlojaban egyesek vannak, tehat $U_2{U}_1^{-1}$-nek is a foatlojaban egyesek vannak. Tehat mindket oldalon az egyseg matrix van.

$$⟹L_2^{-1}{L}_1=I=U_2{U}_1^{-1}⟹L_1=L_2,U_1=U_2$$

Megmutathato, hogy ha ${\Delta }_j\ne 0$ valamely $j$-re, akkor $\exists$ LU-felbontasa $A$-nak.
$2\times 2$ esetben jol latszik:

$$\left[\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right]=\left[\begin{array}{cc}0& a_{12}\\ a_{21}& a_{22}\end{array}\right]$$ $$\left[\begin{array}{cc}0& a_{12}\\ a_{21}& a_{22}\end{array}\right]=\left[\begin{array}{cc}{l}_{11}& 0\\ l_{21}& l_{22}\end{array}\right]\cdot \left[\begin{array}{cc}1& u_{12}\\ 0& 1\end{array}\right]⟹l_{11}=0⟹\text{ekkor }L\text{ nem invertalhato}$$

Kov.: A Gauss-eliminacio pontosan akkor hajthato vegre, ha $A$ osszes bal felso sarokdeterminansa nem $0$.

related: NumMod 1