Metody numeryczne
Laboratorium
Temat ćwiczenia: Rozwiązywanie układów równań
liniowych
Grupa 4
sekcja 2, podsekcja 5
Mariusz Matyszkiewicz
Mateusz Odrobiński
Metody numeryczne
Laboratorium
Temat ćwiczenia: Rozwiązywanie układów równań
liniowych
Grupa 4
sekcja 2, podsekcja 5
Mariusz Matyszkiewicz
Mateusz Odrobiński
1. Wstęp - metoda iteracji prostej
Metoda iteracji prostej umożliwia obliczanie przybliżonych wartości rozwiązań układów równań
liniowych za pomocą kolejnych aproksymacji.
Jest to powszechnie wykorzystywany sposób, ponieważ pozwala obliczyć wartość rozwiązania
znacznie szybciej niż w tradycyjny sposób. Obarczony jest jednak błędem, który powstaje w
wyniku kolejnych przybliżeń.
W technice zachodzi potrzeba rozwiązywania układów równań w jak najkrótszym czasie,
zaś dokładność obliczeń często nie jest tak ważna. Ograniczenie ilości wykonywanych obliczeń
jest szczególnie ważne w urządzeniach cyfrowych o małej mocy obliczeniowej
czy w urządzeniach mobilnych, w których co raz większe zapotrzebowanie na moc obliczeniową
przekłada się na zwiększenie poboru energii.
W metodzie iteracji prostej przekształcamy równanie
do postaci
wartość przybliżona kolejnego rozwiązania
wektor powstały z przekształceń wektora
wartość bieżącego rozwiązania
wektor powstały z przekształceń macierzy
Warunkiem dostatecznym zbieżności procesu jest:
Koniec procesu jest uwarunkowany kryterium stopu:
2. Wyniki działania algorytmu iteracji prostej zaimplementowanego w C++
Do obliczeń przyjęliśmy
I.
Układ równań
1. Parametry:
A =
[
]; b = [
]
detA = -42
2. Rozwiązania:
Metoda dokładna
[
] [
]
Metoda iteracji prostej
[
]
3. Ilość iteracji = 13
4. Błędy:
5. Wykres
-1,5
-1
-0,5
0
0,5
1
1,5
2
2,5
3
3,5
0
2
4
6
8
10
12
14
x1
x2
II.
Układ równań
1. Parametry:
A =
[
]; b = [
]
detA = 971
2. Rozwiązania:
Metoda dokładna
[
]
Metoda iteracji prostej
[
]
3. Ilość iteracji = 18
4. Błędy
5. Wykres
-12
-10
-8
-6
-4
-2
0
2
4
6
8
10
0
2
4
6
8
10
12
14
16
18
20
x1
x2
III.
Układ równań
1. Parametry:
A =
[
]; b = [
]
detA = 80,3026
2. Rozwiązania:
Metoda dokładna
[
]
Metoda iteracji prostej
[
]
3. Ilość iteracji = 17
4. Błędy
5. Wykres
0
0,1
0,2
0,3
0,4
0,5
0,6
0
2
4
6
8
10
12
14
16
18
x1
x2
IV.
Układ równań
1. Parametry:
A =
[
]; b = [
] eps = 0.0001
detA = 838
2. Rozwiązania:
Metoda dokładna
[
];
Metoda iteracji prostej
[
]
3. Ilość iteracji = 8
4. Błędy
5. Wykres
-1,4
-1,2
-1
-0,8
-0,6
-0,4
-0,2
0
0,2
0,4
0,6
0,8
0
2
4
6
8
10
x1
x2
x3
V.
Układ równań
1. Parametry:
A =
[
]; b = [
] eps = 0.0001
detA = 0.5846
Wyznacznik bliski 0.
2. Rozwiązania:
Metoda dokładna
[
]
Metoda iteracji prostej
[
]
3. Ilość iteracji = 2164
4. Błędy
5. Wykres
-50
-40
-30
-20
-10
0
10
20
30
40
50
0
500
1000
1500
2000
2500
x1
x2
VI.
Układ równań dla którego nie spełnione są warunki zbieżności
1. Parametry:
A =
[
]; b = [
] eps = 0.0001
detA = 0,053
2. Rozwiązania:
Metoda dokładna
[
]
Metoda iteracji prostej
[
]
3. Ilość iteracji = 3118
-800
-600
-400
-200
0
200
400
0
500
1000
1500
2000
2500
3000
3500
x1
x2
3. WNIOSKI
W celu zbadania działania algorytmu przeprowadziliśmy obliczenia dla różnych danych
wejściowych. Wyniki działania programu porównaliśmy z dokładnymi rozwiązaniami,
należy jednak pamiętać, że nie zawsze są one idealne, ze względu na skończoną ilość cyfr
na których są zapisane. W przypadku układów równań od I do V różnice pomiędzy
otrzymanym wynikiem a dokładnym rozwiązaniem są pomijalnie małe.
Układ równań VI nie spełnia wymagań (norma macierzy H>1) dlatego program generuje
ostrzeżenie, celowo jednak nie przerwaliśmy jego działania – algorytm kończy działanie
dopiero po 3118 iteracjach, a otrzymane wyniki są diametralnie różne od prawidłowego
rozwiązania. Niewątpliwie jest to wada metody iteracji prostej.
Analizując wyniki stwierdziliśmy, że o ilości iteracji potrzebnych do otrzymania wyniku
spełniającego warunek stopu decyduje wyznacznik macierzy A. Jeśli jego wartość jest
bliska zeru (układ równań V), czas działania programu wzrasta około kilkaset razy, błędy
obliczeń również rosną, jednak można przypuszczać że wyznaczone rozwiązania
są wystarczająco dokładne w większości zastosowań. Zarówno dla ujemnych wartości
wyznacznika macierzy A, jak i dla dużych jego wartości nie zauważyliśmy wpływu na
ilość iteracji czy błędy otrzymanych wyników.
Ilość iteracji w przypadku układu 3 równań jest podobna jak w przypadku układu 2
równań.
Na podstawie wykresów można zauważyć, że w przypadku gdy wymagana jest mała
dokładność obliczeń, ilość wykonywanych operacji może być znacznie mniejsza, jednak
gdy wyznacznik macierzy A jest bliski zeru, ilość iteracji nadal musiałaby być bardzo
duża.
4. Kod programu
#include <iostream>
#include <math.h>
#include <fstream>
using namespace std;
#define N 2
int main()
{
ofstream file("wielomiany_wykresy.csv", ios::out);
ofstream file2("wielomiany_wyniki.csv", ios::out);
file << "Iteracja;" << "x1;" << "x2;" << "x...\n";
double a[N][N], b[N], x[N], h[N][N], g[N], suma, ilosc_iteracji = 0, suma_eps, xp, det, eps;
//Dane wejściowe
eps=0.0001;
a[0][0] = 15.43;
a[0][1] = 13.94;
a[1][0] = 10.5;
a[1][1] = 14.82;
b[0] = 9.42;
b[1] = 8.35;
if (N == 2) det = a[0][0] * a[1][1] - a[0][1] * a[1][0];
double sum;
for (int i = 0; i<N; ++i)
{
g[i] = b[i] / a[i][i];
x[i] = g[i];
sum=0;
for (int j = 0; j<N; ++j)
{
if (i == j)h[i][j] = 0;
else h[i][j] = -a[i][j] / a[i][i];
sum += fabs(h[i][j]);
}
if(sum>=1) cout << "Uklad rownan nie spelnia warunkow !";
}
do
{
file << ++ilosc_iteracji << ";";
suma_eps = 0;
for (int i = 0; i<N; i++)
{
suma = 0;
for (int j = 0; j<N; ++j) suma += (h[i][j] * x[j]);
xp = x[i];
x[i] = g[i] + suma;
suma_eps += powf(x[i] - xp, 2.0);
file << x[i] << ";";
}
file << endl;
suma_eps = powf(suma_eps, 0.5);
} while (suma_eps > eps);
for (int i = 0; i<N; ++i)
{
cout << x[i] << endl;
}
cout << "Iteracje "<< ilosc_iteracji <<endl;
cout <<"detA " << det <<endl;
file2 << "A=;" << a[0][0] << ";" << a[0][1] << endl << ";"<< a[1][0] << "; " << a[1][1] << endl;
file2 << "B=;" << b[0] << endl << ";" << b[1] <<endl;
file2 << "zadany eps=;" << eps << endl;
if (N == 2) file2 << "detA=;" << det << endl;
file2 << "x=;" << x[0] << endl << ";" << x[1]<<endl;
file2 << "Ilosc iteracji:;" << ilosc_iteracji << endl;
system("pause");
return 0;
}