Министерство образования РФ
Волгоградский государственный технический университет
Контрольнаяработа
Методыодномерной оптимизации
Выполнил:
Группа АУЗ-362
Проверил:
Яновский Т.А.
Волгоград2011
Метод установленияграниц начального отрезка локализации минимума
Представляет собойпроцедуру эвристического типа, предваряющую использование метода одномерногопоиска, которому требуется начальный отрезок локализации минимума.
Алгоритм Свенна.
Шаг 1. Выбратьпроизвольную начальную точку /> и /> – начальный положительный шаг.
Шаг 2. Вычислить />
Шаг 3. Сравнить />:
а) если /> то, согласнопредположению об унимодальности функции, точка минимума должна лежать правее,чем точка />.Положить />,/>, k=2 и перейти на шаг 5.
б) если />, то вычислить />.
Шаг 4. Сравнить />:
а) если />, то точка минимумалежит между точками /> и />, которые и образуют границыначального отрезка локализации минимума. Положить /> и завершить поиск.
б) если /> то, согласнопредположению об унимодальности функции, точка минимума должна лежать левее,чем точка />.Положить />,k=2 и перейти на шаг 5.
Шаг 5. Вычислить />.
Шаг 6. Сравнить />:
а) если />, то
при /> положить />
при /> положить />
и завершить поиск.
б) если />, то
при /> положить />
при /> положить />
положить k=k+1 и перейти нашаг 5.
Метод золотого сечения
Необходимо задать начальный отрезоклокализации минимума и число />, характеризующее желаемуюточность вычисления x*.
Шаг 1. Вычислить />.
Шаг 2. Найти пробныеточки /> и />.
Шаг 3. Вычислить значенияфункции в пробных точках /> и />.
Шаг 4. Сравнить /> и />:
а) если />, то положить />.
б) если />, положить />.
Шаг 5. Вычислить />. Если />, то положить /> и закончитьпоиск, иначе перейти к шагу 3.
Замечание: Данный алгоритм является несколькоболее медленно сходящимся по сравнению с алгоритмом, точно соответствующимметоду “золотого сечения”, из-за того, что на каждой итерации он требует двухвычислений функции f(x) вместо одного. Однако это делаетего более точным, так как при оперировании только с одной новой точкой ошибкиокругления могут привести к потере интервала, содержащего минимум.
Задание.
1.Самостоятельно найти влитературе по “Методам оптимизации” определение унимодальной функции иразобраться с его смыслом. Это важно, так как вычислительный процесс в любомметоде одномерной оптимизации опирается на предположение об унимодальности />.
2. Программно реализоватьна языке C++ метод Свенна
(Программа должнаобеспечить вывод на экран
— начальной точки и шага
на каждой итерацииметода:
— номера итерации,
— генерируемой методом новой точки x и значения функции в ней;
а на последней итерации
— отрезка [a, b] локализацииминимума функции f(x) и его длины, а также числаитераций.
Метод оценивания точкиминимума внутри найденного отрезка локализации минимума
(Программа должнаобеспечить на каждой итерации метода вывод на экран:
— номера итерации,
— границ текущего отрезка [a, b],
— внутренних точек и значений функции вних, а затем
— финальной оценки x* точки минимума функции f(x)
— соответствующего точке x* значения функции f(x*)).
3. С помощью программырешить следующие задачи одномерной оптимизации
— f(x) = x2 – 12x. Начальные точки: 1, 3, 0, 10. ∆ = 1, 10
— f(x) = 2x2+(16/x) Начальные точки: 1,6, 2, 1, 0.1, 10. ∆ = 1, 2
— f(x) = (127/4)x2-(61/4)x+2. Начальные точки: 0, 1, 2, -10, 10. ∆= 0,5, 1
4.Составить отчет, содержащий:
— Титульный лист с указанием учебнойдисциплины, номера и названия задания, ФИО выполнившего работу студента;
— Полностью текст задания, приведенныйнесколькими строками выше;
— Определение унимодальности;
— Алгоритмы;
— Текст программы на С++;
— Подробное решение одной изпредложенных задач – то, что выводит программа при ее решении на каждойитерации;
— Сводную таблицу результатов решениязадач, содержащую информацию о тестовой функции, начальных данных задачи ипараметрах программы и результаты решения задачи(оценку точки минимума,значение функции в ней, число итераций).
Задание№1
Программно реализовать наязыке C++ метод Свенна
(Программа должнаобеспечить вывод на экран
— начальной точки и шага на каждойитерации метода:
— номера итерации,
— генерируемой методом новой точки x и значения функции в ней; а напоследней итерации отрезка [a, b] локализации минимума функции f(x) и его длины, а также числа итераций.
С помощью программырешить следующие задачи одномерной оптимизации
— f(x) = x2 – 12x. Начальные точки: 1, 3, 0, 10. ∆ = 1, 10
— f(x) = 2x2+(16/x) Начальные точки: 1,6, 2, 1, 0.1, 10. ∆ = 1, 2
— f(x) = (127/4)x2-(61/4)x+2. Начальные точки: 0, 1, 2, -10, 10. ∆= 0,5, 1
Текст программы на С++
#include
#include
#include
#include
usingnamespace std;
doublef(double ) ;
int_tmain(int argc, _TCHAR* argv[])
{
doublet,ll,e,l,xk,yk,a,b;
double x,delta,xp,x1,x2,k=0,y;
int p=0;
cout
cin>>x;
cout
cin>>t;
x1=x-t;
x2=x+t;
if ((f(x-t)>=f(x)) && (f(x+t) >=f(x)))
{
a=x-t;
b=x+t;
p=1;
};
if ((f(x-t)
{
p=1;
};
xp=x;
if ((f(x-t)>f(x)) && (f(x) >f(x+t)))
{
delta=t;
a=x ;
x=x+t;
}
if ((f(x-t)
{
delta=-t;
b=x ;
x=x-t;
}
while((p!=1))
{
if((f(x)0))
a=xp;
if((f(x)
b=xp;
if((f(x)> f(xp)) && (delta*t >0))
{
b=x;
p=1;
};
if((f(x)> f(xp)) && (delta*t
{
a=x;
p=1;
};
k++;
coutНомеритерации"
coutГаницыотрезкаa="
xp=x;
x=xp+pow(2.0,k-1)*delta;
}
coutКоличествоитераций= "
system(«pause»);
return 0;
}
doublef(double x)
{
double y;
y=x*x-12*x;
return (y);
}
Решение задачи
Функция f(x) = x2-12x нач. точка x0= 1 шаг 1
Номер итерации 1
Начальная точка 1
X1 = a = 1
F(x) = -11
Номер итерации 2
Начальная точка 1
Шаг 1
X2 = a= 2
F(x) = -20
Номер итерации 3
Начальная точка 2
Шаг 2
X3 = a = 4
F(x) = -32
Номер итерации 4
Начальная точка 4
Шаг 4
X4 = b = 8
F(x) = -32
Отрезок [a;b] =[2;8] Число итераций = 4
Сводная таблицарезультатов №1
f(x) = x2-12x
Начальная
точка
Шаг
Отрезок
Число итераций 1 1 [2;8] 4 1 10 [-9;11] 3 3 1 [4;11] 4 3 10 [-7;13] 3 1 [2;16] 5 10 [0;30] 3 10 1 [2;8] 4 10 10 [0;20] 3
Сводная таблицарезультатов №2
f(x) = 2x2+(16/x)
Начальная
точка Шаг Отрезок Число итераций 1.6 1 [0.6;2.6] 3 1.6 2 [-0.4;3.6] 3 2 1 [1;3] 3 2 2 [0;2] 3 0.1 1 [-0.9;2.1] 3 0.1 2 [-1.9;4.1] 3 10 1 [-5;9] 4 10 2 [-4;8] 3
Сводная таблицарезультатов №3
f(x) = (127/4)x2-(61/4)x+2
Начальная
точка Шаг Отрезок Число итераций 0.5 [-0.5;0.5] 2 1 [-1;1] 2 1 0.5 [-1;0.5] 3 1 1 [-1;1] 2 2 0.5 [-2;1] 4 2 1 [-2;1] 3 -10 0.5 [-6;6] 6 -10 1 [-6;6] 5 10 0.5 [-6;6] 6 10 1 [-6;6] 5
Задание№2
Найти точки минимумавнутри найденного отрезка локализации минимума методом золотого сечения.
(Программа должнаобеспечить на каждой итерации метода вывод на экран:
— номера итерации,
— границ текущего отрезка [a, b],
— внутренних точек и значений функции вних,
а затем
— финальной оценки x* точки минимума функции f(x)
— соответствующего точке x* значения функции f(x*)).
Текст программы на С++
#includeiostream.h>
#include
#include
#include
#include
doublefunction(double); // вычисляет значение функции вданной точке
void main(void)
{
double a,b, E, F1, F2, LM, x = 0, fc, fd, fx, i = 0, c = 0, d = 0; // Определениепеременных
clrscr();
coutendla0 = ";
cin>> a;
cout
cin>> b;
coutendlE= ";
cin>> E;
clrscr();
coutendliaendl;
cout
cout
F1 = (3 — sqrt(5))*0.5;
F2 = 1 — F1;
do
{
LM = b — a;
cout
coutendliaendl;
cout
if (LM
{
x = (a +b)*0.5;
fx =function(x);
cout
coutF(x) в точке минимума = » setprecision(10) fxendl;
cout
getch();
exit(0);
}
else
{
c = a + F1* LM;
d = a + F2* LM;
fc =function(c);
fd =function(d);
coutisetprecision(10) cendl;
coutd[» isetprecision(10) dendl;
coutF(x) в точке с[» isetprecision(10) fcendl;
coutF(x) в точке d[» isetprecision(10) fdendl;
}
if (fc ==fd)
{
a = c;
b = d;
x = (a +b)*0.5;
fx =function(x);
cout
coutF(x) в точке минимума = » setprecision(10) fxendl;
cout
getch();
exit(0);
}
else
{
if (fc
{
a = a;
b = d;
i++;
}
else
{
a = c;
b = b;
i++;
}
}
}
while (1);
}
doublefunction (double x)
{
double y;
y = x * x — 12 * x;
return(y);
}
Решение задачи
Функция f(x) = x2-12x
Границы начальногоотрезка:
а[0] = -9
b[0] = 11
Число Е = 0.1
Номер итерации 1
Границы текущего отрезка:
а[0] = -9
b[0] = 11
Значение внутренней точкис[0] = -1.36
Значение внутренней точкиd[0] = 3.36
Значение функции F(x) вточке с[0] = 18.17
Значение функции F(x) вточке d[0] = -29.03
Номер итерации 2
Границы текущего отрезка:
а[1] = -1.36
b[1] = 11
Значение внутренней точкис[1] = 3.36
Значение внутренней точкиd[1] = 6.27
Значение функции F(x) вточке с[1] = -29.03
Значение функции F(x) вточке d[1] = -35.92
Номер итерации 3
Границы текущего отрезка:
а[2] = 3.36
b[2] = 11
Значение внутренней точкис[2] = 6.27
Значение внутренней точкиd[2] = 8.08
Значение функции F(x) вточке с[2] = -35.92
Значение функции F(x) вточке d[2] = -31.66
Номер итерации 4
Границы текущего отрезка:
а[3] = 3.36
b[3] = 8.08
Значение внутренней точкис[3] = 5.16
Значение внутренней точкиd[3] = 6.27
Значение функции F(x) вточке с[3] = -35.3
Значение функции F(x) вточке d[3] = -35.92
Номер итерации 5
Границы текущего отрезка:
а[4] = 5.16
b[4] = 8.08
Значение внутренней точкис[4] = 6.27
Значение внутренней точкиd[4] = 6.96
Значение функции F(x) вточке с[4] = -35.92
Значение функции F(x) вточке d[4] = -35.06
Номер итерации 6
Границы текущего отрезка:
а[5] = 5.16
b[5] = 6.96
Значение внутренней точкис[5] = 5.85
Значение внутренней точкиd[5] = 6.27
Значение функции F(x) вточке с[5] = -35.97
Значение функции F(x) вточке d[5] = -35.92
Номер итерации 7
Границы текущего отрезка:
а[6] = 5.16
b[6] = 6.27
Значение внутренней точкис[6] = 5.58
Значение внутренней точкиd[6] = 5.85
Значение функции F(x) вточке с[6] = -35.83
Значение функции F(x) вточке d[6] = -35.97
Номер итерации 8
Границы текущего отрезка:
а[7] = 5.58
b[7] = 6.27
Значение внутренней точкис[7] = 5.85
Значение внутренней точкиd[7] = 6.01
Значение функции F(x) вточке с[7] = -35.97
Значение функции F(x) вточке d[7] = -35.99
Номер итерации 9
Границы текущего отрезка:
а[8] = 5.85
b[8] = 6.27
Значение внутренней точкис[8] = 6.01
Значение внутренней точкиd[8] = 6.11
Значение функции F(x) вточке с[8] = -35.999
Значение функции F(x) вточке d[8] = -35.986
Номер итерации 10
Границы текущего отрезка:
а[9] = 5.85
b[9] = 6.11
Значение внутренней точкис[9] = 5.95
Значение внутренней точкиd[9] = 6.01
Значение функции F(x) вточке с[9] = -35.997
Значение функции F(x) вточке d[9] = -35.999
Номер итерации 11
Границы текущего отрезка:
а[10] = 5.95
b[10] = 6.11
Значение внутренней точкис[10] = 6.01
Значение внутренней точкиd[10] = 6.05
Значение функции F(x) вточке с[10] = -35.999
Значение функции F(x) вточке d[10] = -35.997
Номер итерации 12
Границы текущего отрезка:
а[11] = 5.95
b[11] = 6.05
Значение внутренней точкис[11] = 5.99
Значение внутренней точкиd[11] = 6.01
Значение функции F(x) вточке с[11] = -35.999
Значение функции F(x) вточке d[11] = -35.999
Номер итерации 13
Границы текущего отрезка:
а[12] = 5.95
b[12] = 6.01
Точка минимума x =5.981
Значение функции F(x)в точке минимума = -35.999999
f(x) = x2-12x
отрезки Точка минимума Значение функции Число итераций 0.1 [2;8] 6.003 -35.999999 10 [-9;11] 5.981 -35.999999 13 [4;11] 5.996 -35.999999 10 [-7;13] 6.018 -35.999966 13 [2;16] 6.006 -35.999957 12 [0;30] 6.002 -35.999997 13 [2;8] 6.003 -35.999999 10 [0;20] 6.005 -35.999965 13
f(x) = 2x2+(16/x)
отрезки Точка минимума Значение функции Число итераций 0.01 [0.6;2.6] 1.5875 15.119055 13 [-0.4;3.6] 1.5820 15.119055 15 [1;3] 1.5861 15.119055 14 [0;2] 1.5874 15.119052 13 [-0.9;2.1] 1.5880 15.119050 13 [-1.9;4.1] 1.5864 15.119057 15 [-5;9] 1.5862 15.119061 17 [-4;8] 1.5866 15.119055 16
f(x) = (127/4)x2 — (61/4)x+2
Отрезки Точка минимума Значение функции Число итераций 0.001 [-0.5;0.5] 0.2418 0.18548 16 [-1;1] 0.2418 0.18548 17 [-1;0.5] 0.2420 0.18548 17 [-1;1] 0.2418 0.18548 17 [-2;1] 0.2420 0.18548 18 [-2;1] 0.2420 0.18548 18 [-6;6] 0.2418 0.18548 21 [-6;6] 0.2418 0.18548 21 [-6;6] 0.2418 0.18548 21 [-6;6] 0.2418 0.18548 21