Plik Metoda Gaussa-Seidla jest procedurą iteracyjną służącą do znajdowania przybliżonych rozwiązań układu liniowych równań algebraicznych z dowolnie wybraną precyzją. Metodę stosuje się do macierzy kwadratowych z niezerowymi elementami na przekątnych, a zbieżność jest gwarantowana, jeśli macierz jest po przekątnej dominująca.
Został stworzony przez Carla Friedricha Gaussa (1777-1855), który w 1823 r. Dał prywatną demonstrację jednemu ze swoich uczniów. Został później oficjalnie opublikowany przez Philippa Ludwiga von Seidela (1821-1896) w 1874 r., Stąd imiona obu matematyków..
Aby w pełni zrozumieć tę metodę, należy wiedzieć, że macierz dominuje po przekątnej, gdy bezwzględna wartość elementu przekątnego każdego rzędu jest większa lub równa sumie wartości bezwzględnych pozostałych elementów z tego samego rzędu..
Matematycznie wyraża się to następująco:
Indeks artykułów
Aby zilustrować, na czym polega metoda Gaussa-Seidla, weźmiemy prosty przypadek, w którym wartości X i Y można znaleźć w układzie równań liniowych 2 × 2 pokazanym poniżej:
5X + 2Y = 1
X - 4Y = 0
1- Po pierwsze, konieczne jest ustalenie, czy zbieżność jest bezpieczna. Od razu można zauważyć, że w efekcie jest to układ dominujący po przekątnej, ponieważ w pierwszym rzędzie pierwszy współczynnik ma wyższą wartość bezwzględną niż pozostałe w pierwszym rzędzie:
| 5 |> | 2 |
Podobnie drugi współczynnik w drugim rzędzie jest również dominujący po przekątnej:
| -4 |> | 1 |
dwa- Zmienne X i Y są rozwiązane:
X = (1 - 2Y) / 5
Y = X / 4
3- Umieszczana jest dowolna wartość początkowa, zwana „ziarnem”: Xo = 1, I = 2.
4-Rozpoczyna się iteracja: aby otrzymać pierwsze przybliżenie X1, Y1, ziarno jest podstawiane w pierwszym równaniu z kroku 2, a wynik w drugim równaniu z kroku 2:
X1 = (1 - 2 I) / 5 = (1 - 2 × 2) / 5 = -3/5
Y1 = X1 / 4 = (-3/5) / 4 = -3/20
5- W podobny sposób postępujemy, aby otrzymać drugie przybliżenie rozwiązania układu równań:
X2 = (1 - 2 Y1) / 5 = (1 - 2x (-3/20)) / 5 = 13/50
Y2 = X2 / 4 = (13/50) / 4 = 13/200
6- Trzecia iteracja:
X3 = (1 - 2 Y2) / 5 = (1 - 2 (13/200)) / 5 = 87/500
Y3 = X3 / 4 = (87/500) / 4 = 87/2000
7- Czwarta iteracja, jako ostatnia iteracja tego przykładowego przypadku:
X4 = (1 - 2 Y3) / 5 = (1 - 2 (87/2000)) / 5 = 913/5000
Y4 = X4 / 4 = (913/5000) / 4 = 913/20000
Wartości te dość dobrze zgadzają się z rozwiązaniem znalezionym przez inne metody rozdzielczości. Czytelnik może to szybko sprawdzić za pomocą programu matematycznego online.
Jak widać, w metodzie Gaussa-Seidela przybliżone wartości uzyskane dla poprzedniej zmiennej w tym samym kroku należy podstawić w następnej zmiennej. To odróżnia ją od innych metod iteracyjnych, takich jak metoda Jacobiego, w której każdy krok wymaga przybliżeń z poprzedniego etapu..
Metoda Gaussa-Seidla nie jest procedurą równoległą, podczas gdy metoda Gaussa-Jordana jest. Jest to również powód, dla którego metoda Gaussa-Seidela ma szybszą zbieżność - w mniejszej liczbie kroków - niż metoda Jordana..
Jeśli chodzi o warunek macierzy dominującej po przekątnej, nie zawsze jest on spełniony. Jednak w większości przypadków zwykła zamiana wierszy z oryginalnego systemu jest wystarczająca, aby warunek został spełniony. Ponadto metoda jest zbieżna prawie zawsze, nawet jeśli warunek dominacji po przekątnej nie jest spełniony..
Poprzedni wynik, uzyskany przez cztery iteracje metody Gaussa-Seidla, można zapisać w postaci dziesiętnej:
X4 = 0,1826
Y4 = 0,04565
Dokładne rozwiązanie proponowanego układu równań to:
X = 2/11 = 0,1818
Y = 1/22 = 0,04545.
Tak więc po zaledwie 4 iteracjach otrzymujesz wynik o jednej tysięcznej dokładności (0,001).
Rysunek 1 ilustruje, jak kolejne iteracje szybko zbiegają się do dokładnego rozwiązania.
Metoda Gaussa-Seidla nie ogranicza się tylko do układu równań liniowych 2 × 2. Powyższą procedurę można uogólnić w celu rozwiązania liniowego układu n równania z n niewiadome, które są reprezentowane w takiej macierzy:
DO X = b
Gdzie DO jest matrycą n x n, Podczas X jest wektorem n składników n zmiennych do obliczenia; Y b jest wektorem zawierającym wartości niezależnych terminów.
Uogólnienie sekwencji iteracji zastosowanych w przykładzie do systemu n x n, z którego ma być obliczana zmienna Xi, zostanie zastosowana następująca formuła:
W tym równaniu:
- k jest indeksem wartości uzyskanej w iteracji k.
-k + 1 wskazuje nową wartość poniżej.
Ostateczna liczba iteracji jest określana na podstawie wartości uzyskanej w iteracji k + 1 różni się od uzyskanej bezpośrednio wcześniej ilością ε, która jest dokładnie pożądaną precyzją.
Napisz ogólny algorytm do obliczania wektora przybliżonych rozwiązań X liniowego układu równań nxn, biorąc pod uwagę macierz współczynników DO, wektor niezależnych terminów b, liczba iteracji (tjter) i wartość początkową lub „ziarnistą” wektora X.
Algorytm składa się z dwóch cykli „Do”, jednego dla liczby iteracji, a drugiego dla liczby zmiennych. Byłoby to następująco:
Dla k ∊ [1… iter]
Dla i ∊ [1… n]
X [i]: = (1 / A [i, i]) * (b [i] - ∑j = 1n(A [i, j] * X [j]) + A [i, i] * X [i])
Sprawdź działanie poprzedniego algorytmu, stosując go w oprogramowaniu matematycznym Studio SMath darmowy, dostępny dla systemów Windows i Android. Weźmy jako przykład przypadek macierzy 2 × 2, która pomogła nam zilustrować metodę Gaussa-Seidela.
Zastosuj algorytm Gaussa-Seidla dla następującego układu równań 3 × 3, który został wcześniej uporządkowany w taki sposób, aby współczynniki przekątnej były dominujące (czyli miały większą wartość bezwzględną niż wartości bezwzględne współczynników w tym samym rzędzie):
9 X1 + 2 X2 - X3 = -2
7 X1 + 8 X2 + 5 X3 = 3
3 X1 + 4 X2 - 10 X3 = 6
Użyj wektora zerowego jako ziarna i rozważ pięć iteracji. Skomentuj wynik.
Dla tego samego systemu z 10 iteracjami zamiast 5 otrzymujemy następujące wyniki: X1 = -0,485; X2 = 1,0123; X3 = -0,3406
To mówi nam, że wystarczy pięć iteracji, aby uzyskać dokładność do trzech miejsc po przecinku i że metoda szybko zbliża się do rozwiązania.
Korzystając z podanego wyżej algorytmu Gaussa-Seidla, znajdź rozwiązanie podanego poniżej układu równań 4 × 4:
10 x1 - x2 + 2 x3 + 0 x4 = 6
-1 x1 + 11 x2 - 1 x3 + 3 x4 = 25
2 x1 - 1 x2 + 10 x3 - 1 x4 = -11
0 x1 + 3 x2 - 1 x3 + 8 x4 = 15
Aby rozpocząć metodę, użyj tego ziarna:
x1 = 0, x2 = 0, x3 = 0 i x4 = 0
Rozważ 10 iteracji i oszacuj błąd wyniku, porównując go z iteracją numer 11.
W porównaniu z następną iteracją (numer 11) wynik jest identyczny. Największe różnice między dwiema iteracjami są rzędu 2 × 10-8, co oznacza, że przedstawione rozwiązanie ma dokładność co najmniej siedmiu miejsc po przecinku.
Jeszcze bez komentarzy