Федеральное агентство по образованию

Санкт-Петербургский государственный

электротехнический университет «ЛЭТИ»

Кафедра САПР

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ № 1

«ИССЛЕДОВАНИЕ МЕТОДОВ ОДНОМЕРНОГО ПОИСКА МИНИМУМА УНИМОДАЛЬНЫХ ФУНКЦИЙ»

Выполнил:

Группа:

Проверил:

(Ф.И.О.)

Санкт-Петербург

2012

Оглавление:

Задание…………………………………………………………………………….3

Описание методов оптимизации…………………………………………………3

Блок-схема программы………………………………………………………..…5

Спецификация программы……………………………………………………….6

Текст программы ………………………………………………………………....6

Результаты тестирования…………………….………….……………………….8

Графическая интерполяция………………………………………………………8

Выводы…………………………………………………………………………….9

Ответы на контрольные вопросы………………………………………………...9

Задание:

Изучение методов одномерной минимизации функций одной переменной, разработка программы.

Описание методов оптимизации:

Метод Свенна:

С помощью этого метода получаем начальный интервал локализации минимума.

Начальный этап:

1) задать x⁰ – произвольная начальная точка.

2) выбрать шаг h равным 0.001 или 0.01*|x⁰|.

Основной этап:

Шаг 1:

Установить направление убывания целевой функции. Для этого надо взять x₂=x₁+h. Если f₁<f₂, то надо поменять направление движения(h=-h и взять x₂=x₁+h).

Шаг 2:

Вычислять f_k в точках x_k+1=x_k+h_k, где h_k=2h_k-1, k=2,3,…,n-1 до тех пор пока не придём в точку x_n такую что f_n>f_n-1.

Шаг 3:

Установить начальный интервал локализации минимума a₁=x_n-2 и b₁=x_n.

Метод дихотомии:

Начальный этап:

1. Предположить, что функция унимодальная.

2. Есть известная начальная точка x₁.

3. Получить интервал методом Свенна

Основной этап:

Шаг 1:

Взять 2 точки _k и _k на расстоянии /2 от центра текущего интервала. Сокращаем ТИЛ, если f₁<f₂ то возвращаемся в начало шага.

Шаг 2:

Проверка критерия окончания поиска.

Наращиваем счетчик числа операций k=k+1, пока (b_k – a_k) ≤ ε, если условие не выполняется, то возвращаемся на шаг 1.

Метод Ньютона:

Начальный этап:

1) Ввести начальное приближение x₀ и условие остановки .

2) Принять k = 0.

Основной этап:

Шаг 1:

Определить направление спуска p_k.

Шаг 2:

Определить последующую точку x_k+1=x_k+p_k.

Шаг 3:

Вычислить в точке x_k+1 градиент.

Шаг 4:

Если ||f '(x_k+1)||  ε, то поиск на этом заканчивается и полагается

x = x_k+1 и y = f(x_k+1).

Иначе k = k + 1 и переход к шагу 1.

x,x1,x2,

h=0.01,e=0.001

Начало

f(x2)>

f(x1)

h=-h;

x2=x1+h;

Да

Нет

h=Sven (x1,x2,h);

cout<<a

cout<<b

x1=a;

x2=b;

x1=x2-dif(x2)/dif2(x2);

k++;

while (fabs(x1-x2)>e && fabs(dif(x1))>e);

cout<<x1

Конец

Спецификация программы:

a, b – текущий интервала локализации

h – размер шага

min –минимум

x1 – стартовая точка

k, k1 – счетчики числа итераций.

Текст программы:

#include <conio.h>

#include <math.h>

#include <iostream.h>

long double a,b;

int k1, k;

double fx(double x) // функции

{

// возрат в зависимocти от x

if(x>=0)

return (4*x*x*x-3*x*x*x*x);

else

return (4*x*x*x+3*x*x*x*x);

}

double dif(double x) // производные для ньютона

{ if(x>=0)

return (12*x*x-12*x*x*x);

else

return (12*x*x+12*x*x*x);

}

double dif2(double x)

{ if(x>=0) return (24*x-36*x*x);

else return (24*x+36*x*x);

}

double Sven(long double x1, long double x2, long double h)

{ // Метод Свенн

long double x3,z;

x2=x1+h;

while (1)

{

h=2*h;

x3=x2+h;

if (fx(x3)>fx(x2))

break;

x1=x2;

x2=x3;

k1=k1+1;

}

a=x1;

b=x3;

if (a>b) // a – всегда слева, b - справа

{

z=b;

b=a;

a=z;

}

return h;

}

void main()

{

clrscr();

double x1,x2,h=0.01,e=0.001;

x1=0.4; //Начальня точка

x2=x1+h;

cout<<"\nNach tochka x1: "<<x1;

if ( fx(x2) > fx(x1))

{

h=-h; // меняем знак если функция растет

x2=x1+h;

}

h=Sven (x1,x2,h);

cout << "\n\nsSchag svenn. k= " << k1;

cout << "\nInterval posle Svenn";

cout << "\na= " << a << endl;

cout << "b= " << b << endl;

do // Ньютон

{

x1=a;

x2=b;

x1=x2-dif(x2)/dif2(x2);

k++;

cout<<"\nx1-x2;

}

while(fabs(x1-x2)>e && fabs(dif(x1))>e);

cout << "\n\nsSchag Nuton. k= " << k;

cout << "\n\nMinimum= " << x1;

getch();

}

Результаты работы программы

интервал по Свенну: -2.15 … -0.23

число повторений цикла после установления интервала k=6

минимум функций по Ньютону 1.000000

График функции

Выводы:

В результате лабораторной работы были изучены методы одномерной минимизации функций одной переменной. Минимум функции был найден посредством метода Свенна и последующего применения метода Ньютона (результат совпал с ожидаемым).

Ответы на контрольные вопросы:

1. Сравните метод золотого сечения, Фибоначчи и дихотомического поиска по числу вычислений значений функций для достижения заданной точности при локализации минимума.

Метод дихотомии наиболее прост в реализации, но по сравнению с методом золотого сечения он менее эффективен. Метод Фибоначчи использует числа Фибоначчи и поэтому он быстрее сходится к искомому минимуму, чем метод золотого сечения. 2.Указать отличие метода золотого сечения 1 от метода золотого сечения 2?

ЗС-1 опирается на точное вычисление точек на каждой итерации, а ЗС-2 использует соблюдения правила симметрии и для старта требуется указать одну и только одну точку.

3. Как сокращается текущий интервал локализации минимума в методах Фибоначчи-1 и Фибоначчи-2? Фиб1: Начальный этап

(1) Задать константу , начальный интервал [a1, b1], длину конечного интервала Ln и определить число n так, чтобы выполнялось условие Fn > (b1 - a1)/Ln.

(2) Взять две пробные точки 1 = a1 + (Fn-2/Fn)(b1 - a1) и 1 = a1 + (Fn-1/Fn)(b1-a1). Положить k = 1.

Основной этап

Шаг 1. Сократить текущий интервал локализации:

(1) Если f(k) < f(k), то положить ak+1 = ak, bk+1 = k,k+1 =k и вычислить новую точку k+1 = ak+1 + (Fn-k-2/Fn-k)Lk+1, где Lk+1 = bk+1 - ak+1; перейти на шаг 2.

(2) Если f(k)>> f(k),то положить ak+1 =k, bk+1 = bk, k+1 = k и вычислить k+1 = ak+1 + (Fn-k-1/Fn-k) Lk+1.

Шаг 2. Проверить критерий окончания поиска:

(1) Заменить k на k+1. (2) Если k = n - 1, перейти на шаг 3, иначе - на шаг 1.

Шаг 3. Найти аппроксимирующий минимум х(*):

(1) Положить k = k + .

(2) Если f(k) > f(k), то x(*) = (k + bk)/2. В противном случае - x(*) = (ak + k)/2.

Фиб2 : сокращение происходит аналогично, только вначале берется не 2 точки а одна, которая откладывается от любого из концов интервала, и все последующие точки берутся по правилу симметрии Х2 = Ак+Вк–Х1 и сравнением 4ех ситуаций (как в методе ЗС-2) происходит сокращение интервала.

4. Определите достоинства и недостатки методов Ньютона и трехточечного поиска.

Метод трехточечного поиска позволяет сократить интервал локализации минимума на основе сравнения значений функции в пробных точках без вычисления производных. А в методе Ньютона минимизация f(x) основывается на использовании квадратичной аппроксимации функции f(x) в точке xk:

F(x) = f(xk) + f '(xk)(x - xk) + f ''(xk)(x - xk)2 * 1/2

В качестве приближения хk+1 к минимуму х* берется точка, в которой производная F'(x) равна нулю, т.е. f '(xk) + f ''(xk)(xk+1 -xk) = 0.

Таким образом, xk+1 = xk - f '(xk)/f ''(xk).

Итерационный процесс строит последовательность точек {xk}, которая при определенных условиях квадратично сходится к некоторой стационарной точке х* функции f(x), т.е. к точке, в которой f ' (x*) = 0. Процесс останавливается, когдаxk+1 - xk ≤  и f '(xk) ≤ , где  > 0 - заранее заданное малое число.

Существенными недостатками метода Ньютона являются: 1) сложность задания начального приближения х1 в малой окрестности искомого минимума х*; 2) необходимость вычисления вторых производных минимизируемой функции.

5.Что такое унимодальная функция и каково её значение в теории оптимизации?

Унимодальная функция – это функция которая имеет единственный минимум и монотонна по обе стороны от него. При этом у неё не должно быть горизонтальных участков. Унимодальная функция является основой в теории поиска, так как она разработана для большинства методов поиска.

6.Сформулировать необходимые и достаточные условия минимума функции одной переменной? Как преобразовать задачу на поиск максимума в задачу на минимум?

Аналитическое условие экстремума, т.е. равенство производной функции в данной точке, является необходимым и достаточным условием минимума. Задача на поиск максимума преобразуется в задачу на поиск минимума противоположной функции, т.е. задача на поиск максимум функции F(x), а на поиск минимума (-F(x))

7.Характерные особенности организации одномерного поиска?

Линейный поиск, рассматриваются только унимодальные функции.

Начальный интервал локализации минимума находится методом Свенна

Меньший интервал локализации получается путём рассмотрения значений функции в двух точках на ТИЛ, или в производной в одной точке, и выборе новых границ интервала.

8. Дайте геометрическую интерпретацию 2-х способов выбора последних точек в методе Фибоначчи.

Точки в методе Фибоначчи 1 находятся по формулам:

k+1 = ak+1 + (Fn-k-2/Fn-k)Lk+1 и k+1 = ak+1 + (Fn-k-1/Fn-k) Lk+1.

А очередная точка в методе Фибоначчи 2 находится по правилу симметрии Х2 = Ак+Вк–Х1