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:
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:
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
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.
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 = 0Obliczmy 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
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 30 | |
| Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 3 | |
| Tomasz Lubiński | Java | .java | .java | ***** / 10 |
Poprawiony: 08 września 2015 08:37
dlaczego tak się dzieje? wina implementacji, czy algorytm ma jakieś ograniczenia?