КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Визначення найменшого значення функції на заданому відрізку за допомогою методів одновимірної оптимізації
Визначимо найменше значення функції 
на відрізку 
з точністю 
, використовуючи
· метод дихотомії:
Розіб’ємо відрізок навпіл і візьмемо дві симетричні відносно центру точки 
такі, що 
, де 
і відкинемо ту з точок, до якої ближче виявилась одна з двох знову поставлених точок з максимальним значенням.
Обчислюємо значення функції 
в цих точках:
Оскільки 
, то нові межі відрізка 
і 
. В цьому звуженому проміжку знову розраховуємо дві точки, симетричні відносно його середини і значення функції в цих точках. Процедура буде продовжуватись до тих пір, поки не буде виконуватись умова 
.
В нашому випадку 
. Тому знову розраховуємо дві точки:
Оскільки 
то нові межі відрізка 
і 
. Перевіряємо умову зупинки: 
. Отже продовжуємо процедуру.
нові межі відрізка , 
. Перевіряємо умову зупинки: 
. Отже продовжуємо процедуру.
нові межі відрізка 
, 
. Перевіряємо умову зупинки: 
. Продовжуємо процедуру.
нові межі відрізка 
, .
Перевіряємо умову зупинки: 
. Отже продовжуємо процедуру.
нові межі відрізка 
, 
. Перевіряємо умову зупинки: 
. Отже продовжуємо процедуру.
нові межі відрізка , 
. Перевіряємо умову зупинки: 
. Отже продовжуємо процедуру.
нові межі відрізка 
, 
. Перевіряємо умову зупинки: 
. Продовжуємо процедуру.
нові межі відрізка 
, . Перевіряємо умову зупинки: 
. Продовжуємо процедуру.
нові межі відрізка 
, 
. Перевіряємо умову зупинки: 
. Продовжуємо процедуру.
нові межі відрізка 
, 
.
Перевіряємо умову зупинки: 
. Отже в якості точки локального мінімуму можна наближено прийняти середину відрізку 
. Тоді мінімальне значення вихідної функції буде рівним:
Метод половинного ділення (бісекції)
Відрізок ізоляції кореня можна зменшити шляхом ділення його навпіл.
Такий метод можна застосовувати, якщо функція 
неперервна на відрізку 
і на його кінцях приймає значення різних знаків, тобто виконується умова 
(1).
Розділімо відрізок 
навпіл точкою, 
, яка буде наближення значення кореня 
.
Для зменшення похибки наближення кореня уточнюють відрізок ізоляції кореня. У цьому випадку продовжують ділити відрізки, що містять корінь, навпіл.
З відрізків 
і 
вибирають тієї, для якого виконується нерівність (1).
, де 
.
Далі повторюємо операцію ділення відрізка навпіл, тобто знаходимо 
і так далі до тих пір, поки не буде досягнуть задана точність 
. Тобто до тих пір, поки не перестануть змінюватися збереженні у відповіді десяткові знаки або до виконані нерівності 
.
Гідність методу: простота (достатності виконані нерівності (1)).
Недолік методу: повільна збіжність результату до заданої точності.
Приклад. Вирішити рівняння 
методом половинного ділення з точністю до 0,001.
Рішення. Відомій відрізок ізоляції кореня 
і задана точність 
. За рівнянням складемо функцію 
.
Знайдемо значення функції на кінцях відрізка:
, .
Перевіримо виконання нерівності (1):
- умова виконується, значить можна застосувати метод половинного ділення.
Знайдемо середину відрізка 
і обчислимо значення функції в отриманій точці:
, 
.
Серед значення 
і 
виберемо два значення різних знаків, але близьких один до одного. Це 
і 
. Отже, з відрізків 
і 
вибираємо той, на кінцях якого значення функції різних знаків. У нашому випадку це відрізок 
і знову знаходимо середину відрізка и обчислюємо значення функції в цій точці:
, 
, 
, 
- задана точність результату не досягнуть, продовжимо обчислення .
, 
, 
, 
.
, 
, 
, 
.
, 
, 
, 
.
, 
, 
, 
.
, 
, 
, 
.
, 
, 
, 
.
, 
, 
, 
.
, 
, 
, 
.
, 
- задана точність результату досягнуть, значить, знайшли наближення значення кореня 
. Відповідь: корінь рівняння 
з точністю до 0,001.
Нехай дано рівняння f(x)=0. Необхідно знайти його корінь з точністю e на відрізку [a,b], на якому функція безперервна і у кінцях має значення різних знаків, тобто f(a)×f(b)<0. Таким чином, згідно теореми 1, на цьому відрізку існує хоча б один розв’язок рівняння.
Знаходиться середина відрізку [a,b] точка с (рис. 3.2). Корінь може опинитись на відрізку [a,с] або на [с,b], чи співпасти з с. В останньому випадку метод припиняє роботу, інакше за допомогою перевірки виконання умов f(a)×f(c)<0 і f(c)×f(b)<0 з’ясовується, на якій частині відрізку залишився корінь. Далі процедура повторюється для тієї половини відрізку, на якій є корінь, доки відрізок не зменшиться настільки, що його довжина буде менше від заданої похибки.
Рисунок 3.2 – Метод половинного ділення
Алгоритм методу:
Крок 1. Знаходиться середина відрізку с:= (b+a)/2.
Крок 2. Перевіряються наступні умови.
1. Якщо f(c)=0 – корінь знайдено.
2. Якщо f(a)×f(c)<0 – корінь на [a,c], тому b:=c.
3. Якщо f(c)×f(b)<0 – корінь на [c,b], тому a:=c.
Крок 3. Перевіряється умова b-a<?. Якщо вона виконується, то корінь знайдено. В цьому випадку він дорівнює (a+b)/2. Інакше повертаються до кроку 1. Блок-схема методу представлена на рис.3.3.
Похибка розв’язку 
через n ітерацій знаходиться в межах
Метод має малу швидкість збіжності, оскільки інтервал, де знаходиться корінь, з кожним кроком зменшується не більше, ніж в два рази.
Рисунок 1 – Алгоритм методу половинного ділення
Дата добавления: 2015-07-26; просмотров: 165; Мы поможем в написании вашей работы!; Нарушение авторских прав |