2Sprawozdanie z MOO, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labki i inne, DROPBOX, Laboratorium


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

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 α.

0x08 graphic

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.

0x08 graphic

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.



Wyszukiwarka

Podobne podstrony:
sprawko nowe, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labki
sprawko moo1, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labki
sprawko powell, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labk
moo1 barteksprawko, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce,
2analityczne, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labki
sprawozdanie-MaciejPawnukTomaszImiołek, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Opty
sprawko-6, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Laborki, lab6, got
sciaga kolos, Automatyka i Robotyka, Semestr III, Metody numeryczne
Mechanika - opracowanie, Automatyka i Robotyka, Semestr III, Mechanika, Gotowce, Mechanika, Mechanik
BD Lesiu, Automatyka i Robotyka, Semestr III, Bazy Danych, Gotowce
metody numeryczne wartosc funkcji, Automatyka i Robotyka, Semestr IV, Metody Numeryczne, Lab, lab2
GR D, Automatyka i Robotyka, Semestr III, Bazy danych
sciaga a, Automatyka i Robotyka, Semestr III, Bazy danych
DAPTA spraweczko, Automatyka i Robotyka, Semestr III, Elektrotechnika i Elektromechanika, Gotowce, E
Zestaw C++-zaliczenie wcze, Automatyka i Robotyka, Semestr III, Języki programowania

więcej podobnych podstron