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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

РЕФЕРАТ

У роботі розглядаються методи знаходження мінімуму функції однієї змінної та функції багатьох змінних.
Пояснювальна записка до курсової роботи складається з двох основних частин: теоретичної та практичної.
У теоретичній частині розглядається пошук мінімуму функції однієї змінної методом золотого перерізу, пошук мінімуму функції багатьох змінних - методами покоординатного спуску, найшвидшого спуску і випадкового пошуку.
Практична частина містить розробку програмного забезпечення обчислення локального мінімуму функції Гіммельблау методом покоординатного спуску, реалізовану на мові 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). Тому відрізок можна відкинути і залишити відрізок . Перший крок процесу зроблено.


ax 1 x 3 x 2 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, а), функція має екстремум вздовж цього напрямку. Знайшовши таку точку, ми завершуємо в ній спуск по першому напрямку, і повинні почати спуск за другим напрямом (оскільки напрями ми зараз вибираємо паралельно координатним осям, то другий напрямок перпендикулярно першому).
Нехай лінії рівня утворюють справжній яр. Тоді можливий випадок (рис. 3, б), коли спуск по одній координаті приводить нас на «дно» яру, а будь-який рух за такою координаті (пунктирна лінія) веде нас на підйом. Ніякої подальший спуск по координатах неможливий, хоча мінімум ще не досягнуто; процес спуску за координатами в даному випадку не сходиться до мінімуму.
Навпаки, якщо функція достатньо гладка, то в деякому околі мінімуму процес спуску по координатах сходиться до цього мінімуму. Нехай функція має неперервні другі похідні, а її мінімум не виродилися. Для простоти знову розглянемо функцію двох змінних . Виберемо деякий нульове наближення і проведемо лінію рівня через цю точку. Нехай в області , Що обмежена цією лінією рівня, виконуються нерівності, що означають позитивну визначеність квадратичної форми (12):
. (15)
Доведемо, що тоді спуск за координатами з даного нульового наближення сходиться до мінімуму, причому лінійно.
Значення функції вздовж траєкторії спуску не зростають, тому траєкторія не може вийти з області , І нерівності (15) будуть виконуватися на всіх кроках. Розглянемо один з циклів, що починається в точці (Рис. 3, а). Попередній цикл закінчився пошуком мінімуму за напрямом , Отже, і . Перший крок нового циклу спускає нас у напрямку в точку , В якій і . Оскільки друга похідні неперервні, можна застосувати теорему про середню; отримаємо

де через позначені відстані між точками. Звідси отримуємо . Виконаємо другий крок циклу - спуск у напрямку в точку , Після якого і . Аналогічні міркування дають співвідношення з . Об'єднуючи ці нерівності, знайдемо
.
Отже, за один цикл зменшується в разів; те ж справедливо для , Якщо розглянути цикл, зрушений на один крок, тобто починається в точці і кончающийся в точці .
Значить, коли число циклів , То всі перші похідні лінійно прагнуть до нуля:
і ~ .
Перші похідні одночасно звертаються в нуль в точці мінімуму і поблизу нього є лінійними однорідними функціями збільшень координат. Тому координати точок спуску лінійно прагнуть до координат точки мінімуму, тобто в даному випадку спуск по координатах сходиться, причому лінійно.
Випадок (15) завідомо реалізується в досить малої околиці невиродженого мінімуму, бо ці умови еквівалентні вимогу позитивної визначеності квадратичної форми (12). Такими чином, поблизу невиродженого мінімуму достатньо гладкої функції спуск по координатах лінійно сходиться до мінімуму. Зокрема, для квадратичної функції цей метод сходиться при будь-якому нульовому наближенні.
Фактична швидкість збіжності буде непоганий при малих , Коли лінії рівня близькі до еліпсах, осі яких паралельні осям координат. Для еліпсів, сильно витягнутих під значним кутом до осей координат, величина і збіжність дуже повільна.
Якщо збіжність повільна, але траєкторія вже потрапила в близьку околиця мінімуму, то ітерації можна уточнювати процесом Ейткена; зрозуміло, при цьому треба брати в якості вихідних значення не на трьох останніх спусках, а на трьох циклах спусків (тобто не точки , А точки і третя точка, якої немає на рис. 3, а).
Розв'язано яр нагадує сильно витягнуту улоговину (див. рис. 3, б). При попаданні траєкторії спуску в такій яр збіжність стає настільки повільною, що розрахунок практично неможливо вести. Відзначимо, що в стохастичних задачах наявність помилок еквівалентно перетворенню істинних ярів і гребенів у розв'язані; розрахунок при цьому можна продовжувати, хоча практична цінність такого розрахунку невелика: збіжність дуже повільна.
Метод спуску по координатах нескладний і легко програмується на ЕОМ. Але сходиться він повільно, а при наявності ярів - дуже погано. Тому його використовують в якості першої спроби при знаходженні мінімуму.
Приклад. Розглянемо квадратичну функцію і виберемо нульове наближення . Виконуючи обчислення, отримаємо
.
Уточнення з Ейткену дає , Тобто точне положення мінімуму (зауважимо, що робити уточнення з використанням нульового наближення не можна).
2.3 найшвидшого спуску
Спускатися можна не тільки паралельно осям координат. Уздовж будь-якої прямої функція залежить тільки від однієї змінної, , І мінімум на цій прямій можна знайти.
Найбільш відомим є метод найшвидшого спуску, коли вибирається , Тобто напрямок, в якому функція швидше за все убуває при нескінченно малий рух з даної точки. Спуск по цьому напрямку до мінімуму визначає нове наближення . У цій точці знову визначається градієнт і робиться наступний спуск.
Однак цей метод значно складніше спуску по координатах, бо потрібно обчислювати похідні і градієнт і переходити до інших змінних. До того ж, за збіжності найшвидшого спуску не краще спуску по координатах. При попаданні траєкторії в дійсний яр спуск припиняється, а в вирішуваною яру сильно сповільнюється.
Якщо функція є позитивно певної квадратичною функцією
, (16)
то формули найшвидшого спуску набувають нескладний вигляд. Уздовж прямий функція (16) квадратично залежить від параметра :
. (17)
З рівняння легко знаходимо її мінімум
, (18)
дає нам наступну точку спуску:
(19)
напрям найшвидшого спуску визначається градієнтом квадратичної функції (16):
. (20)

Підставляючи це значення в формули (18) - (19), отримаємо остаточні вирази для обчислення послідовних спусків.
Якщо скористатися розкладанням всіх рухів по базису, що складається з власних векторів матриці , То можна довести, що для квадратичної функції метод найшвидшого спуску лінійно сходиться, причому
, Де ; (21)
тут - Власні значення позитивно певної матриці (Вони речовинні і позитивні). Якщо , Що відповідає сильно витягнутим еліпсах - лініям рівня, то і збіжність може бути дуже повільною.
Є такі початкові наближення (рис. 4), коли точно реалізується найгірша можлива оцінка, тобто в (21) має місце рівність.
Причини неважко зрозуміти. По-перше, в даній точці будь-яку пряму, в тому числі невигідну для спуску, можна зробити напрямком градієнта, якщо спеціально підібрати зміна масштабів по осях. По-друге, кожен спуск закінчується в точці, де його напрямок стосується лінії (поверхні) рівня. Градієнт перпендикулярний поверхні рівня. Отже, у методі найшвидшого спуску кожен спуск перпендикулярний попередньому. У двовимірному випадку це означає, що ми здійснюємо спуск по координатах, поверненим так, що одна вісь паралельна градієнту початкової точки.
Для поліпшення методу найшвидшого спуску пропонують «кухонні» поправки до алгоритму - наприклад, здійснюють по кожному напрямку спуск не точно до мінімуму. Найбільш цікавим видається така видозміна алгоритму. Будемо робити у напрямку, протилежному градієнту, тільки нескінченно малий крок і після нього знову уточнювати напрямок спуску. Це призводить до руху по кривій , Що є рішенням системи звичайних диференціальних рівнянь:
. (22)
Уздовж цієї кривої , Тобто функція спадає, і ми рухаємося до мінімуму при . Рівняння (22) моделює безінерційні рух матеріальної точки вниз по лінії градієнта. Можна побудувати і інші рівняння - наприклад, диференціальне рівняння другого порядку, що моделює рух точки при наявності в'язкого тертя.
Проте від ідеї методу ще далеко до надійного алгоритму. Фактично систему диференціальних рівнянь (22) треба чисельно інтегрувати. Якщо інтегрувати з великим кроком, то чисельне рішення буде помітно відхилятися від лінії градієнта. А при інтегруванні малим кроком сильно зростає обсяг розрахунків. Крім того, якщо рельєф має звивисті яри, то важко очікувати гарної збіжності цього методу.
Алгоритми найшвидшого спуску і всіх його видозмін зараз недостатньо відпрацьовані. Тому метод найшвидшого спуску для складних нелінійних задач з великим числом змінних ( ) Рідко застосовується, але в окремих випадках він може виявитися корисним.
2.4 Випадковий пошук
Методи спуску неповноцінні на неврегульованому рельєфі. Якщо локальних екстремумів багато, то спуск з одного нульового наближення може зійтися тільки до одного з локальних мінімумів, не обов'язково абсолютному. Тоді для дослідження задачі застосовують випадковий пошук.
Припускають, що цікавить нас мінімум (чи все мінімуми) лежить в деякій замкнутій області; лінійним перетворенням координат поміщають її всередину одиничного -Мірного куба. Вибирають в цьому кубі випадкових точок.
Навіть при мільйоні пробних точок ймовірність того, що хоча б одна точка потрапить в невелику околиця локального мінімуму, мізерно мала. Справді, нехай діаметр улоговини біля мінімуму становить від меж зміни кожної координати. Тоді обсяг цієї улоговини становить частину обсягу -Мірного куба. Вже при ні одна точка в улоговину не потрапить.
Тому беруть невелику кількість точок і кожну точку розглядають як нульове наближення. З кожної точки здійснюють спуск, швидко потрапляючи в найближчий яр або улоговину; коли кроки узвозу сильно коротшають, його припиняють, не добиваючись високої точності. Цього вже достатньо, щоб судити про величину функції в найближчому локальному мінімумі із задовільною точністю.
Порівнюючи (візуально або за допомогою програми) остаточні значення функції на всіх спусках між собою, можна вивчити розташування локальних мінімумів функції і зіставити їх величини. Після цього можна відібрати потрібні за змістом завдання мінімуми і провести в них додаткові спуски для отримання координат точок мінімуму з високою точністю.
Зазвичай у прикладних задачах потрібно в першу чергу добитися того, щоб досліджувана функція прийняла мінімальне або майже мінімальне значення. Але поблизу мінімуму значення функції слабко залежить від зміни координат. Навіщо тоді потрібно знаходити координати точки мінімуму з високою точністю? Виявляється, що це має не тільки теоретичний, а й практичний сенс.
Нехай, наприклад, координати - це розміри деталей механічної конструкції, а мінімізіруемая функція є міра якості конструкції. Якщо ми знайшли мінімум точно, то ми знаходимося в самому центрі улоговини біля мінімуму. У цьому випадку варіації координат впливають на функцію слабкіше, ніж в точках, розташованих ближче до країв улоговини. А безпечні варіації координат мають в даному прикладі сенс допусків на точність обробки деталей. Значить, при акуратному обчисленні координат мінімуму ми можемо дозволити великі допуски, тобто здешевити обробку деталей.
Метод випадкового пошуку часто дозволяє знайти всі локальні мінімуми функції від 10-20 змінних зі складним рельєфом. Він корисний і при дослідженні функції з єдиним мінімумом; в цьому випадку можна обійтися помітно меншим числом випадкових точок. Недолік методу в тому, що треба заздалегідь задати область, в якій вибираються випадкові точки. Якщо ми поставимо занадто широку область, то її важче детально дослідити, а якщо виберемо дуже вузьку область, то багато локальні мінімуми можуть виявитися поза нею. Правда, становище дещо полегшується тим, що при спусках траєкторії можуть вийти за межі заданої області і зійтися до лежачих поза цією областю мінімумів.

ВИСНОВОК

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

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Каліткін М.М. Чисельні методи. М.: Наука, 1978. 512с.
2. Амосов А.А., Дубинський Ю.А., Копченова Н. В. Обчислювальні методи для інженерів. М.: Вища школа, 1994. 543с.
3. Ракітін В.І., Первушин В.Є. Практичний посібник з методів обчислень. М.: Вища школа, 1998. 383с.

Додаток 1
Лістинг програми:
{Методом покоординатного спуску знайти точки локального мінімуму функції Гіммельблау f (x) = (x1 * x1 + x2-11) * (x1 * x1 + x2-11) + (x1 + x2 * x2-7) * (x1 + x2 * x2-7) з точністю e = 0.01}
program spusk;
uses crt;
const n = 2; k = 2;
type vector = array [1 .. n] of real;
var i: integer;
d, e, e1, h, h1, z: real;
x: vector; ch: char;
procedure pausa;
begin
writeln;
writeln ('Для виходу натисніть будь-яку клавішу ...');
repeat ch: = readkey until ch <>'';
end;
function f (x: vector): real;
var a, b: real;
begin a: = x [1] * x [1] + x [2] -11;
b: = x [1] + x [2] * x [2] -7;
f: = a * a + b * b;
end;
procedure scan (i: integer);
var a: boolean;
d1, z1: ​​real;
begin z: = f (x);
repeat d1: = abs (h1); x [i]: = x [i] + h1; z1: = f (x); a: = (z1> = z);
if a then h1: =- h1 / k;
z: = z1;
until a and (d1 <e1);
end;
begin
clrscr;
writeln ('Введіть координати початкового вектора (x1, x2 ):');
for i: = 1 to n do read (x [i]);
writeln ('Задайте точність знаходження точки min f (x ):');
read (e);
h: = 0.2; e1: = e / k;
repeat d: = abs (h);
for i: = 1 to n do
begin
h1: = h; scan (i);
end;
h: = h / k;
until d <e;
writeln ('Точка мінімуму: x1 =', x [1]: 9:6, '', 'x2 =', x [2]: 9:6);
writeln ('Похибка:', e: 9:6);
pausa;
end.

Додаток 2
Результат роботи програми:
Введіть координати початкового вектора (x1, x2):
1
2
Задайте точність знаходження точки min f (x):
0.01
Точка мінімуму: x1 = 2.996875 x2 = 2.000000
Похибка: 0.010000
Для виходу натисніть будь-яку клавішу.


[1] Безліч компактно, якщо з кожного нескінченного і обмеженого його підмножини можна виділити сходящуюся послідовність.
[2] Безліч замкнуто, якщо межа будь збіжної послідовності його елементів належить цій безлічі.
[3] Це вірно не за всяких поділках відрізка, але для поділу відповідно (4) це справедливо.
[4] Див попередню виноску.
[5] Квадратична форма називається позитивно визначеною, якщо при будь-яких (За винятком звертаються одночасно в нуль) вона позитивна.
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Курсова
92.2кб. | скачати


Схожі роботи:
Функції багатьох змінних Означення границя та неперервність похідні диференціали
Мінімізація функції багатьох змінних Наближені чисельні методи Метод Монте-Карло
Пошук максимуму однієї функції багатьох змінних методом покоординатного спуску і з допомогою методу
Функція багатьох змінних
Вивчення диференціального числення функцій однієї та багатьох змінних в умовах модульно-рейтингової
Монотонність функції необхідні і достатні умови Eкстремум функції однієї та декількох змінних
Чисельне інтегрування функції двох змінних
Діагностичний мінімум
Прожитковий мінімум
© Усі права захищені
написати до нас
Рейтинг@Mail.ru