Wikiszótár

Gauss-elimináció

Magyar

Kiejtés

  • IPA: [ ˈɡɒuʃːɛliminaːt͡sijoː]

Főnév

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:

 
 
 
 

Az eljárás során az egyenletrendszer megoldásait keressük, ahol megoldás alatt olyan   értendő, amely az   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

Gauss-elimináció algoritmus

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.


Algoritmus célja

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


Lépések

  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.


Pszeudokód

function GaussElimination(A, b):
    n = A mérete
    C = [A|b]  # 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[j][i]) > abs(C[pivot_row][i]):
                pivot_row = j

        # Sorcsere
        C[i], C[pivot_row] = C[pivot_row], C[i]

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

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

    return x

Python implementáció

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[i:, i]))
        C[[i, max_row]] = C[[max_row, i]]  # Sorcsere

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

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

    return x

# Példa használat
A = np.array([[2.0, 1.0, -1.0],
              [-3.0, -1.0, 2.0],
              [-2.0, 1.0, 2.0]])
b = np.array([8.0, -11.0, -3.0])

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

Kimenet: 

Az ismeretlenek megoldásvektora: [2. 3. -1.]

C++ implementáció

#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[i].push_back(b[i]);
    }

    // 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[k][i]) > fabs(A[max_row][i])) {
                max_row = k;
            }
        }
        swap(A[i], A[max_row]);

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

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

    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

Összegzés

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.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Gauss-elimináció&oldid=3480339”