Materiały przygotowane w ramach projektu „Uruchomienie unikatowego kierunku studiów Informatyka Stosowana odpowiedzią na zapotrzebowanie rynku pracy” ...
10 downloads
13 Views
165KB Size
Metody numeryczne
materiały do wykładu dla studentów
3. Metody iteracyjne rozwiązywania układów równań liniowych 3.1. 3.2. 3.3.
Metoda iteracji prostej Metoda iteracji Seidela Zbieżność metod iteracyjnych i warunek stopu
Materiały przygotowane w ramach projektu „Uruchomienie unikatowego kierunku studiów Informatyka Stosowana odpowiedzią na zapotrzebowanie rynku pracy” ze środków Programu Operacyjnego Kapitał Ludzki współfinansowanego ze środków Europejskiego Funduszu Społecznego nr umowy UDA – POKL.04.01.01-00-011/0900
Metody numeryczne – 3. Metody iteracyjne rozwiązywania układów równań liniowych
Metody iteracyjne są szczególnymi przypadkami metody kolejnych przybliżeń.
3.1. Metoda iteracji prostej
Układ równań liniowych
⋯ , ⋯ , 3.1 ………………………………………… ⋯ ,
przekształcamy do postaci dogodnej do stosowania metody iteracji prostej (zakładamy wstępnie, że wszystkie elementy 0dla 1,2, … , ) dzieląc -te równanie układu przez czynnik :
gdzie
⋯ , ⋯ , 3.2 ……………………………………………… ⋯ , , ,
, ,
0, Oznaczając: ! ⋮ # , $
!
0
…
1,2, … , , 1,2, … ,
0 …
zapisujemy układ równań 3.2 w postaci macierzowej: %
1,2, … ,
3.3
… … … … # … … … … 0 … ,
$% 3.4
Postać ta jest podstawą utworzenia ciągu kolejnych przybliżeń rozwiązania: % '( % )
© Uniwersytet Ekonomiczny w Krakowie
$% ' 3.5 dowolne 36
Metody numeryczne – 3. Metody iteracyjne rozwiązywania układów równań liniowych
Najczęściej za przybliżenie zerowe %
)
przyjmuje się wektor zerowy lub wektor .
Zależność 3.5 można zapisać w postaci: 4 2 3 2 1
'(
'
⋯
⋯ ……………………………………………… ' ' ⋯ ,
'(
'(
'
'
'
'
'
,
, 3.6
'
,
Twierdzenie 3.1.
Jeżeli ciąg 7% ' 8 jest zbieżny, to jego granica jest rozwiązaniem układu równań 3.2 (równoważnie – rozwiązaniem układu 3.1 ). Przykład 3.1. 5
2 10 3
5 10 12
Metodą iteracji prostej znaleźć pierwsze dwa przybliżenia rozwiązania układu równań: 6 2
3 6
Przekształcamy podany układ równań do postaci dogodnej do stosowania metody iteracji:
© Uniwersytet Ekonomiczny w Krakowie
37
Metody numeryczne – 3. Metody iteracyjne rozwiązywania układów równań liniowych
3.2. Metoda iteracji Seidela Metoda ta jest pewną modyfikacją metody iteracji prostej. W metodzie iteracji prostej przy obliczaniu 1 -go przybliżenia niewiadomych , , … , korzystamy jedynie z tego przybliżenia niewiadomych , , … , . W metodzie Seidela wykorzystujemy natomiast najświeższą informację, bowiem przy obliczaniu 1 -ego przybliżenia niewiadomej 9 1 korzystamy z uprzednio obliczonych 1 -szych przybliżeń niewiadomych , … , . Sprowadzamy układ równań do postaci dogodnej do stosowania metody iteracji i wówczas: '(
'(
∑
;
'(
'(
'
'(
,
∑
;
'(
'
,
∑
;
'
……………………………………………………… '(
∑
;
'(
∑
'
;
,
,
3.2
3.7
……………………………………………………… '(
∑
;
'(
© Uniwersytet Ekonomiczny w Krakowie
'
.
38
Metody numeryczne – 3. Metody iteracyjne rozwiązywania układów równań liniowych
Jako przybliżenie %
)
przyjmujemy wektor .
Zapisując powyższe wzory w postaci macierzowej mamy: przy czym $
=
>, gdzie:
=
%
=%
'(
'(
0 0 0 … 0 B 0 0 … 0 E A … D A 0 0 D , > A … … … … …D … 0C @
>%
'
, 3.8
0 B 0 0 A A 0 0 0 A… … … @ 0 0 0
… E … D … D. … …D … 0 C
Uwaga 3.1. Ze względu na „zapamiętywanie” tylko ostatnich obliczeń metoda Seidela charakteryzuje się mniejszym zużyciem pamięci niż metoda iteracji prostej i z tego powodu jest bardziej użyteczna dla zagadnień z macierzami dużego wymiaru. Z drugiej jednak strony, metoda iteracji jest stabilniejsza, tzn. jest zbieżna w pewnych przypadkach, w których metoda Seidela jest rozbieżna.
Przykład 3.2. 5
2
5 10 12
Metodą Seidela znaleźć pierwsze i drugie przybliżenie rozwiązania układu równań: 6 2
10 3
© Uniwersytet Ekonomiczny w Krakowie
3 6
39
Metody numeryczne – 3. Metody iteracyjne rozwiązywania układów równań liniowych
3.3. Zbieżność metod iteracyjnych i warunek stopu
W twierdzeniu 3.1. znalezienie rozwiązania układu równań liniowych metodą iteracyjną uzależnione jest od zbieżności ciągu iteracyjnego. Podamy teraz kryteria, które zapewniają zbieżność procedury iteracyjnej.
Twierdzenie 3.2.
Ciąg kolejnych przybliżeń 3.5 dla układu równań 3.1 jest zbieżny, jeśli zachodzi jeden z warunków: a) macierz T jest przekątniowo dominująca, tzn.: ∀ ∈ H1, … , I: KL ; M
lub równoważnie:
LN|
∀ ∈ H1, … , I: KL ; M
|,
L N 1;
b) macierz T jest słabo przekątniowo dominująca, tzn.: ∀ ∈ H1, … , I: KL ; M
LQ|
| ∧ ∃ ∈ H1, … , I: KL
c) macierz T jest symetryczna i dodatnio określona.
© Uniwersytet Ekonomiczny w Krakowie
; M
LN|
|;
40
Metody numeryczne – 3. Metody iteracyjne rozwiązywania układów równań liniowych
Uwaga 3.2. Twierdzenie 3.2. dotyczące warunków zbieżności metody iteracji jest słuszne także dla metody Seidela. Metoda Seidela zapewnia na ogół szybszą zbieżność niż metoda iteracji prostej. Uwaga 3.3. Dla macierzy o dominującej przekątnej można sformułować wniosek, że zazwyczaj im większa dominacja przekątnej nad pozostałymi elementami, tym metody iteracji prostej i Seidla są szybciej zbieżne. Nie jest to jednakże prawda w ogólnym przypadku, znane są bowiem kontrprzykłady.
Uwaga 3.4. Teza twierdzenia 3.2 pozostaje w mocy, jeśli to macierz TU będzie przekątniowo dominująca. Oznacza to, że element przekątnej może dominować „w kolumnach”, a nie „w wierszach”.
Uwaga 3.5. Twierdzenie 3.2 nie wyczerpuje warunków wystarczających na zbieżność metody Seidela. Zdarza się, że algorytm jest zbieżny w sytuacjach nieopisanych powyższymi kryteriami. Tak jest np. w przypadku macierzy Google’a z poprzedniego rozdziału, do których rozwiązania stosuje się właśnie metody iteracyjne.
Przykład 3.3. (cd. Przykładu 3.1.) 5
2 10 3
Rozważmy ponownie układ z przykładu 3.1: 6 2
3 6
5 10 12
Warunki zbieżności z podpunktu a) twierdzenia 3.2. są tu spełnione, bo:
Kolejnym zagadnieniem jest odpowiedź na pytanie, w którym momencie należy przerwać procedurę iteracyjną, aby uzyskać przybliżenie rozwiązania z żądaną dokładnością. Sformułowanie warunku stopu wymaga wprowadzenia pojęcia normy macierzy (w szczególności te same definicje pracują dla wektorów).
© Uniwersytet Ekonomiczny w Krakowie
41
Metody numeryczne – 3. Metody iteracyjne rozwiązywania układów równań liniowych
Definicja 3.1. (Norma macierzy)
Niech T będzie macierzą kwadratową stopnia `. Normę macierzy T wyznacza każde z podanych wyrażeń: a) norma kolumnowa
b) norma wierszowa
'
‖T‖
max KL
L
‖T‖[
max KL
L
c) norma euklidesowa ‖T‖\
Z Z'
;
'
Z Z'
'
'
;
]K K ;
;
^
/
Załóżmy, że metoda iteracji dla układu równań 3.2 jest zbieżna, zaś wektor %c jest jego rozwiązaniem dokładnym. Wtedy: Twierdzenie 3.3.
∀ ∈ a: b%c
%
‖$‖ ( bQ ⋅ b% 1 ‖$‖
%
)
Wniosek 3.4.
b.
Jeśli e 9 0 jest zadaną dokładnością rozwiązania iteracyjnego oraz której: to wektor %
‖$‖ ( ⋅ b% 1 ‖$‖
%
)
b N e,
∈ a jest liczbą, dla
przybliża rozwiązanie dokładne %c z dokładnością e.
Uwaga 3.6. Nie ma znaczenia, jakiego rodzaju normy użyjemy w twierdzeniu 3.3. Istotne jest jedynie, aby stosować konsekwentnie ten sam rodzaj normy w całym wzorze.
© Uniwersytet Ekonomiczny w Krakowie
42
Metody numeryczne – 3. Metody iteracyjne rozwiązywania układów równań liniowych
Przykład 3.4. (cd. Przykładu 3.1) 5
Zapytamy teraz, która iteracja dla układu 6 2
przybliży rozwiązanie z dokładnością e
2 10 3
© Uniwersytet Ekonomiczny w Krakowie
3 6
0,00001.
5 10 12
43
