Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

obrazek

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Równania

Eliminacja Gaussa-Crouta

SPIS TREŚCI
Podrozdziały

Definicje

W podstawowym algorytmie eliminacji Gaussa wykonywane jest dzielenie przez element leżący na przekątnej głównej macierzy współczynników. Jeśli element ten jest równy 0, to dzielenie nie może zostać wykonane i algorytm musi zakończyć pracę z błędem.

Wprowadź do programu z poprzedniego rozdziału poniższe dane:

4
0 2 3 4 49
1 0 3 4 45
1 2 0 4 36
1 2 3 0 23

Wynik
Rozwiązywanie układu równań liniowych metodą eliminacji Gaussa
--------------------------------------------------------------

Wpisz dane wejściowe:

4
0 2 3 4 49
1 0 3 4 45
1 2 0 4 36
1 2 3 0 23

Błąd w trakcie obliczeń!!!

Układ posiada jednak rozwiązanie:

x0 = 2
x1 = 3
x2 = 5
x3 = 7

Rozwiązanie układu równań może istnieć pomimo porażki eliminacji Gaussa. Aby uniknąć tego typu sytuacji, postępujemy podobnie jak w algorytmie rozkładu LU z piwotowaniem. Zamiast dzielić przez element przekątnej, wyszukujemy w danym wierszu współczynnik największy, po czym przestawiamy kolumny macierzy tak, aby ten największy element znalazł się na przekątnej macierzy współczynników. Aby fizycznie nie przestawiać kolumn, zastosujemy wektor kolumnowy, poprzez który będziemy się odwoływać do elementów macierzy współczynników.

Taki zmodyfikowany algorytm nosi nazwę eliminacji Gaussa-Crouta.

Na początek:  podrozdziału   strony 

Eliminacja Gaussa-Crouta

Algorytm eliminacji Gaussa-Crouta

Dane wejściowe:

ε stała określająca dokładność porównania z zerem.
n liczba równań i niewiadomych w układzie.
AB macierz o rozmiarze n × (n +1), w której znajdują się współczynniki przy niewiadomych oraz wyrazy wolne w kolumnie n + 1.

Dane wyjściowe

true/false określa, czy operacja powiodła się, czy nie.
X macierz n × 1 z wartościami niewiadomych, jeśli wynikiem jest true.

Zmienne pomocnicze

i,j,k indeksy
m wartość ujemnego ilorazu, przez który będą mnożone współczynniki równań przy eliminacjach
s suma
WK macierz 1 × ( n + 1 ) z numerami kolumn macierzy AB.

Lista kroków

K01: Utwórz macierz WK o rozmiarze n + 1 Przygotowujemy wektor kolumnowy
K02: Dla i = 0,1,...,n:
wykonuj
WK  [ i ] ← i
Wypełniamy go numerami kolumn
K03: Dla i = 0,1,...,n – 2:
wykonuj
kroki K04...K10
Przechodzimy przez kolejne równania od pierwszego do przedostatniego
K04:     k ← i Numer startowy kolumny
K05:     Dla j = i + 1, i + 2,...,n – 1:
    wykonuj:
        jeżeli | AB  [ i,WK  [ k ] ] | < | AB  [ i,WK  [ j ] ] |,
        to k ← j
Szukamy elementu największego w wierszu i-tym od kolumny i-tej
K06:     Jeśli k ≠ i,
    to WK [ i ] ↔ WK  [ k ]
Wymieniamy kolumnę i-tą z kolumną elementu maksymalnego
K07:     Jeśli | AB  [ i, WK  [ i ] ] | < ε,
    to zakończ z wynikiem false
Reszta algorytmu to eliminacja Gaussa
K08:     Dla j = i + 1, ..., n – 1:
    wykonuj kroki K09... K10
 
K09:          
K10:         Dla k = i + 1, i + 2, ..., n:
        wykonuj:
            AB  [ j,WK[ k ] ] ← AB  [ j,WK  [ k ] ] + m × AB  [ i,WK  [ k ] ]
 
K11: Dla i = n – 1,...,0:
wykonuj kroki K12...K15
 
K12:     Jeśli | AB [ i,WK [ i ] ] | < ε,
    to zakończ z wynikiem false
 
K13:     s ← AB [ i,n ]  
K14:     Dla j = n – 1,..., i + 1:
    wykonuj: s ← s – AB  [ i,WK  [ j ] ] × X  [ WK  [ j ] ]
 
K15:      
K16: Zakończ z wynikiem true  

Poniższy program jest przykładową realizacją algorytmu eliminacji Gaussa-Crouta. Jest to program z poprzedniego rozdziału, w którym dokonaliśmy zmian wymaganych przez nowy algorytm.

Dane do programu mają następującą budowę:

Pierwsza liczba określa liczbę równań i niewiadomych n. Następne liczby określają współczynniki przy niewiadomych oraz wyrazy wolne. Należy wprowadzać je wierszami. Pierwsze n  liczb w każdym wierszu to kolejne współczynniki przy niewiadomych. Po tych n  współczynnikach należy wprowadzić wyraz wolny. Wierszy takich musi być n.

Układ równań:

Dane wejściowe:

4
0 2 3 4 49
1 0 3 4 45
1 2 0 4 36
1 2 3 0 23
Przykładowy program w języku C++
// Eliminacja Gaussa
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//---------------------------

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

const double EPS = 0.000000001;

// Funkcja rozwiązuje układ równań
// metodą eliminacji Gaussa
// n - stopień macierzy
// AB - wskaźnik macierzy n x (n +1)
// X - wskaźnik macierzy rozwiązań n x 1
// Jeśli układ został rozwiązany, to wynikiem jest true.
// Inaczej wynikiem jest false.
//------------------------------------------------------

bool GaussCrout(int n, double ** AB, double * X)
{
    int i,j,k;
    double m,s;
    int * WK;


    // Przygotowujemy wektor kolumnowy

    WK = new int [n + 1];

    for(i = 0; i <= n; i++) WK[i] = i;

    // Eliminacja

    for(i = 0; i < n - 1; i++)
    {
        for(k = i, j = i + 1; j < n; j++)
            if(fabs(AB[i][WK[k]]) < fabs(AB[i][WK[j]])) k = j;

        if(k != i) swap(WK[k],WK[i]);

        if(fabs(AB[i][WK[i]]) < EPS)
        {
            delete [] W;
            return false;
        }

        for(j = i + 1; j < n; j++)
        {
            m = -AB[j][WK[i]] / AB[i][WK[i]];
            for(k = i + 1; k <= n; k++) AB[j][WK[k]] += m * AB[i][WK[k]];
        }
    }

    // Obliczanie wartości niewiadomych

    for(i = n - 1; i >= 0; i--)
    {
        if(fabs(AB[i][WK[i]]) < EPS)
        {
            delete [] W;
            return false;
        }
        s = AB[i][n];
        for(j = n - 1; j > i; j--) s -= AB[i][WK[j]] * X[WK[j]];
        X[WK[i]] = s / AB[i][WK[i]];
    }

    // Usuwamy wektor kolumnowy

    delete [] WK;

    return true;
}

// Program główny
//---------------

int main()
{
    setlocale(LC_ALL,"");

    cout << setprecision(5) << fixed;

    cout << "Rozwiązywanie układu równań liniowych metodą eliminacji Gaussa-Crouta" << endl
         << "---------------------------------------------------------------------" << endl << endl
         << "Wpisz dane wejściowe:" << endl << endl;

    int n;     // Liczba równań w układzie

    cin >> n;

    int i,j;

    // Tworzymy dynamicznie potrzebne macierze

    double ** AB ; // Macierz współczynników przy niewiadomych x oraz wyrazów wolnych
    double * X ;   // Macierz niewiadomych

    AB = new double * [n];
    X  = new double [n];

    for(i = 0; i < n; i ++) AB[i] = new double [n + 1];

    // Odczytujemy dane układu równań

    for(i = 0; i < n; i++)
        for(j = 0; j <= n; j++) cin >> AB[i][j];

    cout << endl;

    // Rozwiązujemy układ równań

    if(GaussCrout(n,AB,X))
    {
        for(i = 0; i < n; i++)
            cout << "x" << i << " = " << setw(12) << X[i] << endl;
    }
    else cout << "Błąd w trakcie obliczeń!!!" << endl;

    cout << endl;

    // Usuwamy tablice dynamiczne

    for(i = 0; i < n; i++) delete [] AB[i];
    delete [] AB;
    delete [] X;

    return 0;
}
Wynik
Rozwiązywanie układu równań liniowych metodą eliminacji Gaussa-Crouta
---------------------------------------------------------------------

Wpisz dane wejściowe:

4
0 2 3 4 49
1 0 3 4 45
1 2 0 4 36
1 2 3 0 23

x0 =      2.00000
x1 =      3.00000
x2 =      5.00000
x3 =      7.00000
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.