„Gauss-elimináció” változatai közötti eltérés

nincs szerkesztési összefoglaló
(jelentős javításra szorul, de külön szócikk indokolt (ld. más nyelvek))
Nincs szerkesztési összefoglaló
:<math>a_{m1}x_{1}+a_{m2}x_{2}+\dots+a_{mn}x_{n}=b_{m}</math>
 
Az eljárás során az egyenletrendszer megoldásait keressük, ahol megoldás alatt olyan <math>k_{1}, k_{2}, \dots, k_{n}</math> értendő, amely az <math>x_{1}, x_{2}, \dots, x_{n}</math> ismeretlenek helyére behelyettesítve mind az m egyenletet kielégíti.<ref>Az eljárással meghatározható [[Mátrixmátrix (matematika)|mátrixok]] rangja és [[determináns]]a is.</ref>
 
Az elimináció-, azaz kiküszöbölés-módszer lényege abban áll, hogy rendszerünket visszavezetjük vagy valamely háromszög- vagy átlós mátrixszal reprezentálható alakra. Ezt sorozatos, jobb és bal oldalon egyaránt alkalmazott, lineáris [[Transzformáció (matematika)|transzformációk]] segítségével érjük el.<br />
Az egyenletrendszert felfoghatjuk így: <br />
:<math>Ax=b\,</math>
<math>a_{m1}x_{1}+a_{m2}x_{2}+\dots+a_{mn}x_{n}=b_{m}</math>
 
Ekkor tegyük fel, hogy <math>a_{11}\neq0</math> . (Ez az állapot az egyenletek sorrendjének felcserélésével elérhető.) Ekkor vonjuk ki az i. egyenletből ( ahol <math>i\geq2</math> ) az első egyenlet <math>\frac{a_{i1}}{a_{11}}</math> – szeresét. Az <math>a_{11}</math> átlómenti elemet, amellyel osztunk, ''főelem''nek nevezzük.
A következő egyenletrendszert kapjuk:
 
<math>0+a_{m2}^{,}x_{2}+\dots+a_{mn}^{,}x_{n}=b_{m}^{,}</math>
 
Ezután az i!=2 egyenletekből vonjuk ki a második egyenlet <math>\frac{a_{i2}}{a_{22}}</math> – szeresét–szeresét. Ekkor a
 
<math>a_{11}^{,,}x_{1}+0+\dots+a_{1n}^{,,}x_{n}=b_{1}^{,,}</math><br /><br />
 
:<math>
\begin{bmatrix}
a_{11}^{*}&0&\dots&0&a_{1r+1}^{*}&\dots&a_{1n}^{*}&b_{1}^{*}\\
0&a_{22}^{*}&\dots&0&a_{2r+1}^{*}&\dots&a_{2n}^{*}&b_{2}^{*}\\
 
== Következmények ==
Ha a <math> b_{r+1}^{*}\dots b_{m}^{*}</math> mindegyike egyenlő 0-val, akkor az egyenletrendszer megoldható ( ekkor az egyenletrendszer mátrixának rangja megegyezik a kibővített mátrixának rangjával).
 
Ha ezen elemek valamelyike nem 0 akkor az egyenletrendszer nem oldható meg. ( ekkor az egyenletrendszer mátrixának rangja kisebb a kibővített mátrixénál.)
 
Tehát egy egyenletrendszer akkor és csak akkor oldható meg, ha mátrixának rangja egyenlő kibővített mátrixának rangjával.
Miután kinullázzuk a megfelelő elemeket, a rendszerünk ilyen alakú lesz:
<center><math>\begin{pmatrix} a_{11}^{(1)} & a_{12}^{(1)} & \cdots & a_{1n}^{(1)} \\ 0 & a_{22}^{(2)} & \cdots & a_{2n}^{(2)} \\ \vdots & \cdots & \vdots \\ 0 & 0 & \cdots & a_{nn}^{(n)}\end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n\end{pmatrix} = \begin{pmatrix} b_1^{(1)} \\ b_2^{(2)} \\ \cdot \\ b_n^{(n)}\end{pmatrix}</math></center><br />
az (1), (2)... (n) felsőindexekfelső indexek az egyes lépéseket jelölik.<br />
 
A [[Gauss]]-módszer [[algoritmus]]a a következőképpen képzelhető el:
 
'''''function''''' <math>Gauss</math> '''''inout:''''' <math>(a_{ij}),(b_i) i,j=1..n</math> (az '''''A''''' mátrixot és a '''''b''''' vektort "helyben" módosítjuk)<br />
:'''''for''''' <math>k \leftarrow 1</math> '''''to''''' <math>n-1</math> '''''do'''''
::'''''for''''' <math> i \leftarrow k+1</math> '''''to''''' <math>n</math> '''''do'''''
'''''end function'''''
 
Ebben az algoritmusban feltételeztük, hogy az <math>a^{(k)}_{kk} \neq 0</math> feltétel minden esetben teljesül. Az algoritmus megvalósításánál azonban ezt a tesztelést célszerű a kódba beépíteni.
 
A kapott rendszer mátrixa egy felső-háromszög mátrix. Amennyiben az utolsó egyenletre is érvényes az <math>a^{(n)}_{nn} \neq 0</math> feltétel, akkor a rendszert egyszerűen megoldhatjuk.
 
A kiküszöbölés vezető rendben <math>n^3/3</math> műveletet tesz szükségessé, tehát a visszahelyettesítés <math>n^2/2</math> műveletigénye elhanyagolható nagy rendszerek megoldása esetén.
Példaképpen tekintsük át a módszer lépéseit egy konkrét 3 x 3-as mátrixszal leírható egyenletrendszer esetén:<br /><br />
<math> \begin{pmatrix} 1 & 5 & -2 \\ 2 & 3 & 1 \\ 2 & 4 & -3 \end{pmatrix} </math>
<math> \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} </math> =
<math> \begin{pmatrix} 2 \\ 5 \\ 2 \end{pmatrix} </math> (főelem: 1) →<br /><br />
<math> \begin{pmatrix} 1 & 5 & -2 \\ 0 & -7 & 5 \\ 0 & -6 & 1 \end{pmatrix} </math>
<math> \begin{pmatrix} 2 \\ 1 \\ \frac{-20}{7} \end{pmatrix} </math>
 
A megoldások:
<math>x_1=\frac{31}{23}, x_2=\frac{11}{23}, x_3=\frac{20}{23}</math>