ustify"> При розгляді n = 5 отримуємо (рис 8, б), що Ln покращилося на ? /2, що змушує відмовитися від непарного числа експериментів.
При довільному парному n найкраща стратегія складається парами ? - експериментів (Xi рознесені на відстань ?).
У загальному випадку Ln? 2/n +? /2.
В
рис.8
метод дихотомії
Існує досить очевидна теорема: "Якщо безперервна функція на кінцях деякого інтервалу має значення різних знаків, то всередині цього інтервалу у неї є корінь (як мінімум, один, але м.б. і декілька)" ;. Ось на базі цієї теореми і побудовано чисельну знаходження наближеного значення кореня функції. Узагальнено цей метод називається "дихотомією", тобто "Діленням відрізка на дві частини". Узагальнений алгоритм виглядає так:
задати початковий інтервал [a; b];
переконатися, що на кінцях функція має різний знак
<0.;
Початкове наближення
= .
повторювати
вибрати усередині інтервалу точку X;
порівняти знак функції в точці X зі знаком функції в одному з кінців;
якщо збігається, то перемістити цей кінець інтервалу в точку X,
інакше перемістити в точку X інший кінець інтервалу;
Після кожної ітерації відрізок, що містить корінь зменшується вдвічі;
поки не буде досягнута потрібна точність.
"Потрібна точність" визначається умовами завдання. Іноді потрібно, щоб значення функції було менше якоїсь наперед заданої величини, але це рідко - найчастіше потрібно визначити значення кореня з відхиленням від істинного в заданих межах. Найкраще, якщо можна з упевненістю гарантувати інтервал, в якому знаходиться корінь. p align="justify"> Метод вибору точки поділу - ключовий для швидкості роботи методу. Добре, якщо функція, чий корінь знаходиться, проста і швидко обчислюється; але всередині функції можуть бути і матричні операції, і чисельне інтегрування, і все що завгодно; так що головним критерієм оптимізації є мінімізація числа поділів (природно, без погіршення точності методу).
Метод розподілу навпіл дозволяє виключати в точності половину інтервалу на кожній ітерації. При використанні методу вважається, що функція неперервна і має на кінцях інтервалу різний знак. Після обчислення значення функції в середині інтервалу одна частина інтервалу відкидається так, щоб функція мала різний знак на кінцях частини, що залишилася. Інерційний процес п...
