Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

ІІІ. Використані матеріали





F(a, b, h) == 2hb + ab + 2ha->м’іn.

Визначення мінімальної витрати матеріалу для прямокутної відкритої ємності.

Обсяг ємності

V = abh = м3,

де V — обсяг, м3; a — довжина, м; Ь — ширина, м; h — висота, м.

Мінімальна площа ємності

Обмеження f (a, b, h) = 0, тобто / (a, b, h} «= abh — V допоміжна функція з застосуванням множників Лагранжа буде мати вид

? = (a, b, h, ?)=F (a, b,h)+K (a, b,h- V}:

?= (a, b, h, ?) == 2hb + ab + 2ha + ? (a, b, h — V}. Частки похідні на a, b, h і ?:

 

2.3. ПОЧАТКОВІ сведения ПРО ЧИСЕЛЬНІ МЕТОДИ ОПТИМІЗАЦІЇ.

2.3.1. ПОНЯТТЯ ПРО ЧИСЕЛЬНІ МЕТОДИ ОПТИМІЗАЦІЇ Й АЛГОРИТМ У МАТЕМАТИЧНОМУ ПРОГРАМУВАННІ.

Спираючи на відомі умови оптимальності, не завжди вдається в явному виді одержати рішення задач оптимізації. У більшості випадків задачу вирішують чисельно, за допомогою ЕОМ. Любою чисельний метод – алгоритм рішення задачі оптимізації, заснований на точному чи приблизному обчисленні наступних характеристик задач оптимізації:

1. Значень цільової функції.

2. Значень функцій, що задають припустиму безліч рішень.

3. Похідних функцій.

На підставі отриманої при цьому інформації будується:

а). Або наближення до рішення задачі, тобто до шуканої крапки.

Б). Або наближення до оптимального значення цільової функції.

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

Опр1. Алгоритм рішення чисельних методів оптимізації – процес, що дозволяє виходячи з заданої початкової крапки будувати послідовність, кінцеву чи нескінченну.

 

 

3. ЧИСЕЛЬНІ МЕТОДИ БЕЗУМОВНОЇ ОПТИМІЗАЦІЇ, ЩО ВИКОРИСТОВУЮТЬ ПОХІДНІ.

3.1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА МЕТОДІВ. ІДЕЯ ГРАДИЕНТНОГО ПОШУКУ.

Класичні методи оптимізації, що використовують умову Куна-Такера на практиці використовуються нечасто через велику складність аналізу одержуваної системи рівнянь, але ці методи служать теоретичним обґрунтуванням різних чисельних методів пошуку экстремума функції. У залежності від використовуваної інформації про цільову функцію і її похідні існують методи вибору послідовності крапок , що чи



1. Використовують значення (обчислені) функції .

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

У першому випадку методи звуться координатних методів пошуку экстремумов цільової функції, у тому числі методи координатного спуска (підйому) чи методи Гауса – Зайделя.

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

Градиентные методи. Градієнтом функції називають вектор, що має напрямок найбільшого збільшення функції і по величині рівний похідної по цьому напрямку.

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

 

Це означає: рух на малий крок у напрямку градієнта функції, забезпечує найбільший ріст, а в напрямку антиградієнта – найбільше зменшення функції f(x). Тому напрямок руху по градієнті – найшвидший підйом, а по антиградієнті – найшвидший спуск. Зі сказаного випливає загальна ідея градиентных методів: відправляючись від заданої крапки коштують послідовність крапок , так що перехід від крапки до крапки виробляється в напрямку якнайшвидшого підйому (спуска), що будуються у вихідній точці кожної ітерації. Існують модифікації градиентных методів, що залежать від правила вибору послідовності крапок, величини кроку руху по градієнті й ознаки закінчення обчислювальної процедури. Причиною виникнення модифікацій послужили недоліки градиентных методів. Найбільш істотні:

1. У загальному випадку, якщо f(x) – не функція спеціального виду (опукла, увігнута), те для відшукання оптимуму потрібно велике число ітерацій.

2. У загальному випадку не забезпечується глобальний оптимум.

3. Послідовність не завжди сходиться до оптимуму .

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

З інших методів відшукання оптимальних умов широко застосовують методи випадкового пошуку, крутого сходження, метод симплексів. Усі розглянуті методи відрізняються від прямих методів повного перебору меншим обсягом обчислень і тому одержали широке поширення. Завдяки зменшенню обсягу обчислень і застосуванню обчислювальних машин можна одержати оптимальне рішення для дуже складних технічних і економічних задач при невеликих витратах часу. Застосування ЕОМ у деяких випадках дозволяє робити повний перебір усіх можливих значень функції відгуку.



 

IV.......� ПРОЦЕДУРИ МЕТОДУ НАЙШВИДШОГО СПУСКА (ПІДЙОМУ).

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

Необхідно:

1. Установити правило визначення кроку руху по градієнті, тобто правило переходу від к.

2. Правило визначення чи обчислення експерименту для визначення значення функції f(х) і її похідних (перших).

3. Правило зупинки обчислень.

 

Метод крутого сходження, чи метод Боксу — Уилсона, сполучить позитивні методи Зайделя — Гаусса, методу градієнта і методу повного чи дробового факторного експерименту.

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

При плануванні факторного експерименту досліджуваний об’єкт представляють у виді чорної шухляди, вхідними параметрами якого є фактори Xi, a вихідним — один з Y, прийнятий як параметр оптимізації. Математичну модель записують у виді функції відгуку в = f(Xi, Ху… , х’к)у простір з координатами хi, хy, …, хk, у якому шляхом крутого сходження (спуска) по поверхні відгуку необхідно знайти оптимальну крапку. Метод застосуємо для випадку, коли поверхня має одну екстремальну крапку й один параметр оптимізації. Цей емпіричний підхід дуже ефективний і дозволяє значно скоротити число досвідів, тому що описати порівняно великі ділянки поверхні відгуку традиційними методами при великій кількості факторів практично неможливо.

Опис проведення з малюнками.

 

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

 

V.......� МЕТОДИ ЩО ВИКОРИСТОВУЮТЬ.ДРУГІ ПОХІДНІ,

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

(1);

 

 

- досить малий крок у - околиці крапки.

Н(Х) – матриця других похідних (матриця Гэса).

Відомо, що в околиці экстремума будь-яка функція може бути ограниченна квадратичною функцією типу (1) чи (2), якщо її другі похідні не дорівнюють нулю.

Дамо геометричне пояснення ідеї обчислювальних процедур, що використовують другі похідні:

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

кращої апроксимацией кореня вираження , що лежить в. Ґрунтуючись на кресленні, можна записати: .

Запишемо правило при переході з крапки в крапку:

Запишемо рівняння апроксимирующей кривої в загальному виді в крапці b з використанням других похідних: (3)

На підставі (3) будуються наступні міркування: очевидно, що розумніше апроксимации min f(x) може бути min апроксимации функції (3). Нехай цей мінімум знаходиться в , тоді відповідно до теореми про необхідні і достатні умови, повний диференціал функції в крапці b повинний дорівнювати нулю . Визначення повного диференціала і рішення системи рівнянь, що складаються з часток похідних, дає в загальному виді умова: (4).

Рішення рівняння (4) для квадратичної функції має вид:

(5).

Якщо рішення задачі не сходиться за один крок, що має на увазі вираження (5), то його легко модифікувати для ітераційних процедур до наступного виду:

.

Метод Ньютона: Методом Ньютона може бути знайдений мінімум функції n перемінних F(x1 , …, xn ) чи знайдені рішення системи рівнянь виду:

Fi (x1 , x2 , …, xn ) = 0, i = 1, …, n

Рішення даної системи еквівалентно відшуканню рівного нулю мінімуму функції:

Для перебування мінімуму F задаємо деяке початкове наближення xi (0) (i = 1, …, n) і будуємо наступні наближення по формулі:

де напрямку vi (j) і величина кроку на j-ом кроці відповідно рівні:

Усі похідні обчислюються при xi = xi (j). Ітераційний процес продовжується доти, поки не буде задовольнятися умова

|xi (j+1)-xi (j)| < e (i = 1, …, n)

чи вся похідні d/dxk не стануть дорівнюють нулю.

 

 

У залежності від умови: вираження (5) чи вираження (6), а також від нормировки кроку руху , виходить та чи інша модифікація методу других похідних, але в будь-якому випадку, при використанні формул (5) і (6), на кожнім кроці потрібно обчислення й утворення матриць S. Часто ці обчислення визначають трудомісткість методу других похідних. Застосування даних формул не гарантує швидку збіжність методів, особливо якщо початкова крапка выбранна далеко від оптимальної. Ці недоліки породили нову групу алгоритмів.

Інші методи, що використовують другі похідні: усі ці методи основанны на удосконаленні визначення напрямку пошуку на кожній ітерації, про так само на використанні необхідності звертання матриць. Так метод Дэвидсона – Флетчера – Паула не вимагає звертання матриць. Так само часто використовується метод Усопряженного градиентаф, що використовує ідею теорії подвійності. Дуже часто алгоритми, що використовують другі похідні, містять у собі окремі алгоритми одномірного пошуку по кожній з координат.

 

VI.......� МЕТОДИ ПОКООРДИНАТНОГО СПУСКА (ПІДЙОМУ).

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

Ідея методу Гаусса – Зейделя: розглянемо функцію двох перемінних і зобразимо на кресленні лінії рівного рівня, що відповідають їй. У цьому методі по черзі розглядаються зміни по одній координаті при фіксованому значенні іншої. Фіксуємо одну координату, а другу змінюємо за законом (рівномірно). Обчислюємо значення функції в цих крапках, порівнюємо їх, і для крапок у який значення найкращі (у змісті більше, менше), у них обчислюють значення перших похідних для того, щоб із заданою точністю знайти крапку, де похідна дорівнює нулю (торкнулася лінії рівня). Фіксуємо цю координату і робимо те ж саме.

Метод Зейделя — Гаусса є часткою случаємо методу градієнта і передбачає почергове перебування частки экстремума по кожному з параметрів. При методі Зейделя — Гаусса шлях до оптимуму подовжується і стабілізація параметрів на тривалий час неможлива. Градиентные методи мають кілька різновидів (релаксационный, випадкового пошуку, найшвидшого спуска), але сутність їхній не змінюється.

 

 

4. ЧИСЕЛЬНІ МЕТОДИ ОПТИМІЗАЦІЇ. МЕТОДИ РЕГУЛЯРНОГО ПОШУКУ.

4.1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА МЕТОДІВ.

Дана група методів у процесі обчислень не вимагає визначення похідних і обчислення їх. Обмежимося лише чи обчисленням експериментальним визначенням значень цільової функції в деякій послідовності крапок. Шляхом послідовного порівняння цих значень, вибирають крапку, де досягається оптимальне рішення. Усі методи відрізняються друг від друга способами завдання послідовності і правилами зупинки рішення. У залежності від цього розроблені різні алгоритми регулярного пошуку, призначені як для оптимізації одномірних так і багатомірних функцій. Більшість з цих методів не дозволяють визначити глобальний оптимум за винятком опуклих функцій. За допомогою чисельних методів безпосередньо шукається роцес со функції f(х) у деякій заданій області, у якій приблизно знаходиться оптимум. Як правило, оптимізація функції одним перемінної є необхідним елементом методів оптимізації багатомірних функцій. Методи регулярного одномірного пошуку застосовуються в наступних ситуаціях:

1. Значення досліджуваної функції можна з’ясувати тільки після проведення якого-небудь експерименту.

2. Функція складна, і бажано зменшити кількість обчислень.

3. У практичних задачах часто невідомо, чи є функція дифференцируемой функцією.

4. Функція не має безупинних чи похідних разрывна.

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

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

Другою бажаною умовою є умова безперервності функції в деякій припустимій області. Ін. на відрізку [a,b] для одномірної функції. У цій ситуації також для точного визначення оптимуму необхідно було б перебрати всі припустимі крапки відрізка, але тому що на практиці необов’язково точне обчислення оптимальної крапки, те досить вибрати кінцеве число крапок інтервалу і визначити оптимум із заданою погрішністю. Методи регулярного пошуку відрізняються друг від друга способами вибору цих крапок. Більшість методів регулярного пошуку складається в побудові послідовності відрізків , що стягаються в крапці . Однак, як показали дослідження, завжди можна вказати таку безупинну функцію х, що для всякого кінцевого номера , відрізок , побудований будь-яким регулярним методом не буде містити оптимальної крапки, навіть якщо відомий початковий відрізок [a,b], усередині якого існує оптимум. У такий спосіб не для всіх класів функцій можна гарантувати приналежність останньому інтервалу невизначеності. Це можна зробити для класу унимодальных і строго унимодальных функцій.

Нагадаємо: по визначенню – функція f(х) називається унимодальной на х, якщо існує така крапка її мінімуму , що якщо , для . , якщо . У такий спосіб з возростанием х, функція f(х) ліворуч від крапки мінімуму монотонно убуває, а праворуч від крапки монотонно возростает, якщо функція f(х) унимодальна на дійсному інтервалі [a,b], якщо вона має мінімум і якщо виконується співвідношення .

У такий спосіб унимодальности функції на відрізку [a,b] володіє тим властивістю, що вона має єдиний локальний мінімум, але вона не обов’язково дифференцируема і не обов’язково повинна бути безупинної, тобто одномірні методи пошуку досить ефективні для функцій виду:

Методи регулярного (детермінованого) пошуку можуть будуватися на двох принципах:

1. Шукається положення мінімуму в крапці, що апроксимує з заздалегідь заданою точністю.

2. Визначення малого інтервалу, у якому знаходиться мінімум.

 

Унимодальные функції на [a,b].

У залежності від використовуваного принципу створюються ті чи інші стратегії визначення послідовності . Основна проблема методів регулярного пошуку – проблема вдалого (мінімального) вибору кількості крапок N, послідовності . Усі методи регулярного пошуку містять у собі процедури:

1. Завдання початкового інтервалу чи невизначеності [0;1] чи , у якому по припущенню знаходиться крапка оптимуму. Це не формализуемая процедура.

2. Завдання послідовності крапок , у яких обчислюється, чи експериментально визначається значення .

3. Порівняння значень , з метою визначення , або визначення інтервалу, що свідомо не містить оптимальну крапку і відкида на даному кроці .

Для організації цих процедур існують дві великі групи методів пошуку. Регулярний і випадковий. Обидві ці групи містять методи активного і пасивного пошуку. До найбільш ефективних і розповсюджених методів регулярного пошуку відносяться:

Пасивний пошук: - рівномірний;

- рівномірний розподілом навпіл.

Активний пошук: - спосіб дихотомії;

- спосіб Фибоначчи (Кифера);

- спосіб Золотого перетину;

- спосіб пошуку по роцес с.

Крім названих методів існує велика група активного пошуку, що використовують квадратичні і кубічні формули апроксимації функції f(х) у крапках біля . Найбільш відомі алгоритми Пауэла і Дэвис – Свен – Кемпла. Оскільки існує багато методів, то для вибору найбільш придатного необхідно вміти оцінити ефективність кожного методу.

 

VII.......� ПАСИВНИЙ ПОШУК.

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

 

VIII.......� РІВНОМІРНИЙ ПОШУК.

Перед початком пошуку задається вихідний інтервал невизначеності і число досвідів – N. Для визначення крапки відліку, довжину початкового інтервалу невизначеності поділяють на N, тобто . Кожна з цих крапок обчислюється значенням в. Недолік: для визначення з заданою точністю необхідно зробити багато експериментів (близько 20 тисяч).

 

IX.......� РІВНОМІРНИЙ ПОШУК РОЗПОДІЛОМ НАВПІЛ.

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

 

X.......� АКТИВНІ МЕТОДИ ПОШУКУ.

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

 

XI.......� МЕТОД ДИХОТОМІЇ.

Він застосовний для пошуку экстремума унимодальной функції при відсутності перешкод у неточності обчислень і вимірів, коли значення функції f(х) визначається в заданих крапках. Ідея методу: зона, де приблизно знаходиться оптиум, поділяється навпіл, і відображається та половина, де оптиум свідомо бути не може. Нехай відрізок містить приблизно оптимальну крапку . Розділимо на першому кроці цей проміжок крапкою Х, . У районі цієї крапки зробимо два виміри функцій і . Обчислення і виробляються з метою з’ясувати, чи праворуч ліворуч від Х знаходиться роцес со унимодальной функції , .

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

 

Помітимо, що при дуже малому , знак може змінюватися, стосовно щирого, за рахунок перешкод при обчисленні f(х). Це може привести до невірного відкидання інтервалу, і процес обчислення не зійдеться до оптимуму. У такий спосіб у результаті двох вимірів функцій і початковий інтервал невизначеності скорочується вдвічі, тому що половина безперспективного відрізка відкидається. Процес розподілу продовжується доти поки на - кроці після n=2N вимірів кінцевий інтервал невизначеності стане рівним (1) і де . Видозмінивши формулу (1) таким чином, щоб у довжині кінцевого інтервалу врахувати величину . Ідею пояснимо малюнком. Отже: (2), тому що n=2N. З формули (2) можна визначити швидкість збіжності методу .

 

XII.......� ПОШУК МЕТОДОМ ФИБОНАЧИ.

Метод дихотомії не оптимальний у тім змісті, що при фіксованому числі ітерацій N, він не приводить до найменшого, можливого для цього N, інтервалу невизначеності. Мінімально можлива при цьому N величина може бути полученна в методах Фибоначи й Узолотого сеченияф. Ідея вибору відрізків по

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

 

(3).

Тобто: .

Відповідно до результатів порівняння і виключеними може бути або чи відрізок , але тому що значення f(х) поки передбачається невідомим, те якщо ми хочемо, щоб величина інтервалу, що залишився, не зависила від результатів виміру f(х), те повинні выплняться рівності: . Це можливо якщо і симетричні щодо центра інтервалу , до цього результату можна прийти аналітично, якщо сформулювати задачу пошуку мінімального інтервалу або як задачу на минимакс, чи двоїсті задачі математичного програмування, чи задачу пошуку оптимального параметра як градієнт методу. Формула (3) описує співвідношення: чи .

Розподіл відрізків за правилом (3) породжує алгоритм методу Фибоначи (див. практику). Метод Фибоначи ефективніше методу дихотомії, тому що останній інтервал невизначеності є істотно менше і визначається як: , n=N+1.

 

XIII.......� ПОШУК МЕТОДОМ УЗОЛОТОГО СЕЧЕНИЯФ.

Метод – варіант методу Фибоначи, що дозволяє ефективно скорочувати інтервали, але не вимагає завдання числа ітерацій N. Метод золотого перетину застосовується для пошуку мінімуму функції одному перемінного на відрізку. Метод використовує наступна властивість безупинних функцій: якщо крапки g і h (g < h) розташовані на (a, b) і f(g) <= f(h), те на відрізку [a, h] є хоча б один мінімум функції. Аналогічно, якщо f(g) >= f(h), те на відрізку [g, b] є хоча б один мінімум.

Метод золотого перетину вибирає на відрізку дві симетричні крапки: g = A+(B-A)*(3-Sqrt(5))/2 і h = A+(B-A)*(Sqrt(5)-1)/2. Застосовується зазначена вище процедура, що приводить до відрізка [A, h] чи [g, B] (для визначеності розглянемо перший варіант). Якщо повторити зазначену процедуру, то можна знову зменшити відрізок. Важливою властивістю алгоритму є те, що на кожнім кроці можна використовувати одне значення функції з попереднього кроку, тому що при новій розбивці відрізка [A, h] крапками h’ і g’, ми побачимо, що h’ = g. Т.е. на кожнім кроці обчислюється тільки одне значення функції (і ще два на самому початку роботи).

Метод володіє стабільною лінійною швидкістю збіжності, що не залежить від рельєфу функції.

 

 

1. Бурдо О.Г., Калинин Л.Г. Прикладное моделирование роцес сов переноса в технологических системах: Учебник. – Одесса, ОНАХТ, 2008-348 с.

2. Мультимедійний підручник «Прикладное моделирование процессов переноса в технологических системах» Одеса: ОНАХТ 2007.

3. Ю.П. Адлер, Е.В. Маркова, Ю.В. Грановский. Планирование эксперимента при поиске оптимальных условий. –М. Наука 1971 – 283с.

 

 

Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой




Дата добавления: 2013-12-14; Просмотров: 404; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.078 сек.