Одномерная оптимизация функций методом золотого сечения

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное образовательное учреждение высшего профессионального образования

"Чувашский государственный университет им. И.Н. Ульянова"

Факультет Информатики и вычислительной техники

Кафедра Информационно-вычислительных систем

Специальность 230100

Тема курсовой работы:

Одномерная оптимизация функций методом золотого сечения

Выполнили:

студенты гр. ИВТ 12-08

Прокопьева О. В.,

Степанова Е. В.

Проверил: старший преподаватель

Н.Н.Иванова

Чебоксары – 2005

Аннотация

Курсовая работа разработана в среде программирования MatLab.

При помощи этой программы можно решать задачи одномерной оптимизации функций (нахождение минимума и максимума) методом золотого сечения.

Программа дает навыки использования некоторых элементарных встроенных в MatLab функций таких как disp, plot…

Программа является наглядным примером для операций над матрицами.

Annotation

The course job is developed in environment(Wednesday) of programming MatLab.

Through this program it is possible to do a sum of a single-measure improvement (finding of minimum and maximum) by the method of golden section.

The program gives skills of use some elementary built - in MatLab of functions such as disp, plot…

The program is an evident example for operations above matrixes.

Оглавление

1. Содержание задания

2. Содержание расчетно-пояснительной записки

2.1 Теоретическая часть

2.2 Введение

2.3 Теоретическое описание

3 Программная часть

3.1 Текст программы в среде MatLab

3.2 Руководство программиста

3.3 Руководство пользователя

3.4 Распечатка серии тестов

3.5 Анализ полученных результатов

4 Список использованной литературы

1. Содержание задания

1. Построить блок-схему алгоритма.

2. Написать программу в среде MatLab.

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

4. Провести серию тестов, используя написанную программу и встроенные функции. Построить графики исследованных функций. Проанализировать результаты решений.

Тестовые функции:

а) f(x) =

б) f(x) = arctg(sinx- cosx);

в) f(x) = +x²
.

2. Содержание расчетно-пояснительной записки

2.1 Теоретическая часть

Целью данной курсовой работы является изучение и приобретения навыков работы в языке для технических расчетов MatLab.

Необходимо создать программу для решения задачи одномерной оптимизации (нахождение минимума и максимума функций) методом золотого сечения и построить графики исследованных функций. Так же необходимо изучить работу встроенных в MatLab функций.

Протестировать программу на серии тестов.

Теоретическое описание

Одномерная оптимизация функций методом золотого сечения

Метод золотого сечения состоит в построении последовательности отрезков [a₀
, b₀
], [a₁
, b₁
], …,стягивающихся к точке минимума функции f(x). На каждом шаге, за исключением первого, вычисление значения функции f(x) проводится лишь один раз. Эта точка, называемая золотым сечением, выбирается специальным образом.

На первом шаге процесса оптимизации внутри отрезка [a₀
, b₀
] выбираем две внутренние точки x₁
и x₂
и вычисляем значения целевой функции f(x₁
) и f(x₂
). Поскольку в данном случае f(x₁
) < f(x₂
), очевидно, что минимум расположен на одном из прилегающих к x₁
отрезков [a₀
, x₁
] или [x₁
, x₂
]. Поэтому отрезок [x₂
, b₀
] можно отбросить, сузив тем самым первоначальный интервал неопределенности.

Второй шаг проводим на отрезке [a_1,
b₁
], где a₁
= a₀
, b₁
= x₂
. Нужно снова выбрать две внутренние точки, но одна из них (x₁
) осталась из предыдущего шага, поэтому достаточно выбрать лишь одну точку x₃
, вычислить значение f(x₃
) и провести сравнение. Поскольку здесь f(x₃
) > f(x₁
), ясно, что минимум находится на отрезке [x₃
, b₁
]. Обозначим этот отрезок [a₂
, b₂
], снова выберем одну внутреннюю точку и повторим процедуру сужения интервала неопределенности. Процесс оптимизации повторяется до тех пор, пока длина очередного отрезка [a_n
, b_n
] не станет меньше заданной величины ε.

Теперь рассмотрим способ размещения внутренних точек на каждом от резке [a_k
, b_k
]. Пусть длина интервала неопределенности равна l, а точка деления делит его на части l₁
, l₂
: l₁
> l₂
, l = l₁
+ l₂
. Золотое сечение интервала неопределенности выбирается так, чтобы отношение длины большего отрезк к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка: (1)

Из этого соотношения можно найти точку деления, определив отношение l₂
/l₁
. Преобразуем выражение (1), и найдем это значение:

l=l₂
l₁
, l=l₂
(l₁
+ l₂
),

l+l₁
l₂
- l=0,

²
+ - 1 =0,

=.

Поскольку нас интересует только положительное решение, то

.

Отсюда l₁
k₁
l, l₂
k₂
l.

Поскольку заранее неизвестно, в какой последовательности делить интервал неопределенности, то рассматривают внутренние точки, соответствующие двум этим способам деления. Точки деления x₁
и x₂
выбираются с учетом полученных значений для частей отрезка. В данном случае имеем

x₁
– a₀
= b₀
– x₂
= k₂
d₀
,

b₀
- x₁
= x₂
– a₀
= k₁
d₀
,

d₀
= b₀
– a₀
.

После первого шага оптимизации получается новый интервал неопределенности – отрезок [a_1,
b₁
].

Можно показать, что точка x₁
делит этот отрезок в требуемом отношении, при этом

b₁
– x₁
= k₂
d₁
, d₁
= b₁
– a₁
.

Для этого проведем очевидные преобразования:

b₁
– x₁
= x₂
– x₁
= (b₀
– a₀
) – (x₁
– a₀
) – (b₀
– x₂
) = d₀
– k₂
d₀
- k₂
d₀
= k₃
d₀
,

d₁
= x₂
– a₀
= k₁
d₀
,

b₁
– x₁
= k₃
(d₁
/k₁
) = k₂
d₁
.

Вторая точка деления x₃
выбирается на таком же расстоянии от левой границы отрезка, т.е. x₃
– a₁
= k₂
d₁
.

И снова интервал неопределенности уменьшается до размера

d₂
= b₂
– a₂
= b₁
– x₃
= k₁
d₁
= kd₀
.

Используя полученные соотношения, можно записать координаты точек деления y и z отрезка [a_k
, b_k
] на k +1 шаге оптимизации (y < z):

y = k₁
a_k
+ k₂
b_k
,

z = k₂
a_k
+ k₁
b_k
.

При этом длина интервала неопределенности равна

d_k
= b_k
– a_k
= kd₀
.

Процесс оптимизации заканчивается при выполнении условия d_k
< ε. При этом проектный параметр оптимизации составляет a_k
< x < b_k
. Можно в качестве оптимального значения принять x = a_k
(или x = b_k
, или x = (a_k
+ b_k
)/2 и т.п.).

Блок-схема алгоритма

3. Программная часть

3.1 Текст программы в среде MatLab

А. Программа вычисления максимума:

function Maximum(a,b,eps)

%Maximum(a,b,eps) функция нахождения максимума функции f(x)

% методом "золотого сечения" на отрезке [a, b] с точностью eps.

% Функция f(x) задаётся в M-файле, находящимся в той же дирекктории.

% (!) Для правильной работы функции необходимо, чтоб a<b и

% искомое значение было б единствено на [a, b].

%--------------------------------------------

% Построим график (необязательно)

x=a:0.001:b; y=f(x);

plot(x,y,'k',a,f(a),'.b',b,f(b),'.b');

text(a,f(a),'A','FontSize',15); text(b,f(b),'B','FontSize',15);

title('График функции f(x).');

xlabel('Ось x.'); ylabel('f(x)');

grid on; hold on;

%--------------------------------------------

k1=(sqrt(5)-1)/2; k2=1-k1;

x1=k1*a+k2*b; x2=k2*a+k1*b;

A=f(x1); B=f(x2);

while 1

if A>B

b=x2;

if b-a<eps break;

else x2=x1; B=A; x1=k1*a+k2*b; A=f(x1);

end;

else

a=x1;

if b-a<eps break;

else x1=x2; A=B; x2=k2*a+k1*b; B=f(x2);

end;

end;

end;

x=(a+b)/2;

tab=strcat('%.',int2str(abs(floor(log10(eps)))),'g');

%(!) здесь задаётся точность результата(сколько цифр после запятой)

% и формат вывода, сравни Minimum

disp(sprintf(strcat('%s',tab),'Максимум функции f(x): x_max = ',x));

%-----------------------------------

%выведем результат на график

plot(x,f(x),'or'); text(x,f(x),'X_{max}','FontSize',15);

Б. Программа вычисления минимума:

functionMinimum(a,b,eps)

%Minimum(a,b,eps) функция нахождения минимума функции f(x)

% методом "золотого сечения" на отрезке [a, b] с точностью eps.

% Функция f(x) задаётся в M-файле, находящимся в той же дирекктории.

% (!) Для правильной работы функции необходимо, чтоб a<b и

% искомое значение было б единствено на [a, b].

k1=(sqrt(5)-1)/2; k2=1-k1;

x1=k1*a+k2*b; x2=k2*a+k1*b;

A=f(x1); B=f(x2);

while 1

if A<B

b=x2;

if b-a<eps break;

else x2=x1; B=A; x1=k1*a+k2*b; A=f(x1);

end;

else

a=x1;

if b-a<eps break;

else x1=x2; A=B; x2=k2*a+k1*b; B=f(x2);

end;

end;

end;

x=(a+b)/2;

disp(sprintf('%s %.15f','Минимумфункции f(x): x_min = ',x));

3.2 Руководство программиста

Запускается файл Example.m, она вызывает 2 функции максимум и минимум. Функция максимум вычисляет максимум В функцию максимум передаётся промежуток, в которой нужно вычислить максимум…В первых строках строится график заданной функции. Цикл while – бесконечный цикл. Он останавливается только, если у нас погрешность вычисленного значения меньше заданного eps. Потом задаётся точность результата (сколько цифр после запятой) и формат вывода.

Функция минимум вычисляет минимум… В функцию минимум передаётся промежуток, в которой нужно вычислить минимум … Цикл while – бесконечный цикл. Он останавливается только, если у нас погрешность вычисленного значения меньше заданного eps. Потом задаётся точность результата(сколько цифр после запятой) и формат вывода.

3.3 Руководство пользователя

Для того, чтобы вычислить максимум и минимум необходимо открыть файл Example.m, ввести промежутки вычисления минимума и максимума, задать eps и нажать Run (F5). После чего программа построит график заданной функции и вычислит максимум и минимум.

3.4 Описание всех использованных в программе встроенных функций MatLab

В программе использовались встроенный функции: plot, gridon, abs,disp, holdon.

plot – функция построения графиков.

disp — функция, выводящая текстовые данные.

gridon – функция включения отображения сетки, которая строится пунктирными линиями.

abs – возвращает абсолютную величину для каждого числового элемента вектора x.

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

Описание встроенных функций
MatLab
помогающих облегчить решение систем уравнений

Важной задачей численных методов – поиск минимума функций f(x) в некотором интервале изменения x – от x₁
до x_2.
Если нужно найти максимум такой функции, то достаточно поставить знак "минус" перед функцией. Для решения этой задачи используется следующая функция:

- fmin (‘ fun’, x1, x2) возвращает значение x, которое является локальным минимумом функции funx на интеравле x1<x<x2;

- fmin (‘ fun’, x1, x2, options) – сходна с описанной выше функцией, но использует контрольные параметры options для управления процессом по умолчанию;

- [x, options] = fmin(…) дополнительно возвращает вектор контрольных параметров options, в десятом столбце которого содержится число выполненных итераций.

В этих представлениях используются следующие обозначения: x1, x2 – интервал, на котором ищется минимум функции; P1, P2…- передаваемые в функцию аргументы; fun – строка, содержащая название функции, которая будет минимизирована; options – вектор контрольных параметров, имеющий 18 компонентов. Только три из них используются функцией fmin: options(1) – при ненулевом значении отображаются промежуточные шаги решения, options (2) задает итерационную погрешность, по умолчанию она равна 1.е-4, и options (14) задает максимальное число итераций, по умолчанию равное 500.

3.5.Распечатка серии тестов

Проведем серию тестов, решив приведенные выше системы в заданиях для тестовых расчетов, используя написанную программу .

а). Запускаем example.m для функции f(x) = в промежутке [-4,4].

Максимум функции f(x): x_max = 4

Минимум функции f(x): x_min = 0.000000005266636

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

б) Запускаем example.m дляфункцииf(x) = arctg(sinx- cosx) впромежутке (-3.14, 3.14);

Максимум функции f(x): x_max = 2.35619

Минимум функции f(x): x_min = -0.785398139394453

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

в) Запускаем example.m для функции f(x) = +x²
в промежутке (0, 20)

3.6 Анализ полученных результатов

В ходе курсовой работы мною были изучены некоторые аспекты программирования в среде MATLAB, а также некоторые встроенные функции данного пакета. При оформлении курсовой работы был получены навыки оформления программной документации в соответствии с Единой Системой Программной Документации, а также большой практический опыт работы в MATLAB, Microsoft Word 2003, (хотя освоение этих программных продуктов не было целью курсовой работы, данные навыки нельзя считать бесполезными). Теоретические сведения были закреплены практическими занятиями.

4. Список использованной литературы

1. Численные методы. Волков Е.А.: Учебное пособие. – М.: Наука. Главная редакция физико-математической литературы, 1982.

2. Дьяконов В., Круглов В. MATLAB. Анализ, идентификация и моделирование систем. Специальный справочник. – СПб.: Питер, 2002.

3. Дьяконов В. MATLAB. Обработка сигналов и изображений. Специальный справочник. – СПб.: Питер, 2002.

4. Дьяконов В.

5. MATLAB: учебный курс. — СПб: Питер, 2001.