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

#include <iostream.h>

#include <math.h>

#include <conio.h>

double f(double x)

{

return x*x+3*x;

}

void three_points_search(double E, double a,double b)

{

double Lk,Xm,x1,x2,x;

int k=1 ;

Lk=fabs(a-b);

while(Lk>=E)

{

Lk=fabs(a-b);

Xm=(a+b)/2;

x1=a+(Lk/4);

x2=b-(Lk/4);

if((f(x1))<(f(Xm)))

{

b=Xm;

Xm=x1;

}

else

{

if((f(x1)>=f(Xm))&&(f(Xm)<=f(x2)))

{

a=x1;

b=x2;

}

else

{

a=Xm;

Xm=x2;

}

}

k++;

}

;

cout<<"Минимум найденнный с помощью трехточечноно поиска : "<<Xm<<'\n';

cout<<"Число итераций : "<<k<<'\n';

}

void Swann1(double x1, double* a, double* b)

{

float h, x2;

h=0.001*fabs(x1);

x2=x1+h;

if (f(x2)>f(x1))

{

h=-h;

x2=x1+h;

}

do

{

x1=x2;

h=2*h;

x2=x1+h;

}

while (f(x2)<f(x1));

*a=x1-0.5*h;

*b=x2;

if (*a>*b)

{

*a=*b+*a;

*b=*a-*b;

*a=*a-*b;

}

}

void main()

{

clrscr();

double a, b, x1, E=0.0001;

cout<<"Введите начальную точку: Xo=";

cin>>x1;

Swann1(x1, &a, &b);

cout<<"Интервал полученный методом Свенна: ["<<a<<";"<<b<<"]"<<'\n';

three_points_search( E, a, b) ;

getch();

}

#include <iostream.h>

#include <math.h>

#include <conio.h>

double f(double x)

{

return x*x+3*x;

}

double f1( double x )

{

return 2*x+3;

}

void main()

{

clrscr();

double x0,x1,Xm,a,b,E=0.000001,h1;

int k=1;

cout << "Введите произвольную точку: Xo= ";

cin>>x0;

h1=0.01*x1;

x1=x0+h1;

if (f1(x1)>0)

h1=-h1;

x1=x0+h1;

while(f1(x0)*f1(x1)>0)

{

x0=x1;

h1=2*h1;

x1=x0+h1;

}

a=x0;

if(a>x1)

{

b=a;

a=x1;

}

else

b=x1;

cout<<" Интервал = [ "<<a<<" "<<b<<" ]"<<'\n';

Xm=b-f1(b)*(b-a)/(f1(b)-f1(a));

while(fabs(f1(Xm))>E)

{

Xm=b-f1(b)*(b-a)/(f1(b)-f1(a));

if (f1(Xm)>0)

{

b=Xm;

}

else

{

a=Xm;

}

k++;

}

;

cout<<"Минимум найденнный с помощью линейной интерполяции : "<<Xm<<'\n';

cout<<"Число итераций : "<<k<<'\n';

getch();

}

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

Выводы:

В данной лабораторной работе был реализован метод получения начального интервала локализации минимума и метод одномерного поиска минимума на полученном интервале.

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

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

11