- Mátrixok és vektorok
- Vektorok, egyenesek és síkok egyenletei
- Vektorterek, független és összefüggő vektorok
- Lineáris egyenletrendszerek, mátrixok rangja és inverze
- Determináns, adjungált, kvadratikus alakok
- Sajátérték, sajátvektor, sajátfelbontás
- Lineáris leképezések
- Síkbeli és térbeli leképezések és mátrixaik
- Egyenletrendszerek optimális megoldása, pszeudoinverz
- Lineáris programozás alapok
- Vektornorma, mátrixnorma, mátrixok kondíciószáma
- Ortogonális mátrixok, Fourier-együtthatók, Gram-Schmidt ortogonalizáció
- Mátrixok LU-felbontása és QR-felbontása
- Iterációs módszerek egyenletrendszerek megoldására
- Komplex számok
- Polinomok
- Interpolációs polinomok
- Oszthatóság
- Euklideszi algoritmus, Diofantoszi egyenletek
- Kongruenciák, Euler-Fermat tétel
- Csoportok, gyűrűk, testek
Iterációs módszerek egyenletrendszerek megoldására
Kontrakció
Az $f:$ $R \mapsto R$ leképezést kontrakciónak nevezzük, ha létezik olyan $0<q<1$ valós szám, hogy minden $x \in R$ és $y \in R$ esetén
\( \mid f(x)-f(y) \mid \leq q \cdot \mid x -y \mid \)
Banach-féle fixponttétel
Hogyha az $f$ $R \mapsto R$ leképezés kontrakció, akkor egyértelműen létezik egy $x^{*} \in R$ fixpont, amelyre $f(x^{*})=x^{*}$ és tetszőleges $x_0$ pontból induló $x_{n+1}=f(x_n)$ sorozat konvergens és $x_n \rightarrow x^{*}$.
Iteráció gyorsasága
A konvergencia gyorsaságára a következő hibabecslés adható:
\( \mid x_n - x^{*} \mid \leq \frac{q^n}{1-q} \cdot \mid x_1 -x_0 \mid \)
Iterációs módszerek egyenletrendszer megoldására
Hogyha itt van ez az egyenlet...
\( 2x+1 = 5x-5 \)
Aminek a megoldása $x=2$, akkor megoldhatjuk iterációs módszerekkel is.
Az első lépés, hogy kifejezzük $x$-et, lehetőleg úgy, hogy az együtthatója 1-nél kisebb legyen:
\( x=\frac{2}{5}x+\frac{6}{5} \)
Így $f(x)=\frac{2}{5}x+\frac{6}{5}$ egy kontrakció, és a fixpontja $x^{*}=f(x^{*})$, ami éppen az egyenlet megoldása.
Ha most veszünk egy ilyen sorozatot:
$x_{n+1}=f(x_n) \qquad x_n \to x^{*}=2$
Akkor a fixponttétel miatt ez a sorozat konvergál a fixponthoz, vagyis az egyenlet megoldásához.
Ezt a sorozatot iterációs sorozatnak nevezzük, magát az eljárást pedig iterációnak.
Az iteráció lényege, hogy elkezdjük egyesével kiszámolni a sorozat tagjait. És minél több tagot számolunk ki, annál közelebb kerülünk a megoldáshoz.
$x_{n+1}=\frac{2}{5}x_n + \frac{6}{5} \qquad x_n \to x^{*}=2$
$x_0=0$
$x_1=\frac{2}{5}\cdot 0 + \frac{6}{5}=1,2$
$x_2=\frac{2}{5}\cdot 1,2 + \frac{6}{5}=1,68$
$x_3=\frac{2}{5}\cdot 1,68 + \frac{6}{5}=1,872$
$x_4=\frac{2}{5}\cdot 1,872 + \frac{6}{5}=1,9488$
$\dots$
$x_{10}=1,99979$
Jacobi iteráció
Legyen $A$ egy nxn-es reguláris mátrix, és az $A\underline{x}=\underline{b}$ egyenletrendszer megoldása $\underline{x}^{*}$. Ekkor az
$ \underline{x}^{(n+1)} = B \underline{x}^{(n)}+\underline{c}$
iterációt az egyenletrendszerrel konzisztensnek nevezzük, ha teljesül rá, hogy
$\underline{x}^{*}=B\underline{x}^{*}+\underline{c}$
Az $ \underline{x}^{(n+1)} = B \underline{x}^{(n)}+\underline{c}$ iteráció pontosan akkor tart az egyenletrendszer megoldásához, ha $ \rho{(B)}<1$
A Jacobi iteráció szerint:
\( \underline{x}^{(n+1)} = D^{-1} (-L-U) \underline{x}^{(n)} + D^{-1} \underline{b} \)
Spektrálsugár
Egy mátrix spektrálsugarát úgy kapjuk meg, hogy vesszük a sajátértékeinek az abszolútértékét, és ezek közül a legnagyobb a spektrálsugár.
Gauss-Seidel iteráció
Legyen $A$ egy nxn-es reguláris mátrix, és az $A\underline{x}=\underline{b}$ egyenletrendszer megoldása $\underline{x}^{*}$. Ekkor az
$ \underline{x}^{(n+1)} = B \underline{x}^{(n)}+\underline{c}$
iterációt az egyenletrendszerrel konzisztensnek nevezzük, ha teljesül rá, hogy
$\underline{x}^{*}=B\underline{x}^{*}+\underline{c}$
Az $ \underline{x}^{(n+1)} = B \underline{x}^{(n)}+\underline{c}$ iteráció pontosan akkor tart az egyenletrendszer megoldásához, ha $ \rho{(B)}<1$
A Gauss-Seidel iteráció szerint:
\( \underline{x}^{(n+1)} = (D+L)^{-1}(-U) \underline{x}^{(n)} + (D+L)^{-1} \underline{b} \)
Iteráció konvergenciája egyenletrendszereknél
Ha az $A\underline{x}=\underline{b}$ egyenletrendszer $A$ együtthatómátrixa szigorúan diagonális domináns, akkor a Jacobi és a Gauss-Seidel iterációk is bármely kezdővektor esetén az egyenletrendszer megoldásához konvergálnak.
Ha az $A\underline{x}=\underline{b}$ egyenletrendszer $A$ együtthatómátrixa szimmetrikus pozitív definit mátrix, akkor a Gauss-Seidel iteráció bármely kezdővektor esetén az egyenletrendszer megoldásához konvergál.
Szigoruan diagonálisan domináns mátrix
Egy mátrixot szigorúan diagonálisan dominánsak nevezünk, ha bármely sorában a főátlóban lévő elem abszolútértéke nagyobb, mint a sorban szereplő összes többi elem abszolútértékének összege.
\( A = \begin{pmatrix} a_{11} & \dots & \dots & \dots & \dots & a_{1n} \\ a_{21} & \dots & \dots & \dots & \dots & a_{2n} \\ \dots & \dots & \dots & \dots & \dots & \dots\\ a_{i1} & a_{i2} & \dots & a_{ii} & \dots & a_{in} \\ \dots & \dots & \dots & \dots & \dots & \dots\\ a_{n1} & \dots & \dots & \dots & \dots & a_{nn} \end{pmatrix} \)
\( \mid a_{ii} > \sum_{k=1 \\ k\neq i}^{n} \mid a_{ik} \mid \)
Richardson iteráció
Az $\underline{x}^{(n+1)}= B \underline{x}^{(n)} + \underline{c}$ iteráció pontosan akkor tart az egyenletrendszer megoldásához, ha $\rho{(B)}<1$
A Richardson iteráció szerint:
$\underline{x}^{(n+1)} = (I-\alpha \cdot A) \underline{x}^{(n)} + \alpha \cdot \underline{b} \quad \alpha \in R, \; \alpha \neq 0 $
Relaxációs módszerek
A relaxációs módszerek segítségével megváltoztathatjuk az iterációk konvergenciájának sebességét.
\( \underline{v}=(1-\omega)\cdot \underline{x}^{(n)}+\omega \cdot \underline{x}^{(n+1)} \quad \omega \in R \)
A trükk lényege, hogy az iterációs sorozat vektorait szépen egyesével kicseréljük ezekre a $\underline{v}$ vektorokra.
Az $\omega$ paramétert relaxációs paraméternek nevezzük.
Relaxált Jacobi módszer
Az $\underline{x}^{(n+1)}= B \underline{x}^{(n)} + \underline{c}$ iteráció pontosan akkor tart az egyenletrendszer megoldásához, ha $\rho{(B)}<1$
A Relaxált Jacobi iteráció (JOR) szerint:
$\underline{x}^{(n+1)} = (I-\omega D^{-1} A) \underline{x}^{(n)} + \omega \cdot D^{-1} \underline{b} \quad \omega \in R$
JOR
Az $\underline{x}^{(n+1)}= B \underline{x}^{(n)} + \underline{c}$ iteráció pontosan akkor tart az egyenletrendszer megoldásához, ha $\rho{(B)}<1$
A Relaxált Jacobi iteráció (JOR) szerint:
$\underline{x}^{(n+1)} = (I-\omega D^{-1} A) \underline{x}^{(n)} + \omega \cdot D^{-1} \underline{b} \quad \omega \in R$
Relaxált Gauss-Seidel módszer
Az $\underline{x}^{(n+1)}= B \underline{x}^{(n)} + \underline{c}$ iteráció pontosan akkor tart az egyenletrendszer megoldásához, ha $\rho{(B)}<1$
A Relaxált Gauss-Seidel módszer (SOR) szerint:
$\underline{x}^{(n+1)} = (D+\omega \cdot L)^{-1}\left((1-\omega)D-\omega\cdot U \right) \underline{x}^{(n)} + \omega \cdot (D+\omega\cdot L)^{-1} \underline{b} \quad \omega \in R$
SOR
Az $\underline{x}^{(n+1)}= B \underline{x}^{(n)} + \underline{c}$ iteráció pontosan akkor tart az egyenletrendszer megoldásához, ha $\rho{(B)}<1$
A Relaxált Gauss-Seidel módszer (SOR) szerint:
$\underline{x}^{(n+1)} = (D+\omega \cdot L)^{-1}\left((1-\omega)D-\omega\cdot U \right) \underline{x}^{(n)} + \omega \cdot (D+\omega\cdot L)^{-1} \underline{b} \quad \omega \in R$
Iterációk leállási feltételei egyenletrendszereknél
\( \lVert \underline{x}^{*} - \underline{x}^{(n)} \rVert \leq \frac{ \lVert B \rVert^n}{1 - \lVert B \rVert} \cdot \lVert \underline{x}^{(1)}-\underline{x}^{(0)} \rVert \)
Egyenletrendszerek megoldására nagyon sok módszer létezik.
Ami közös bennük, hogy mindegyik fárasztó és unalmas.
Túl sokat kell ugyanis számolni.
Most forradalmasítani fogjuk az egyenletrendszerek megoldását.
Minden egyenletből kifejezünk egy ismeretlent.
Az elsőből kifejezzük x1-et…
A másodikból x2-t…
És a harmadikból x3-at.
Most pedig elkezdünk iterálni.
Azzal kezdjük, hogy itt mindegyik ismeretlen helyére nullát írunk.
Kezdetnek mindegyik ismeretlen helyére nullát helyettesítünk.
És meg is van az első iterációs lépés.
Most azzal folytatjuk, hogy ezeket helyettesítjük be.
Aztán jön egy kis iteráció, ami az összes problémánkat megoldja.
Ezzel meg is van az iterációs sorozat első eleme.
Most pedig ezeket…
megint berakjuk szépen ide.
Így megkapjuk a sorozat második elemét.
Nem rosszak itt ezek az indexek…
De inkább rakjuk át őket ide.
Nehogy véletlenül összekeverjük ezekkel a másik indexekkel…
És most folytassuk az iterációt.
Már jön is az iterációs sorozat harmadik eleme.
Az általános tag pedig ezzel a remek kis rekurzióval írható le.
Minél több tagot számolunk ki…
Annál közelebb kerülünk az egyenletrendszer megoldásához.
És íme, a megoldás.
Na persze csak akkor, ha az iterációs sorozat konvergens.
Léteznek ugyanis olyan alattomos egyenletrendszerek, ahol az iterációs sorozat nem konvergál a megoldáshoz.
Az, hogy a sorozat konvergál-e vagy sem, a B mátrixon múlik.
Ezen a B mátrixon...
Az iterációs sorozat pontosan akkor konvergál az egyenletrendszer megoldásához, ha a B mátrix spektrálsugara 1-nél kisebb.
Egy mátrix spektrálsugarát úgy kapjuk meg, hogy vesszük a sajátértékeinek az abszolútértékét…
És ezek közül a legnagyobb a spektrálsugár.
Legyen A egy nxn-es reguláris mátrix, és az egyenletrendszer megoldása
Az
iterációt az egyenletrendszerrel konzisztensnek nevezzük, ha teljesül rá, hogy
Az iteráció pontosan akkor tart az egyenletrendszer megoldásához, ha
Az iterációs sorozat vektoros alakja így néz ki…
Az iterációs sorozat vektoros alakját úgy kapjuk meg…
…hogyha betesszük szépen ezeket egy-egy vektorba.
Ez pedig az iterációs sorozat vektoros alakja:
Az iterációt az eredeti egyenletrendszerrel konzisztensnek nevezzük, ha az egyenletrendszer megoldását ide behelyettesítve az egyenlőség teljesül.
Ezt a B mátrixot az egyenletrendszer együtthatómátrixából kényelmesen elő is tudjuk állítani.
A főátló elemeit betesszük ebbe a D mátrixba…
A főátló alatti elemeket az L-be…
A főátló felettieket pedig az U-ba.
És készen is van a B mátrix.
Az iteráció gyorsaságáért is a B mátrix felel.
A Banach fixponttétel alapján a konvergencia gyorsaságára a következő becslés adható:
Az iteráció gyorsasága:
Az egyenletrendszereknek ezt az iterációs megoldását Jacobi iterációnak nevezzük.
A Jacobi iterációt egy ügyes kis trükkel még hatékonyabbá lehet tenni.
A trükk lényege, hogy amikor az iteráció során valamelyik változónak megkaptuk az új értékét, azt rögtön fel is használjuk, nem várunk vele a következő iterációs ciklusig.
A Jacobi iteráció azzal kezdődött, hogy itt mindegyik változó helyére nullát írtunk.
De most, hogy megkaptuk x1 új értékét…
Ezt rögtön fel is használjuk.
Aztán kiszámoljuk x2 új értékét…
És felhasználjuk ezt is.
Ettől az új módszertől azt várjuk, hogy az iterációs sorozat gyorsabban fog konvergálni a megoldáshoz.
Azt, hogy ez végül tényleg így lesz-e, hamarosan megtudjuk.
Jacobi iteráció:
.
Itt jön egy újabb iterációs módszer egyenletrendszerek megoldására.
Ezt az iterációt Gauss-Seidel iterációnak nevezzük.
A módszer lényege, hogy amikor az iteráció során valamelyik változónak megkapjuk az új értékét, azt rögtön fel is használjuk, nem várunk vele a következő iterációs ciklusig.
Most is azzal kezdünk, hogy mindegyik egyenletből kifejezünk egy változót…
Aztán az egyenlőségek jobb oldalába behelyettesítünk egy kezdőértéket.
A kezdőérték bármi lehet. Mondjuk például nulla.
És x1 már meg is van.
A Gauss-Seidel iteráció lényege, hogy ezt az x1-et rögtön fel is használjuk.
Az x3-ra még nem jött ki semmi, így ide kénytelenek vagyunk nullát írni…
Ezzel megvan az új x2 is.
x3-at pedig már 100%-ban friss alapanyagokból készítjük el.
És itt is van az iterációs sorozat első tagja.
Lássuk, mi lesz a második tag.
Az iterációs sorozat általános tagja pedig ezzel a remek kis rekurzióval írható le.
Minél több tagot számolunk ki…
Annál közelebb kerülünk az egyenletrendszer megoldásához.
Ettől az új módszertől azt várjuk, hogy az iteráció valahogy gyorsabban fog konvergálni, mint korábban a Jacobi iteráció.
Mindjárt meglátjuk, hogy ez végül tényleg így lesz-e…
Az iteráció vektoros alakját most egy kicsit komplikáltabban kapjuk meg…
És egy kis átalakítás még jót tesz neki.
Sőt, nem is olyan kicsi…
És most lássuk, hogy tényleg gyorsabb-e a Gauss-Seidel, mint a Jacobi.
Oldjuk meg ezt az egyenletrendszert mindkét módszerrel.
Így versenyeztetni tudjuk egymással ezeket a módszereket.
A megoldások egyébként ezek lesznek:
Az egyenletrendszer megoldása:
Ezt kéne megkapnunk az iterációkkal is.
Lássuk, valóban így lesz-e.
Megint azzal kezdjük, hogy kifejezzük a változókat…
Aztán elkezdjük az iterációt.
Jacobi iteráció
Gauss-Seidel iteráció
Ahogy egyre több tagját számoljuk ki az iterációs sorozatnak…
A Gauss-Seidel valóban gyorsabbnak tűnik.
Ha négy tizedesjegy pontossággal számolunk…
Akkor a hatodik tagnál a Gauss-Seidel már egészen lenyűgöző teljesítményt nyújt.
De ahogyan minden lenyűgöző teljesítménynél…
Most sem árt egy kicsit gyanakodni.
Itt van például ez a másik egyenletrendszer.
És nézzük, mi történik, ha elkezdjük megoldani a Jacobi és a Gauss-Seidel iterációval.
Az egyenletrendszer megoldása egyébként ez:
Már jönnek is az iterációk…
Most a Jacobi valahogy jobbnak tűnik...
Azért tűnik jobbnak, mert jobb is.
A Jacobi iteráció ugyanis konvergens.
A Gauss-Seidel pedig divergens.
Ha megnézzük az iterációk B mátrixait…
És kiszámoljuk a mátrixok sajátértékeit…
Akkor kiderül, hogy a spektrálsugár a Jacobinál 1-nél kisebb…
A Gauss-Seidelnél viszont 1-nél nagyobb.
A Gauss-Seidel iteráció tehát semmivel sem jobb, mint a Jacobi.
Vannak olyan esetek, amikor az egyik konvergál gyorsabban…
És vannak olyan esetek is, amikor a másik.
A konvergencia gyorsaságára pedig a B mátrixok spektrálsugarából tudunk következtetni.
A spektrálsugár kiszámítása mondjuk eléggé fárasztó feladat…
Ki kell hozzá számolni a mátrixok sajátértékeit, és az bizony nem túl kellemes.
Szerencsére vannak még más módszerek is annak eldöntésére, hogy az iteráció konvergens-e vagy sem.
Már jönnek is.
És most lássuk, milyen módszerekkel tudjuk eldönteni, hogy az iteráció konvergens-e vagy sem.
Azt már tudjuk, hogy az iterációk konvergenciája a B mátrixok spektrálsugarán múlik.
A legújabb kutatások szerint a spektrálsugarak kiszámolása nem szerepel a világ tíz legkedveltebb tevékenységének listáján…
Szerencsére itt jön most néhány újabb módszer amivel tisztázni lehet, hogy egy iteráció konvergens lesz-e.
Egy mátrixot szigorúan diagonálisan dominánsnak nevezünk, ha bármely sorában…
…a főátlóban lévő elem abszolútértéke nagyobb…
…mint a sorban szereplő összes többi elem abszolútértékének összege.
Ha az egyenletrendszer együtthatómátrixa szigorúan diagonálisan domináns, akkor a Jacobi és a Gauss-Seidel iterációk is bármely kezdővektor esetén az egyenletrendszer megoldásához konvergálnak.
Lássuk, mi a helyzet ezzel az egyenletrendszerrel.
Hát, ez a mátrix nem szigorúan diagonálisan domináns.
Hogyha viszont átrendezzük egy kicsit az egyenleteket…
Na, akkor már igen.
Az iteráció tehát biztosan konvergens lesz.
Ez a feltétel egy elégséges feltétel, ami azt jelenti, hogyha teljesül, akkor az iteráció egészen biztosan konvergens.
De ha nem, abból még nem következik, hogy divergens.
Ennek az egyenletrendszernek az együtthatómátrixa például nem szigorúan diagonálisan domináns.
A Jacobi iteráció viszont mégis konvergens.
Ezt onnan tudjuk, hogy ez az egyenletrendszer volt az előző epizód végén, és akkor még konvergens volt.
Ami pedig még érdekesebbé teszi a helyzetet, hogy a Gauss-Seidel iteráció viszont itt divergens.
Itt jön aztán egy újabb feltétel az iterációk konvergenciájára.
Ha az egyenletrendszer együtthatómátrixa szimmetrikus pozitív definit mátrix, akkor a Gauss-Seidel iteráció bármely kezdővektor esetén az egyenletrendszer megoldásához konvergál.
És most lássuk, mi a helyzet ezzel az egyenletrendszerrel.
Íme az együtthatómátrix…
Ez a mátrix nem szigorúan diagonálisan domináns…
És nem is szimmetrikus…
Sőt nem is pozitív definit.
Így hát az új módszereinkkel nem vagyunk képeseik eldönteni, hogy az iteráció konvergens lesz-e vagy sem.
Kénytelenek vagyunk kiszámolni a spektrálsugarat.
Nézzük meg például a Jacobi iteráció B mátrixát.
Kiszámoljuk a sajátértékeket…
Ennek a remek kis determinánsnak a segítségével.
Ezt az egyenletet hívjuk karakterisztikus egyenletnek.
És ennek az egyenletnek a megoldásai a sajátértékek.
A B mátrix spektrálsugara a sajátértékek abszolútértékei közül a legnagyobb:
A spektrálsugár 1-nél kisebb, így a Jacobi iteráció konvergens.
Hogyha tehát elkezdjük a Jacobi iterációt, akkor már elég hamar megkapjuk, hogy ennek az egyenletrendszernek a megoldása és .
Na persze fölmerül itt azért egy kérdés…
Mégis minek szenvedünk itt sajátértékekkel meg iterációkkal egy olyan egyenletrendszer megoldásán, ami még érettségi feladatnak is túl könnyű lenne…
A válasz az, hogy ezeket a módszereket olyan egyenletrendszerekre fejlesztették ki, ahol a változók száma akár több száz is lehet.
Ilyen nagy egyenletrendszereknél pedig a hagyományos módszerek műveletigénye nagyon nagy lehet.
Ráadásul a Gauss-elimináció vagy az elemi bázistranszformáció közben vétett kerekítési hibák szép lassan összeadódnak, így a végeredmény jelentősen eltérhet az egyenletrendszer valódi megoldásától.
Hogyha tehát egy olyan egyenletrendszert kell megoldanunk, amit az élet írt, és nem valamelyik matektanár, akkor szinte minden esetben iterációs módszereket használunk a megoldásukhoz.
Itt jön egy újabb iterációs módszer, amit Richardson iterációnak neveztek el.
Az iteráció konvergenciája mindig ezen a B mátrixon múlik…
A Richardson iteráció lényege pedig az, hogy nem bízza a B mátrixot a véletlenre.
Itt van az eredeti egyenletrendszer…
És beszorozzuk valami nem nulla számmal.
Aztán még rendezgetünk egy kicsit…
És meg is van a Richardson iteráció általános alakja.
A dolog azért nagyon ravasz, mert így a B mátrixot kedvünk szerint tudjuk úgy alakítgatni, hogy a spektrálsugara 1-nél kisebb legyen.
Próbáljuk ki a Richardson iterációt ennek az egyenletrendszernek a megoldására.
Elkészítjük a Richardson iteráció B mátrixát:
És most kipróbálunk néhány -t.
A cél az, hogy a B mátrix spektrálsugara 1-nél kisebb legyen.
A B mátrix spektrálsugara a sajátértékek abszolútértékei közül a legnagyobb.
Hogyha például …
Akkor a spektrálsugár…
A B mátrix sajátértékeinek abszolútértékei közül a legnagyobb.
Ezek itt a sajátértékek…
És a sajátértékek abszolútértékei közül a legnagyobb…
Ez lesz a spektrálsugár.
…
Hát, ez sajna 1-nél nagyobb, úgyhogy az iteráció divergens.
Nem baj, akkor keresünk másik -t.
Nézzük, mi van akkor, ha mondjuk .
Megint kiszámoljuk a sajátértékeket.
És a spektrálsugár…
Még mindig 1-nél nagyobb.
Hát, még az se jó.
Próbáljuk ki az értéket is…
És bumm. Ez jó.
A spektrálsugár végre 1-nél kisebb.
Az iteráció konvergens lesz, a rekurziós képlet pedig:
Nézzünk meg még egy ilyet.
Oldjuk meg ezt az egyenletrendszert a Richardson iterációval.
Lássuk a B mátrixot:
És most jó lenne, ha nem kellene annyit szenvednünk az –val, mint az előbb…
Szerencsére itt jön erre egy remek kis feltétel.
Ha az egyenletrendszer együtthatómátrixa nxn-es szimmetrikus pozitív definit mátrix, és sajátértékei akkor a Richardson iteráció ezekre az paraméterekre konvergens:
Az optimális paraméter pedig:
Az optimális paraméterhez tehát szükségünk van az A mátrix sajátértékeire.
És most jöhet az iteráció.
Az iteráció szép lassan konvergál a megoldáshoz.
Hogyha öt egymást követő tag már alig tér el egymástól, akkor szinte biztosak lehetünk benne, hogy meg is van a megoldás.
