Gauss-elimináció

• IPA:

Gauss-elimináció

1. (matematika, lineáris algebra, algoritmusok)

A Gauss-elimináció a lineáris algebra egy lineáris egyenletrendszerek megoldására használatos algoritmusa. Legyen adott a következő lineáris egyenletrendszer:

${\displaystyle a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}=b_{1}}$

${\displaystyle a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}=b_{2}}$

${\displaystyle \dots }$

${\displaystyle a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}=b_{m}}$

Az eljárás során az egyenletrendszer megoldásait keressük, ahol megoldás alatt olyan ${\displaystyle k_{1},k_{2},\dots ,k_{n}}$ értendő, amely az ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ ismeretlenek helyére behelyettesítve mind az m egyenletet kielégíti. Az eljárással meghatározható mátrixok rangja és determinánsa is. 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ók segítségével érjük el

A Gauss-elimináció egy hatékony módszer lineáris egyenletrendszerek megoldására. Az algoritmus az egyenletrendszer mátrixát lépcsőzetes alakra alakítja, majd visszahelyettesítéssel meghatározza az ismeretlenek értékeit.

Az algoritmus célja egy lineáris egyenletrendszer megoldása: ahol: - (A): az egyenletrendszer együtthatómátrixa, - (x): az ismeretlenek vektora, - (b): a jobb oldali konstansok vektora.

1. Bemenet: Az (A) mátrix és (b) vektor.
2. Elimináció:
   • Az (A) mátrixot lépcsőzetes alakra alakítjuk (felső háromszög alakúvá).
   • Minden oszlopban kiválasztjuk a legnagyobb abszolút értékű elemet (pivotálás).
   • A pivot elemet felhasználva kinullázzuk az alatta lévő elemeket.
3. Visszahelyettesítés:
   • A felső háromszög alakú mátrixból visszafelé haladva kiszámítjuk az ismeretleneket.

function GaussElimination(A, b):
    n = A mérete
    C =   # Az együtthatómátrix és a jobb oldali vektor összefűzése

    # Eliminációs lépés
    for i = 0 to n-1:
        # Pivotálás: Legnagyobb abszolút értékű elem keresése az aktuális oszlopban
        pivot_row = i
        for j = i+1 to n-1:
            if abs(C) > abs(C):
                pivot_row = j

        # Sorcsere
        C, C = C, C

        # Kinullázás az i. oszlop alatt
        for j = i+1 to n-1:
            factor = C / C
            for k = i to n:
                C -= factor * C

    # Visszahelyettesítés
    x =  * n
    for i = n-1 down to 0:
        x = (C - sum(C * x for j = i+1 to n-1)) / C

    return x

import numpy as np

def gauss_elimination(A, b):
    """
    Gauss-eliminációs algoritmus lineáris egyenletrendszerek megoldására.
    :param A: Együtthatómátrix
    :param b: Jobb oldali vektor
    :return: Az ismeretlenek megoldásvektora
    """
    n = len(A)
    C = np.hstack((A, b.reshape(-1, 1)))  # Az A mátrix és b vektor összefűzése

    # Eliminációs lépés
    for i in range(n):
        # Pivotálás
        max_row = i + np.argmax(np.abs(C))
        C] = C]  # Sorcsere

        # Kinullázás az i. oszlop alatt
        for j in range(i + 1, n):
            factor = C / C
            C -= factor * C

    # Visszahelyettesítés
    x = np.zeros(n)
    for i in range(n - 1, -1, -1):
        x = (C - np.dot(C, x)) / C

    return x

# Példa használat
A = np.array(,
              ,
              ])
b = np.array()

solution = gauss_elimination(A, b)
print(f"Az ismeretlenek megoldásvektora: {solution}")

Kimenet:

Az ismeretlenek megoldásvektora: 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<double> gauss_elimination(vector<vector<double>> A, vector<double> b) {
    int n = A.size();
    vector<double> x(n, 0.0);

    // Augmentált mátrix létrehozása
    for (int i = 0; i < n; ++i) {
        A.push_back(b);
    }

    // Eliminációs lépés
    for (int i = 0; i < n; ++i) {
        // Pivotálás
        int max_row = i;
        for (int k = i + 1; k < n; ++k) {
            if (fabs(A) > fabs(A)) {
                max_row = k;
            }
        }
        swap(A, A);

        // Kinullázás az i. oszlop alatt
        for (int j = i + 1; j < n; ++j) {
            double factor = A / A;
            for (int k = i; k <= n; ++k) {
                A -= factor * A;
            }
        }
    }

    // Visszahelyettesítés
    for (int i = n - 1; i >= 0; --i) {
        x = A / A;
        for (int j = i - 1; j >= 0; --j) {
            A -= A * x;
        }
    }

    return x;
}

int main() {
    vector<vector<double>> A = {
        {2, 1, -1},
        {-3, -1, 2},
        {-2, 1, 2}
    };
    vector<double> b = {8, -11, -3};

    vector<double> solution = gauss_elimination(A, b);

    cout << "Az ismeretlenek megoldásvektora: ";
    for (double val : solution) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Kimenet:

Az ismeretlenek megoldásvektora: 2 3 -1

A Gauss-elimináció hatékony és jól alkalmazható módszer lineáris egyenletrendszerek megoldására: - Időbonyolultság: (O(n^3)), ahol (n) az egyenletek száma. - Előnyök: - Egyszerű implementáció. - Alkalmas kis és közepes méretű rendszerekre. - Hátrányok: - Nagyobb mátrixoknál numerikus instabilitás léphet fel. - Nem hatékony ritka mátrixokra, ahol speciális módszerek előnyösebbek.

• angol: Gaussian elimination (en)
• német: gaußsches Eliminationsverfahren (de)
• orosz: метод Гаусса (ru) (metod Gaussa)

• Gauss-elimináció - Értelmező szótár (MEK)
• Gauss-elimináció - Etimológiai szótár (UMIL)
• Gauss-elimináció - Szótár.net (hu-hu)
• Gauss-elimináció - DeepL (hu-de)
• Gauss-elimináció - Яндекс (hu-ru)
• Gauss-elimináció - Google (hu-en)
• Gauss-elimináció - Helyesírási szótár (MTA)
• Gauss-elimináció - Wikidata
• Gauss-elimináció - Wikipédia (magyar)