^{Рисунок 5.5. Алгоритм методу Ейлера для ЗДР}

^{Рисунок 4 Схема алгоритму методу Ейлера для ЗДР}

^{Рисунок 5 Схема алгоритму методу Ейлера для ЗДР}

З проміжним виведенням результатів

^{Рисунок 5.6. Алгоритм методу Ейлера з проміжним виведенням результатів для ЗДР}

^{Рисунок 5 Схема алгоритму методу Ейлера для ЗДР з проміжним виведенням результатів}

^{Рисунок 4 Схема алгоритму методу Ейлера для ЗДР}

5 Рисунок 5.7 Схема алгоритму методу Ейлера для системи здр .4 Метод Рунге-Кутта

Цей метод є більше точним і розповсюдженим. В ньому для обчислення похідних правої частини використовується сімейство схем різного порядку точності, що дає можливість при меншому обсязі обчислень більш точно обчислити збільшення y на кожному кроці.

Найбільш використовувана в обчислювальній практиці модифікація цього методу 4-го порядку на кожному кроці припускає обчислення правої частини рівняння (першій похідній 4 рази (у чотирьох сусідніх точках). Збільшення функції для переходу від до визначається, як усереднене значення збільшень у цих точках.

Уточнення досягається за рахунок спеціального підбора координат . Розрахункові формули:

(5.13)

де

Для системи 2-х рівнянь формули (5.13) будуть мати вигляд:

(5.14)

де

Погрішність методу становить порядку h⁵.

Схема алгоритму методу Рунге-Кутта для ЗДР наведена на рисунку 5.8, методу Рунге-Кутта для системи ЗДР – на рисунку 5.9.

Як ілюстрацію, наведено програму 1, що реалізує алгоритм методу Рунге-Кутта для ЗДР; програму 2, що реалізує алгоритм методу Ейлера для системи ЗДР.

Рисунок 5.8 Схема алгоритму методу Рунге-Кутта для ЗДР

Рисунок 5.9 Схема алгоритму методу Рунге-Кутта для системи ЗДР

Фрагмент Basic-програми (Метод Рунге-Кутта)

Function F(x, y)

F = Sin(2 * x) - Log(y) + 0.32

End Function

REM Чисельне рішення диференціального рівняння методом Рунге-Кутта

REM Вихідне рівняння y' =sіn (2x) - log(y)+0.32

CLS

X0 =…

Y0 =…

XK = …

H = …

X=X0: Y=Y0

PRІNT " X="; X, " Y="; Y

10 K1=H*F (X,Y)

K2= H*F (X+H/2,Y+K1/2)

K3= H*F (X+H/2,Y+K2/2)

K4= H*F (X+H,Y+K3)

Y=Y+(K1+2* K2+2* K3+ K4)/6

X=X+H

PRІNT " X="; X, " Y="; Y

ІF X<XK THEN 10

Фрагмент Basic-програми (Метод Ейлера)

Function F1(x, y, z)

F1 = 2 * x - 3 * y + 2 * z

End Function

Function F2(x, y, z)

F2 = 3 * x - 2 * y + z

End Function

REM Чисельне рішення системи диференціальних рівнянь методом Эйлера

REM Вихідні рівняння y' = 2x – 3y+2z

REM z'=3x-2y+z

CLS

N = …

X0 =…

Y0 =…

Z0 =…

H =…

X = X0

Y = Y0

Z = Z0

PRІNT " X Y Z"

PRІNT X; Y; Z

FOR І = 2 TO N2

Y = Y + H * F1(X, Y, Z)

Z = Z + H * F2(X, Y, Z)

X = X + H

PRІNT X; Y; Z

NEXT І

Лабораторна робота № 6. Метод золотого перетину в задачах однопараметричної оптимізації

Методи оптимізації дозволяють вибрати найкращій варіант системи (виробу), що розробляється з усіх можливих варіантів. Пошук оптимальних інженерних рішень є основним у завданні проектування і моделювання систем. Звичайно це процес чи послідовність операцій, які дозволяють отримати уточнене рішення. Вираз, для значення якого інженер-дослідник має обчислити max або min називається цільовою функцією.

Цільова функція дозволяє кількісно порівняти два альтернативних рішення задачі оптимізації.

Прикладами цільових функцій, які часто зустрічаються в інженерній практиці, є вартість, вага, міцність, габарити, ККД тощо.

Незалежно від типу розв’язуваної задачі, для пошуку екстремуму можна користуватися одним і тим же алгоритмом, тобто задачу мінімізації можна легко перетворити в задачу на знаходження max, змінивши знак цільової функції на зворотній.

У більшості задач, особливо потребуючих негайного рішення (у режимі реального часу), основним критерієм застосовності того або іншого методу є час, що затрачується на розрахунки.

Із усього різноманіття відносно "швидких" методів зупинимося на методі золотого перетину, основні ідеї якого знайшли застосування в багатьох предметних областях.

Цей метод передбачає розподіл інтервалу пошуку оптімуму точками, координати яких обчислюються за певним законом, обчислення значень цільової функції Q(x) в них, порівняння цих значень між собою і відкидання тієї частини інтервалу, на якій відсутній оптімум. При цьому не потрібно безперервності Q(x), досить, щоб вона була унімодальною.

Функція, задана на , називається унімодальною

(рис. 6.1), якщо існує єдина точка x* мінімуму Q(x)

Q(x*)=MIN Q(x)

a<=x<=b

і якщо для будь-яких двох точок виконуються співвідношення

x₁<x₂<x* (для усіх точок, що розташовані лівіше точки мінімуму)  Q(x₁)>Q(x₂)

x₂>x₁>x* (для усіх точок, що розташовані правіше точки мінімуму)  Q(x₁)<Q(x₂)

Рисунок 6.1 Умови унімодальності функції

Нехай відомо, що Q(x) унімодальна на [a, b]. Тоді по будь-яких двох значеннях Q(x₁) і Q(x₂) можна вказати інтервал, у якому перебуває точка x*, що мінімізує Q(x). Цей інтервал має довжину, меншу за довжину попереднього (рисунок 6.2). Для визначності шукатимемо MIN (MAX визначається аналогічно).

Нехай для визначеності x₁<x_2. Можливі такі 3 варіанти:

a) Q(x₁)>Q(x₂) b) Q(x₁)<Q(x₂) c) Q(x₁)=Q(x₂)

Рисунок 6.2 Геометрична інтерпретація розбивки інтервалу пошуку мінімуму функції

Можливі три випадки:

a) варто відкинути інтервал ;

b) варто відкинути інтервал ;

c) варто відкинути інтервали і , бо на цих інтервалах не може перебувати x*, виходячи з припущення про унімодальність Q(x).

При заданій кількості обчислень Q(x) оптимальною є стратегія, що приводить до найменшого інтервалу невизначеності (інтервалу, на якому перебуває MІN).

На кожній ітерації будемо ділити точкою на дві частини так, щоб відношення довжини всього інтервалу до його більшої частини дорівнювало відношенню більшої частини до меншої частини (рисунок 7.3).

або

Із цього співвідношення Z₁²=Z Z₂. З врахуванням того, що Z=Z₁+Z₂ підставимо Z з останнього виразу в попередній і поділимо на Z₁². Одержимо

Для додатнього кореня .

Це відношення називається золотим перетином.

Відзначимо, що

,

За допомогою цієї формули можна легко визначити чергові значення послідовності { ν _n }. Маємо числа: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, .......

Ця послідовність чисел називається числами Фібоначчі.

Золотий перетин роблять дві точки:

точка ;

точка , розташована симетрично точці щодо середини відрізку

Рисунок 6.3 Геометрична інтерпретація методу золотого перетину

Алгоритм методу золотого перетину:

1. Визначаємо значення точок x₁, x₂

2. Обчислюємо значення Q(x₁), Q(x₂)

3. Якщо Q(x₁)<=Q(x₂), то для подальшого розгляду залишаємо , що еквівалентно переносу точки b в точку x₂

4. Якщо Q(x₁)>Q(x₂), то для подальшого розгляду залишаємо [x₁,b], що еквівалентно переносу точки a в точку x₁

Процес розподілу триває поки довжина інтервалу невизначеності не стане менше заданої точності ε. На кожному кроці довжина нового інтервалу невизначеності приблизно дорівнює 0.618034 довжини старого інтервалу.

.

Рисунок 6.4. Схема алгоритму методу золотого перетину

Фрагмент Basic-програми

SUB ZS (a, b, xr, N, m, eps)

' Подпрограмма метода золотого сечения

t = .618034

x1 = b - (b - a) * t

x2 = a + (b - a) * t

y1 = FC(x1, m)

y2 = FC(x2, m)

DO WHILE b - a > eps

N = N + 1 'накопление числа итераций

IF y1 > y2 THEN

a = x1

x1 = x2

y1 = y2

x2 = a + (b - a) * t

y2 = FC(x2, m)

ELSE

b = x2

x2 = x1

y2 = y1

x1 = b - (b - a) * t

y1 = FC(x1, m)

END IF

LOOP

xr = (a + b) / 2

END SUB

FUNCTION FC (x, m)

'запишіть СВОЮ функцію для методу золотого перетину

f =

IF m = 1 THEN f = -f

FC = f

END FUNCTION