Wikiszótár

Gauss-Jordan-elimináció

Magyar

Kiejtés

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

Főnév

Gauss-Jordan-elimináció

  1. (matematika, algoritmusok) A Gauss-Jordan-elimináció egy algoritmus, amelyet lineáris egyenletrendszerek megoldására, mátrix inverz kiszámítására és mátrix rangjának meghatározására használnak. Az eljárás az egyenletrendszer kibővített mátrixát átalakítja soronként redukált alakra (reduced row-echelon form, RREF) az elemi soroperációk alkalmazásával.


Célja

  • Megoldani a (A x = b) egyenletrendszert, ahol (A) egy koefficiensmátrix, (x) az ismeretlenek vektora, és (b) az eredményvektor.
  • Az eredmény (x) vektor értéke lesz.


Algoritmus lépései

  1. Kibővített mátrix létrehozása:
    • Az (A x = b) egyenletrendszert átalakítjuk egy kibővített mátrixá: [ [A|b] ]
  2. Sorok átrendezése:
    • Ha az aktuális pivot elem nulla, cseréljük ki azt egy másik sorral, amelyben a pivot nem nulla.
  3. Pivotálás:
    • Osztjuk a pivot elem sorát úgy, hogy a pivot elem (1) legyen.
  4. Zérósítás a pivot alatt és felett:
    • Az oszlop többi elemét nullává alakítjuk úgy, hogy a pivot oszlop elemei kivételével minden elem nulla legyen.
  5. Ismétlés minden oszlopra:
    • Lépjünk a következő pivot helyre, és ismételjük meg a folyamatot.
  6. Redukált alak ellenőrzése:
    • A mátrixot addig módosítjuk, amíg az egységmátrix bal oldalon ki nem alakul, és a jobb oldali rész tartalmazza a megoldásokat.


Eredmény

A mátrix az alábbi formában lesz: [ [I | x] ] ahol (I) az egységmátrix, (x) pedig az egyenletrendszer megoldása.


Pszeudokód

GaussJordan(A, b):
    Létrehozzuk a kibővített mátrixot [A|b]
    n = A sorainak száma

    for i in range(n):
        Pivot elem kiválasztása (nem nulla elem az i. oszlopban)
        Ha a pivot elem nulla:
            Sorcsere
        Pivot sor normalizálása úgy, hogy a pivot elem 1 legyen
        Nullázd ki az i. oszlop többi elemét

Példa

Egyenletrendszer

[

]

Kibővített mátrix

[ ]

Gauss-Jordan-elimináció

  1. Pivotálás az első oszlopban:
    • Normalizáljuk az első sort ((a_{11}) = 1).
  2. Nullázás az első oszlop többi helyén:
    • Alakítsuk nullává az első oszlop többi elemét ((a_{21}, a_{31})).
  3. Ismétlés a második és harmadik oszlopokra:
    • Az eljárást folytatva minden oszlop pivot helyén 1-et hozunk létre, a többi helyen nullát.

Redukált mátrix

[ ]

Eredmény

[ x = 5, , y = 3, , z = -2 ]


Python implementáció

import numpy as np

def gauss_jordan(A, b):
    # Kibővített mátrix
    n = len(A)
    augmented_matrix = np.hstack((A, b.reshape(-1, 1)))

    for i in range(n):
        # Pivot elem normalizálása
        augmented_matrix[i] = augmented_matrix[i] / augmented_matrix[i, i]
        
        # Nullázás az oszlop többi helyén
        for j in range(n):
            if i != j:
                augmented_matrix[j] = augmented_matrix[j] - augmented_matrix[j, i] * augmented_matrix[i]

    # Megoldás vektor
    return augmented_matrix[:, -1]

# Példa
A = np.array([
    [1, 1, 1],
    [0, 2, 5],
    [2, 5, -1]
], dtype=float)
b = np.array([6, -4, 27], dtype=float)

solution = gauss_jordan(A, b)
print("Megoldás:", solution)

Kimenet: 

Megoldás: [ 5.  3. -2.]

C++ implementáció

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

void gauss_jordan(vector<vector<double>>& A, vector<double>& b) {
    int n = A.size();

    // Kibővített mátrix
    for (int i = 0; i < n; ++i) {
        A[i].push_back(b[i]);
    }

    // Gauss-Jordan elimináció
    for (int i = 0; i < n; ++i) {
        // Pivot normalizálása
        double pivot = A[i][i];
        for (int j = 0; j <= n; ++j) {
            A[i][j] /= pivot;
        }

        // Nullázás az oszlop többi helyén
        for (int k = 0; k < n; ++k) {
            if (k != i) {
                double factor = A[k][i];
                for (int j = 0; j <= n; ++j) {
                    A[k][j] -= factor * A[i][j];
                }
            }
        }
    }

    // Megoldás kiírása
    for (int i = 0; i < n; ++i) {
        cout << "x" << i + 1 << " = " << A[i][n] << endl;
    }
}

int main() {
    vector<vector<double>> A = {
        {1, 1, 1},
        {0, 2, 5},
        {2, 5, -1}
    };
    vector<double> b = {6, -4, 27};

    gauss_jordan(A, b);

    return 0;
}

Kimenet: 

x1 = 5
x2 = 3
x3 = -2

Előnyök

  1. Általános módszer:
    • Képes tetszőleges lineáris egyenletrendszert megoldani.
  2. Közvetlen megoldás:
    • Az algoritmus közvetlenül adja meg a megoldást.


Hátrányok

  1. Numerikus stabilitás:
    • Lebegőpontos számok használata esetén pontatlanságokat okozhat.
  2. Komplexitás:
    • Az algoritmus időbonyolultsága (O(n^3)), ezért nagy rendszerek esetén lassú.


Összegzés

A Gauss-Jordan-elimináció egy hatékony és közvetlen módszer lineáris egyenletrendszerek megoldására és mátrixinverzióra. Bár kisebb rendszerekhez jól alkalmazható, nagyobb problémák esetén numerikus stabilitási problémák és nagy számítási költség jelentkezhet. Modern numerikus módszerek gyakran helyettesítik iteratív eljárásokkal vagy LU-felbontással.

További információk

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