МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Федеральне державне освітня установа вищої професійної освіти
"Чуваська державний університет ім. І. М. Ульянова"
Факультет Інформатики та обчислювальної техніки
Кафедра Інформаційно-обчислювальних систем
Спеціальність 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.
Зміст
Зміст завдання
Зміст розрахунково-пояснювальної записки
Теоретична частина
Введення
2.3 Теоретичне опис
Програмна частина
Текст програми в середовищі MatLab
Керівництво програміста
Керівництво користувача
Роздруківка серії тестів
Аналіз отриманих результатів
Список використаної літератури
1. Зміст завдання
Побудувати блок-схему алгоритму.
Написати програму в середовищі MatLab.
Вивчити строєні функції пакету MatLab, що дозволяють вирішувати завдання одномірної оптимізації (знаходження мінімуму і максимуму функцій) методом золотого перерізу.
Провести серію тестів, використовуючи написану програму і вбудовані функції. Побудувати графіки досліджених функцій. Проаналізувати результати рішень.
Тестові функції:
а) f (x) =
б) f (x) = arctg (sinx-cosx);
в) f (x) = + X 2.
2. Зміст розрахунково-пояснювальної записки
2.1 Теоретична частина
Метою даної курсової роботи є вивчення та набуття навичок роботи в мові для технічних розрахунків MatLab.
Необхідно створити програму для вирішення завдання одномірної оптимізації (знаходження мінімуму і максимуму функцій) методом золотого перерізу і побудувати графіки досліджених функцій. Так само необхідно вивчити роботу вбудованих в MatLab функцій.
Протестувати програму на серії тестів.
Теоретичний опис
Одновимірна оптимізація функцій методом золотого перерізу
Метод золотого перерізу полягає в побудові послідовності відрізків [a 0, b 0], [a 1, b 1], ..., стягуються до точці мінімуму функції f (x). На кожному кроці, за винятком першого, обчислення значення функції f (x) проводиться лише один раз. Ця точка, звана золотим перетином, вибирається спеціальним чином.
На першому кроці процесу оптимізації всередині відрізка [a 0, b 0] вибираємо дві внутрішні точки x 1 і x 2 і обчислюємо значення цільової функції f (x 1) і f (x 2). Оскільки в даному випадку f (x 1) <f (x 2), очевидно, що мінімум розташований на одному з прилеглих до x 1 відрізків [a 0, x 1] або [x 1, x 2]. Тому відрізок [x 2, b 0] можна відкинути, звузивши тим самим початковий інтервал невизначеності.
Другий крок проводимо на відрізку [a 1, b 1], де a 1 = a 0, b 1 = x 2. Потрібно знову вибрати дві внутрішні точки, але одна з них (x 1) залишилася з попереднього кроку, тому досить вибрати лише одну точку x 3, обчислити значення f (x 3) і провести порівняння. Оскільки тут f (x 3)> f (x 1), ясно, що мінімум знаходиться на відрізку [x 3, b 1]. Позначимо цей відрізок [a 2, b 2], знову виберемо одну внутрішню точку і повторимо процедуру звуження інтервалу невизначеності. Процес оптимізації повторюється до тих пір, поки довжина чергового відрізка [a n, b n] не стане менше заданої величини ε.
Тепер розглянемо спосіб розміщення внутрішніх точок на кожному від різанні [a k, b k]. Нехай довжина інтервалу невизначеності дорівнює l, а точка поділу ділить його на частини l 1, l 2: l 1> l 2, l = l 1 + l 2. Золотий перетин інтервалу невизначеності вибирається так, щоб відношення довжини великого відрізка до довжини всього інтервалу дорівнювало відношенню довжини меншого відрізка до довжини більшого відрізка: (1)
З цього співвідношення можна знайти точку розподілу, визначивши відношення l 2 / l 1. Перетворимо вираз (1), і знайдемо це значення:
l = L 2 l 1, l
= L 2 (l 1 + l 2),
l + L 1 l 2 - l
= 0,
2 +
- 1 = 0,
=
.
Оскільки нас цікавить тільки позитивне рішення, то
.
Звідси l 1 k 1 l, l 2
k 2 l.
Оскільки заздалегідь невідомо, в якій послідовності ділити інтервал невизначеності, то розглядають внутрішні точки, що відповідають двом цим способам поділу. Крапки розподілу x 1 і x 2 вибираються з урахуванням отриманих значень для частин відрізка. У даному випадку маємо
x 1 - a 0 = b 0 - x 2 = k 2 d 0,
b 0 - x 1 = x 2 - a 0 = k 1 d 0,
d 0 = b 0 - a 0.
Після першого кроку оптимізації виходить новий інтервал невизначеності - відрізок [a 1, b 1].
Можна показати, що точка x 1 ділить цей відрізок в необхідному відношенні, при цьому
b 1 - x 1 = k 2 d 1, d 1 = b 1 - a 1.
Для цього проведемо очевидні перетворення:
b 1 - x 1 = x 2 - x 1 = (b 0 - a 0) - (x 1 - a 0) - (b 0 - x 2) = d 0 - k 2 d 0 - k 2 d 0 = k 3 d 0,
d 1 = x 2 - a 0 = k 1 d 0,
b 1 - x 1 = k 3 (d 1 / k 1) = k 2 d 1.
Друга точка розподілу x 3 вибирається на такій же відстані від лівої межі відрізка, тобто x 3 - a 1 = k 2 d 1.
І знову інтервал невизначеності зменшується до розміру
d 2 = b 2 - a 2 = b 1 - x 3 = k 1 d 1 = k d 0.
Використовуючи отримані співвідношення, можна записати координати точок розподілу y і z відрізка [a k, b k] на k +1 кроці оптимізації (y <z):
y = k 1 a k + k 2 b k,
z = k 2 a k + k 1 b k.
При цьому довжина інтервалу невизначеності дорівнює
d k = b k - a k = k d 0.
Процес оптимізації закінчується при виконанні умови 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 ba <eps break;
else x2 = x1; B = A; x1 = k1 * a + k2 * b; A = f (x1);
end;
else
a = x1;
if ba <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);
Б. Програма обчислення мінімуму:
function Minimum (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 ba <eps break;
else x2 = x1; B = A; x1 = k1 * a + k2 * b; A = f (x1);
end;
else
a = x1;
if ba <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% .15 f', 'Мінімум функції f (x): x_min = ', x));
3.2 Керівництво програміста
Запускається файл Example.m, вона викликає 2 функції максимум і мінімум. Функція максимум обчислює максимум У функцію максимум передається проміжок, в якій потрібно обчислити максимум ... У перших рядках будується графік заданої функції. Цикл while - нескінченний цикл. Він зупиняється тільки, якщо у нас похибка обчисленого значення менше заданого eps. Потім задається точність результату (скільки цифр після коми) і формат виводу.
Функція мінімум обчислює мінімум ... У функцію мінімум передається проміжок, в якій потрібно обчислити мінімум ... Цикл while - нескінченний цикл. Він зупиняється тільки, якщо у нас похибка обчисленого значення менше заданого eps. Потім задається точність результату (скільки цифр після коми) і формат виводу.
3.3 Керівництво користувача
Для того, щоб обчислити максимум і мінімум необхідно відкрити файл Example.m, ввести проміжки обчислення мінімуму і максимуму, задати eps і натиснути Run (F 5). Після чого програма побудує графік заданої функції і обчислить максимум і мінімум.
3.4 Опис усіх використаних у програмі вбудованих функцій MatLab
У програмі використовувалися вбудований функції: plot, grid on, abs, disp, hold on.
plot - функція побудови графіків.
disp - функція, що виводить текстові дані.
grid on - функція включення відображення сітки, яка будується пунктирними лініями.
a bs - повертає абсолютну величину для кожного числового елемента вектора x.
hold on - забезпечує продовження виведення графіків в поточне вікно, що дозволяє додавати наступні графіки до вже сеществующім.
Опис вбудованих функцій MatLab допомагають полегшити рішення систем рівнянь
Важливим завданням чисельних методів - пошук мінімуму функцій f (x) в деякому інтервалі зміни x - від x 1 до x 2. Якщо потрібно знайти максимум такої функції, то достатньо поставити знак "мінус" перед функцією. Для вирішення цього завдання використовується наступна функція:
- Fmin ('fun', x 1, x 2) повертає значення x, що є локальним мінімумом функції funx на інтеравле x 1 <x <x 2;
- Fmin ('fun', x 1, x 2, options) - подібна до описаної вище функцією, але використовує контрольні параметри options для керування процесом за умовчанням;
- [X, options] = fmin (...) додатково повертає вектор контрольних параметрів options, в десятому стовпці якого міститься число виконаних ітерацій.
У цих уявленнях використовуються наступні позначення: x 1, x 2 - інтервал, на якому шукається мінімум функції; P 1, P 2 ... - передані у функцію аргументи; 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 2 в проміжку (0, 20)
3.6 Аналіз отриманих результатів
В ході курсової роботи мною були вивчені деякі аспекти програмування в середовищі MATLAB, а також деякі вбудовані функції даного пакету. При оформленні курсової роботи був отримані навички оформлення програмної документації відповідно до Єдиної Системою Програмної Документації, а також великий практичний досвід роботи в MATLAB, Microsoft Word 2003, (хоча освоєння цих програмних продуктів не було метою курсової роботи, дані навички не можна вважати марними). Теоретичні відомості були закріплені практичними заняттями.
4. Список використаної літератури
Чисельні методи. Волков О.А.: Навчальний посібник. - М.: Наука. Головна редакція фізико-математичної літератури, 1982.
Дьяконов В., Круглов В. MATLAB. Аналіз, ідентифікація та моделювання систем. Спеціальний довідник. - СПб.: Пітер, 2002.
Дьяконов В. MATLAB. Обробка сигналів та зображень. Спеціальний довідник. - СПб.: Пітер, 2002.
Дьяконов В.
MATLAB: навчальний курс. - СПб: Питер, 2001.