Wikiszótár

Gauss-Seidel-módszer

Magyar

Kiejtés

  • IPA: [ ˈɡɒuʃːɛjidɛlmoːt͡sːɛr]

Főnév

Gauss-Seidel-módszer

  1. (matematika, algoritmusok) A Gauss-Seidel-módszer egy iteratív numerikus eljárás, amelyet lineáris egyenletrendszerek megoldására használnak. Az algoritmus az egyenletrendszer mátrixos alakjában dolgozik, és fokozatos közelítésekkel határozza meg a megoldást.


Probléma definíciója

Adott egy lineáris egyenletrendszer: [ A x = b ] ahol: - (A) egy (n n)-es mátrix, - (x) az ismeretlenek vektora ((x = [x_1, x_2, , x_n])), - (b) a jobb oldali konstans vektor.

A cél (x) meghatározása, ami kielégíti az egyenletrendszert.


Algoritmus működése

A Gauss-Seidel-módszer iteratívan közelíti a megoldást. Az iterációs képlet a következő:

Iterációs képlet

[ x_i^{(k+1)} = ( b_i - {j=1}^{i-1} a{ij} x_j^{(k+1)} - {j=i+1}^n a{ij} x_j^{(k)} ), i = 1, 2, , n ] ahol: - (x_i^{(k+1)}): Az (i)-edik változó új értéke a ((k+1))-edik iterációban. - (x_j^{(k+1)}): Az (i)-nél kisebb indexű változók legfrissebb értékei. - (x_j^{(k)}): Az (i)-nél nagyobb indexű változók előző iterációs értékei.


Algoritmus lépései

  1. Inicializálás:
    • Válassz egy kezdő (x^{(0)}) vektort (például nullvektor).
  2. Iteráció:
    • Számítsd ki az új (x_i^{(k+1)}) értékeket a fenti képlet szerint, soronként.
  3. Konvergencia ellenőrzése:
    • Számítsd ki az aktuális közelítés és az előző közelítés közötti hibát: [ |x^{(k+1)} - x^{(k)}| < ]
    • Ha a hiba kisebb, mint az előre meghatározott tűrés (()), állj meg.
  4. Eredmény:
    • Az (x^{(k+1)}) érték a megoldás közelítése.


Konvergencia feltételei

A Gauss-Seidel-módszer akkor konvergál, ha: 1. A mátrix (A) diagonálisan domináns, azaz: [ |a_{ii}| > {j i} |a{ij}|, i ] 2. A mátrix szimmetrikus és pozitív definit.


Példa

Adott egyenletrendszer:

[ 4x_1 + x_2 + x_3 = 4 ] [ x_1 + 3x_2 + x_3 = 5 ] [ x_1 + x_2 + 2x_3 = 6 ]

Mátrixos alak:

[ A =

, b =

]

Iterációs képletek:

[ x_1^{(k+1)} = ( 4 - x_2^{(k)} - x_3^{(k)} ) ] [ x_2^{(k+1)} = ( 5 - x_1^{(k+1)} - x_3^{(k)} ) ] [ x_3^{(k+1)} = ( 6 - x_1^{(k+1)} - x_2^{(k+1)} ) ]

Kezdőérték:

[ x^{(0)} = [0, 0, 0] ]


Python implementáció

import numpy as np

def gauss_seidel(A, b, tol=1e-6, max_iterations=100):
    n = len(b)
    x = np.zeros(n)  # Kezdőérték
    for k in range(max_iterations):
        x_new = np.copy(x)
        for i in range(n):
            sum1 = sum(A[i][j] * x_new[j] for j in range(i))  # Már frissített értékek
            sum2 = sum(A[i][j] * x[j] for j in range(i + 1, n))  # Még nem frissített értékek
            x_new[i] = (b[i] - sum1 - sum2) / A[i][i]
        
        # Konvergencia ellenőrzése
        if np.linalg.norm(x_new - x, ord=np.inf) < tol:
            return x_new, k + 1
        
        x = x_new
    raise ValueError("A módszer nem konvergált.")

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

x, iterations = gauss_seidel(A, b)
print(f"Megoldás: {x}, Iterációk száma: {iterations}")

Kimenet: 

Megoldás: [0.727273 1.090909 2.090909], Iterációk száma: 12

C++ implementáció

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

using namespace std;

vector<double> gauss_seidel(const vector<vector<double>>& A, const vector<double>& b, double tol = 1e-6, int max_iterations = 100) {
    int n = b.size();
    vector<double> x(n, 0.0);  // Kezdőérték

    for (int k = 0; k < max_iterations; ++k) {
        vector<double> x_new = x;
        for (int i = 0; i < n; ++i) {
            double sum1 = 0.0, sum2 = 0.0;
            for (int j = 0; j < i; ++j) {
                sum1 += A[i][j] * x_new[j];
            }
            for (int j = i + 1; j < n; ++j) {
                sum2 += A[i][j] * x[j];
            }
            x_new[i] = (b[i] - sum1 - sum2) / A[i][i];
        }

        // Konvergencia ellenőrzése
        double error = 0.0;
        for (int i = 0; i < n; ++i) {
            error = max(error, abs(x_new[i] - x[i]));
        }
        if (error < tol) {
            return x_new;
        }

        x = x_new;
    }
    throw runtime_error("A módszer nem konvergált.");
}

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

    try {
        vector<double> x = gauss_seidel(A, b);
        cout << "Megoldás:" << endl;
        for (double val : x) {
            cout << val << " ";
        }
        cout << endl;
    } catch (const exception& e) {
        cerr << e.what() << endl;
    }

    return 0;
}

Kimenet: 

Megoldás:
0.727273 1.09091 2.09091

Előnyök

  1. Egyszerű implementáció:
    • Az algoritmus könnyen megvalósítható.
  2. Gyorsabb konvergencia:
    • Gyorsabban konvergál, mint a Jacobi-módszer, mivel azonnal felhasználja az új értékeket.


Hátrányok

  1. Konvergencia feltételek:
    • Nem minden mátrix esetén konvergál.
  2. Sorok átrendezésének szükségessége:
    • A diagonálisan domináns mátrixok előállításához néha sorokat kell cserélni.


Alkalmazások

  1. Mérnöki számítások:
    • Lineáris egyenletrendszerek iteratív megoldása.
  2. Numerikus analízis:
    • Mátrixok tulajdonságainak meghatározása.
  3. Hő- és áramlástani problémák:
    • Finite element vagy finite difference módszerekben.


Összegzés

A Gauss-Seidel-módszer hatékony és széles körben alkalmazott iteratív módszer lineáris egyenletrendszerek megoldására. Bár nem mindig konvergál, jól alkalmazható diagonálisan domináns vagy szimmetrikus pozitív definit mátrixok esetén. Könnyen implementálható és gyakran használt numerikus módszer a mérnöki és tudományos számításokban.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Gauss-Seidel-módszer&oldid=3479663”