WYKŁAD 7
UKŁADY RÓWNAŃ LINIOWYCH – METODY ITERACYJNE
STACJONARNE METODY ITERACYJNE
Omawianie metod iteracyjnych rozpoczniemy od przedstawienia macierzy wyjściowego układu równań
AX = B
w postaci sumy
(1)
A =S+D+T= D+J
(2)
macierzy trójkątnej dolnej S o zerowych elementach diagonalnych, macierzy diagonalnej D = diag(ai i ) oraz
macierzy trójkątnej górnej T o zerowych elementach diagonalnych. Rozwiązywany układ równań (1)
mo emy więc zapisać następująco
D X = − ( S + T) X + B .
(3)
Jeśli macierz D jest nieosobliwa mo emy przejść do postaci
X = −D −1 (S + T) X + D −1 B ,
(4)
gdzie
D −1 = diag (1 ai i )
i utworzyć ciąg kolejnych przybli eń
X [ k +1] = α J X [ k ] + β J (k = 0, 1, 2),
(5)
gdzie:
α J = −D −1 (S + T) ,
β J = D −1 B ,
określający najprostszą metodę iteracyjną zwaną metodą Jacobiego lub te metodą iteracji prostej. Łatwo mo na
sprawdzić, e zachodzi następująca zale ność po-między współrzędnymi kolejnych przybli eń
x
[ k +1]
i
1
=
ai i
n
[k ]
bi − ∑ ai j x j .
j =1
( j ≠i)
(6)
Metoda Gaussa i Seidela jest modyfikacją metody Jacobiego, w której przy obliczaniu przybli enia wy szego
niewiadomej xi (i 1) wykorzystywane są znane ju wartości ka dego wy szego przybli enia niewiadomych
x1 , x2 , ..., xi −1 . Metodę Gaussa i Seidela określa zatem zmodyfikowany układ równań (6), w którym czyni się u ytek
z wy szego przybli enia xi[ k +1] natychmiast po jego obliczeniu
[ k +1]
x1
[ k +1]
xi
=
1
ai i
=
1
a11
n
[k ]
b1 − ∑ a1 j x j ,
j=2
i −1
n
[ k +1]
[k ]
bi − ∑ ai j x j − ∑ ai j x j
j =1
j = i +1
(i 1; k = 0, 1, 2, ...) .
(7)
Korzystając z przedstawienia (4) układu równań (1) mo emy te zale ności zapisać w następującej
postaci macierzowej
X [ k +1] = α GS X [ k ] + β GS ,
(8)
gdzie:
α GS = − (S + D) −1 T,
β GS = (S + D) −1 B.
Przepisując zale ności (7) w postaci
x
[ k +1]
i
=x
[k ]
i
n
1 i −1
[ k +1]
[k ]
−
∑ ai j x j + ∑ ai j x j − bi
ai i j = 1
j= i
( i 1)
(i = 1, 2, ..., n) ,
po pomno eniu poprawek obliczanych niewiadomych
ω ∈ (0, 2), otrzymujemy ciągi kolejnych przybli eń:
x1 , x 2 ,
...,
xn
przez odpowiednio dobraną liczbę:
x
[ k +1]
i
=x
[k ]
i
n
ω i −1
[ k +1]
[k ]
−
∑ ai j x j + ∑ ai j x j − bi
ai i j = 1
j= i
(i 1)
(i = 1, 2, ..., n) ,
określające
metody
W przypadku
relaksacyjne.
Liczba
ω
oznacza
(9)
tzw.
ω 1
parametr
relaksacji.
(10)
metoda nosi nazwę metody kolejnych nadrelaksacji (w skrócie SOR, od ang. successive
overrelaxation), w przypadku
01)
(i = 1, 2, ..., n) ,
n
∑a
j = i +1
ij
x
[k ]
j
− bi
skąd wynika zapis macierzowy metod relaksacyjnych
X
[ k +1]
= αω X
[k ]
+ βω ,
(12)
gdzie:
α ω = (D + ω
(…)
…
(14)
{Sprowadzanie ukladu rownan do postaci normalnej}
for i:=1 to n do
for j:=1 to n do
AT[i,j]:=A[j,i];
for i:=1 to n do
for j:=1 to n do begin
sp:=0;
for k:=1 to n do
sp:=sp+AT[i,k]*A[k,j];
C[i,j]:=sp;
end;
for i:=1 to n do begin
sp:=0;
for k:=1 to n do
sp:=sp+AT[i,k]*B[k];
D[i]:=sp;
end;
for i:=1 to n do begin
B[i]:=D[i];
for j:=1 to n do
A[i,j]:=C[i,j];
end;
omin:
{Rozwiazywanie ukladu rownan…
... zobacz całą notatkę
Komentarze użytkowników (0)