Iteracyjne metody rozwiązywania układu równań

Metody iteracyjne (przybliżone) służą obliczaniu przybliżonych wartości pierwiastków układu równań liniowych za pomocą kolejnych aproksymacji. W tym celu należy przyjąć pewien dowolny wektor x⁽⁰⁾ jako rozwiązanie początkowe i według określonego schematu tworzyć kolejno ciąg wektorów x⁽¹⁾, x⁽²⁾,..., x⁽ⁿ⁾,... tak, aby wektor x⁽ⁿ⁺¹⁾ lepiej przybliżał rozwiązanie dokładne od wektora x⁽ⁿ⁾. Najprostszą metodą iteracyjnego rozwiązywania układu równań liniowych jest metoda Jacobiego

Cel ćwiczenia

Celem ćwiczenia jest wykonanie programu, rozwiązującego liniowy układ równań o czterech niewiadomych, metodą Jacobiego lub Gaussa - Seidela. Do weryfikacji poprawności obliczeń wykorzystane mogą zostać podane przykłady.

Metoda Jacobiego

W metodzie tej układ równań liniowych

lub w postaci macierzowej
A x = b
Przekształcić należy do postaci

lub w notacji macierzowej
x = g + H x
gdzie:

Na tym etapie należy sprawdzić zbieżność metody iteracji prostej dla danego zestawu parametrów. Warunkiem wystarczającym uzyskania zbieżności jest aby dowolna z norm macierzy H była mniejsza od jedności. Jako najprostsze można wykorzystać warunki

co oznacza, że największa z sum wierszy macierzy H jest mniejsza od jedności,lub

co oznacza, że największa z sum kolumn macierzy H jest mniejsza od jedności.

Kolejnym etapem jest iteracyjne wyznaczanie kolejnych przybliżeń wektora x. Jako wektor początkowy x⁽⁰⁾ przyjmuje się zwykle wektor wartości zerowych lub wyrazów wolnych , tj. x⁽⁰⁾ = g. Kolejne przybliżenia wyznacza się wg reguły

lub w postaci macierzowej
x^(k+1) = g + H x^(k), k = 0, 1, 2, ...

Metoda Gaussa - Seidela

Metoda ta różni się od metody Jacobiego jedynie innym sposobem wyznaczania wektora x^(k). Element x^k₁ wyznacza się tak samo, jak w metodzie Jacobiego, pozostałe zaś elementy wektora x^(k)oblicza się korzystając zarówno z wartości wektora x^(k-1), jak i z wyznaczonych już elemtów wektora x^(k).
Wektor x^(k) wyznacza się w oparciu o wyrażenie

Podejście algorytmiczne (metoda Jacobiego)

Na przykładzie układu o czterech niewiadomych

1. Wczytanie wspólczynników równania - macierz A o wymiarach n * n.
2. Wczytanie wektora wyrazów wolnych b.
3. Przyjęcie wektora początkowego x⁽⁰⁾=0
   x₁⁽⁰⁾ = 0
   x₂⁽⁰⁾ = 0
   x₃⁽⁰⁾ = 0
   x₄⁽⁰⁾ = 0
   
4. Iteracyjne wyznaczanie kolenych wektorów x^(k):
   
5. Należy w każdej iteracji sprawdzać warunek stopu, najlepiej poprzez wyznaczenie sumarycznego błędu r
   ,
   gdzie:
   .
   Iteracje należy przerwać po z góry założonej ilości iteracji lub osiągnięciu błędu rozwiązania r < d, gdzie d to z góry założona dokładność.

Podejście algorytmiczne (metoda Gaussa - Seidela)

Na przykładzie układu o czterech niewiadomych

1. Wczytanie wspólczynników równania - macierz A o wymiarach n * n.
2. Wczytanie wektora wyrazów wolnych b.
3. Przyjęcie wektora początkowego x⁽⁰⁾=0
   x₁⁽⁰⁾ = 0
   x₂⁽⁰⁾ = 0
   x₃⁽⁰⁾ = 0
   x₄⁽⁰⁾ = 0
   
4. Iteracyjne wyznaczanie kolenych wektorów x^(k):
   
5. Należy w każdej iteracji sprawdzać warunek stopu, najlepiej poprzez wyznaczenie sumarycznego błędu r
   ,
   gdzie:
   .
   Iteracje należy przerwać po z góry założonej ilości iteracji lub osiągnięciu błędu rozwiązania r < d, gdzie d to z góry założona dokładność.

Przykłady

Przykład 1

Rozwiązanie metodą Jacobiego:

• x₁ = 0,25

• x₁ = 0,375

Rozwiązanie metodą Gaussa - Seidela:

• x₁ = 0,25

• x₁ = 0,40625

Wynik

• x1 = 0,5
• x2 = 0,75
• x3 = 0,25
• x4 = 0,5

Przykład 2

• x1 = 1
• x2 = 2
• x3 = 3
• x4 = 1