algorytm.org

Metoda Jacobiego



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 Jacobiego
Ocena użytkowników:***** / 171
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 08 sierpnia 2005 21:10

Metoda Jacobiego 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). Kolejne przybliżenia będziemy obliczać według następującego wzoru:
x^{n+1} = Mx{n} + Nb
(indeksy n oznaczają tutaj numer iteracji)
gdzie M = I - NA, N jest pewną macierzą kwadratową, I to macierz jednostkowa (złożona z samych zer oprócz głównej przekątnej na której znajdują się jedynki). 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}
W metodzie Jacobiego przyjmiemy, że N=D-1, to wówczas M = -D-1(L+U). 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. Macierz D-1 otrzymamy po podniesieniu do potęgi -1 wszystkich wartości na głównej przekątnej macierzy D. Metoda ta jest zbieżna dla dowolnego przybliżenia początkowego rozwiązania x0, jeśli promil spektralny -D-1(L+U) jest mniejszy od jeden (promień spektralny to największa wartość bezwzględna z wartości własnej macierzy). W przeciwnym wypadku nie dla każdego przybliżenia początkowego otrzymamy rozwiązanie układu.

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 = N
\begin{bmatrix} 4 & 0 & 0 & 0\\ 0 & 5 & 0 & 0\\ 0 & 0 & 10 & 0\\ 0 & 0 & 0 & 4 \end{bmatrix}^{-1} = \begin{bmatrix} 0.25 & 0 & 0 & 0\\ 0 & 0.2 & 0 & 0\\ 0 & 0 & 0.1 & 0\\ 0 & 0 & 0 & 0.25 \end{bmatrix}
A teraz kolejno M = -D-1(L+U) = -N(L+U).
\begin{bmatrix} 0 & 0.25 & 0.05 & -0.5\\ 0.2 & 0 & 0 & 0.4\\ -0.02 & -0.1 & 0 & 0.1\\ 0 & 0.5 & 0.25 & 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,2x10 + 0,4x40
x21 = 0
x31 = -1 - 0,02x10 - 0,1x20 + 0,1x40
x31 = -1
x41 = 1,25 + 0,5x20 + 0,25x30
x41 = 1,25

Kolejna iteracja
x12 = 7,5 + 0,25x21 + 0,05x31 - 0,5x41
x12 = 6,825
x22 = 0 + 0,2x11 + 0,4x41
x22 = 2
x32 = -1 - 0,02x11 - 0,1x21 + 0,1x41
x32 = -1,025
x42 = 1,25 + 0,5x21 + 0,25x31
x42 = 1

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
***** / 30
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 3
Tomasz LubińskiJava
.java
.java
***** / 10
 
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: 08 września 2015 08:37
Komentarze
photo
+13 # wargavoc 2010-04-27 21:17
Dzięki serdeczne! Ten artykuł pewnie uratuje mi 4 litery na kolokwium! Dzięki!
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-18 # janiu 2010-11-14 17:23
A gdzie porzadek k...
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # Fen 2011-05-23 14:42
Ja mam zastrzeżenia co do implementacji w C. Testowane dla układu równań charakterystycz nego dla metody thomasa - przy tej daje zupełnie rozbieżne wyniki. Każda iteracja się oddala od rozwiązania zamiast przybliżać.
dlaczego tak się dzieje? wina implementacji, czy algorytm ma jakieś ograniczenia?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+4 # goscina 2012-11-18 17:06
Warunkiem wystarczajacym aby zaszla zbieznosc iteracji jest to aby amcierz A byla macierza przekatniowo dominujaca.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-6 # gosciu 2011-12-19 20:41
pewnie chodzi o zbieznosc gosciu
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-7 # mac_ 2012-05-12 13:03
Super jasno i przejrzyście opisana teoria oraz problem i jego rozwiązanie. Dzięki
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz