BSz1 Jegyzet

8. Tétel:

Lineáris egyenletrendszer megoldása Gauss-eliminációval. A megoldhatóság, illetve a megoldás egyértelműségének feltétele. Lépcsős alak és redukált lépcsős alak fogalma. Kapcsolat az egyenletek és ismeretlenek száma, illetve a megoldás egyértelműsége között.

8.1. Lineáris egyenletrendszerek fogalma

Egy $k$ egyenletből álló és $n$ változós lineáris egyenletrendszer leírásához bevezetjük a kettős indexelésű együtthatókat. Az $a_{i,j}$ jelöli az $i$-edik egyenletben a $j$-edik változó együtthatóját minden $1 \le i \le k$ és $1 \le j \le n$ esetén.

A lineáris egyenletrendszer „hagyományos” alakja:

$$ \begin{matrix} a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,n}x_n & = & b_1 \\ a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,n}x_n & = & b_2 \\ \vdots & \vdots & \vdots \\ a_{k,1}x_1 + a_{k,2}x_2 + \dots + a_{k,n}x_n & = & b_k \end{matrix} $$

Az egyenlet jobb oldalán álló konstans tagokat $b_i$-vel jelöljük.

Kibővített együtthómátrix

Az egyenletrendszer tömör formában is felírható a változók elhagyásával:

$$ \left( \begin{array}{cccc|c} a_{1,1} & a_{1,2} & \dots & a_{1,n} & b_1 \\ a_{2,1} & a_{2,2} & \dots & a_{2,n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{k,1} & a_{k,2} & \dots & a_{k,n} & b_k \end{array} \right) $$

A megoldás megkereséséhez az egyenletrendszeren elemi sorekvivalens lépéseket végzünk. Ezek a lépések lehetővé teszik a rendszer egyszerűbb alakra hozását a megoldáshalmaz megváltoztatása nélkül.

Példafeladat: Mátrixos ábrázolás

Feladat:

Adja meg a következő lineáris egyenletrendszer kibővített együtthatómátrixát! $$ \begin{cases} 3x_1 + x_2 = 7 \\ x_1 - 2x_2 = -4 \end{cases} $$

Megoldás

$$ \left( \begin{array}{cc|c} 3 & 1 & 7 \\ 1 & -2 & -4 \end{array} \right) $$

A mátrix első két oszlopa az együtthatókat, a függőleges vonal utáni rész a konstansokat tartalmazza.

8.2. Elemi sorekvivalens lépések

A lineáris egyenletrendszerek megoldása során olyan átalakításokat végzünk a kibővített együtthatómátrixon, amelyek a rendszer megoldásait nem befolyásolják. Ezeket a műveleteket nevezzük elemi sorekvivalens lépéseknek.

2.3.1. Definíció:

Kibővített együtthatómátrixával adott lineáris egyenletrendszer esetén elemi sorekvivalens lépésnek nevezzük az alábbiakat tetszőleges $1 \le i, j \le k, i \neq j$ és $\lambda \in \mathbb{R}$ skalár esetén:

  • i A mátrix $i$-edik sorának (tagonként való) megszorzása $\lambda$-val, ha $\lambda \neq 0$;
  • ii A mátrix $i$-edik sorának helyettesítése saját magának és a $j$-edik sor $\lambda$-szorosának (tagonként vett) összegével;
  • iii Az $i$-edik és a $j$-edik sor felcserélése;
  • iv Egy csupa nulla elemeket tartalmazó sor elhagyása.

Az elnevezés indoklása

Szinte magától értetődő, de a Gauss-elimináció működése szempontjából alapvető fontosságú, hogy ezek a lépések ekvivalentak, vagyis az átalakítás előtti és utáni egyenletrendszer megoldáshalmaza megegyezik.

Példafeladat: Sorekvivalens lépések alkalmazása

Feladat:

Végezze el a következő átalakítást: adja hozzá az első sor $(-2)$-szeresét a második sorhoz! $$ \left( \begin{array}{cc|c} 1 & 3 & 4 \\ 2 & 1 & -2 \end{array} \right) $$

1. Művelet tervezése (ii. típusú lépés)

Az új 2. sor = (eredeti 2. sor) + $(-2) \cdot$ (1. sor).

$x: 2 + (-2) \cdot 1 = 0$
$y: 1 + (-2) \cdot 3 = -5$
$b: -2 + (-2) \cdot 4 = -10$
$$ \left( \begin{array}{cc|c} 1 & 3 & 4 \\ 0 & -5 & -10 \end{array} \right) $$

Látható, hogy ezzel a lépéssel az $x_1$ változó együtthatóját kinulláztuk a második egyenletben.

8.3. Az átalakítások ekvivalenciája

Bár a sorekvivalens lépések során a mátrix kinézete megváltozik, a mögötte álló egyenletrendszer lényegi tulajdonsága – a megoldáshalmaza – érintetlen marad. Ezt rögzíti az alábbi fontos állítás:

2.3.2. Állítás:

A 2.3.1. Definícióban felsorolt lépések ekvivalens átalakítások, vagyis az egyenletrendszer megoldásait nem változtatják meg.

Ez pontosabban azt jelenti, hogy ha az $x_1, x_2, \dots, x_n$ számok kielégítik az egyenletrendszert egy lépés megtétele előtt, akkor a megtétele után is; és fordítva, ha a lépés megtétele után kielégítik, akkor előtte is.

A tétel bizonyítása a (ii) típusú lépésre:

Tegyük fel, hogy az $x_1, \dots, x_n$ számok kielégítik az egyenletrendszert. Ekkor az $i$-edik és a $j$-edik egyenletre fennáll: $a_{i,1}x_1 + a_{i,2}x_2 + \dots + a_{i,n}x_n = b_i$
$a_{j,1}x_1 + a_{j,2}x_2 + \dots + a_{j,n}x_n = b_j$

Az utóbbi egyenlet $\lambda$-szorosát az előbbihez adva kapjuk az új $i$-edik egyenletet: $(a_{i,1} + \lambda a_{j,1})x_1 + (a_{i,2} + \lambda a_{j,2})x_2 + \dots + (a_{i,n} + \lambda a_{j,n})x_n = b_i + \lambda b_j$ Ez pontosan azt jelenti, hogy az új $i$-edik egyenlet is teljesül, míg a többi egyenlet változatlan maradt.

Megfordítva: Ha az új rendszer teljesül, akkor az új $i$-edik egyenletből a $j$-edik egyenlet $\lambda$-szorosát kivonva visszakapjuk az eredeti $i$-edik egyenletet. Mivel a művelet visszafordítható, a megoldáshalmaz azonos marad. □

Módszertani következmény

Ez a tulajdonság teszi lehetővé, hogy a Gauss-elimináció végén kapott egyszerű alakból (például ahol $x_1 = 5$) közvetlenül leolvashassuk az eredeti, bonyolult rendszer megoldásait is.

8.4. Lépcsős alak és redukált lépcsős alak

A Gauss-elimináció során a célunk a kibővített együtthatómátrix olyan alakra hozása, amelyből a megoldások szisztematikusan leolvashatók. Ehhez vezetjük be a lépcsős alak fogalmát:

2.3.3. Definíció:

Egy kibővített együtthatómátrixot lépcsős alakúnak mondunk, ha az alábbiak teljesülnek:

  • i A mátrix minden (nem csupa nulla) sorában az első nemnulla elem egy 1-es – ezt nevezzük vezéregyesnek;
  • ii Bármely két egymás utáni sor közül az alsóbb sor vezéregyese hátrébb (jobbra) van, mint a felette lévő soré;
  • iii A vezéregyesek alatt az oszlopukban minden elem 0.

Redukált lépcsős alakúnak mondjuk a mátrixot, ha a fentieken túl még az alábbi is teljesül:

  • iv A vezéregyesek felett is minden elem 0 az oszlopukban.

    • A megoldás leolvasása

    A redukált lépcsős alak egy „eleve megoldott” egyenletrendszernek tekinthető. A vezéregyeseket nem tartalmazó oszlopoknak megfelelő változók a szabad paraméterek, míg a vezéregyeseket tartalmazó oszlopok változói ezek segítségével fejezhetők ki. Ha minden oszlopban van vezéregyes (és nincs ellentmondás), akkor a megoldás egyértelmű.

    Példafeladat: Alakok felismerése és megoldás

    Lépcsős alak (REF)

    $$ \left( \begin{array}{ccc|c} \mathbf{1} & 2 & 1 & 5 \\ 0 & \mathbf{1} & 3 & -2 \\ 0 & 0 & 0 & 0 \end{array} \right) $$

    Vezéregyesek: $a_{1,1}$ és $a_{2,2}$. A harmadik oszlopban nincs vezéregyes, így $x_3$ szabad paraméter lesz.

    Redukált lépcsős alak (RREF)

    $$ \left( \begin{array}{ccc|c} \mathbf{1} & 0 & -5 & 9 \\ 0 & \mathbf{1} & 3 & -2 \\ 0 & 0 & 0 & 0 \end{array} \right) $$

    A második vezéregyes feletti elem ($a_{1,2}$) is nullává vált. A megoldás közvetlenül felírható $x_3 = t$ paraméterrel.

    A végleges megoldás felírása (RREF-ből)

    $x_3 = t \in \mathbb{R}$
    $x_2 = -2 - 3t$
    $x_1 = 9 + 5t$

    8.5. A megoldhatóság esetei (2.3.5. Tétel)

    A Gauss-elimináció algoritmusa egy szisztematikus folyamat, amely minden lineáris egyenletrendszer esetén egyértelmű választ ad a megoldhatóságra. A folyamat végén az alábbi három eset közül pontosan egy valósul meg:

    2.3.5. Tétel

    Tetszőleges, kibővített együtthatómátrixával adott lineáris egyenletrendszer esetén a Gauss-eliminációt futtatva az alábbiak egyike következik be:

    i

    Nincs megoldás

    Az eljárás során „tilos sort” találunk (olyan sor, ahol az együtthatók mind nullák, de a konstans tag nem nulla). Ekkor az egyenletrendszer ellentmondásos.

    ii

    Egyértelmű megoldás

    Az algoritmus redukált lépcsős alakra hozza a mátrixot, amelynek minden oszlopában van vezéregyes. Ekkor pontosan egy megoldás létezik.

    iii

    Végtelen sok megoldás

    Az algoritmus redukált lépcsős alakra hozza a mátrixot, de nem minden oszlopában van vezéregyes. A vezéregyes nélküli oszlopokhoz tartozó változók szabad paraméterek lesznek.

    A (ii) és (iii) esetekben a megoldások a redukált lépcsős alakból közvetlenül kiolvashatók.

    Példafeladat: „Tilos sor” felismerése

    Vizsgált mátrix állapot:

    $$ \left( \begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 0 & 1 & 3 & -2 \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{5} \end{array} \right) $$

    A harmadik sor jelentése: $0x_1 + 0x_2 + 0x_3 = 5$, azaz $0 = 5$.

    Ez egy nyilvánvaló ellentmondás, hiszen nincs olyan valós számhármas, amelyre ez teljesülne.

    Következtetés

    Az egyenletrendszernek nincs megoldása.

    8.6. Az egyértelmű megoldhatóság feltétele

    Gyakori kérdés, hogy hány egyenletre van szükségünk egy ismeretlen mennyiség egyértelmű meghatározásához. Az alábbi tétel szigorú matematikai korlátot szab erre vonatkozóan:

    2.3.6. Tétel:

    Ha egy $k$ egyenletből álló, $n$ ismeretlenes lineáris egyenletrendszer egyértelműen megoldható, akkor $k \ge n$.

    (Vagyis ismeretlenjeink számánál nem lehet kevesebb egyenletünk az egyértelműséghez.)

    A tétel bizonyítása:

    Futtassuk le a Gauss-eliminációt az egyenletrendszerre. Mivel a feltétel szerint a rendszer megoldható, az eljárás során nem keletkezik tilos sor.

    Az algoritmus végén kapott redukált lépcsős alakban jelölje a sorok számát $k'$. Nyilvánvaló, hogy $k' \le k$, mert az algoritmus során sorokat vonhatunk össze vagy hagyhatunk el (nullsorok), de új sorokat nem hozunk létre.

    Mivel az egyenletrendszer egyértelműen megoldható, a 2.3.5. Tétel értelmében a redukált lépcsős alak minden oszlopa tartalmaz vezéregyest. Ebből következik, hogy a sorok száma nem lehet kevesebb az oszlopok (ismeretlenek) számánál: $k' = n$.

    Ezeket összevetve: $k \ge k' = n$, amivel a tételt beláttuk. □

    Példafeladat: Megoldhatóság korlátai

    Feladat:

    Adott egy 3 egyenletből álló, 4 ismeretlenes ($x_1, x_2, x_3, x_4$) lineáris egyenletrendszer. Lehet-e ennek a rendszernek egyetlen, egyértelmű megoldása?

    Elemzés a 2.3.6. Tétel alapján:

    • Egyenletek száma: $k = 3$
    • Ismeretlenek száma: $n = 4$

    A tétel kimondja, hogy az egyértelmű megoldáshoz szükséges feltétel a $k \ge n$ egyenlőtlenség teljesülése.

    Vizsgálat: $3 \ge 4$ ?
    Hamis.

    Végeredmény

    Mivel kevesebb egyenletünk van, mint ismeretlenünk, a rendszernek nem lehet egyértelmű megoldása.
    (Vagy nincs megoldása, vagy végtelen sok megoldása van.)

    Gauss-elimináció és Vezéregyesek

    Redukált lépcsős alak meghatározása

    Egyenletrendszer bővített mátrixa