Реферати українською » Математика » Мінімум функції багатьох змінних


Реферат Мінімум функції багатьох змінних

Страница 1 из 2 | Следующая страница

>РЕФЕРАТ

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

>Пояснительная записка до курсової роботі і двох основних частин: теоретичної і з практичної.

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

Практична частина містить розробку програмного забезпечення обчислення локального мінімуму функціїХиммельблау методомпокоординатного спуску, реалізовану мовоюPascal.

Обсяг пояснювальній записки: 1

Кількість малюнків: 4

Кількість використовуваних джерел: 3


>СОДЕРЖАНИЕ

ЗАПРОВАДЖЕННЯ

1. Мінімум функції одного змінного

1.1 Постановка завдання

1.2 Золоте перетин

2. Мінімум функції багатьох змінних

2.1 Рельєф функції

2.2 Узвіз по координатам

2.3Наискорейший спуск

2.4 Випадковий пошук

>ЗАКЛЮЧЕНИЕ

СПИСОКИСПОЛЬЗОВАННЫХИСТОЧНИКОВ

Додаток 1

Додаток 2


ЗАПРОВАДЖЕННЯ

 

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


1. Мінімум функції одного змінного

 

1.1 Постановка завдання.

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

. (1)

У функції можна знайти багато локальних мінімумів. Якщо ж виконується

, (2)

то говорять про досягненні функцією мінімуму цьому безлічі .

>Потребуем, щоб функція була безупинної чи, по крайнього заходу,кусочно-непреривной, а безліч булокомпактно[1] ізамкнуто[2] (зокрема, якщо саме є простір, це простір має бутибанаховим). Якщо такі вимоги не дотримані, то навряд чи видасться можливим побудувати розумний алгоритм знаходження рішення. Наприклад, а то й єкусочно-непреривной, то єдиний засіб виконання завдання є перебір всіх елементів , у яких задана функція; цей спосіб не вважається прийнятним. Чим більше більш жорстких вимог задовольняє (таких як існування безперервних похідних різного порядку), тим побудувати хороші чисельні алгоритми.

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

Для перебування мінімуму є лише одне спосіб: знайти локальні мінімуми, порівняти їх і вибрати найменше значення. Тому завдання (2) зводиться до завданню (1), і ми переважно займатися завданням пошуку локальних мінімумів.

Відомо, що ухвалено рішення завдання (1) задовольняє рівнянню

. (3)

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

Нехай є деяким безліччю, що належить якомусь простору. Тоді (1) називають завданням щонайменше в обмеженою області. Зокрема, якщо безліч виділено з простору з допомогою обмежують умов типу рівностей, то завдання (1) називають завданням на умовний екстремум; завдання методом невизначених множниківЛагранжа часто можна зводити до завданням на безумовний екстремум. Проте за чисельній рішенні зазвичай зручніше мати справу безпосередньо із вихідною завданням (1), хоча за її рішення у обмеженою області виникають свої труднощі.

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

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

1.2 Золоте перетин

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

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

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


a x1 x3 x2 b

>Рис. 1

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

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

.

Рішення всіх цих рівнянь дає

. (4)

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

Запишемо алгоритм обчислення. Для однаковості записи позначимо

,

а по черзі запроваджувані внутрішні точки будуть У першому кроці вважаємо відповідно до (4)

. (5)

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

. (6)

Потім відкидаємо ту точку, яка найбільшеудалена[3] від ; нехай цієї точкою виявилася :

. (7)

>Определим порядок розташування решти трьох точок на числової осі; нехай, для визначеності,

. (8)

Тоді нову внутрішню точку введемо такимсоотношением[4]:

, (9)

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

. (10)

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

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

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


2. Мінімум функції багатьох змінних

 

2.1 Рельєф функції

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

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

 

 а) б)


в)

>Рис. 2 р)


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

, (11)

і розкладання функції формулі Тейлора поблизу мінімуму має вигляд

, (12)

причому квадратична форма (12) – позитивноопределенная[5], інакше цю крапку б не буланевирожденним мінімумом. А лінії рівнязнакоопределеннойквадратичной форми – це еліпси.

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

Зазначимо, що умові (11) задовольняють також точки максимумів іседловие точки. Однак у точках максимумів квадратична форма (12) негативно певна, а сідловинах воназнакопеременна.

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

Розглянемоовражний тип рельєфу. Якщо лінії рівнякусочно-гладкие, то виділимо з кожної їх точку зламу.Геометрическое місце точок зламу назвемо істинним яром, якщо кут направлений у бік зростання функції, і гребенем – якщо зігнорувати зменшення (рис. 2, б). Частіше лінії рівня скрізь гладкі, але них є ділянки з великою кривизною; геометричні місця точок із найбільшою кривизною назвемо розв'язуються ярами чи гребенями (рис. 2, в). Наприклад, рельєф функції

, (13)

зображений у цьому малюнку, має яскраво виражений звивистий розв'язний яр, «дно» якого – синусоїда, а нижча точка – початок координат.

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

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

, (14)

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

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

2.2 Узвіз по координатам

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

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

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

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

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

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

Страница 1 из 2 | Следующая страница

Схожі реферати:

Навігація