II. RF KMF DokuWiki

7.1 Lineáris algebrai feladatok és azoknak a forrásai
7.2 Mátrixok típusai és tulajdonságai
7.3 Vektor és mátrix normák
7.4 Lineáris egyenletrendszer kondicionáltsága
7.5 Lineáris egyenletrendszerek megoldása. Gauss módszer
7.6 Főelem-kiválasztásos Gauss-módszer
7.7 Gauss-módszerrel előállított megoldásának iterációs javítása
7.8 Gauss-Jordan módszer
7.9 LU-módszer
7.10 Cholesky-módszer (Négyzetgyök-módszer)
7.11 Iterációs módszerek
7.12 Lineáris teljes lépéses első rendű módszerek
7.13 Fokozatos közelítések módszere (Jacobi-iteráció)
7.14 Lineáris egylépéses első rendű módszerek

A lineáris algebrához sok fontos feladat tartozik, melyek közül a legfontosabb a lineáris egyenletrendszer megoldása. Az alkalmazások szempontjából a következő feladatok a legérdekesebbek.

1) Oldjuk meg a

$$Ax = b\tag{7.1}\label{eq:7.1}$$

egyenletrendszert, ahol $A\in \mathbb{R}^{n\times n}$ négyzetes valós (vagy komplex) mátrix,

$b\in\mathbb{R}^{n}$ – oszlop-vektor, $x\in\mathbb{R}^{n}$ – ismeretlen oszlop-vektor.

2) Előfordul, hogy az előző feladatot azonos $A$ mellet több ($k$ számú) $b$ vektorokkal kell megoldani. Akkor ezt a feladatot egy mátrix-egyenletként

$$A\cdot X = B\tag{7.2}\label{eq:7.2}$$

lehet kezelni, ahol $X,B\in \mathbb{R}^{n\times k}$ mátrixok.

3) Az adott $A$ mátrix inverzét $A^{-1}$ kell előállítani.

4) Meg kell keresni a valós szimmetrikus A mátrix valós saját-értékeit

$$Ax = λx\tag{7.3}\label{eq:7.3}$$

és lehetséges, a hozzátartozó saját vektorokat is.

5) Meg kell keresni a valós A mátrix saját-értékeit és saját vektorait:

$$Ax = λx \tag{7.4}\label{eq:7.4}$$

Általános esetben a saját-értékek komplex számok is lehetnek.

6) Meg kell oldani a nem kompatibilis egyenletrendszert

$$Cx = d\tag{7.5}\label{eq:7.5}$$

ahol $C\in \mathbb{R}^{n\times k}C$ – mátrix, $d\in \mathbb{R}^{n}$ $n$-komponenses vektor ($n>k$). Ez az egyenletrendszer túlhatározott, mivel az egyenletrendszerben több egyenlet van mint változó, Ilyen egyenletrendszerek általános esetben nem kompatibilisek. A megoldás alatt a legkisebb négyzetek módszerével

$$|| Cx^* - d|| = \min || Cx - d|| \tag{7.6}\label{eq:7.6}$$

előállított $x^*$ vektort fogjuk tekinteni.

7) Meg kell oldani a

$$Ax \geqslant b\tag{7.7}\label{eq:7.7}$$

egyenlőtlenségi rendszert.

Az alkalmazott matematikus az adatok feldolgozása kapcsán keresheti a gyakorlati problémához tartozó paraméterek értékeit. Például, az interpolációs polinom meghatározásának a feladata $(n+1)$ alappont alapján lineáris egyenletrendszerhez vezethet. Természetesen, léteznek bonyolultabb esetek is, amikor nem lineáris egyenletrendszert kapunk. De ebben az esetben is van lehetőség a nem lineáris feladatot linearizálással a lineáris esetre redukálni. A linearizálásnak az az alapja, hogy a nem lineáris egyenletrendszer megoldását közelítsük a lineáris egyenletrendszer megoldásával egy iterációs eljáráson belül.

Egy másik gyakori forrás, a folytonos funkcionális egyenletek (egyenletrendszerek) approximációja (közelítése) lineáris egyenletrendszerekkel. Ez egy gyakori eljárás, amikor a folytonos természetű feladat helyet szerkesztünk egy diszkrét feladatot, úgy hogy annak a megoldása közzel legyen az eredeti feladat megoldásához. Ez azért is indokolt, mert a számítógép diszkrét problémákat képes megoldani.

Például, így lehet megoldani a matematikai fizikához tartozó Dirihle-problémát a Laplace-féle differenciális operátorával. Az így létrejött mátrixok majdnem mindig nagy méretűek és ritkák.

A legkisebb négyzetek módszerének alkalmazása normál egyenletrendszerhez vezet. Általában, a normál egyenletrendszer kis méretű és sűrű mátrixa van.

A statisztikai számításokban gyakran szükség van az inverz mátrixra. Ezt a mátrixot a statisztikai paraméterek becslésére alkalmazzák.

A sajátértékeket és sajátvektorokat alkalmazzák a lineáris közönséges differenciális egyenletek megoldására.

Az $A$ mátrix – ritka mátrix, ha csak egyes elemei (komponensei) $a_{ij} ≠ 0$, és az elemek többsége

$$a_{ij}= 0.$$

A ritka mátrixok gyakran sok ezer vagy millió elemet tartalmaznak. A számítógépben ritka mátrixokat csak nem hagyományos formában tárolhatjuk, és bizonyos kódolási rendszerben tárolják a nem zérus elemeket. Természetesen, ezt a kódolást figyelembe kell venni az algoritmusokban is, kódolási rendszernek olyannak kell lenni, hogy a mátrix elemeit könnyen lehessen feldolgozni.

Ha az $A$ mátrix elemeinek többsége $a_{ij} ≠ 0$, akkor a mátrix – sűrű mátrix.

Előfordulhat, hogy egy sűrű mátrixot sem szükséges hagyományos formában tárolni, ha a mátrix elemeit kiszámíthatjuk egy algoritmus által az indexek alapján. Például,

$$a_{ij} = \frac{1}{i+j-1}, \quad i,j =1, 2, …, n.$$

A gyakorlati feladatok nagyon nagy mátrixokat igényelhetnek. Danzing leírt egy lineáris programozási feladatot, amely millió egyenletet és 40000 ismeretlent tartalmazott. Varga megemlített egy egyenletrendszert 108000 ismeretlennel.

Egy lineáris algebrai feladat megoldhatóságának az elemzésénél figyelembe kell venni a feladat n nagyságrendjét, a mátrix sűrűségét, más tulajdonságait is, a számítógép paramétereit. Gyakran egy-egy feladatot elvileg különböző módszerekkel lehet megoldani. Ezért a megfelelő módszer kiválasztása nem egyszerű feladat. Például, a ritka mátrixok tárolása speciális formában történik, amit a módszernek is figyelembe kell venni. A legtöbb iterációs módszer a ritka mátrixot lépésről lépésre sűrű mátrixokká alakítja át, ami tárolási problémákhoz vezethet.

A feladatok gyakoriak sávmátrixokat tartalmaznak. Akkor mondjuk, hogy egy mátrix sávmátrix p alsó sávszélességgel és q felső sávszélességgel, ha teljesül, hogy

$$a_{ij} = 0,\quad i > j+p, \text{ vagy } i +q < j$$

A mátrix nem zérus elemeinek indexei:

$$j - q \leqslant i \leqslant j+p.$$

Gyakran $q=p=m$, és $m$ lényegesen kisebb, mint $n$. Ilyen mátrixban a sáv $2m+1$ átlót tartalmazz, beleértve a főátlót is.

7.1. Példa $$A=\begin{pmatrix} a_{11} & a_{12} & 0 & 0 & 0 \\ a_{21} & a_{22} & a_{23} & 0 & 0 \\ 0 & a_{32} & a_{33} & a_{34} & 0 \\ 0 & 0 & a_{43} & a_{44} & a_{45} \\ 0 & 0 & 0 & a_{54} & a_{55} \\ \end{pmatrix} $$

ha $| i - j | > 1$, akkor $a_{ij} = 0$.

A sávos mátrixok olyan feladatokban keletkeznek, melyekben az ismeretlen változók csak néhány más „szomszédos” ismeretlennel vannak kapcsolatban. Például, ilyen lehet egy egyenletrendszer, amely áramköröket ír le, és amelyben sok csatlakozási pont van, de egymással kevés pont van összekapcsolva.

A gyakorlati feladatokban olyan mátrix típus előfordulhat, amelyeknek a legnagyobb (abszolút érték szerinti) elemei a főátlón vannak elhelyezve, úgy hogy

$$|a_{ii}|\geqslant\sum_{j=1\\j\neq i}^n|a_{ij}|,\quad i,\ldots,n$$

és legalább egy $i$-re igaz, hogy

$$|a_{ii}|>\sum_{j=1\\j\neq i}^n|a_{ij}|,\quad i,\ldots,n$$

feltétel.

A $D\in\mathbb{R}^{n\times n}$ diagonálmátrix, ha

$$D=\begin{pmatrix} d_1 & 0 & \cdots & 0\\ 0 & d_2 & \cdots & 0\\ 0 & 0 & \cdots & \cdots\\ 0 & 0 & \cdots & d_n \end{pmatrix}$$

A $B\in\mathbb{R}^{n\times n}$ mátrixot a $A\in \mathbb{R}^{n\times n}$ mátrix inverzének nevezzük, ha

$$BA = AB = I,$$

$I$ – egységmátrix, az $A$ inverz mátrixát $A^{-1}$ jelöljük. Az inverz mátrix tulajdonságai

$$(A^{-1})^{-1} = A,\quad (AB)^{-1} = B^{-1} A^{-1},$$

$C$ alsó háromszög mátrix, ha $c_{ij} = 0, i< j$.

$C$ felső háromszög mátrix, ha $c_{ij} = 0, i > j$.

Az $A$ mátrix – pozitív definiált mátrix, ha tetszőleges $x ≠ 0$ nézve

$$x^{T}Ax >0$$

A lineáris algebrai numerikus módszerek alkalmazása szempontjából fontos szerepe van a norma fogalmának.

Legyen

$$x\in\mathbb{R}^{n},\,x=(x_1,x_2,\cdots,x_n)$$

$x$ – vektor normája egy olyan valós szám $|| x ||$, amelyre igaz, hogy:

$$|| x || >0,\text{ ha } x ≠ 0,$$

és

$$|| x || =0, \text{ ha } x= 0,\tag{7.8}\label{eq:7.8}$$

$$|| cx || = | c |\cdot|| x ||,\tag{7.9}\label{eq:7.9}$$

$c$ – tetszőleges szám, és

$$|| x+ y|| \leqslant|| x|| +|| y||\tag{7.10}\label{eq:7.10}$$

Az $||A ||$ funkciónál az $A$ mátrix normája, ha

$$||A || >0,\text{ ha } A ≠ 0,\text{ és } ||A || =0,\text{ ha } A = 0,\tag{7.11}\label{eq:7.11}$$

$$||cA || = |c|·||A ||\tag{7.12}\label{eq:7.12}$$

$c$ –tetszőleges szám,

$$||A+B|| \leqslant ||A|| + ||B||\tag{7.13}\label{eq:7.13}$$

$$||AB|| \leqslant ||A||\, ||B||\tag{7.14}\label{eq:7.14}$$

Leggyakrabban a következő vektor normákat szokták alkalmazni:

$$\|x\|_1=\sum_{i=1}^n|x_i|,\tag{7.15}\label{eq:7.15}$$

euklideszi norma : $$\|x\|_2=\sqrt{\sum_{i=1}^n|x^2_i|},\tag{7.16}\label{eq:7.16}$$

$$|| x ||_∞ = \max | x_i |\tag{7.17}\label{eq:7.17}$$

Mind a három normára igazak a (7.8),(7.9) feltételek. Ellenőrizzük, hogy teljesül-e a (7.10) feltétel.

$$\|x+y\|_1\leqslant\sum_{i=1}^n|x_i+y_i|\leqslant\sum_{i=1}^n|x_i|+\sum_{i=1}^n|y_i|=\|x\|_1+\|y\|_1,$$

A Cauchy–Bunyakovszkij–Schwarz-féle egyenlőtlenség alapján:

$$\|x+y\|_2=\sqrt{\sum_{i=1}^n(x_i+y_i)^2}\leqslant\sqrt{\sum_{i=1}^nx^2_i}++\sqrt{\sum_{i=1}^ny^2_i}=\|x\|_2+\|y\|_2$$

$$|| x ||_∞ \leqslant \max| x_i+ y_i | \leqslant \max| x_i| + \max| y_i | = || x ||_∞ +|| y||_∞$$

A mátrix-normákat is többféle képen lehet bevezetni:

$$\|A\|_1=\max_k\sum_{i=1}^n|a_{ik}|,\tag{7.18}\label{eq:7.18}$$

spektrál norma:

$$\|A\|_2=\sqrt{\lambda_1} \tag{7.19}\label{eq:7.19}$$

ahol a $λ_1$ az $A^{T}A$ mátrix maximális sajátértéke ( $A^{T}$ – az $A$ transzponált mátrixa).

$$\|A\|_\infty=\max_i\sum_{k=1}^n|a_{ik}|, \tag{7.20}\label{eq:7.20}$$

Frobenius-norma. $$\|A\|_F=\sqrt{\sum_{i=1}^n\sum_{j=1}^n|a_{ij}|^2}, \tag{7.21}\label{eq:7.21}$$

Definíció.

A $||A||_M$ mátrixnormát a $||x||_V$ vektornorma által indukált mátrixnormának nevezzük, ha

$$\|A\|_M=\max_{\|x\|_V=1}\|Ax\|_V \tag{7.22}\label{eq:7.22}$$

Az indukált mátrixnorma a $||x||_V = 1$ vektorok megnyújtásának a maximális értékét fejezik ki, vagy másképp fogalmazva, az egységgömb képének az A mátrix által leképezett ellipszoidnak az origóból vett leghosszabb vektor normájával egyenlő.

A következő mátrixnormák a megfelelő vektornormák indikált mátrixnormái:

$$||x||_1 → ||A||_1$$

$$||x||_2 → ||A||_2$$

$$||x||_∞ → ||A||_∞$$

Definíció.

A $||A||_M$ mátrixnorma kompatibilis az $||x||_V$ vektornormával, ha

$$||Ax||_V \leqslant ||A||_M\cdot||x||_V\tag{7.23}\label{eq:7.23}$$

Megjegyzés. Az indukált mátrixnormák az őket indukáló vektornormákkal mindig kompatibilisek.

A normák fontosabb tulajdonságai.

$$||AB|| \leqslant ||A||\cdot||B||\tag{7.24}\label{eq:7.24}$$

Létezik olyan x vektor, hogy

$$||Ax|| = ||A||\cdot||x||$$

és, $$\|A\|=\max_{\|x\|=1}\|Ax\| \tag{7.25}\label{eq:7.25}$$

Legyen $λ$ az $A$ mátrix sajátértéke. Akkor létezik olyan $x ≠ 0$ vektor, hogy

$$Ax = λx$$

és

$$||Ax|| = |λ|\cdot ||x||$$

Mivel

$$||Ax|| \leqslant ||A||\cdot||x||$$

akkor

$$|λ|· ||x|| \leqslant ||A||\cdot||x||$$

$$|λ| \leqslant ||A||$$

és mivel ez minden $λ$-ra igaz,

akkor

$$\max |λ_i| \leqslant ||A|| \tag{7.26}\label{eq:7.26}$$

Definíció.

Az $U$ mátrix ortogonális, ha

$$U^{T}U = U\, U^{T} = I,$$

ahol $I$ – egységmátrix.

Tétel 7.1

Minden $A$ mátrixra igaz, hogy léteznek olyan valós ortogonális $U$, $V$ mátrixok, hogy

$$D = U^{T}AV\tag{7.27}\label{eq:7.27}$$

$$D=\begin{pmatrix} \mu_1 & 0 & \cdots & 0\\ 0 & \mu_2 & \cdots & 0\\ 0 & 0 & \cdots & 0\\ 0 & 0 & \cdots & \mu_n \end{pmatrix}$$

$$μ_1 \geqslant μ_2 \geqslant … \geqslant μ_r \geqslant μ_{r+1} = … = μ_n =0$$

a $μ_i$ – szinguláris számoknak nevezzük.

Legyen $r$ az $A$ mátrix rangja. Ha $A$ nem elfajuló mátrix, akkor

$$μ_1 \geqslant μ_2 \geqslant … \geqslant μ_n \geqslant 0$$

Be lehet bizonyítani, hogy

$$D^{-1}=\begin{pmatrix} \mu_1^{-1} & 0 & \cdots & 0\\ 0 & \mu_2^{-1} & \cdots & 0\\ 0 & 0 & \cdots & 0\\ 0 & 0 & \cdots & \mu_n^{-1} \end{pmatrix}$$

és hogy

$$||A|| = ||D|| = μ_1\tag{7.28}\label{eq:7.28}$$

$$||A^{-1}|| = ||D^{-1}|| = μ_n^{-1} \tag{7.29}\label{eq:7.29}$$

Az $A^{-1}A $ mátrix sajátértékei pedig – $μ_1^2, μ_2, … μ_n^2$.

A szinguláris számokat a $A^{-1}A$ mátrix sajátértékei alapján lehet kifejezni:

$$μ_i = \sqrt{λ_i}$$

Bevezetjük a mátrix kondíciószámát:

$$\operatorname{cond}(A) = ||A||\cdot||A^{-1}|| \tag{7.30}\label{eq:7.30}$$

Akkor a $\eqref{eq:7.28}$(7.28) és $\eqref{eq:7.29}$(7.29) alapján

$$\operatorname{cond}(A) = \frac{μ_1}{μ_n} \geqslant 1 \tag{7.31}\label{eq:7.31}$$

A kondíciószám meghatározza az egységgömb maximális torzulását, amely az $A$ mátrix által végrehajtott lineáris transzformáció okozott.

Ha kicsi a $\operatorname{cond}(A)$ értéke, akkor a mátrix jól kondicionált, ha pedig a $\operatorname{cond}(A)$ értéke nagy, akkor a mátrix rosszul kondicionált. A függvény kondicionáltságáról lásd az [1.6]-ban.

Elemezzük a

$$Ax = b$$

egyenletrendszert.

Ha $|A| ≠ 0$, akkor az egyenletrendszernek van megoldása

$$x = A^{-1}b$$

Feltételezzük, hogy az $A$ és $b$ nem pontosan vannak megadva, hibát tartalmaznak. Megvizsgáljuk ennek a hatását a x megoldás pontosságára.

1). Először elemezzük azt a esetet, amikor a hibát csak a b vektor tartalmazza, tehát az egyenletrendszer b helyet b+Δb tartalmazza. Akkor

$$A(x+Δx) = b+Δb$$

vagy

$$AΔx =Δb$$

$$Δx = A^{-1}Δb$$

A norma tulajdonságának alapján:

$$|| Δx || \leqslant ||A^{-1}||\, || Δb || \tag{7.32}\label{eq:7.32}$$

Mivel $b=Ax$, akkor

$$|| b || \leqslant ||A||\, || x ||\tag{7.33}\label{eq:7.33}$$

A $\eqref{eq:7.32}$, $\eqref{eq:7.33}$ szorzása után:

$$|| Δx ||\, || b ||\leqslant||A||\, ||A^{-1}||\, ||x||\, || Δb ||$$

Ha $b≠0$, akkor:

$$\frac{|| Δx ||}{||x ||} \leqslant||A|| \,||A^{-1}|| \displaystyle\frac{|| Δb ||}{||b||}$$

A $\eqref{eq:7.30}$(7.30) alapján

$$\displaystyle\frac{|| Δx ||}{||x ||} \leqslant\operatorname{cond}(A) \displaystyle\frac{|| Δb ||}{ ||b||} \tag{7.34}\label{eq:7.34}$$(7.34)

$\displaystyle\frac{|| Δx ||}{||x ||}$ a megoldás relatív hibáját fejezi ki, a $\displaystyle\frac{|| Δb ||}{||b||}$ pedig a $b$ relatív hibáját.

Az $x$ relatív bizonytalanságát a $\displaystyle\frac{|| Δx ||}{ ||x ||}$ értéke fejezi ki. Hasonlóan, a $b$ relatív bizonytalanságát a $\displaystyle\frac{|| Δb ||}{||b ||}$ értéke adja.

Ha $\operatorname{cond}(A)=1$, akkor $μ_1 = μ_2 = … = μ_n$, és

$$\frac{|| Δx ||}{||x ||} =\frac{|| Δb ||}{||b ||}$$

de ha, például, $\operatorname{cond}(A)=10^6$, akkor

$$\frac{|| Δx ||}{||x ||} \leqslant 10^6\frac{|| Δb ||}{||b ||}$$

ami azt jelenti, hogy a megoldás hibabecslésének az értéke nagyon megnövekszik.

2) Most azt feltételezzük, hogy a hibát az $A$ mátrix tartalmazza. Akkor az egyenletrendszerben $A$ helyet $A+ΔA$ lesz megadva. Akkor

$$(A +Δb)\cdot(x +Δx) = b \tag{7.60a}\label{eq:7.60a}$$ (7.60a)

és

$$x +Δx = (A +Δb)^{-1}b\tag{7.61a}\label{eq:7.61a}$$ (7.61a)

$$Δx = \left[(A +Δb)^{-1}-A^{-1}\right]b \tag{7.62a}\label{eq:7.62a}$$ (7.62a)

Legyen

$$B = A +ΔA\tag{7.63a}\label{eq:7.63a}$$ (7.63a)

akkor

$$B^{-1}- A^{-1} = A^{-1}(A-B) B^{-1}$$

$$Δx = -A^{-1} (ΔA)^{-1} (A +ΔA)^{-1} b = -A^{-1} (ΔA) (x +Δx)$$

$$|| Δx || \leqslant || A^{-1}||\, || ΔA ||\, ||x + Δx ||$$

$$\frac{|| Δx ||}{||x + Δx ||} \leqslant \operatorname{cond}(A) \frac{|| ΔA ||}{||A||} \tag{7.64a}\label{eq:7.64a}$$ (7.64)

Meg lehet mutatni, ha a $\displaystyle\frac{|| ΔA ||}{||A||}$ értéke kicsi, akkor

$$\frac{||Δx||}{||x||} \leqslant \operatorname{cond}(A) \frac{||ΔA||}{||A||} \tag{7.35a}\label{eq:7.35a}$$ (7.35)

Ha az $A$ mátrix ortogonális, akkor $\operatorname{cond}(A)=1$, és a mátrix jól kondíciónál. Előfordulhat, hogy a legegyszerűbb mátrixok is lehetnek rosszul kondicionáltak.

Megjegyzés. A $\operatorname{cond}(A)$ értéke sokkal fontosabb tényező az $Ax=b$ feladat szempontjából, mint a mátrix determinánsa, vagy az $n$ nagyságrendje.

7.2. Példa

$$A=\begin{pmatrix} 1& 0,\!99\\ 0,\!99 & 0,\!98 \end{pmatrix}$$

$$Ax = λx$$

$$\begin{vmatrix} 1-\lambda& 0,\!99\\ 0,\!99 & 0,\!98-\lambda \end{vmatrix}=0$$

Az $A$ mátrix sajátértékei:

$$λ_1 = 1,\!9805, \quad λ_2 = 0,\!00005.$$

Mivel

$$A = A^{T},\quad A\,A^{T} = A^2,$$

ezért a $AA^{T}$ mátrix sajátértékei $1,\!98052$, $0,\!000052$ lesznek.

Kiszámítva a

$$μ_1 = 0,\!00005,\quad μ_2 = 1,\!9805$$

értékekeit, megállapítjuk, hogy a

$$\operatorname{cond}( A) = 39600$$

Ez egy nagyon rosszul kondicionált feladat. Mivel a mátrix rosszul kondicionált, az egyenletrendszer megoldásakor nehézségekre lehet számítani.

$$x_1 + 0,\!99 x_2 = 1,\!99$$

$$0,\!99x_1 + 0,\!98 x_2 = 1,\!97$$

Az egyenletrendszer pontos megoldása $(x_1, x_2 ) = (1, 1)$$

Feltételezve, hogy b hibát tartalmaz:

$$\Delta b=\begin{pmatrix} -0,\!000097\\ 0,\!000106 \end{pmatrix}$$

akkor az egyenletrendszer megváltozik

$$x_1 + 0,\!99 x_2 = 1,\!989903$$

$$0,\!99x_1 + 0,\!98 x_2 = 1,\!970106$$

és a megoldása $(x_1, x_2 ) = (3,\!0000, -1,\!0203)$ lesz. Ez azt jelenti, hogy a $b$ vektor kis változtatása nagy hibához vezet az eredményben:

$$\Delta x=\begin{pmatrix} 2,\!0000\\ -2,\!0203 \end{pmatrix}$$

Megállapítjuk a hibák közti összefüggéseket:

$$\|x\|=\sqrt{2},\quad\|\Delta x\|\approx 2\sqrt{2}\approx 2,\!82$$

$$\|b\|=2\sqrt{2},\quad\|\Delta b\|\approx 10^{-4}\sqrt{2},$$

$$\frac{|| Δx || }{||x ||} ≈ 40000 \frac{|| Δb ||}{||b ||}$$

Tehát, az eredmény hiba-becslése nagyon nagy, ami várható volt, mivel a mátrix kondíciószáma megfelel ennek az értéknek.

7.3. Példa

$$x_1 + 0\cdot x_2 = 1$$

$$x_1 + 0,\!01 x_2 = 1$$

$$μ = 200,$$

A megoldás: $x_1 = 1;\, x_2=0$

Megváltoztatjuk a $b$ értékét

$$Δb = (0; 0,\!01)$$

Akkor a

$$x_1 + 0 \cdot x_2 = 1$$

$$x_1 + 0,\!01 x_2 = 1,\!01$$

egyenletrendszer megoldása

$$x_1 = 1; x_2=1$$

lesz.

$$\begin{matrix} a_{11}x_1 + a_{12}x_2 + …. + a_{1n}x_n = b_1\\ a_{21}x_1 + a_{22}x_2 + …. + a_{2n}x_n = b_2\\ ……………………………\\ a_{n1}x_1 + a_{n2}x_2 + …. + a_{nn}x_n = b_n \end{matrix}\tag{7.35}\label{eq:7.35}$$

(7.35)

vagy

$$Ax = b\tag{7.36}\label{eq:7.36}$$ (7.36)

ahol $$ A=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix}=(a_{ij})^{n,n}_{i,j=1}, \tag{7.37}\label{eq:7.37}$$ MATH (7.37)

$$b^{T} = (b_1, b_2, … , b_n)\tag{7.38}\label{eq:7.38}$$ (7.38)

Gauss-eliminációs módszer (kiküszöböléses módszer)

A Gauss módszer algoritmusának a végrehajtása két lépésben történik.

1. Az egyenletrendszert azonos átalakításokkal felső háromszög alakúra hozzuk.

2. megoldjuk az így kapott háromszögmátrixú egyenletrendszert.

a). Ha $a_{11} ≠ 0$, akkor kinullázzuk az $a_{11}$ alatti együtthatókat, úgy hogy

az $i$-ik sorból kivonjuk az első sor s-szorzatát

$$s = \frac{a_{i1}}{a_{11}}\tag{7.39}\label{eq:7.39}$$ (7.39)

$$(a_{i1}-s\, a_{11})x_1 + (a_{i2}-s\, a_{12})x_2 + … + (a_{in}-s\, a_{1n})x_n = b_i – s\, b_{1} \tag{7.40}\label{eq:7.40}$$ (7.40)

Az első oszlop $a_{11}$ alatti együtthatók kinullázása a $\eqref{eq:7.39}$, $\eqref{eq:7.40}$ (7.39),(7.40) alapján a következő algoritmus szerint történik

$$s = \frac{a_{i1}}{ a_{11}}$$

$$a_{ij}= a_{ij} - s\, a_{1j},\quad j = 2, 3, …, n$$

$$b_i= b_i - s\, b_1 \quad i = 2, 3, …, n $$

Az átalakított egyenletrendszer:

$$\begin{equation}\begin{aligned} a_{11}x_1 + a_{12}x_2 + … + a_{1n}x_n &= b_1 \\ a_{22}x_2 + … + a_{2n}x_n &= b_2 \\ \cdots\cdots\cdots\cdots\cdots&\cdots\\ a_{n2}x_2 + … + a_{nn}x_n &= b_n \end{aligned}\end{equation} \tag{7.41}\label{eq:7.41}$$ (7.41) Ha $a_{22} ≠ 0$, akkor az $a_{22}$ alatti együtthatókat kinullázzuk: az $i$-ik sorból kivonjuk a második sor s-szorzatát, és így tovább folytatjuk. Ha $a_{kk} \neq 0$, akkor az $a_{kk}$ alatti együtthatókat kinullázzuk: az $i$-ik sorból kivonjuk a $k$-ik sor $s$-szorzatát.

$$s = \frac{a_{ik}}{a_{kk}}$$

$$a_{ij} = a_{ij} - s\,a_{kj}, \quad j = k+1, … , n$$

$$b_i = b_i - s\,b_k \quad i = k+1, … , n$$

A kinullázást addig folytatjuk, amíg az $a_{kk} ≠ 0$, és $k\leqslant n - 1$. Ha sikerült a mátrixot felső háromszög alakra hozni, akkor az egyenletet visszahelyettesítéssel könnyen megoldjuk.

Gauss-módszer algoritmusa

1. lépés.

$$ \begin{equation}\begin{aligned} &\textbf{for}\, k \leftarrow \overline{1,n - 1}\, \textbf{do}\\ &\quad\textbf{for}\, i \leftarrow \overline{k+1,n}\, \textbf{do}\\ &\qquad s \leftarrow \frac{a_{ik}}{a_{kk}}\\ &\qquad a_{i,k+1 ..n} \leftarrow a_{i,k+1 ..n} - s\, a_{k,k+1 ..n}\\ &\qquad b_i \leftarrow b_i - s\, b_k\\ &\quad \textbf{end for}\\ &\textbf{end for} \end{aligned}\end{equation} $$ 2. lépés. $$ \begin{equation}\begin{aligned} &x_n \leftarrow \frac{b_n}{a_{nn}}\\ &\textbf{for}\, i \leftarrow \overline{n-1, 1}\, \textbf{do}\\ &\qquad x_i\leftarrow\frac{b_i-\displaystyle\sum_{j=i+1}^na_{ij}x_j}{a_{ii}}\\ &\textbf{end for}\\ \end{aligned}\end{equation} $$ A Gauss-módszer műveletigénye: $$\frac{2n^3}{3} + \mathcal{O}(n^2)$$ A Gauss módszereknek több változata is létezik, amelyek a mátrixok tárolásával, eliminációk sorrendjével, a kerekítési hibák megelőzésének stratégiájával különböznek egymástól. A szimmetrikus mátrix esetén a módszernek vannak speciális változatai. $$$$

Ha $a_{kk} \neq 0$, akkor a sorok vagy oszlopok felcserélésével megkíséreljük elérni, hogy $a_{kk}$ ne legyen zérus. Az $a_{kk}\,k$-ik pivot, vagy főelemnek nevezzük. A sorok felcserélését pivotálási, vagy főelem-kiválasztási eljárásnak nevezzük. Pivot elemnek azt az elemet kell választani,a melynek nagy az abszolút értéke.

7.4. Példa

a) $$\begin{equation}\begin{aligned} 10^{-17}x + y &=1 \\ x + y &=2 \\ \end{aligned}\end{equation}$$ a megoldás: $$x=\frac{1}{1-10^{-17}},\quad y = 1-\frac{10^{-17}}{1-10^{-17}}$$ b) $$\begin{equation}\begin{aligned} x + y &=2 \\ 10^{-17}x + y &=1\\ \end{aligned}\end{equation}$$ a megoldás: $$x = 1,\quad y = 1.$$ Részleges főelem-kiválasztás. A $k$-ik lépésben a $k$ -ik oszlop $a_{jk}\, (k \leqslant j \leqslant n)$ maximális abszolút értékű elemet kell kiválasztani.

A pivotolás után

$$|a_{kk}|=\max_{k \leqslant j \leqslant n}|a_{jk}| \tag{7.42}\label{eq:7.42}$$ MATH (7.42)

Részleges főelem-kiválasztás algoritmusa:

$$\begin{equation}\begin{aligned} &\textbf{for}\, k \leftarrow \overline{1,n-1}\,\textbf{do} \\ &\quad|a_{qk}|\leftarrow\max_{k \leqslant j \leqslant n}|a_{jk}|\\ &\quad\textbf{ha }\, k≠ q \textbf{ akkor }\{\text{csere: a }k\text{-ik és }q\text{-ik sorok}\}\\ &\quad\textbf{for}\, i \leftarrow\overline{k+1,n}\,\textbf{do}\\ &\qquad s \leftarrow \frac{a_{ik}}{a_{kk}}\\ &\qquad a_{i, k+1..n} \leftarrow a_{i, k+1..n} - s\, a_{k, k+1..n}\\ &\qquad b_i = b_i - s\, b_k\\ &\quad\textbf{end for}\\ &\textbf{end for} \end{aligned}\end{equation}$$ Teljes főelem-kiválasztás. A $k$-ik lépésben az $a_{ik}\ (k \leqslant i \leqslant n, k \leqslant j \leqslant n )$ mátrixelemek maximális abszolút értékű elemet kell kiválasztani.

A pivotolás után

$$|a_{kk}|=\max_{k \leqslant i,j \leqslant n}|a_{jk}| \tag{7.43}\label{eq:7.43}$$ MATH (7.43)

Oszlopcsere esetén az $x_k$ változók is helyet cserélnek.

7.5. Példa

Oldjuk meg a

$$1,\!1161 x_1 + 0,\!1254 x_2 + 0,\!1397 x_3 + 0,\!1490 x_4 = 1,\!5471$$

$$0,\!1582 x_1 + 1,\!1675 x_2 + 0,\!1768 x_3 + 0,\!1871 x_4 = 1,\!6471$$

$$0,\!1968 x_1 + 0,\!2071 x_2 + 1,\!2168 x_3 + 0,\!2271 x_4 = 1,\!7471$$

$$0,\!2368 x_1 + 0,\!2471 x_2 + 0,\!2568 x_3 + 1,\!2671 x_4 = 1,\!8471$$

egyenletrendszert a főelem-kiválasztásos Gauss-módszerrel.

a kiválasztott főelemet $a_{i1}^*$ jelel jelöljük.

$$m_i = - \frac{a_{ij}}{a_{ij}^*}$$

$$\begin{equation}\begin{aligned} &1,\!06616\ x_1 &= 1,\!10944 \\ &0,\!10492\ x_1 + 1,\!11170\ x_2 &= 1,\!20639 \\ &0,\!15436\ x_1 + 0,\!16281\ x_2 + 1,\!17077\ x_3 &= 1,\!41604 \\ &0,\!2368\ x_1 + 0,\!2471\ x_2 + 0,\!2568\ x_3 + 1,\!2671\ x_4 &= 1,\!84710 \\ \end{aligned}\end{equation}$$ $$x_1 = \frac{1,\!10944}{1,\!06616} = 1,\!04059,$$ $$x_2 = \frac{1,\!20639 - 0,\!10492\cdot 1,\!04059}{1,\!11170} = 0,\!98697,$$ $$x_3 = 0,\!93505,$$ $$x_4 = 0,\!88130.$$ Javasoljuk megoldani a 10. Fejezetben található feladatokat. $$$$

Legyen $x^{(1)}$ a egyenletrendszer

$$Ax =b$$

Gauss-módszerrel előállított megoldása. Akkor a

$$r^{(1)} = b - A x^{(1)}$$

vektor a megoldás pontosságát (az eltérést) fejezi ki. Utána megoldjuk a

$$Az = r^{(1)}$$

egyenletrendszert, amelynek a megoldását $z(1)$ jelöljük. Ha $z(1)$ pontosan van kiszámítva, akkor

$$x^{(2)} = x^{(1)} + z^{(1)}$$

lesz a pontos megoldás, mivel

$$Ax^{(2)} = A(x^{(1)} + z^{(1)}) = Ax^{(1)} + Az^{(1)} =$$

$$=Ax^{(1)} + r^{(1)} = b$$

Ha a $z(1)$ értéke is tartalmaz hibát, akkor hasonló képen folytatjuk a megoldás iterációs javítását

$$r^{(2)} = b - A x^{(2)}$$

és utána hasonlóan megkapjuk a $z^{(2)}$ , $x^{(3)}$ értékeket. Ha tovább folytatjuk az iterációkat, akkor a következő

$$x^{(1)}, x^{(2)}, …,x^{(k)}, …$$

sorozatot kapunk. Ez a sorozat gyorsan konvergál a $x*$ megoldáshoz, ha lépésről lépésre a $r(k)$ eltérések nagyobb pontossággal lesznek kiszámítva. A hiba-becslés az első lépés után:

$$e^{(1)} = x^{(1)}-A^{-1}b=A^{-1}(A x^{(1)}-b)=–A^{-1}r^{(1)}$$

$$|| e^{(1)} ||\leqslant|| A^{-1}||\, ||r^{(1)}||$$

A következő közelítések hiba-becslései:

$$|| e^{(k)} ||\leqslant|| A^{-1}||\, ||r^{(k)}|| \tag{7.44}\label{eq:7.44}$$ (7.44)

7.6. Példa

$$Ax = b$$

A nyolc tizedes számjeggyel kiszámított eredmény:

$$x^* = A^{-1}b = (1,\!22402691; 1,\!24536512)$$

A Gauss-módszer a következő megoldást adja:

$$x^{(1 )}= (1,\!2560; 1,\!2121),$$

Ez a megoldás nagy hibát tartalmaz,\!

Végrehajtjuk az első iterációs javítást:

$$e^{(1 )}= (0,\!0320; –0,\!0333),$$

$$r^{(1 )}= (0,\!0000057; 0,\!000033715),$$

A $Az = r^{(1 )}$ megoldása:

$$z^{(1 )}= (–0,\!03221; 0,\!033502),$$

A további lépések eredményei:

$$x^{(2 )}= (1,\!2238; 1,\!2456),$$

$$e^{(2 )}= (–0,\!000272; 0,\!000235),$$

$$r^{(2 )}= (0,\!00000118; 0,\!0000009),$$

$$z^{(2 )}= (0,\!0002215; –0,\!0002365),$$

$$x^{(3 )}= (1,\!2240; 1,\!2454),$$

$$e^{(3 )}= (–0,\!0000272; 0,\!000351),$$

$$r^{(3 )}= (–0,\!00000682; –0,\!00000659),$$

$$z^{(3 )}= (0,\!00002717; –0,\!00003515),$$

$$x^{(4 )}= (1,\!22402717; 1,\!24536485),$$

Ha nagyobb pontosságra van szükségünk, akkor ezeket az iterációkat tovább folytathatjuk.

A Gauss-Jordan módszer a Gauss-módszer olyan változata, amely a eliminációkat nem csak a főátló alatti sorokra alkalmazza $(k>i),≠$ hanem a főátló feletti elemekhez is $(k≠i)$. Mivel a Gauss-Jordan módszer lényegesen nem tér el a Gauss-módszertől, ezért annak a működését csak egy példán mutatjuk be.

7.7. Példa

A következő egyenletrendszert oldjuk meg a Gauss-Jordan módszerrel.

$$1,\!1161 x_1 + 0,\!1254 x_2 + 0,\!1397 x_3 + 0,\!1490 x_4 = 1,\!5471$$

$$0,\!1582 x_1 + 1,\!1675 x_2 + 0,\!1768 x_3 + 0,\!1871 x_4 = 1,\!6471$$

$$0,\!1968 x_1 + 0,\!2071 x_2 + 1,\!2168 x_3 + 0,\!2271 x_4 = 1,\!7471$$

$$0,\!2368 x_1 + 0,\!2471 x_2 + 0,\!2568 x_3 + 1,\!2671 x_4 = 1,\!8471$$

$$x_1 = 1,\!04059, x_2 = 0,\!98697, x_3 = 0,\!04059, x_4= 0,\!88130.$$

Javasoljuk megoldani a 10. Fejezetben található feladatokat.

A Gauss eliminációs módszer algebrai alapját a következő tétel fejezi ki. ($L$, Lower - alsó, $U$, Upper - felső).

7.2 LU-tétel

Legyen $A\in \mathbb{R}^{n\times n}$ mátrix, $A_k$ a mátrix főminorja, amely a mátrix első k soraiból és oszlopaiból van szerkesztve. Legyenek $|A_k| ≠ 0$, $k= 1, 2, …, n - 1$. Akkor létezik olyan egyetlen alsó háromszög mátrix $L = (l_{ij})$, $l_{11}= l_{22}= … = l_{nn}= 1$, és egyetlen felső háromszög mátrix $U = (u_{11})$, , hogy

$$A = LU$$

és

$$|A| = u_{11} u_{22} … u_{nn}$$

Ha $A$ – szimmetrikus, pozitív definiált mátrix, akkor létezik olyan egyetlen felbontás

$$A = GG^{T}$$

ahol $G$ alsó háromszög mátrix, melynek a fő-diagonális elemei pozitív valós számok.

Az $LU$-felbontást alkalmazhatjuk az $Ax=b$ egyenletrendszer megoldására.

Legyen

$$A = LU\tag{7.45}\label{eq:7.45}$$ (7.45)

ahol

$$L=\begin{pmatrix} 1 & 0 & \cdots & 0\\ l_{21} & 1 & \cdots & 0\\ \cdots & \cdots & \cdots & \cdots\\ l_{n1} & l_{n2} & \cdots & 1 \end{pmatrix} \tag{7.46}\label{eq:7.46}$$ MATH (7.46)

alsó háromszög mátrix, és

$$U=\begin{pmatrix} u_{11} & u_{12} & \cdots & u_{1n}\\ 0 & u_{22} & \cdots & u_{2n}\\ \cdots & \cdots & \cdots & \cdots\\ 0 & 0 & \cdots & u_{nn} \end{pmatrix} \tag{7.47}\label{eq:7.47}$$ MATH (7.47)

felső háromszög mátrix. Akkor

$$Ax = (LU)x = L(Ux) = b$$

alapján az egyenletrendszer felbontható két egyszerűbb egyenletrendszerre:

$$Ux =y,\quad Ly =b$$

Az LU-módszer algoritmusa.

1 lépés. Hajtsuk végre a

$$A = LU$$

felbontást. Ezt a mátrixszorzat tulajdonsága alapján lehet végrehajtani.

2 lépés. Oldjuk meg a

$$Ly =b$$

egyenletrendszert.

3 lépés. Oldjuk meg a

$$Ux =y$$

egyenletrendszert.

Az LU-módszer különösen akkor előnyös, ha egy azonos együtthatómátrixszal több egyenletrendszert kell megoldani

$$Ax = b_1,\quad Ax = b_2,\quad\ldots\quad Ax = b_k$$

mivel az

$$A = LU$$

felbontást csak egyszer kell végrehajtani.

7.8. Példa

$$x_1 + 2x_2 - x_3 = 2$$

$$-x_1 -2x_2 + 2x_3 = 0$$

$$2x_1 - x_2 + x_3 = 2$$

$$A=\begin{pmatrix} 1 & 2 & -1\\ -1 & -2 & 2\\ 2 & -1 & 1 \end{pmatrix}$$

Első lépés.

$$LU=\begin{pmatrix} 1 & 0 & 0\\ l_{21} & 1 & 0\\ l_{31} & l_{32} & 1 \end{pmatrix}\cdot \begin{pmatrix} u_{11} & u_{12} & u_{13}\\ 0 & u_{22} & u_{23}\\ 0 & 0 & u_{33} \end{pmatrix}= \begin{pmatrix} 1 & 2 & -1\\ -1 & -2 & 2\\ 2 & -1 & 1 \end{pmatrix} $$

$$u_{11} = 1, \quad u_{12} = 2,\quad u_{13} = -1,$$

$$l_{21} = -1,\quad l_{31} = 2,$$

$$l_{21} u_{12} + u_{22} = -1,\quad u_{22} = 1, \quad l_{21} u_{13} + u_{23} = 2,\quad u_{23} = 1,$$

$$l_{31} u_{12} + l_{32} u_{22} = -1,\quad l_{32} = -5,$$

$$l_{31} u_{13} + l_{32} u_{23}+ u_{33} = 1,\quad u_{33} = 8.$$

$$L=\begin{pmatrix} 1 & 0 & 0\\ -1 & 1 & 0\\ 2 & -5 & 0 \end{pmatrix} ,\quad U=\begin{pmatrix} 0 & 2 & -1\\ 0 & 1 & 1\\ 0 & 0 & 8 \end{pmatrix}$$

Ellenőrzés:

$$ \begin{pmatrix} 1 & 0 & 0\\ -1 & 1 & 0\\ 2 & -5 & 0 \end{pmatrix} \cdot \begin{pmatrix} 0 & 2 & -1\\ 0 & 1 & 1\\ 0 & 0 & 8 \end{pmatrix} =\begin{pmatrix} 1 & 2 & -1\\ -1 & -2 & 2\\ 2 & -1 & 1 \end{pmatrix}$$

Második lépés.

$$\begin{pmatrix} 1 & 0 & 0\\ -1 & 1 & 0\\ 2 & -5 & 0 \end{pmatrix} \cdot \begin{pmatrix} y_1\\ y_2\\ y_3 \end{pmatrix} = \begin{pmatrix} 2\\ 0\\ 0 \end{pmatrix}, $$

$$(y_1, y_2, y_3) = (2, 2, 8)$$

Harmadik lépés.

$$ \begin{pmatrix} 0 & 2 & -1\\ 0 & 1 & 1\\ 0 & 0 & 8 \end{pmatrix} \cdot \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} = \begin{pmatrix} 2\\ 2\\ 8 \end{pmatrix}, $$

$$(x_1, x_2, x_3) = (1, 1, 1)$$

$$\begin{matrix} a_{11}x_1 + a_{12}x_2 + …. + a_{1n}x_n = b_1\\ a_{21}x_1 + a_{22}x_2 + …. + a_{2n}x_n = b_2\\ ……………………………\\ a_{n1}x_1 + a_{n2}x_2 + …. + a_{nn}x_n = b_n \end{matrix}\tag{7.48}\label{eq:7.48}$$

vagy

$$Ax = b$$

$A$ - szimmetrikus mátrix, és annak a felbontása:

$$A = T^\prime\cdot T\tag{7.49}\label{eq:7.49}$$ (7.49)

$$T=\begin{pmatrix} t_{11} & t_{12} & \cdots & t_{1n}\\ 0 & t_{22} & \cdots & t_{2n}\\ \cdots & \cdots & \cdots & \cdots\\ 0 & 0 & \cdots & t_{nn} \end{pmatrix}$$

$$T^\prime= \begin{pmatrix} t_{11} & 0 & \cdots & 0\\ t_{12} & t_{22} & \cdots & 0\\ \cdots & \cdots & \cdots & \cdots\\ t_{1n} & t_{2n} & \cdots & t_{nn} \end{pmatrix}$$

A (7.49) alapján:

$$t_{11}=\sqrt{a_{11}},\quad t_{ij}=\frac{a_{1j}}{t_{11}},\quad j>1$$

$$t_{ii}=\sqrt{a_{ii}-\sum_{k=1}^{i-1}t_{ki}^2},\quad i=2,3,\ldots,n $$

$$t_{ij}=\frac{a_{ij}-\displaystyle\sum_{k=1}^{i-1} t_{ki}t_{kj}}{t_{ii}} \quad j=i+1,\ldots,n. $$

$$t_{ij} =0,\quad j< i$$

Akkor

$$A = b\ \,\Rightarrow\ \,(T^\prime\cdot T)x =b\ \,\Rightarrow\ \, T^\prime(Tx)=b\ \,\Rightarrow\ \,T^\prime y =b,$$

ahol

$$y =Tb.$$

Ez a módszer három lépésben valósítható meg.

1) A $T$ mátrix kiszámítása.

2) A

$$T^\prime y =b$$

egyenletrendszer megoldása (y vektor az ismeretlen): $$\begin{equation}\begin{aligned} &t_{11}\ y_1 &= b_1\\ &t_{12}\ y_1 + t_{22}\ y_2 &= b_2\\ &\cdots\cdots\cdots\cdots\cdots\cdots&\\ &t_{1n}\ y_1 + t_{2n}\ y_2 + \cdots + t_{nn}\ y_n &= b_2\\ \end{aligned}\end{equation}$$ $$y_i=\frac{b_1}{t_{11}},\quad y_{i}=\frac{b_{i}-\displaystyle\sum_{k=1}^{i-1} t_{ki}y_{k}}{t_{ii}}, \quad i>1. $$ 3) A $$Tx = y$$ egyenletrendszer megoldása: $$y_n=\frac{y_n}{t_{nn}},\quad x_{i}=\frac{y_{i}-\displaystyle\sum_{k=1}^{i-1} t_{ik}x_{k}}{t_{ii}}, \quad i<n. $$ Megkaptuk a megoldást - az $x$ vektort.

Javasoljuk megoldani a 10. Fejezetben található feladatokat.

A lineáris egyenletrendszer iterációs megoldásának az általános képlete:

$$x^{(k+1)} = F_k(x^{(0)}, x^{(1)}, … , x^{(k)})\tag{7.50}\label{eq:7.50}$$ (7.50)

ahol az $x^{(0)}$ a megoldás kezdő közelítése, $F_k$ –függvény, amely függhet az $A$ mátrixtól, $b$-től, $k$-tól, és az előző $x^{(0)}, x^{(1)}, … , x^{(k)}$ közelítésektől.

Az iterációs módszert első rendűnek nevezzük, ha $F_k$ csak a $x^{(k)}$ függ.

A módszer stacionárius, ha $F$ nem függ a $k$-tól. A legegyszerűbb esetben $F$ lineáris

$$x^{(k+1)} = B_kx^{(k)} + c^{(k)}\tag{7.51}\label{eq:7.51}$$ (7.51)

$B_k \in \mathbb{R}^{n\times n}$ mátrix, $c^{(k)}\in \mathbb{R}^{n}$vektor.

Az iterációs módszerektől elvárjuk azt, hogy ha a $\eqref{eq:7.51}$ (7.51)-ben a $x^{(k+1)}, x^{(k)}$ helyet behelyettesítjük a $Ab^{-1}$ pontos megoldást, akkor

$$A^{-1}b = B_k A^{-1}b + c^{(k)}\tag{7.52}\label{eq:7.52}$$ (7.52)

egyenlőséget kapunk. Innen

$$c^{(k)} = (I -B_k)A^{-1}b = C_k b\tag{7.53}\label{eq:7.53}$$ (7.53)

ahol

$$C_k = (I -B_k)A^{-1}$$

vagy, átalakítva:

$$B_k + C_kA =I$$

Ez alapján átírhatjuk a $\eqref{eq:7.51}$(7.51)-et:

$$x^{(k+1)} = B_kx^{(k)}+ C_kb\tag{7.54}\label{eq:7.54}$$ (7.54)

vagy

$$x^{(k+1)} = x^{(k)}- C_k (Ax^{(k)} - b)\tag{7.55}\label{eq:7.55}$$ (7.55)

Ha létezik $C_k^{-1}$ ,akkor a $\eqref{eq:7.54}$ (7.54)-et így lehet kifejezni:

$$D_k x^{(k+1)} + E_k x^{(k)} = b\tag{7.56}\label{eq:7.56}$$ (7.56)

úgy hogy legyen

$$D_k + E_k = A\tag{7.57}\label{eq:7.57}$$ (7.57)

A $\eqref{eq:7.56}$(7.56) alapján a $x^{(k+1)}$ csak implicit módon fejeztető ki. Ezért fontos, hogy a $D_k^{-1}$ mátrixok elemeit könnyen lehessen kiszámítani. Leggyakrabban a $D_k$ mátrixokat úgy szerkesztik, hogy az legyen diagonálmátrix vagy háromszög mátrix.

Diagonálmátrix esetén az iterációs módszert teljes lépésesnek nevezzük, háromszög mátrix esetén a módszer, pedig egylépéses.

Ezek a módszerek a (7.54),(7.55) képleteken alapszanak. Megvizsgáljuk a módszer konvergenciáját. A (7.54) alapján:

$$x^{(k+1)} -A^{-1}b = B_k(x^{(k)} -A^{-1}b )\tag{7.58}\label{eq:7.58}$$ (7.58)

Ha ezt a képletet alkalmazzuk a $k=0, 1, …, m$ értékek mellet, akkor:

$$x^{(k+1)} -A^{-1}b = B_m B_{m-1}… B_1 B_0 (x^{(0)} -A^{-1}b ) \tag{7.59}\label{eq:7.59}$$ (7.59)

és

$$||x^{(k+1)}-A^{-1}b || \leqslant ||B_m||\, ||B_{m-1}||… ||B_1||\, ||B_0||\, || x^{(0)} -A^{-1}b ||\tag{7.60}\label{eq:7.60}$$ (7.60)

Ha $$||B_m||\, ||B_{m-1}||… ||B_1||\, ||B_0|| \xrightarrow[m\to 0]{}0 \tag{7.61}\label{eq:7.61}$$

(7.61)

akkor $$||x^{(m+1)}-A^{-1}b ||\xrightarrow[m\to 0]{}0$$

és $$x^{(m+1)}\xrightarrow[m\to 0]{} A^{-1}b$$ MATH

Ha a

$$||B_m|| < γ< 1,$$

akkor teljesül a $\eqref{eq:7.61}$ (7.61) feltétel.

Ha az iterációs folyamat stacionárius, $B_m = B$, akkor lehet pontosabb feltételt megfogalmazni.

7.3. Tétel

A stacionárius lineáris iterációs folyamat

$$x^{(k+1)} = B_kx^{(k)} + C_kb$$

akkor és csak akkor konvergens tetszőléges $x^{(0)}$ és $b$ esetén, ha a $B$ mátrix összes saját értékei

$$|λ_i | < 1$$

A tételben leírt feltétel nehezen ellenőrizhető, mivel a $λ_i$ kiszámítása gyakran bonyolultabb lehet, mint az egyenletrendszer megoldása. Ezért helyette egyszerűbb szükséges feltételeket alkalmaznak.

A Jacobi-iterációs módszer a lineáris teljes lépéses első rendű módszerek legismertebb változata.

Legyen $x^*$ a $Ax =b$ egyenletrendszer megoldása.

Az $A$ mátrixot úgy bontjuk fel:

$$A = D + L + U\tag{7.62}\label{eq:7.62}$$ (7.62)

ahol

$$D=\begin{pmatrix} a_{11} & 0 & \cdots & 0\\ 0 & a_{22} & \cdots & 0\\ 0 & 0 & \cdots & \cdots\\ 0 & 0 & \cdots & a_{nn} \end{pmatrix},$$

diagonálmátrix,

$$L=\begin{pmatrix} 0 & 0 & \cdots & 0\\ a_{21} & 0 & \cdots & 0\\ \cdots & \cdots & \cdots & \cdots\\ a_{n1} & a_{n2} & \cdots & 0 \end{pmatrix},$$

alsó háromszög mátrix, és

$$U=\begin{pmatrix} 0 & a_{12} & \cdots & a_{1n}\\ 0 & 0 & \cdots & a_{2n}\\ \cdots & \cdots & \cdots & \cdots\\ 0 & 0 & \cdots & 0 \end{pmatrix}$$

felső háromszög mátrix.

Akkor

$$Dx = - (L + U)x + b$$

és

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

$$x = Bx + c\tag{7.63}\label{eq:7.63}$$ (7.63)

ahol

$$B = - D^{-1}(L + U) \tag{7.64}\label{eq:7.64}$$ (7.64)

$$c =- D^{-1}b \tag{7.65}\label{eq:7.65}$$ (7.65)

Legyen $x^{(0)}$ a kezdővektor. Ha behelyettesítjük az $x^{(0)}$ a $\eqref{eq:7.63}$(7.63) jobboldali részébe, akkor megkapjuk az $x^{(1)}$ vektort:

$$x^{(1)} = Bx^{(0)} +c$$

Mivel $x^{(1)} ≠ x^{(0)}$, akkor $x^{(1)}$ még nem lehet az egyenletrendszer megoldása, és ezért szükség van a következő iterációra:

$$x^{(2)} = Bx^{(1)} +c $$

Tovább folytatjuk, amíg nem érjük a szükséges pontosságot, ami a két szomszédos közelítő megoldás közti távolsággal mérhető:

$$|| x^{(2)} - x^{(1)} ||\leqslant ε$$

Az iterációs eljárás általános képlete:

$$x^{(m+1)} = Bx^{(m)} +c, \quad m =0, 1, 2, … \tag{7.66}\label{eq:7.66}$$ (7.66)

Az átalakított egyenletrendszer másik alakja

$$ \begin{equation}\begin{aligned} &x_1^{(m+1)} = -\frac{a_{12}x_2^{(m)} + a_{13}x_3^{(m)} + … + a_{1n}x_n^{(m)} - b_1}{a_{11}} \\ &x_2^{(m+1)} = –\frac{a_{21}x_1^{(m)} + a_{23}x_3^{(m)} + … + a_{2n}x_n^{(m)} - b_2}{a_{22 } }\\ &…………………………\\ &x_n^{(m+1)} = -\frac{a_{n1}x_1^{(m)} + a_{n2}x_2^{(m)} + … + a_{n, n-1}x_{n-1}^{(m)} - b_n}{a_{nn}} \end{aligned}\end{equation} \tag{7.67}\label{eq:7.67}$$ (7.67) vagy $$x^{(m+1)} = \widetilde{A}x^{(m)}+\widetilde{b} \tag{7.68}\label{eq:7.68}$$ (7.68) $$$$

$$\widetilde{A}=\begin{pmatrix} 0 & \displaystyle\frac{a_{12}}{a_{11}} & \cdots & \displaystyle\frac{a_{1n}}{a_{11}} \\ \displaystyle\frac{a_{21}}{a_{22}} & 0 & \cdots & \displaystyle\frac{a_{2n}}{a_{22}} \\ \cdots &\cdots &\cdots &\cdots \\ \displaystyle\frac{a_{n1}}{a_{nn}} & \displaystyle\frac{a_{n1}}{a_{nn}} & \cdots & 0 \\ \end{pmatrix} \tag{7.69}\label{eq:7.69}$$ (7.69)

$$\widetilde{b}=\begin{pmatrix} \displaystyle\frac{b_1}{a_{11}} \\ \displaystyle\frac{b_2}{a_{22}} \\ \cdots \\ \displaystyle\frac{b_n}{a_{nn}} \\ \end{pmatrix} \tag{7.70}\label{eq:7.70}$$ MATH (7.70)

Ha $x_0= c$, akkor:

$$x^{(m+1)} =[B^{(m+1)} + B^{(m)} +… + B + I] c, \tag{7.71}\label{eq:7.71}$$ (7.71)

$I$ – egységmátrix.

Általános esetben ez az iterációs folyamat nem biztos, hogy konvergens. Ahhoz, hogy elkerüljük egy végtelen ciklust, az algoritmusban meg kell adni az iterációk maximális számát, amely után az befejeződik.

7.9. Példa

Oldjuk meg az egyenletrendszert, ha

$$\widetilde{A}=\begin{pmatrix}&\\ 6,\!1818 & 0,\!1818 & 0,\!3141 & 0,\!1415 & 0,\!1516 & 0,\!2141 \\ & 7,\!1818 & 0,\!2141 & 0,\!1815 & 0,\!1526 & 0,\!3114 \\ & & 8,\!2435 & 0,\!1214 & 0,\!2516 & 0,\!2618 \\ & & & 9,\!3141 & 0,\!3145 & 0,\!6843 \\ & & & & 5,\!3116 & 0,\!8998 \\ & & & & & 4,\!1313 \\&\\ \end{pmatrix}$$

szimmetrikus mátrix, $$b=\begin{pmatrix} 7,\!1818\\ 8,\!2435\\ 9,\!3141\\ 5,\!3116\\ 4,\!1313\\ 3,\!1816\\ \end{pmatrix}$$ MATH

Akkor az átalakított (7.69) mátrix $$A=\begin{pmatrix}&\\ 0 & 0,029409 & 0,050810 & 0,002289 & 0,024524 & 0,034634 \\ 0,025314 & 0 & 0,029811 & 0,025272 & 0,021248 & 0,043736 \\ 0,038103 & 0,025972 & 0 & 0,014727 & 0,030521 & 0,031758 \\ 0,015192 & 0,019487 & 0,013034 & 0 & 0,033765 & 0,073347 \\ 0,028541 & 0,028730 & 0,047368 & 0,059210 & 0 & 0,169430 \\ 0,051824 & 0,075376 & 0,063370 & 0,165638 & 0,217801 & 0 \\&\\ \end{pmatrix}$$

A következő táblázat tartalmazza az iterációkat. A kezdő iteráció

$$x^{(0)} =b,$$

a $b$ vektort a $\eqref{eq:7.70}$(7.70) szerint kell kiszámítani.

7.4. Tétel. (A konvergencia szükséges és elégséges feltétele).

A lineáris egyenletrendszer $\eqref{eq:7.66}$(7.66)-al meghatározott közelítő megoldása akkor és csak akkor konvergál minden $x(0)$ kezdővektor esetén, ha a $B$ mátrix sajátértékeinek az abszolút értéke $<1$.

7.5. Tétel A konvergencia elégséges feltételei.

Ha

$$\|B\|_1=\max_k\sum_{i=1}^n|b_{ik}|,\tag{7.72}\label{eq:7.72}$$

$$\|B\|_\infty=\max_i\sum_{k=1}^n|b_{ik}|, \tag{7.73}\label{eq:7.73}$$

$$\|B\|_E^2=\sqrt{\sum_{i=1}^n\sum_{k=1}^nb_{ik}^2}, \tag{7.74}\label{eq:7.74}$$

bármelyike kisebb 1-nél, akkor az $x^{(0)}$ tetszőleges kezdővektor esetén

$$x^{(m)}\xrightarrow[m\to\infty]{}x^*$$

ahol a $x^*$ – az egyenletrendszer megoldása.

Alkalmazzuk az ismert

$$A = B + C + D $$

felbontást, ahol a B diagonálmátrix, $C$ alsó háromszög mátrix, és

$c_{ii} =0, i = 1, 2, …, n, D$ felső háromszög mátrix, és $d_{ii} =0, i = 1, 2, …, n$. Kiválasztunk egy $ω ≠ 0$, és következő iterációs eljárást szerkesztünk:

$$(ω^{-1}B + C) x^{(k+1)}+[(1 - ω^{-1})B + D)]x^{(k)} =b \tag{7.74a}\label{eq:7.74a}$$ (7.74a)

Megoldjuk ezt az egyenletrendszert az $x(k+1)$ -ra

$$x_i^{(k+1)}=-\frac{\omega}{a_{ii}} \left[\sum_{j=1}^{i-1}a_{ij}x_i^{(k+1)}+\sum_{j=i+1}^{n}a_{ij}x_i^{(k)}-b_i\right]-(\omega-1)x_i^{(k)} \tag{7.75}\label{eq:7.75}$$ MATH (7.75)

$$i= 1, 2, ..., n$$

Ha $ω = 1$, akkor megkapjuk a Seidel-iterációs módszert.

Seidel-iterációs módszer (Gauss-Seidel módszer)

Formálisan ezt a módszert a Jacobi-iterációs módszer módosításának lehet tekinteni. Miután kiszámítottuk a x(m+1) vektor következő komponensét, azt még ugyan ebben az iterációban azonnal fel használjuk. Akkor a Seidel-iterációs módszert a következő képen lehet meghatározni:

$$ \begin{equation}\begin{aligned} &x_1^{(m+1)} = -\frac{a_{12}x_2^{(m)} + a_{13}x_3^{(m)} + … + a_{1n}x_n^{(m)} - b_1}{a_{11}} \\ &x_2^{(m+1)} = –\frac{a_{21}x_1^{(m+1)} + a_{23}x_3^{(m)} + … + a_{2n}x_n^{(m)} - b_2}{a_{22 } }\\ &…………………………\\ &x_n^{(m+1)} = -\frac{a_{n1}x_1^{(m+1)} + a_{n2}x_2^{(m+1)} + … + a_{n, n-1}x_{n-1}^{(m)} - b_n}{a_{nn}} \end{aligned}\end{equation} \tag{7.76}\label{eq:7.76}$$ A Seidel-iterációs módszer konvergenciája Feltételezve, hogy $ω =1$, megoldjuk a $\eqref{eq:7.74}$ (7.74) egyenletrendszert:

$$x^{(k+1)} = -(B +C)^{-1}D x^{(k)}+(B+C)^{-1}b \tag{7.77}\label{eq:7.77}$$ (7.77)

Ez a képlet azt mutatja, hogy a Seidel-módszer megegyezik a Jacobi-iterációs módszernek azzal a változatával, amelynek a mátrixa

$$-(B +C)^{-1}D$$

és akkor a Tétel 3 alapján a

Seidel-iterációs módszer akkor és csak akkor konvergens, ha a

$$-(B +C)^{-1}D$$

mátrix összes saját értékei $|λ_i|<1$, vagy másként fogalmazva:

$$\det(λI +-(B +C)^{-1}D) = 0$$

vagy

$$\det(λ(B +C) +D) = 0 \tag{7.78}\label{eq:7.78}$$ (7.78)

Ezt a feltételt így is lehet átírni:

$$ \begin{vmatrix} a_{11}\lambda & a_{12} & \cdots & a_{1n} \\ a_{21}\lambda & a_{22}\lambda & \cdots & a_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ a_{n1}\lambda & a_{n2}\lambda & \cdots & a_{nn}\lambda \end{vmatrix}=0$$

A Jacobi-iterációs módszer és a Seidel-iterációs módszer összehasonlítása azt mutatja, hogy létezhet három típusú feladat.

1) mind két módszer konvergens,

2) a Jacobi-iterációs módszer konvergens, a Seidel-iterációs módszer - nem,

3) a Seidel-iterációs módszer konvergens, a Jacobi-iterációs módszer - pedig nem.

Javasoljuk megoldani a 10. Fejezetben található feladatokat.

7.10. Példa

Megoldjuk az előző példát (7.9. Példa) az Seidel-iterációs módszerrel.