Клочко О.В., Липко К.В.

Вінницький національний аграрний університет,Україна

Чисельні методи оптимізації. Метод половинного ділення

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

Чисельний метод – метод наближеного або точного розв’язання математичної задачі, що ґрунтується на побудові скінченої послідовності дій над скінченою множиною чисел [1].

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

Вирізняють чисельні методи стійкі та збіжні[3].

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

Чисельні методи називаються збіжними, якщо результати прямують до точного розв'язання задачі при прямуванні параметрів чисельних методів до певних граничних значень.

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

Метод половинного ділення являє собою один з методів вирішення нелінійних рівнянь і заснований на послідовному звуженні інтервалу, що містить єдиний корінь рівняння F (x) = 0 до того часу, поки не буде досягнута задана точність ɛ. Таким чином, якщо заданий відрізок [а, b], що містить один корінь рівняння, попередньо необхідно визначаємо області локалізації коренів даного рівняння. Якщо на відрізку [а, b] міститься більше одного кореня, то даний метод не працює.

Метод половинного ділення – це найпростіший метод уточнення кореня рівняння. Він сходиться для будь-яких неперервних функцій , в тому числі недиференційованих. Швидкість сходження невелика [3]

.

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

Тобто, нехай рівняння ¦(х) = 0 на відрізку [a;b] має єдиний корінь і функція на ньому неперервна. Поділимо відрізок [a;b] пополам точкою с=(а+в)/2.

Якщо ¦(с) ¹ 0, то можливі два випадки:

- або ¦(х) змінює знак на [a;с]

- або ¦(х) змінює знак на [а;b].

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

Алгоритм методу Половинного ділення полягає у послідовному розв’язанні задачі та виведення результатів дослідження.

Алгоритм даного методу включає [2]:

1) На відрізку вибираємо точку , яка розділяє його на два рівних відрізки і , довжина яких рівна і знаходиться за формулою

2) Перевіряємо чи , якщо так, то – точний корінь початкового рівняння і переходимо до пункту 6.

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

4) Процес ділення відрізка навпіл виконується доти, поки на якомусь етапі, або середина відрізка буде коренем, або буде виконана умова закінчення ітераційного процесу: .

5) У цьому випадку за наближене значення кореня вибирають .

6) Вивід результатів. Кінець алгоритму.

7) Відомо, що при цьому похибка не перевищує , де – число ітерацій.

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

Література:

1. Бахвалов Н.С. Численные методы / Н.С. Бахвалов, Н.П. Житков, Г.М. Кобельков. – М.: Лаборатория базовых знаний, 2001. – 598 с.

2. Поршнев С.В. Численные методы на базе MathCad / С.В. Поршнев, И.В. Беленкова. – С.-П., 2005. – 450 с.

3.Метод половинного поділу [Електронний ресурс]. - Режим доступу:www.posibnyky.vstu.vinnica.ua/chis_met/lek4.htm