1. Schemat blokowy algorytmu metody Quasi-Newtonowskiej z algorytmem
   Davidona-Fletchera-Powella

2. Schemat blokowy algorytmu metody Newtona-Raphsona

3. Tabela wyników działania implementacji algorytmu metody Quasi-Newtonowskiej
dla funkcji/zestawu nr 48

Parametry metody: punkt startowy:

parametr kryterium stopu: 0.0005

Nr iteracji	Punkt osiągnięty w i-tej iteracji	Wartość funkcji celu w osiągniętym punkcie	Wartość kryterium stopu
1	-1.095626, 0.199541, -0.055428, -0.027714	3260.020589	146776.201442
2	-1.305456, 1.542176, 0.293832, 0.048654	3294.381424	205999.801811
3	-1.508481, 1.312382, 1.828981, 0.614792	3297.632572	180804.026394
4	-1.308390, 0.812636, 0.520588, 1.270994	3119.052082	869.010037
5	-1.286331, 0.808855, -0.278359, 3.184315	3116.425558	564.378061
6	-2.057993, 8.549364, -70.810801, 213.450786	2983.444541	112602.242151
7	-15.324875, 175.680811, -1724.210568, 5069.107940	36.930442	42601.565789
8	-16.126322, 184.597318, -1808.820142, 5319.450731	-9.717258	40.141334
9	-15.999648, 182.996159, -1792.963810, 5272.892782	-9.999988	0.010534
10	-15.999998, 182.999974, -1792.999756, 5272.999276	-10.000000	0.000000

4. Wyniki eksperymentu oceny wpływu punktu startowego
na otrzymywany wynik oraz prędkość działania algorytmu przy określonym (o odpowiednio „małej” wartości) parametrze
:

Liczba iteracji	Punkt startowy	Punkt osiągnięty „optymalny”	Wartość funkcji celu w punkcie „optymalnym”	Wartość
10	0 0 0 0	-15.999998, 182.999974, -1792.999756, 5272.999276	-10.000000	0,0005
107	999 999 999 999	-16.000003, 183.000064, -1793.000694, 5273.002041	-10.000000	0,0005
104	-999 -999 -999 -999	-15.999979, 182.999777, -1792.997871, 5272.993742	-10.000000	0,0005
11	10 10 10 10	-15.999815, 182.997595, -1792.976046, 5272.929557	-9.999999	0,0005
11	0 182 0 5258	-15.997524, 182.969144, -1792.696329, 5272.107640	-9.999910	0,0005
18	10 -10 10 -10	-16.000030, 183.000375, -1793.003696, 5273.010863	-10.000000	0,0005
10	-15 -200 -2000 -5000	-15.999999, 182.999983, -1792.999835, 5272.999515	-10.000000	0,0005
4	-15 182 -1788 5258	-16.001540, 183.019243, -1793.189660, 5273.557359	-9.999965	0,0005

5. Wyniki eksperymentu oceny wpływu parametru
na otrzymywany wynik oraz prędkość działania algorytmu dla określonego (odpowiednio „odległego” od rozwiązania) punktu startowego
:

Liczba iteracji	Punkt startowy	Punkt osiągnięty „optymalny”	Wartość funkcji celu w punkcie „optymalnym”	Wartość
9	0 0 0 0	-16.000036, 183.000470, -1793.004685, 5273.013740	-10.000000	0,1
8	0 0 0 0	-16.000560, 183.007969, -1793.081466, 5273.237886	-9.999957	0,5
8	0 0 0 0	-15.951529, 182.399591, -1787.091400, 5255.631672	-9.966044	0,01
10	0 0 0 0	-15.999999, 182.999995, -1792.999958, 5272.999870	-10.000000	0,001
9	0 0 0 0	-15.999989, 182.999857, -1792.998581, 5272.995833	-10.000000	0,0001
10	0 0 0 0	-15.999998, 182.999974, -1792.999756, 5272.999276	-10.000000	0,0005
10	0 0 0 0	-16.000006, 183.000098, -1793.001032, 5273.002998	-10.000000	0,00005

6. Tabela wyników działania implementacji algorytmu metody Newtona-Raphsona
dla funkcji/zestawu nr 48

Parametry metody: punkt startowy:

parametr kryterium stopu: 0.0005

Nr iteracji	Punkt osiągnięty w i-tej iteracji	Wartość funkcji celu w osiągniętym punkcie	Wartość kryterium stopu
1	-16.000064, 183.000730, -1793.007150, 5273.021027	-10.000000	0.000023

7. Wyniki eksperymentu oceny wpływu punktu startowego
na otrzymywany wynik oraz prędkość działania algorytmu przy określonym (o odpowiednio „małej” wartości) parametrze
:

Liczba iteracji	Punkt startowy	Punkt osiągnięty „optymalny”	Wartość funkcji celu w punkcie „optymalnym”	Wartość
1	0 0 0 0	-15.999984, 182.999817, -1792.998207, 5272.994726	-10.000000	0,0005
352594	999 999 999 999	-15.999988, 183.000009, -1792.999967, 5272.999947	-10.000000	0,0005
5	-999 -999 -999 -999	-16.000003, 182.999996, -1792.999997, 5272.999979	-10.000000	0,0005
2	10 10 10 10	-15.999995, 182.999965, -1792.999635, 5272.998934	-10.000000	0,0005
6	0 182 0 5258	-16.000001, 183.000000, -1793.000056, 5273.000000	-10.000000	0,0005
1	10 -10 10 -10	-16.000009, 183.000070, -1793.000656, 5273.001921	-10.000000	0,0005
3	-15 -200 -2000 -5000	-16.000000, 182.999998, -1793.000001, 5272.999952	-10.000000	0,0005
2	-15 182 -1788 5258	-15.999992, 182.999992, -1792.999960, 5272.999881	-9.999965	0,0005

8. Wyniki eksperymentu oceny wpływu parametru
na otrzymywany wynik oraz prędkość działania algorytmu dla określonego (odpowiednio „odległego” od rozwiązania) punktu startowego
:

Liczba iteracji	Punkt startowy	Punkt osiągnięty „optymalny”	Wartość funkcji celu w punkcie „optymalnym”	Wartość
1	0 0 0 0	-15.999992, 182.999913, -1792.999152, 5272.997506	-10.000000	0,1
1	0 0 0 0	-15.999990, 182.999888, -1792.998903, 5272.996773	-10.000000	0,5
1	0 0 0 0	-16.000038, 183.000430, -1793.004215, 5273.012396	-10.000000	0,01
1	0 0 0 0	-16.000015, 183.000173, -1793.001690, 5273.004971	-10.000000	0,001
1	0 0 0 0	-15.999999, 182.999985, -1792.999849, 5272.999557	-10.000000	0,0001
1	0 0 0 0	-16.000064, 183.000730, -1793.007150, 5273.021027	-10.000000	0,0005
1	0 0 0 0	-15.999991, 182.999891, -1792.998937, 5272.996873	-10.000000	0,00005

9. Wnioski i spostrzeżenia

Metoda Quasi-Newtonowskia pozwala w dość szybki sposób osiągnąć minimum funkcji (10 iteracji) jednak bez porównania szybszym algorytmem jest metoda Newtona-Raphsona która zwykle znajduje rozwiązanie w jednej iteracji co stawia ją na pierwszym miejscu spośród wszystkich stosowanych dotychczas metod na laboratorium.

Jednak metoda ta ma pewną wadę, dla dużych punktów startowych ilość iteracji wzrasta a dla jednego z przypadku jest niepokojąco duża bo osiąga ponad 350 tysięcy iteracji. Jest to spowodowane istnieniem zależności ilości iteracji od położenia punktu początkowego - im bardziej oddalony od minimum funkcji jest punkt początkowy tym większa jest ilość iteracji. W skrajnej sytuacji może to doprowadzić do sytuacji w której minimum nie zostanie wyznaczone przed wykonaniem określonej liczby iteracji.

Inaczej ma się sytuacji w algorytmie Quasi-Newtonowskim gdzie wybór pierwszego punktu nie spowodował aż tak gwałtownego wzrostu iteracji, można wręcz powiedzieć że dla naszych badań wyniki oscylują w granicach 8-11 iteracji (poza nietypowym przypadkiem 999;999;999;999 w którym algorytm potrzebuje 107 wykonań).

W obu metodach zmiana wartości epsilon nie miała wpływu na ilość wykonanych iteracji i dokładność otrzymanych wyników.

Podsumowując:

Metoda Gaussa-Seidla jest stosunkowo prostą metodą którą z powodzeniem można zastosować w każdym problemie jednak zużywa dużo zasobów i jest bardzo czasochłonna.

Metoda Powella jest znacznie szybsza od poprzedniej metody jednak dla zadanych dużych dokładności przy różnych punktach startowych możemy otrzymywać niedokładne wyniki.

Metoda Quasi-Newtonowska jest to szybka metoda pozwalająca osiągnąć cel mimo to do uzyskania odpowiedzi potrzebnych jest kilka iteracji.

Metody Newtona-Raphsona to jedyny algorytm który daje nam rozwiązanie w jednej iteracji jednak słabo sprawdza się dla funkcji wyższych rzędów niż kwadratowe gdy punkty startowe są znacznie oddalone od rozwiązania co powoduje że nie nadaje się wszystkich zastosowań.

10. Kody źródłowe programów

Quasi-Newtonowska.m

function [x_wyj,it_wyj] = Quasi_Newtonowska(x_st,eps,max_it, krok)

B=[1 0 0 0;

0 1 0 0;

0 0 1 0;

0 0 0 1];

Plik = fopen('Wyniki lab6 QN.doc', 'w');

Plik1 = fopen('Wyniki lab6 QN.txt', 'w');

fprintf(Plik, 'Rozpoczeto badanie funkcji metodą QN.\n');

fprintf(Plik1, 'Rozpoczeto badanie funkcji metoda QN.\n');

%Calculating function gradient

gradient = gradientFunkcja(x_st);

i = 0;

if gradient ~= 0

for i=1:max_it

disp(B);

kier = -B*gradient;

[x_p, x_k] = PrzedzialdlaZlotego(eps, krok, x_st, kier);

x_st_poprz=x_st;

x_st = ZlotyPodzial(x_p, x_k, krok/1000.0, x_st);

%Calculating function gradient

grad_poprz = gradient;

B_poprz = B;

gradient = gradientFunkcja(x_st);

gradient_norm = norm(gradient);

disp(i);

disp(x_st');

disp(funkcja(x_st));

disp(gradient_norm^2)

fprintf(Plik, 'Iteracja: %d,\t punkty: %f, %f, %f, %f, wartość: %f, kryterium stopu: %f\n',i, x_st', funkcja(x_st), gradient_norm^2);

fprintf(Plik1, 'Iteracja: %d,\t punkty: %f, %f, %f, %f, wartość: %f, kryterium stopu: %f\n',i, x_st', funkcja(x_st), gradient_norm^2);

if( gradient_norm^2 < eps )

it_wyj = i;

break;

else

krok = gradient_norm*10.0;

delta_x = x_st - x_st_poprz;

delta_grad = gradient - grad_poprz;

B = B_poprz + ( delta_x * delta_x' ) / (delta_x' * delta_grad) - ( B_poprz * delta_grad * delta_grad' * B_poprz) / (delta_grad' * B_poprz * delta_grad);

disp(B)

end

end

end

it_wyj = i;

x_wyj = x_st;

fclose(Plik);

fclose(Plik1);

end

Newtona-Raphsona.m

function [x_wyj,it_wyj] = Newtona_Raphsona(x_st,eps,max_it, krok)

Plik = fopen('Wyniki lab6 NR.doc', 'w');

Plik1 = fopen('Wyniki lab6 NR.txt', 'w');

fprintf(Plik, 'Rozpoczeto badanie funkcji metodą NR.\n');

fprintf(Plik1, 'Rozpoczeto badanie funkcji metoda NR.\n');

syms x1 x2 x3 x4

funkcjadlahesjan = 1186*x1 - 216*x2 + 60*x3 + 30*x4 + 242*x1*x2 + 162*x1*x3 + 50*x1*x4 + 90*x2*x3 + 10*x2*x4 + 30*x3*x4 + 583*x1^2 + 308*x2^2 + 48*x3^2 + 5*x4^2 + 3937

H_odw = inv(hessian(funkcjadlahesjan,[x1,x2,x3,x4]));

H_odw = double(H_odw);

disp(H_odw);

gradient = gradientFunkcja(x_st);

i = 0;

if norm(gradient) ~= 0

for i=1:max_it

kier = -H_odw*gradient;

[x_p, x_k] = PrzedzialdlaZlotego(eps, krok, x_st, kier);

x_st = ZlotyPodzial(x_p, x_k, krok/1000.0, x_st);

%Calculating function gradient

gradient = gradientFunkcja(x_st);

gradient_norm = norm(gradient);

disp(i);

disp(x_st');

disp(funkcja(x_st));

disp(gradient');

disp(gradient_norm);

fprintf(Plik, 'Iteracja: %d,\t punkty: %f, %f, %f, %f, wartość: %f, kryterium stopu: %f\n',i, x_st', funkcja(x_st), gradient_norm^2);

fprintf(Plik1, 'Iteracja: %d,\t punkty: %f, %f, %f, %f, wartość: %f, kryterium stopu: %f\n',i, x_st', funkcja(x_st), gradient_norm^2);

if( gradient_norm^2 < eps )

it_wyj = i;

break;

else

krok = gradient_norm*10.0;

%disp(x_new);

end

end

end

it_wyj = i;

x_wyj = x_st;

fclose(Plik);

fclose(Plik1);

end

funkcja.m

function [ y ] = funkcja( x )

y = 1186*x(1) - 216*x(2) + 60*x(3) + 30*x(4) + 242*x(1)*x(2) + 162*x(1)*x(3) + 50*x(1)*x(4) + 90*x(2)*x(3) + 10*x(2)*x(4) + 30*x(3)*x(4) + 583*x(1)^2 + 308*x(2)^2 + 48*x(3)^2 + 5*x(4)^2 + 3937;

end

gradient-funkcja.m

function [gradient] = gradientFunkcja(x_st)

gradient(1) = 1166*x_st(1) + 242*x_st(2) + 162*x_st(3) + 50*x_st(4) + 1186;

gradient(2) = 242*x_st(1) + 616*x_st(2) + 90*x_st(3) + 10*x_st(4) - 216;

gradient(3) = 162*x_st(1) + 90*x_st(2) + 96*x_st(3) + 30*x_st(4) +60;

gradient(4) = 50*x_st(1) + 10*x_st(2) + 30*x_st(3) + 10*x_st(4) + 30;

gradient = gradient';

end

PrzedzialdlaZlotego.m

function [x_p,x_k] = PrzedzialdlaZlotego(eps,krok, x_pocz, kier)

x = x_pocz;

kier = kier / norm(kier);

f1 = funkcja(x_pocz);

x = x_pocz+eps*kier;

f2 = funkcja(x);

if( f1 > f2 )

x_poprz = x_pocz;

while(1)

x = x+krok*kier;

f1 = funkcja(x);

x = x+eps*kier;

f2 = funkcja(x);

if(f1<f2)

x_p = x_poprz;

x_k = x;

break;

else

x_poprz = x;

end;

end

else

x_poprz = x_pocz;

while(1)

x = x-krok*kier;

f1 = funkcja(x);

x = x+eps*kier;

f2 = funkcja(x);

if(f1>f2)

x_k = x_poprz;

x_p = x;

break;

else

x_poprz = x;

end;

end

end

end

ZlotyPodzial.m

%Zloty podzial

function [x_wyj] = ZlotyPodzial(x_p, x_k, eps, x_st)

a=x_p;

b=x_k;

alfa=0.618;

x1 = x_st;

x2 = x_st;

x1 = b-(b-a)*alfa;

x2 = a+(b-a)*alfa;

while(norm(b-a)>eps)

if(funkcja(x1)>funkcja(x2))

a = x1;

x1 = x2;

x2 = a + alfa*(b-a);

else

b = x2;

x2 = x1;

x1 = b - alfa*(b-a);

end

end

min=(b+a)/2;

x_wyj = min;

end

---