Метод оценивания точки минимума внутри найденного отрезка локализации минимума




Метод установления границ начального отрезка локализации минимума.

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

Алгоритм Свенна.

Шаг 1. Выбрать произвольную начальную точку и ∆ – начальный положительный шаг.

Шаг 2. Вычислить , .

Шаг 3. Сравнить , :

а) если > то, согласно предположению об унимодальности функции, точка минимума должна лежать правее, чем точка . Положить и перейти на шаг 5.

б) если , то вычислить .

Шаг 4. Сравнить :

а) если , то точка минимума лежит между точками и , которые и образуют границы начального отрезка локализации минимума. Положить и завершить поиск.

б) если то, согласно предположению об унимодальности функции, точка минимума должна лежать левее, чем точка . Положить и перейти на шаг 5.

Шаг 5. Вычислить .

Шаг 6. Сравнить :

а) если , то

· при положить ;

· при положить .

и завершить поиск.

б) если , то

· при положить;

· при положить.

положить и перейти на шаг 5.

Метод деления пополам (основной вариант).

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

Необходимо задать начальный отрезок локализации минимума и число , характеризующее желаемую точность вычисления , а также константу различимости .

Шаг 1. Найти пробные точки и .

Шаг 2. Вычислить значения функции и в пробных точках.

Шаг 3. Сравнить и :

а) если , то положить .

б) если , положить .

Шаг 4. Вычислить . Если, то положить и закончить поиск, иначе перейти к шагу 1.

 

Задание.

1. Самостоятельно найти в литературе по «Методам оптимизации» определение унимодальной функции и разобраться с его смыслом. Это важно, так как вычислительный процесс в любом методе одномерной оптимизации опирается на предположение об унимодальности .

2. Программно реализовать на языке C++ метод Свенна.

Программа должна обеспечить вывод на экран:

· начальной точки и шага;

на каждой итерации метода:

· номера итерации;

· генерируемой методом новой точки и значения функции в ней;

а на последней итерации

· отрезка локализации минимума функции и его длины, а также числа итераций.

Метод оценивания точки минимума внутри найденного отрезка локализации минимума

 

Программа должна обеспечить на каждой итерации метода вывод на экран:

· номера итерации;

· границ текущего отрезка ;

· внутренних точек и значений функции в них,

а затем

· финальной оценки точки минимума функции ;

· соответствующего точке значения функции .

3. Протестировать программу на простой задаче минимизации . Нач. точка: , шаг . Решение . Определить с помощью разработанной программы точку (точки) локального минимума функции в окрестности .

4.Составить отчет, содержащий:

· Титульный лист с указанием учебной дисциплины, номера и названия задания, ФИО выполнившего работу студента;

· Полностью текст задания, приведенный несколькими строками выше;

· Определение унимодальности;

· Алгоритмы;

· Текст программы на С++;

· Подробное решение одной из предложенных задач – то, что выводит программа при ее решении на каждой итерации;

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

Подписать отчет.

 

Унимодальная функция одной переменной: функция называется унимодальной на интервале [a,b], если она достигает глобального минимума на этом интервале в единственной точке , причем слева от эта функция строго убывает, а справа – строго возрастает. Значение унимодальных функций очень велико, т.к. все сложные задачи разбиваются на простые, среди которых большинство задач сводятся к поиску минимумов унимодальных функций.


Задание№1

Программно реализовать на языке C++ метод Свенна.

Программа должна обеспечить вывод на экран:

· начальной точки и шага;

на каждой итерации метода:

· номера итерации;

· генерируемой методом новой точки и значения функции в ней;

а на последней итерации

· отрезка локализации минимума функции и его длины, а также числа итераций.

Протестировать программу на простой задаче минимизации . Нач. точка: , шаг . Решение . Определить с помощью разработанной программы точку (точки) локального минимума функции в окрестности .

 

Текст программы на С++.

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include <iostream.h>

#include <conio.h>

#include <math.h>

#include <iomanip.h>

#include<windows.h>

using namespace std;

double f(double);

//---------------------------------------------------------------------------

#pragma argsused

char ch[100];

char *Rus(const char in[],char z[]);

char *Rus(const char in[],char z[])

{

if(CharToOem(in,z))return z;

else return 0;

}

int _tmain(int argc, _TCHAR* argv[])

{

double t,ll,e,l,xk,yk,a,b;

double x,delta,xp,k=0,y,y0;

int p=0;

cout<<Rus("Введите нач.точку x0: ",ch);

cin>>x;

cout<<Rus("Введите шаг: ",ch);

cin>>t;

y0=x*x;

cout<<Rus("Значение функции в точке x0: ",ch)<<f(x)<<endl;

cout<<" "<<endl;

cout<<Rus(" Решение: ",ch)<<endl;

if ((f(x-t) >=f(x)) && (f(x+t) >=f(x)))

{

a=x-t;

b=x+t;

p=1;

};

if ((f(x-t) <=f(x)) && (f(x+t) <=f(x)))

{

cout<<"Функция не унимодальная!"<<endl;

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) < f(x)) && (f(x) < f(x+t)))

{

delta=-t;

b=x;

x=x-t;

}

while ((p!=1))

{

if ((f(x)< f(xp)) && (delta*t >0))

a=xp;

if ((f(x)< f(xp)) && (delta*t <0))

b=xp;

if ((f(x)> f(xp)) && (delta*t >0))

{

b=x;

p=1;

};

if ((f(x)> f(xp)) && (delta*t<0))

{

a=x;

p=1;

};

k++;

cout<<" "<<endl;

cout<<Rus(" Шаг ",ch)<<k<<":"<<endl;

cout<<Rus(" Новая точка x: ",ch)<<x<<endl;

cout<<Rus(" Значение функции в точке x: ",ch)<<f(x)<<endl;

cout<<Rus(" Границы отрезка: a=",ch)<<a<<" b="<<b<<endl;

xp=x;

x=xp+pow(2.0,k-1)*delta;

}

cout<<" "<<endl;

cout<<Rus("Ответ: ",ch)<<endl;

cout <<Rus("Интервал [a;b], в котором расположена точка x*: [",ch)<<a<< ";"<< b<<"]"<<endl;

cout<<Rus("Количество итераций: ",ch) << k<< endl;

cout<<" "<<endl;

system("pause");

return 0;

}

double f(double x)

{

double y;

y=x*x;

return (y);

}

//---------------------------------------------------------------------------

Решение задачи:

Функция .

 

Таблица результатов для функции .

Нач.точка Шаг Отрезок [a;b] Число итераций
-5   [-3;3]  
    [-6;6]  

Таблица результатов для функции .

Нач.точка Шаг Отрезок [a;b] Число итераций
  0.5 [0;2]  
    [0.5;2]  

Задание №2



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: