Metoda Eliminacji Gaussa
Dany jest układ równań
)
0
(
)
0
(
b
x
A
=
w postaci:
)
0
(
)
0
(
1
)
0
(
1
0
)
0
(
0
)
0
(
1
)
0
(
1
1
)
0
(
11
0
)
0
(
10
)
0
(
0
)
0
(
0
1
)
0
(
01
0
)
0
(
00
n
n
nn
n
n
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
=
+
+
+
=
+
+
+
=
+
+
+
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
Odejmujemy od i-tego (i=1,2,…,n)wiersza wiersz pierwszy pomnożony przez a
i0
(0)
/a
00
(0)
.
Dostajemy w ten sposób układ równań:
)
1
(
)
1
(
1
)
1
(
1
)
1
(
1
)
1
(
1
1
)
1
(
11
)
1
(
0
)
1
(
0
1
)
1
(
01
0
)
1
(
00
0
0
n
n
nn
n
n
n
n
n
b
x
a
x
a
b
x
a
x
a
b
x
a
x
a
x
a
=
+
+
+
=
+
+
+
=
+
+
+
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
Następnie analogicznie odejmujemy od i-tego wiersza (i=2,3,…,n) wiersz drugi pomnożony
przez a
i1
(1)
/a
11
(1)
. Postępujemy tak n-1 razy, aż do uzyskania macierzy w postaci:
)
2
(
0
)
2
(
0
1
)
2
(
01
0
)
2
(
00
b
x
a
x
a
x
a
n
n
=
+
+
+
K
)
(
1
)
(
1
1
)
(
11
n
n
n
n
n
b
x
a
x
a
=
+
+ K
……………………………….
)
(
)
(
n
n
n
n
nn
b
x
a
=
Teraz już możemy rozwiązać układ równań stosując wzór:
nn
n
n
a
b
x =
ii
i
ii
n
in
i
i
a
x
a
x
a
b
x
1
1
+
+
−
−
−
=
K
, gdzie i=n-1,n-2,…,1.
Metoda Jacobiego
Metoda Jacobiego jest metodą iteracyjną rozwiązania układu równań liniowych. Metody te
polegają na konstruowaniu ciągu przybliżeń wektora rozwiązań x
(0)
, x
(1)
,…,x
(i)
,… określonego
wzorem:
x
(i+1)
=Mx
(i)
+w, i=0,1,… gdzie M jest pewną macierzą kwadratową, a w jest wektorem.
Rozważmy układ równań Ax=b. Przyjmijmy, że A=L+D+U, gdzie L jest macierzą trójkątną
dolną, D jest macierzą diagonalną, a U jest macierzą trójkątną górną.
Układ równań w postaci Ax=b możemy zatem zapisać w postaci:
(L+D+U)x=b
Przekształcając otrzymujemy:
Dx=-(L+U)x+b.
A więc:
x=-D
-1
(L+U)x+D
-1
b.
Możemy więc skonstruować ciąg przybliżeń rozwiązania w postaci:
x
i+1
=-D
-1
(L+U)x
i
+D
-1
b.
Metoda Jacobiego jest zbieżna dla macierzy nieredukowalnych i diagonalnie słabo
dominujących.
Def.:
Macierz A wymiaru n×n (n≥2) nazywamy redukowalną, jeżeli istnieje macierz permutacji P
taka, że:
=
=
−
22
12
11
1
0
'
A
A
A
AP
P
A
, gdzie A
11
i A
22
są macierzami kwadratowymi. Jeżeli taka
macierz permutacji nie istnieje, to A nazywamy macierzą nieredukowalną.
Def.:
Macierz A=
)
(
ij
a
nazywamy diagonalnie słabo dominującą, jeśli dla i=1,2,…,n zachodzą
nierówności:
∑
≠
=
≥
n
i
j
j
ij
ii
a
a
1
oraz istnieje co najmniej jedno i takie, że
∑
≠
=
>
n
i
j
j
ij
ii
a
a
1
.
Przykład: Metoda eliminacji Gaussa:
x
0
+2x
1
+x
2
=8
3x
0
+x
1
+x
2
=8
x
0
+3x
1
+x
2
=10
Mamy więc macierz układu:
10
1
3
1
8
1
1
3
8
1
2
1
Zerujemy pierwszą kolumnę (j=0)
j=0, i=1
a
10
/a
00
=3/1=3
Odejmujemy od wiersza drugiego wiersz pierwszy pomnożony przez 3:
−
−
−
10
1
3
1
16
2
5
0
8
1
2
1
j=0, i=2
a
20
/a
00
=1/1=1
Odejmujemy od wiersza trzeciego wiersz pierwszy pomnożony przez 1:
−
−
−
2
0
1
0
16
2
5
0
8
1
2
1
Zerujemy drugą kolumnę (j=1)
j=1, i=2
a
21
/a
11
=1/(-5)= -1/5
Odejmujemy od wiersza trzeciego wiersz drugi pomnożony przez -1/5:
−
−
−
−
−
5
/
6
5
/
2
0
0
16
2
5
0
8
1
2
1
Teraz, kiedy mamy macierz trójkątną górną przechodzimy do procedury wstecznej i
obliczamy rozwiązanie:
x
2
= (-6/5) / (-2/5)=3
x
1
=(b
1
-a
12
x
2
)/a
11
=(-16+2*3)/(-5)=2
x
0
=(b
0
-a
02
x
2
-a
01
x
1
)/a
00
=(8-1*3-2*2)/1=1
Przykład: Metoda Jacobiego:
3x
0
+x
1
+x
2
=5
5x
1
+x
2
=6
x
0
+x
1
+6x
2
=8
Macierz układu:
=
6
1
1
1
5
0
1
1
3
A
Wektor prawej strony:
=
8
6
5
b
Rozkład na macierze L, D i U:
=
0
1
1
0
0
0
0
0
0
L
=
6
0
0
0
5
0
0
0
3
D
=
0
0
0
1
0
0
1
1
0
U
=
+
0
1
1
1
0
0
1
1
0
U
L
=
−
/
1
0
0
0
5
/
1
0
0
0
3
/
1
1
D
Przyjmujemy x
0
=[0,0,0]
T
.
=
⋅
+
⋅
⋅
−
=
33
,
1
2
,
1
67
,
1
8
6
5
6
/
1
0
0
0
5
/
1
0
0
0
3
/
1
0
0
0
0
1
1
1
0
0
1
1
0
6
/
1
0
0
0
5
/
1
0
0
0
3
/
1
1
x
=
⋅
+
⋅
⋅
−
=
85
,
0
93
,
0
82
,
0
8
6
5
6
/
1
0
0
0
5
/
1
0
0
0
3
/
1
6
/
8
5
/
6
3
/
5
0
1
1
1
0
0
1
1
0
6
/
1
0
0
0
5
/
1
0
0
0
3
/
1
2
x
1. Fortuna Z., Macukow B., Wąsowski J. Metody Numeryczne. Warszawa : Wydawnictwa
Naukowo-Techniczne, 2005. ISBN 83-204-3245-6.
2. Jankowscy, Janina i Michał. Przegląd Metod i Algorytmów Numerycznych, cz.2.
Warszawa : Wydawnictwa Naukowo-Techniczne, 1982. ISBN 83-204-0352-9.