algorytm.org

Metoda Gaussa - Seidela

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 Gaussa - Seidela
Ocena użytkowników:***** / 80
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 13 marca 2006 18:42

Metoda Gaussa - Seidela jest metodą iteracyjną i pozwala nam obliczyć układ n równań z n niewiadomymi Ax = b. Wektor x0 będący początkowym przybliżeniem rozwiązania układu będzie dany (zwykle przyjmuje się go jako wektor złożony z samych zer). By zastosować tą metodę należy najpierw tak zamienić kolejność równań układu, aby na głównej przekątnej były elementy różne od zera.
Na początku macierz współczynników A rozłożymy na sumę trzech macierzy A = L + D + U, gdzie L jest macierzą w której znajdują się elementy których numer wiersza jest większy od numeru kolumny, D to macierz diagonalna z elementami tylko na głównej przekątnej, a U to macierz, w której znajdują się elementy których numery wiersza są mniejsze od numerów kolumny. Można to zapisać następująco:
\begin{bmatrix} a_{1,1} & a_{1,2} & ... & a_{1,n}\\ a_{2,1} & a_{2,2} & ... & a_{2,n}\\ ... & ... & ... & ...\\ a_{n,1} & a_{n,2} & ... & a_{n,n} \end{bmatrix} = \begin{bmatrix} 0 & 0 & ... & 0\\ a_{2,1} & 0 & ... & 0\\ ... & ... & ... & ...\\ a_{n,1} & a_{n,2} & ... & 0 \end{bmatrix} + \begin{bmatrix} a_{1,1} & 0 & ... & 0\\ 0 & a_{2,2} & ... & 0\\ ... & ... & ... & ...\\ 0 & 0 & ... & a_{n,n} \end{bmatrix} + \begin{bmatrix} 0 & a_{1,2} & ... & a_{1,n}\\ 0 & 0 & ... & a_{2,n}\\ ... & ... & ... & ...\\ 0 & 0 & ... & 0 \end{bmatrix}
Następnie obliczymy macierz odwrotną do macierzy D, czyli D-1. Otrzymamy ją po podniesieniu do potęgi -1 wszystkich wartości na głównej przekątnej macierzy. Po tych operacjach możemy przystąpić już do iteracyjnego obliczania kolejnych przybliżeń rozwiązania według następującego wzoru:
x^{n+1} = D^{-1}b - D^{-1}Lx^{n+1} - D^{-1}Ux^n
(indeksy n oznaczają tutaj numer iteracji)

Przykład:

Obliczymy następujący układ równań:
4x1 - x2 - 0.2x3 + 2x4 = 30
-1x1 + 5x2 - 2x4 = 0
0.2x1 + x2 + 10x3 - x4 = -10
- 2x2 - x3 + 4x4 = 5

Zapiszmy go teraz w postaci Ax = b
\begin{bmatrix} 4 & -1 & -0.2 & 2\\ -1 & 5 & 0 & -2\\ 0.2 & 1 & 10 & -1\\ 0 & -2 & -1 & 4 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4 \end{bmatrix} = \begin{bmatrix} 30\\ 0\\ -10\\ 5 \end{bmatrix}
Podzielmy teraz macierz A na sumę macierzy L + D + U
\begin{bmatrix} 4 & -1 & -0.2 & 2\\ -1 & 5 & 0 & -2\\ 0.2 & 1 & 10 & -1\\ 0 & -2 & -1 & 4 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 & 0\\ -1 & 0 & 0 & 0\\ 0.2 & 1 & 0 & 0\\ 0 & -2 & -1 & 0 \end{bmatrix} + \begin{bmatrix} 4 & 0 & 0 & 0\\ 0 & 5 & 0 & 0\\ 0 & 0 & 10 & 0\\ 0 & 0 & 0 & 4 \end{bmatrix} + \begin{bmatrix} 0 & -1 & -0.2 & 2\\ 0 & 0 & 0 & -2\\ 0 & 0 & 0 & -1\\ 0 & 0 & 0 & 0 \end{bmatrix}
Obliczmy teraz macierz D-1
\begin{bmatrix} 4 & 0 & 0 & 0\\ 0 & 5 & 0 & 0\\ 0 & 0 & 10 & 0\\ 0 & 0 & 0 & 4 \end{bmatrix} = \begin{bmatrix} 0.25 & 0 & 0 & 0\\ 0 & 0.2 & 0 & 0\\ 0 & 0 & 0.1 & 0\\ 0 & 0 & 0 & 0.25 \end{bmatrix}^{-1}
A teraz kolejno D-1b, D-1L, D-1U
\begin{bmatrix} 7.5\\ 0\\ -1\\ 1.25 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & 0\\ -0.2 & 0 & 0 & 0\\ 0.02 & 0.1 & 0 & 0\\ 0 & -0.5 & -0.25 & 0 \end{bmatrix} \begin{bmatrix} 0 & -0.25 & -0.05 & 0.5\\ 0 & 0 & 0 & -0.4\\ 0 & 0 & 0 & -0.1\\ 0 & 0 & 0 & 0 \end{bmatrix}
Rozpoczynamy od zerowego przybliżenia czyli x10 = 0, x20 = 0, x30 = 0, x40 = 0

Obliczmy pierwszą iterację metody, według przytoczonego na początku wzoru:
x11 = 7,5 + 0,25x20 + 0,05x30 - 0,5x40
x11 = 7,5
x21 = 0 + 0,2x11 + 0,4x40
x21 = 1,5
x31 = -1 - 0,02x11 - 0,1x21 + 0,1x40
x31 = -1,30
x41 = 1,25 + 0,5x21 + 0,25x31
x41 = 1,675

Kolejna iteracja
x12 = 7,5 + 0,25x21 + 0,05x31 - 0,5x41
x12 = 6,9725
x22 = 0 + 0,2x12 + 0,4x41
x22 = 2,0645
x32 = -1 - 0,02x12 - 0,1x22 + 0,1x41
x32 = -1,1784
x42 = 1,25 + 0,5x22 + 0,25x32
x42 = 1,98765

Można teraz obliczyć kolejną iterację. Każda z nich przybliża nas do dokładnego wyniku.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 17
MarianC/C++C++
.cpp
.cpp
***** / 10
CodenameC/C++
.cpp
.cpp
***** / 3
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 3
Tomasz LubińskiJava
.java
.java
***** / 5
 
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: 23 września 2012 14:11
Komentarze
photo
0 # :o 2009-09-01 18:16
bardzo dobrze wytłumaczone
dziękuję
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # ST_PATRICK 2009-10-13 01:37
Mam pytanie czy wzór:
x^(n+1) = D-1b - D-1Lx^(n+1) - D-1Ux^(n)
nie powinien wyglądać tak:
x^(n+1) = D-1b - D-1Lx^(n) - D-1Ux^(n)

Bo mam wrażenie, że jest tam błąd. Może mi ktoś wytłumaczyć dlaczego jest tak?
Bo z analizy kodów wynika, że powinno być tak jak na dole jak podałem.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Tomek 2009-10-14 19:37
Wzór jest prawidłowy, i taki też jest zastosowany w przykładzie. Stosujemy tylko jedna kopię obliczanych przybliżeń x1, x2, x3, .... I właśnie z właściwości macierzy L wynika ten wzór, obliczając xi, bierzemy obliczone już w tym przybliżeniu elementy, x1, x2, ... xi-1 i ponieważ macierz L ma elementy różne od zera tylko takie których numer wiersza jest większy od numeru kolumny to właśnie do obliczeń weźmiemy x1, x2, ... xi-1, elementy xi+1, xi+2, ... xn ze względu na zera w macierzy nam się wyzerują i dlatego nie bierzemy ich pod uwagę. Dla macierzy U jest dokładnie na odwrót, bierzemy tylko pod uwagę xi+1, xi+2, ... xn, których jeszcze w danym przybliżeniu nie obliczaliśmy.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # AS 2010-05-29 20:05
No niestety podany algorytm jest błędny. Przynajmniej programie w Delphi. Weźmy na przykład takie prosty układ: x1+x2=7, x1-x2=3
Rozwiązaniem są liczby 5 i 2 co łatwo sprawdzić. A program niestety pokazuje inne rozwiązanie.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Kubaaaa 2010-09-14 20:44
A czy nie powinno być jakiś kryteriów ? O tak sobie ma wykonywać iteracje ?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # janiu 2010-11-13 16:44
Algorytmy sa dobre (przynajmniej c++) ale trzeba dodac kryteria zbieznosci oraz ustawienie wierszy macierzy, tak aby dominujace wartosci znajdowaly sie na glwonej przekatnej
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Witek 2011-01-26 11:47
Faktycznie równanie w kodzie jest inne niż to uzyte...przynajmniej w C, bo można to sprawdzić dla przykładu z tej storny...dla 1 iteracji pokaże nam inne wyniki niż te uzyskane tutaj licząc na piechotę... bo np x3 tutaj wynosi -1.3, a w programie -1...własnie dlatego że jest zastosowany wzór :
x^(n+1) = D-1b - D-1Lx^(n) - D-1Ux^(n) a nie tak jak tu podany:
x^(n+1) = D-1b - D-1Lx^(n+1) - D-1Ux^(n)

proszę o wytlumaczenie...
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # koks 2011-04-28 23:36
Cytuję Witek:
Faktycznie równanie w kodzie jest inne niż to uzyte...przynajmniej w C, bo można to sprawdzić dla przykładu z tej storny...dla 1 iteracji pokaże nam inne wyniki niż te uzyskane tutaj licząc na piechotę... bo np x3 tutaj wynosi -1.3, a w programie -1...własnie dlatego że jest zastosowany wzór :
x^(n+1) = D-1b - D-1Lx^(n) - D-1Ux^(n) a nie tak jak tu podany:
x^(n+1) = D-1b - D-1Lx^(n+1) - D-1Ux^(n)

proszę o wytlumaczenie...


jest błąd w pierwszej iteracji 0^0=1 a tu autor przyjął 0^0=0
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # michaello 2011-11-02 14:29
a czy jest możliwość umieszczenia rozwiązania tego programu w Scilabie ?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz