Metoda Gaussa - Seidla
Dana jest funkcja 4 zmiennych, dla której mamy przeprowadzić minimalizację z wykorzystaniem metody Gaussa - Seidla.
Plik fn.m - implementacja funkcji w Matlabie:
function y = fn(x)
y=1542+20*x(1)*x(4)+8*x(3)^2+96*x(2)*x(3)+96*x(1)*x(3)+298*x(2)^2+616*x(1)*x(2)+333*x(1)^2+40*x(4)+16*x(3)+286*x(2)+5*x(4)^2+10*x(2)*x(4)+556*x(1);
%dana funkcja zmiennych x1,x2,x3,x4
Plik gs2.m - algorytm metody Gaussa - Seidla:
function wynik = gs2(x,eps)
p = 1;
i=0;
baza=[1,0,0,0;0,1,0,0;0,0,1,0;0,0,0,1];
%pętla działająca do momentu spełnienia kryterium stopu
while( p > eps)
%wywołanie metody złotego podziału dla każdej wspótrzędnej
x0=x;
x=x+baza(:,1)*zlotyp(x,baza(:,1),eps);
x=x+baza(:,2)*zlotyp(x,baza(:,2),eps);
x=x+baza(:,3)*zlotyp(x,baza(:,3),eps);
x=x+baza(:,4)*zlotyp(x,baza(:,4),eps);
%kryterium stopu
p = sqrt( (x0(1)-x(1))^2 + (x0(2)-x(2))^2 + (x0(3)-x(3))^2 +(x0(4)-x(4))^2 );
%licznik iteracji
i=i+1;
end
%wyświetlenie wyniku
pkt=x'
wynik = fn( x );
i
Plik zlotyp.m - algorytm metody złotego podziału:
function min = zlotyp(x,baza,eps)
%ustalenie punktów granicznych
zakres = 200 ;
a = -zakres;
b = zakres;
k = (sqrt(5)-1)/2;
j=1;
while j==1
while( (b-a) > eps )
%wybór 2 punktów wewnątrz przedziału poszukiwań
xp = b-((b-a)*k);
xk = a+((b-a)*k);
if fn(x+xp*baza) > fn(x+xk*baza)
a=xp;
xp = b-((b-a)*k);
xk = a+((b-a)*k);
else
b=xk;
xk = a+((b-a)*k);
xp = b-((b-a)*k);
end
end
%zwracana współrzędna punktu optymalnego
min = (xp+xk)/2;
%sprawdzenie czy zwrócony punkt nie jest punktem granicznym przedziału
%i ewentualne przesunięcie przedziału
if((a+eps)>min && (a-eps)<min)
a = a-zakres+eps;
b = a+eps;
j = 0;
end
if((b-eps)<min && (b+eps)>min)
a = b-eps;
b = b+zakres-eps;
j = 0;
end
end
Sprawdziliśmy poprawność działania napisanych algorytmów poprzez znalezienie minimum funkcją fminsearch:
f=@(x)1542+20*x(1)*x(4)+8*x(3)^2+96*x(2)*x(3)+96*x(1)*x(3)+298*x(2)^2+616*x(1)*x(2)+333*x(1)^2+40*x(4)+16*x(3)+286*x(2)+5*x(4)^2+10*x(2)*x(4)+556*x(1);
[min, fval] = fminsearch (f, [-1, 1,1,1]);
min
fval
Otrzymany wynik jest zbliżony do wyników zwracanych przez metodę Gaussa - Seidla:
min =
-8.0000 1.0000 41.0000 11.0000
fval =
9.0000
Przykładowy przebieg procesu znajdowania minimum funckji metodą Gaussa - Seidla dla punktu początkowego (-7.5 , 0.5 , 39.5 , 10.5) oraz epsilon równego 0.02:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
W poniższej tabelce zamieściliśmy rezultaty kilku wywołań metody Gaussa - Seidla dla różnych punktów przy stałej wartości epsilon.
liczba iteracji |
punkt startowy |
punkt osiągnięty |
wartość minimum |
epsilon |
855 |
0,0,0,0 |
-8.0497, 1.1150,40.6084,10.9842 |
9.0136 |
0.001 |
1026 |
10;20;30;40 |
-8.0497, 1.1146,40.6103,10.9847 |
9.0135 |
0.001 |
|
|
|
|
0.001 |
|
|
|
|
0.001 |
|
|
|
|
0.001 |
|
|
|
|
0.001 |
|
|
|
|
0.001 |
Jak widać, dobór punktu startowego ma wpływ na ilość iteracji. Im bliżej minimum funkcji ów punkt się znajduje, tym mniejsza jest ilość iteracji. Jednak wartość znalezionego minimum praktycznie nie zależy obranego punktu startowego, co świadczy o wysokiej skuteczności badanej metody.
W poniższej tabelce zamieściliśmy rezultaty kilku wywołań metody Gaussa - Seidla dla stałego punktu startowego przy różnych wartościach epsilon.
liczba iteracji |
punkt startowy |
punkt osiągnięty |
wartość minimum |
epsilon |
49 |
0,0,0,0 |
-9.2558,4.9161,25.0200,9.5856 |
26.7515 |
0.1 |
371 |
0,0,0,0 |
-8.4299,1.9800,37.6991,10.8814 |
9.9963 |
0.01 |
855 |
0,0,0,0 |
-8.0497, 1.1150,40.6084,10.9842 |
9.0136 |
0.001 |
704 |
0,0,0,0 |
-8.1007, 1.2285,40.2336,10.9732 |
9.0544 |
0.002 |
371 |
0,0,0,0 |
-8.4299, 1.9800,37.6991,10.8814 |
9.9963 |
0.007 |
1350 |
0,0,0,0 |
-8.0056, 1.0127,40.9575,10.9985 |
9.0002 |
0.0001 |
1027 |
0,0,0,0 |
-8.0235, 1.0535,40.8198,10.9934 |
9.0030 |
0.0004 |
1059 |
0,0,0,0 |
-8.0204, 1.0505,40.8196,10.9905 |
9.0026 |
0.0009 |
|
0,0,0,0 |
|
|
|
|
0,0,0,0 |
|
|
|
Z analizy wyników tego doświadczenia możemy wyciągnąć wniosek, że im mniejsza wartość epsilon, tym dokładniejszy wynik uzyskujemy, ale musimy liczyć się ze wzrostem ilości iteracji. Przyjęcie zbyt dużej wartości epsilon powoduje, że znalezione minimum nie jest globalnym minimum funkcji, którego poszukiwaliśmy.
Wnioski ogólne
Metoda Gaussa - Seidla daje satysfakcjonujące wyniki. Sprawność i szybkość jej działania zależą od wyboru punktu startowego oraz dokładności epsilon. Odpowiednie dobranie epsilon ma szczególne znaczenie, gdyż dla zbyt dużych wartości funkcja zatrzymywała się w punkcie, który nie był minimum globalnym.
Dla zadanej funkcji minimum znajduje się w punkcie (-8,1,41,11), a jego wartość wynosi 9.