Celem ćwiczenia jest porównanie metody Gaussa-Seidla i metody najszybszego spadku korzystając z następującej funkcji:

1.Opis algorytmu metody Gaussa-Seidla.

W metodzie Gaussa-Seidla podczas szukania minimum funkcji trzech zmiennych należy obrać punkt początkowy (x1,x2,x3) oraz dokładność ε. Następnie należy znaleźć minimum tejże funkcji względem x1, za x2 oraz x3 podstawiając wartości z punktu początkowego. Minimalizację względem jednej zmiennej najlepiej jest przeprowadzić metodą złotego podziału. Następnie obliczamy minimum funkcji względem x2, za x1 podstawiając x1 obliczone w poprzednim w poprzednim kroku, a za x3 wartość z punktu startowego. Analogicznie obliczamy minimum względem x3 podstawiając za x1 i x2 wartości obliczone w dwóch poprzednich krokach. Po minimalizacji funkcji na 3 kierunkach uzyskujemy nowy punkt. Należy sprawdzić czy odległość tego punktu od poprzedniego jest większa od określonej dokładności. Jeżeli tak to punkt ten przyjmujemy za nowy punkt startowy a powyższy proces powtarzamy aż do skutku. W przypadku gdy odległość jest mniejsza lub równa od wymaganej dokładności punkt ten jest minimum.

2. Opis algorytmu metody najszybszego spadku.

Pierwszym krokiem jest obranie punktu startowego (x1,x2,x3) .Następnie należy znaleźć współczynnik kierunkowy α dokonując minimalizacji naszej funkcji 3 zmiennych względem α.

Odpowiednio za x1,x2,x3 podstawiając współrzędne punktu startowego. Następnie możemy obliczyć punkt który jest przybliżeniem szukanego minimum.

Jeżeli odległość między punktem początkowym a nowym punktem jest większa od pożądanej dokładności należy powtarzać powyższe czynności. Gdy odległość między tymi dwoma punktami jest mniejsza od zadanej dokładności możemy zakończyć obliczenia.

Program napisany w C++ realizujący algorytm metody Gaussa-Seidla

#include <cstdlib> #include <iostream> #include <math.h> using namespace std; float f(float x1, float x2, float x3){ float funk; funk=4*x1*x1+6*x2*x2+3*x3*x3-0.9*x1*x2-2.6*x1*x3-6.5*x2*x3-16*x1+36*x2+24*x3+644; return funk; }; int main(int argc, char *argv[]) { float x10,x20,x30,x1,x2,x3,k,e,xL,xR,a,b,w,p; printf ("podaj x1 x2 x3 E\n"); scanf("%f %f %f %f",&x10,&x20,&x30,&w); x1=x10; x2=x20; x3=x30; int n=0; p=1000; e=0.5; k=(sqrt(5)-1)/2; while (p>w){ a=-100; b=100; xL=b-k*(b-a); xR=a+k*(b-a); while (b-a>e){ if (f(xL,x2,x3)<f(xR,x2,x3)){ b=xR; xR=xL; xL=b-k*(b-a); } else{ a=xL; xL=xR; xR=a+k*(b-a); } } x1=(a+b)/2; a=-100; b=100; xL=b-k*(b-a); xR=a+k*(b-a); while ((b-a)>e){ if (f(x1,xL,x3)<f(x1,xR,x3)){ b=xR; xR=xL; xL=b-k*(b-a); } else{ a=xL; xL=xR; xR=a+k*(b-a); } } x2=(a+b)/2; a=-100; b=100; xL=b-k*(b-a); xR=a+k*(b-a); while ((b-a)>e){ if (f(x1,x2,xL)<f(x1,x2,xR)){ b=xR; xR=xL; xL=b-k*(b-a); } else{ a=xL; xL=xR; xR=a+k*(b-a); } } x3=(a+b)/2; p=sqrt((x10-x1)*(x10-x1)+(x20-x2)*(x20-x2)+(x30-x3)*(x30-x3));//odległość x10=x1; x20=x2; x30=x3; n++; } float wynik; wynik=f(x1,x2,x3); printf("%f %f %f\nWartosc funkcji=%f\nn=%d\n",x1,x2,x3,wynik,n); system("PAUSE"); return EXIT_SUCCESS; }

Program napisany w C++ realizujący algorytm metody Gaussa-Seidla

#include <cstdlib> #include <iostream> #include <math.h> using namespace std; float f(float x1, float x2, float x3){ float funk; funk=4*x1*x1+6*x2*x2+3*x3*x3-0.9*x1*x2-2.6*x1*x3-6.5*x2*x3-16*x1+36*x2+24*x3+644; return funk; }; int main(int argc, char *argv[]) { float x1,x2,x3,eps,e,L1,a,b,xL,xR,k,poch1, poch2,poch3,grad1,grad2,grad3,p,x10,x20,x30; int i=0; e=0.5; printf ("podaj x1 x2 x3 E\n"); scanf("%f %f %f %f",&x1,&x2,&x3,&eps); k=(sqrt(5)-1)/2; p=10; while( p > eps ){ i= i +1; x10=x1; x20=x2; x30=x3; a=-100; b=100; poch1=8*x1-0.9*x2-2.6*x3-16; poch2=12*x2-0.9*x1-6.5*x3+36; poch3=6*x3-2.6*x1-6.5*x2+24; grad1=-poch1; grad2=-poch2; grad3=-poch3; while ((b-a)>e){ xL=b-k*(b-a); xR=a+k*(b-a); if( f( x1+xL*grad1,x2+xL*grad2,x3+xL*grad3 ) > f(x1+xR*grad1 ,x2+xR*grad2,x3+xR*grad3) ){ a=xL; } else{ b=xR; } } L1=(a+b)/2; x1=x1+L1*grad1; x2=x2+L1*grad2; x3=x3+L1*grad3; p = sqrt( (x10-x1)*(x10-x1) + (x20-x2)*(x20-x2) + (x30-x3)*(x30-x3) ); } float wynik; wynik=f(x1,x2,x3); printf("%f, %f, %f\n wartosc=%f\ni=%d",x1,x2,x3,wynik,i); system("PAUSE"); return EXIT_SUCCESS; }
3. Wyniki symulacji		Metoda Gaussa-Seidla			Metoda najszybszego spadku
Pkt startowy	ε	Ilość iteracji		Wartość min.	Ilość iteracji		Wartość min.
0,0,0	1	11			8,580679		25		8.024480
0,0,0	0.1	19			4.104275		54		4.021975
0,0,0	0.01	19			4.104275		111		4.000002
1200,60,234	1	19			7.297582		50		10.702698
1200,60,234	0.1	26			4.104275		77		4.036306
1200,60,234	0.01	26			4.104275		106		4.000212
-300,300,300	1	19			7.297582		61		5.839994
-300,300,300	0.1	26			4.104275		90		4.016965
-300,300,300	0.01	26			4.104275		119		4.000163
-10, -20, -30	0.1	2			4.021833		1		4
-10, -20,-30	0.01	2		4.02183	1		4

Powyższe symulacje zostały przeprowadzone prezentowanymi wyżej programami naszego autorstwa.

4.Wnioski

Na podstawie wyników przeprowadzonych symulacji można stwierdzić że metoda Gaussa-Seidla jest wydajniejsza od metody najszybszego spadku, gdyż dla niektórych punktów wymaga niemal 5 razy mniej iteracji niż konkurencyjna metoda. Możemy również zauważyć pewne odstępstwo, dla punktu startowego położonego blisko szukanego minimum (tutaj (-10,-20,-30)) metoda najszybszego spadku wymagała o połowę mniej iteracji niż druga omawiana przez nas.

Dla obu metod wraz ze zwiększeniem dokładności możemy zaobserwować wzrost ilości iteracji, z tym że wartość ta wzrasta znacznie szybciej dla metody najszybszego spadku.

---