Министерство  образование и  науки Российской Федерации

Московский  Авиационный Институт

(Национальный  Исследовательский Университет) 
 
 

Факультет № 1   Авиационная техника”.                                                                                                                                       Кафедра : “Внешнее проектирование                                                                                                                      и эффективность авиационных                                                                                                     комплексов.»                                                                               Специальность :”Моделирование и                                                                                                     исследование операций в                                                                                                                                       организационно – технических                                                                                        системах”. 
 

Курсовая  работа

по Численному моделированию задач специальности.

Нахождение  минимума унимодальной функции методами Дихотомии и Золотого сечения. 
 
 

                                                                                                                                          Исполнитель: Студент гр.01-216

                                                                                                                             Секретарев Максим Дмитриевич 
 
 
 
 
 
 
 
 
 

Москва

2011

Содержание

Постановка  задачи……………………………………………………………..…3 стр.

Теория унимодальных функций.………..………………………….……3 стр.

Алгоритм  метода дихотомии …………………………………………..….4 стр.

Программа решения задания методом дихотомии…….……..6 стр.

Результаты  выполнения программы………………………………...…7стр.

Алгоритм  метода золотого сечения………………………………………8стр.

Программа решения задания методом золотого сечения..10 стр.

Результаты выполнения программы…...……………………..….….12 стр.

Проверка  результатов……………………………………………………..……13стр.

График  функции на заданном отрезке  [0;1,5]……..……………14 стр. 

 

                                                            Вариант 8.

Постановка  задачи:

Найти минимум функции методом дихотомии и методом золотого сечения на отрезке [0;1.5]. Взять точность ε = 0.00001. Составить программы на любом алгоритмическом языке. Построить  график функции. Вычисления: семь знаков после запятой. Сделать проверку полученных результатов. Проверить необходимые условия оптимальности.

Теория унимодальных функций:

Нелинейное программирование  - определяет экстремум функции (максимум или минимум), при ограничениях, которые заданы линейными и нелинейными функциями.

Целевая функция  является линейной или нелинейной функцией.

Унимодальность.

Функция f(x) называется унимодальной на отрезке [a,b], если существует точка минимума на этом отрезке такая, что для любых точек , этого отрезка выполнены условия:

1)         ,

2)        .

Виды функций  показаны на рис.1 и 2.

На рис.1 даны примеры унимодальных функций.

На рис.2 даны примеры  не унимодальных функций. 

Данная задача является задачей нелинейного программирования, так как целевая функция является нелинейной. Рассмотрим два метода отыскания экстремума функции (минимума или максимума): метод дихотомии (половинного деления) и метод золотого сечения .

Алгоритм  метода дихотомии:

Идея метода проста и прозрачна : делить зону, где находиться точка минимума пополам и отбрасывать часть интервала, где минимума нет.

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

Например  , то есть  , то в результате двух экспериментов, промежуток где находиться минимум сокращяеться в два раза. Следующая пара экспериментов проводиться в районе середины оставшегося отрезка.  ,  . Находим  ,   и так далее.

Анологично, производя  шаги поиска минимального значкния функции , до тех пор пока на  -том шаге после экспериментов отрезок   , где находится точка, в которой функция принимаем минимальное значение, не станет  меньше чем  ( т.е   ).

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

Рис.3

Принцип работы метода дихотомии показан на рис.3

Программа решения задания  методом дихотомии:

Решение задачи методом  дихотомии:

program dihotom;

uses crt;

var x0,x1,e,x2,a,b,w:real;

i:integer;

begin

clrscr;

i:=0;

writeln(‘начало и конец отрезка’);

readln(x0);readln(x1);

writeln(‘точность');

read(e);

writeln('f(x)= -4*x-8*x^3+6*x^4');

repeat

i:=i+1;

x2:=(x0+x1)/2;

w:=-4*x2-8*power(x2,3)+6*power(x2,4);

a:=x2+e/2;

b:=x2-e/2;

write (i,'-ое деление ',' f(',x2:5:2,') = ',w:7:5,'  на интервале [',x0:5:2,',',x1:5:2,']');

writeln;

if ((-4*a-8*power(a,3)+6*power(a,4))-(-4*b-8*power(b,3)+6*power(b,4))>0)

then begin x0:=x0 ; x1:=x2; end else

if ((-4*a-8*power(a,3)+6*power(a,4))-(-4*b-8*power(b,3)+6*power(b,4))<0)

then begin x0:=x2;x1:=x1; end;

until (x1-x0)<e;

x2:=(x0+x1)/2;

writeln('min=',(-4*x2-8*power(x2,3)+6*power(x2,4)):7:5,' в точке,x2:7:5);

end. 
 

 

Результаты  выполнения программы приведены  в таблице 1.

Табл.1 

Окончательный результат: минимальное значение функции   на отрезке [0,1.5] равно -6.2803378 и достигается в точке , т.е:

 . 
 

Алгоритм  метода золотого сечения:

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

Перейдем к описанию процедуры поиска минимума с использованием золотого сечения . Пусть для определенности  f(Х1)<f(X2) .Разделим отрезок [Х1, X2] золотым сечением на две части так ,что бы меньший отрезок примыкал к точке Х1 .Обозначим через точку Х’ точку сечения .Могут быть два случая : 

1) f(Х1)<=f(X’)<f(X2) Здесь минимум локализован на отрезке [Х1,X’] ,длина которого равна 0,38(X2- Х1) . Далее с отрезком [Х1,X’] мы будем поступать так ,как ранее с отрезком [Х1, X2] .

2)  f(X’)<=f(Х1)<=f(X2) . В этом случае, для того чтобы сократить интервал поиска минимума ,нам нужно произвести еще одно измерение f(X). Выберем точку Х’’ так ,чтобы отрезок [X’, X2] делился этой точкой в золотом сечении (меньший отрезок примыкал к точке Х’) .Если f(X’)<=f(X’’) , то минимум локализован на отрезке [Х1,X’] , если f(X’)>=f(X’’)  , то минимум локализован на отрезке [Х’, X2] , причем Х’’ делит этот отрезок в золотом сечении . Больший из двух отрезков, на которые разбивается интервал локализации минимума, мы опять делим в золотом сечении точкой Х’’’ и.т.д. ,пока интервал локализации не станет достаточно малым .При этом после каждого измерения функции интервал локализации составляет 0,68 от длины предыдущего интервала локализации .