algorytm.org

Metoda eliminacji Gaussa

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Metoda eliminacji Gaussa
Ocena użytkowników:***** / 97
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 08 sierpnia 2005 21:28

Metoda eliminacji Gaussa pozwala nam obliczyć układ n równań z n niewiadomymi Ax=b. Przekształcamy w niej macierz współczynników A do macierzy trójkątnej górnej R, z której następnie obliczamy ostateczne rozwiązanie - czyli wektor x. Macierz trójkątną górną R otrzymujemy w następujący sposób: (Przez macierz (A,b) rozumieć będziemy macierz współczynników A z dodaną na końcu kolumną wyrazów wolnych b)
  1. W macierzy (A,b) szukamy elementu ar1 różnego od zera i przechodzimy do następnego punktu. Jeżeli natomiast nie istnieje taki element to znaczy, że macierz jest osobliwa i nie możemy rozwiązać tego układu.
  2. Zamieniamy wiersz r-ty i pierwszy.
  3. Odejmujemy od i-tego wiersza macierzy li krotność wiersza i-tego i pierwszego. Można to przedstawić za pomocą wzorów: (i=2,3,...,n j=2,3,...,n)
    a_{ij} = a_{ij} - l_i * a{1j}\\\\ b_i = b_i - l_i * b_i\\\\ \text{gdzie } l_i = \frac{a_{i1}}{a_{11}}
  4. Następnie wywołujemy tą procedurę od punktu pierwszego rekurncyjnie dla macierzy (A',b') - czyli macierz (A,b) pomniejszoną o pierwszą kolumnę i pierwszy wiersz.
    (A,b)=\begin{vmatrix} a_{11}&\begin{matrix} a_{12}&...&a_{1n}&b_{n} \end{matrix}\\ \begin{matrix} a_{21}\\ ...\\ a_{n1} \end{matrix}&\begin{vmatrix} a_{22}&...&a_{2n}&b_{2}\\ ...&...&...&...\\ a_{n2}&...&a_{nn}&b_{n} \end{vmatrix} \end{vmatrix}


    (A',b')=\begin{vmatrix} a_{22}&...&a_{2n}&b_{2}\\ ...&...&...&...\\ a_{n2}&...&a_{nn}&b_{n} \end{vmatrix}


Wybór częściowy elementu podstawowego uzyskamy wybierając za element, a w punkcie pierwszym |ar1|=max|ai1| i=1,2,...,n
Pełny wybór elementu podstawowego poprzez |ars|=max|aij| i=1,2,...,n j=1,2,...,n Musimy przestawić wiersz r-ty i pierwszy oraz kolumnę s-tą i pierwszą (zmiany kolumn należy zapamiętać gdyż powoduje ona zamianę niewiadowmych!).
Gdy przekształcimy już macierz współczynników A do macierzy trójkątnej górnej R, oraz wektor b do wektora c możemy już wyznaczyć ostateczne rozwiązanie ze wzoru: (i=n,n-1,...,1)
x_{i}=\frac{c_{i}-\sum_{k=i+1}^{n}{r_{ik}x_{k}}}{r_{ii}}


Przykład, niech będzie dana macierz A oraz wektor b, z których tworzymy macierz (A,b)
(A,b)=\begin{vmatrix}3&1&0&-3\\1&2&-1&0\\0&-1&3&0\end{vmatrix}


po przekształceniach:
\begin{vmatrix}3&1&0&-3\\0&\frac{5}{3}&-1&1\\0&-1&3&0\end{vmatrix}


natępnie wywołujemy procedurę rekurencyjnie dla:
\begin{vmatrix}\frac{5}{3}&-1&1\\-1&3&0\end{vmatrix}


po przekształceniach:
\begin{vmatrix}\frac{5}{3}&-1&1\\0&\frac{12}{5}&\frac{3}{5}\end{vmatrix}


Ponieważ ostatniej macierzy nie możemy już rekurencyjnie wywołać (po odcięciu górnego wiersza i prawej kolumny zostanie wektor), zatem otrzymaliśmy szukaną macierz R i wektor c, z których wyznaczamy ostateczne rozwiązanie
(R,c)=\begin{vmatrix}3&1&0&-3\\0&\frac{5}{3}&-1&1\\0&0&\frac{12}{5}&\frac{3}{5}\end{vmatrix}


x[3]=0.25 x[2]=0.75 x[1]=-1.25

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Jan WojciechowskiC/C++
.cpp
.cpp
***** / 14
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 15
Andrzej BoruckiDelphi/PascalRozbudowany analizator
.pas
.pas
***** / 1
Adrian CimochowskiJava
.java
.java
***** / 1
slovicPythonpython 2.7 + numpy
.py
.py
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 04 września 2012 13:58
Komentarze
photo
-1 # anonim 2010-04-18 23:30
Artykuł bardzo pomógł. Zobrazował logicznie kroki w eliminacji gaussa oszczędzając mi niemało czasu. =]
Dzięki.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-7 # Anonim zwany Gallem 2011-04-02 17:56
Można by zaimplementować też dla układów z
prostokątną macierzą główną układu przez sprowadzenie go do układu Cramera
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-4 # _exe 2012-01-16 23:07
ma ktoś może implementacje tego w C++? Dość pilnie potrzebna :)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz