Алгоритмы и структуры данных

Практическая работа №1. Анализ алгоритмов и программ.

Задание.Найти локальный минимум (максимум) функции вида f(x) = на заданном интервале [a,b] с заданной точностью ε > 0 одним из способов:

1. 
   Методом «деления отрезка» пополам;
   
2. 
   Методом «золотого сечения»;
   
3. 
   Методом «Фибоначчи».
   

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

1. 
   Время работы программы
   

Директива препроцессора: include Начальное время работы программы:srand(time(0))Конечное время работы программы(в секундах):

---

clock()/1000.0

2. 
   «Пассивный поиск»
   

Графический вид для заданной в задаче функции:Пример Программы, которая осуществляет поиск локального минимума функции на интервале с шагом h = 1для функции f(x) = #include

#include

#include

#include

#include
using namespace std;
int main()

{ SetConsoleCP(1251);

SetConsoleOutputCP(1251);

srand(time(0)); // начальное время

floatmin=0,x,y,k,h=1;// описание используемых в программе переменных

intstep=0;

for(x=-5.0;x<=-2.0;x=x+h)// основной цикл вычисления значений функции на

{ step++; // заданном промежутке

y=x*x*x-x+exp(-x);

printf(" %d. x = %fy = %f\n",step,x,y); // вывод на экран
if(y
{ min=y;

k=x;

};

printf("минимальное значение функции на [-5,-2] \n");

printf("y = %f, точка минимума x = %f\n",min,k);

printf("количество шагов = %d\n",step);

cout<< "Время работы программы = " <<clock()/1000.0<cout<< endl<
}

Ответы:

Если h=1, то	Если h=0.1, то
Если h=0.01, то	Если h=0.001, то
Если h=0.0001, то	Если h=0.00001, то ≈ 8.5 минут!!!

Очевидно, что с ростом количества вычислений пропорционально (с некоторым коэффициентом) растет и время работы программы. Легко подсчитать, что сложность алгоритма равна О(n).

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

Поэтому для вычисления экстремумов функций используют методы, которые определяют значение с некоторой, заранее заданной точностью. Например, чтобы приблизительное решение отличалось от «истинного» с погрешностью ε=0.001.Из примера «пассивного поиска» можно заметить, что искомый минимум лежит где-то в интервале |-3.679099 |.

3. 
   Метод «деления отрезка пополам»
   

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

Д
ля удобства пояснения алгоритма метода обозначим исходный отрезок = (рис. 2.), возьмем , построим точки и вычислим .

Если , то заключаем, что . Если же , то .

В первом случае в качестве приближения точки возьмем и примем обозначение . Во втором случае – . Таким образом, в найден отрезок , где содержится и указано приближение . Если , то поставленная задача решена. В противном случае отрезок следует подвергнуть аналогичному дроблению (схема 2) и продолжить процесс дробления до тех пор, пока на некотором шаге не выполнится неравенство . При этом на отрезке будет получено приближение  точка, в которой функция достигает приближенное значение локального минимума: .

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

Пример.

Определим с точностью точку локального минимума функции . Поиск будем производить на отрезке локализации .

Установим .

Первая итерация:

1. 
   вычислим , , ;
   
2. 
   сравним и . Так как , то установим в качестве нового отрезка локализации отрезок ;
   
3. 
   и так как условия Δ₁= (и ) не выполняются , то произведем очередную итерацию.
   

Итерационный процесс будем продолжать до тех пор, пока для установленного вновь отрезка локализации данные условия не будут выполнены. Результаты итераций сведем в таблицу 1.

Таблица 1

№ шага k
0	-4.000000	-3.000000	-3.600000	-3.400000	-6.457766	-5.939899	1.000000
1	-4.000000	-3.400000	-3.760000	-3.640000	-6.448950	-6.496707	0.600000
2	-3.760000	-3.400000	-3.616000	-3.544000	-6.476333	-6.363350	0.360000
3	-3.760000	-3.544000	-3.673600	-3.630400	-6.509402	-6.489656	0.216000
4	-3.760000	-3.630400	-3.708160	-3.682240	-6.502006	-6.509551	0.129600
5	-3.708160	-3.630400	-3.677056	-3.661504	-6.509618	-6.507023	0.077760
6	-3.708160	-3.661504	-3.689497	-3.680166	-6.508658	-6.509634	0.046656
7	-3.689497	-3.661504	-3.678300	-3.672701	-6.509645	-6.509312	0.027994
8	-3.689497	-3.672701	-3.682779	-3.679420	-6.509517	-6.509646	0.016796
9	-3.682779	-3.672701	-3.678748	-3.676732	-6.509648	-6.509607	0.010078
10	-3.682779	-3.676732	-3.680360	-3.679151	-6.509630	-6.509648	0.006047
11	-3.680360	-3.676732	-3.678909	-3.678183	-6.509648	-6.509644	0.003628
12	-3.680360	-3.678183	-3.679489	-3.679054	-6.509645	-6.509648	0.002177
13	-3.679489	-3.678183	-3.678967	-3.678706	-6.509648	-6.509648	0.001306
14	-3.679489	-3.678706	-3.679176	-3.679019	-6.509648	-6.509648	0.000784

Из таблицы видно, что искомый результат на 14-ом шаге вычислений. При этом: .

4. 
   Метод «золотого сечения»
   

Отличие метода золотого сечения от метода деления отрезка пополам заключается в специальном разбиении отрезка локализации относительно его центра точками.

Термин «золотое сечение» ввел Леонардо да Винчи. Принципы, заложенные в основу этого сечения, широко использовались при композиционном построении многих произведений искусства античности и эпохи Возрождения: особенно в живописи и архитектуре.

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

.

Замечательно также, что точки и осуществляют золотое сечение не только всего отрезка , но и соответственно подотрезков и .



Итерационный процесс локализации минимума функции на заданном числовом отрезке в данном методе ведется аналогично локализации минимума функции в методе деления отрезка пополам. В отличие от него точки и на очередном шаге итерации находятся по формулам:

.

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

5. 
   Метод Фибоначчи
   

Данный метод обеспечивает максимальное гарантированное сокращение отрезка локализации при заданном числе N вычислений функции и основан на использовании чисел Фибоначчи таких, что: для всех при начальных значениях

Метод Фибоначчи состоит из шагов.

Вначале определяется такое число Фибоначчи , для которого справедливо условие где .

Очередной -й шаг выполняется аналогично -й итерации метода деления отрезка пополам, но точки и находятся по формулам

,

где – длина отрезка локализации (рис.2.7).

Аналогично методу деления отрезка пополам определяется новый отрезок локализации:

если , то ;

если , то .

В первом случае за очередное приближение к точке минимума принимают , во втором случае – .



Примерная схема алгоритма:



Все 4 метода реализовать для поиска экстремальных точек в интервалах

переменной x—[-5,-3], [0,3] —точки минимума и [-3,0] — точка максимума.

---

Смотрите также файлы

• М. О. Скрипачев релейная защита электроэнергетических систем. Защита генераторов, трансформаторов и сборных шин.pdf

• Криминологическая характеристика и профилактика самоубийств (суицидов).rtf

• Сибирский государственный университет науки и технологий имени академика М.docx

• Проверила учитель технологии Рябчун Т. Ю. 20212022 уч год Нижний Новгород Проблемная ситуация.docx

• Инмаш (наименование института полностью) Наземные транспортно системные средства.docx