Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Визначення найменшого значення функції на заданому відрізку за допомогою методів одновимірної оптимізації




Визначимо найменше значення функції на відрізку з точністю , використовуючи

· метод дихотомії:

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

Обчислюємо значення функції в цих точках:

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

В нашому випадку . Тому знову розраховуємо дві точки:

Оскільки то нові межі відрізка і . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , .

Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , .

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

Метод половинного ділення (бісекції)

 

Відрізок ізоляції кореня можна зменшити шляхом ділення його навпіл.

Такий метод можна застосовувати, якщо функція неперервна на відрізку і на його кінцях приймає значення різних знаків, тобто виконується умова (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; просмотров: 86; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты