Реферати

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

Траханиот, Юрій Мануїлович. (на прізвисько Старий) (2-я підлога. XV - нач. XVI в.) - придворний, дипломат, можливо письменник-перекладач. Грек, придворний Софії Палеолог, пізніше на службі пануючи Івана III.

Облік реалізації продукції, товарів, робіт і послуг. Зміст Уведення стор.3 Розділ 1: § 1.1 Поняття продукції, товарів, робіт, послуг і їхня оцінка стор.5 § 1.2 Методи обліку реалізації продукції, товарів, робіт і послуг стор.9

Судова криміналістична експертиза. - відновлення знищених маркировочних позначень Багато виробів, як масового, так і одиничного виготовлення маркіруються номером, що необхідно для строго обліку випущених виробів.

Аналіз ділової активності підприємства і кредитоспроможності підприємства. Завдання 1 Аналіз ділової активності, платоспроможності, фінансовій стійкості і рентабельності діяльності підприємства ТОВ "Промінь" за звітний рік

Остзейский комітет. План Уведення 1 Історія 2 Відомі члени комітету в різні періоди Введення Остзейский комітет для розгляду питань землеволодіння в Остзейском краї був створений за вказівкою Російського імператора Миколи I-го в 1846 році.[1] Комітет був розпущений у 1876 році.[2]

МІНІСТЕРСТВО ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ

Федеральна державна освітня установа вищої професійної освіти

"Чуваський державний університет ім. І. Н. Ульянова"

Факультет Інформатики і обчислювальної техніки

Кафедра Інформаційно-обчислювальних систем

Спеціальність 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 а sum of а 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(х) =

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

в) f(х) = +x2.

2. Зміст розрахунково-пояснювальної записки

2.1 Теоретична частина

Метою даної курсової роботи є вивчення і придбання навиків роботи в мові для технічних розрахунків MatLab.

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

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

Теоретичний опис

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

Метод золотого перетину складається в побудові послідовності відрізків [a0, b0], [a1, b1],. .., що стягуються до точки мінімуму функції f(х). На кожному кроці, за винятком першого, обчислення значення функції f(х) проводиться лише один раз. Ця точка, звана золотим перетином, вибирається спеціальним образом.

На першому кроці процесу оптимізації всередині відрізка [a0, b0] вибираємо дві внутрішні точки x1и x2и обчислюємо значення цільової функції f(x1) і f(x2). Оскільки в цьому випадку f(x1) < f(x2), очевидно, що мінімум розташований на одному з прилеглих до x1отрезков [a0, x1] або [x1, x2]. Тому відрізок [x2, b0] можна відкинути, звузивши тим самим первинний інтервал невизначеності.

Другий крок проводимо на відрізку [a1, b1], де a1= a0, b1= x2. Треба знов вибрати дві внутрішні точки, але одна з них (x1) залишилася з попереднього кроку, тому досить вибрати лише одну точку x3, обчислити значення f(x3) і провести порівняння. Оскільки тут f(x3) > f(x1), ясно, що мінімум знаходиться на відрізку [x3, b1]. Визначимо цей відрізок [a2, b2], знов виберемо одну внутрішню точку і повторимо процедуру звуження інтервалу невизначеності. Процес оптимізації повторюється доти, поки довжина чергового відрізка [an, bn] не стане менше заданої величини ε.

Тепер розглянемо спосіб розміщення внутрішніх точок на кожному від різанню [ak, bk]. Нехай довжина інтервалу невизначеності рівна l, а точка ділення ділить його на частині l1, l2: l1 > l2, l = l1+ l2. Золотий перетин інтервалу невизначеності вибирається так, щоб відношення довжини більшого отрезк до довжини всього інтервалу дорівнювало відношенню довжини меншого відрізка до довжини більшого відрізка: (1)

З цього співвідношення можна знайти точку ділення, визначивши відношення l2/l1. Перетворюємо вираження (1), і знайдемо це значення:

l=l2l1, l=l2(l1+ l2),

l+l1l2- l=0,

2+ - 1 =0,

=.

Оскільки нас цікавить тільки позитивне рішення, то.

Звідси l1k1l, l2k2l.

Оскільки зазделегідь невідомо, в якій послідовності ділити інтервал невизначеності, то розглядають внутрішні точки, відповідні двом цим способам ділення. Точки ділення x1и x2вибираются з урахуванням отриманих значень для частин відрізка. У цьому випадку маємо

x1- a0= b0- x2= k2d0,

b0- x1= x2- a0= k1d0,

d0= b0- a0.

Після першого кроку оптимізації виходить новий інтервал невизначеності - відрізок [a1, b1].

Можна показати, що точка x1делит цей відрізок в необхідному відношенні, при цьому

b1- x1= k2d1, d1= b1- a1.

Для цього проведемо очевидні перетворення:

b1- x1= x2- x1= (b0- a0) - (x1- a0) - (b0- x2) = d0- k2d0- k2d0= k3d0,

d1= x2- a0= k1d0,

b1- x1= k3(d1/k1) = k2d1.

Друга точка ділення x3вибирается на такій же відстані від лівої межі відрізка, т. е. x3- a1= k2d1.

І знов інтервал невизначеності меншає до розміру

d2= b2- a2= b1- x3= k1d1= kd0.

Використовуючи отримані співвідношення, можна записати координати точок ділення у і z відрізка [ak, bk] на k +1 кроці оптимізації (у < z):

у = k1ak+ k2bk,

z = k2ak+ k1bk.

При цьому довжина інтервалу невизначеності рівна

dk= bk- ak= kd0.

Процес оптимізації закінчується при виконанні умови dk < ε. При цьому проектний параметр оптимізації складає ak < х < bk. Можна як оптимальне значення прийняти х = ak(або х = bk, або х = (ak+ bk)/2 і т. п.).

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

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

3.1 Текст програми в середовищі MatLab

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

function Maximum(a, b, eps)

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

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

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

% (!) Для правильної роботи функції необхідно, щоб а <b і

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

%%%-%

Побудуємо графік (необов'язково)

х=a:0.001:b; у=f(х);

plot(х, у,'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(х).)(');

xlabel('Вісь x.'); ylabel('f(х)');

grid on; hold on;

%k1%-k1

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

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

А=f(x1); У=f(x2);

while 1

if А > В

b=x2;

if b-a < eps break;

else x2=x1; У=А; x1=k1*а+k2*b; А=f(x1);

end;

else

а=x1;

if b-a < eps break;

else x1=x2; А=В; x2=k2*а+k1*b; У=f(x2);

end;

end;

end;

х=(а+b)/2;

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

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

% і формат висновку, порівняй Minimum

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

%%виведем%-%виведем

результат на графік

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

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

functionMinimum(a, b, eps)

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

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

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

% (!) Для правильної роботи функції необхідно, щоб а <b і

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

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

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

А=f(x1); У=f(x2);

while 1

if А <В

b=x2;

if b-a < eps break;

else x2=x1; У=А; x1=k1*а+k2*b; А=f(x1);

end;

else

а=x1;

if b-a < eps break;

else x1=x2; А=В; x2=k2*а+k1*b; У=f(x2);

end;

end;

end;

х=(а+b)/2;

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

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 - повертає абсолютну величину для кожного числового елемента вектора х.

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

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

Важливою задачею чисельних методів - пошук мінімуму функцій f(х) в деякому інтервалі зміни х - від x1до x2. Якщо треба знайти максимум такої функції, то досить поставити знак "мінус" перед функцією. Для рішення цієї задачі використовується наступна функція:

- fmin (' fun', x1, x2) повертає значення х, яке є локальним мінімумом функції funx на интеравле x1 < х < x2;

- fmin (' fun', x1, x2, options) - схожа з описаною вище функцією, але використовує контрольні параметри options для управління процесом за умовчанням;

- [х, 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(х) = в проміжку [-4,4].

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

Мінімум функції f(х): x_min = 0.000000005266636

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

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

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

Мінімум функції f(х): x_min = -0.785398139394453

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

в) Запускаємо example.m для функції f(х) = +x2в проміжку (0, 20)

3.6 Аналіз отриманих результатів

В ході курсової роботи мною були вивчені деякі аспекти програмування в середовищі MATLAB, а також деякі вбудовані функції даного пакету. При оформленні курсової роботи були отримані навики оформлення програмної документації відповідно до Єдиної Системи Програмної Документації, а також великий практичний досвід роботи в MATLAB, Microsoft Word 2003, (хоч освоєння цих програмних продуктів не було метою курсової роботи, дані навики не можна вважати некорисними). Теоретичні відомості були закріплені практичними заняттями.

4. Список використаної літератури

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

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

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

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

5. MATLAB: учбовий курс. - СПб: Питер, 2001.