3 # 10'Найдено значення f (% 4.4f) =% 4.4f з похибкою e =% 4.4f ', [xk, f (xk), e]));;.
Оптимальний пошук
функція програмування завдання
Розглянемо клас функцій одного аргументу, які називаються унімодальних. Визначимо унімодальних функцію y = f (X) наступним чином:
1. f (X) задана на відрізку [a, b]. 2. нехай X1 і X2 ? [a, b], причому X1 X0 слід f (X2 )> f (X1), а з X2 f (X2).
Приклади унімодальних функцій наведені на рис.7. Зауважимо, що визначення унімодальних виключає можливість ділянок f (X) з постійним значенням
рис. 7
мінімум f (X) може знаходиться у внутрішній точці [a, b] або на кордоні. Спочатку про становище X0 нічого не відомо, крім того, що, X0? [A, b]. [A, b] можна назвати відрізком невизначеності. p> Вибір Xi і обчислення F (Xi) називається експериментом. У всіх випадках після виконання заданих експериментів відрізок невизначеності стає вже. Послідовне повторення експериментів дозволить досягти величини відрізка невизначеності меншою, ніж будь-яке наперед задане? > 0. правило вибору Xi називається стратегією. Оптимальною називається стратегія, яка призводить до X0 (з точністю до?) За мінімальне число кроків (експериментів). p> Позначимо довжину відрізка невизначеності Ln (X1, X2, ..., Xn), де n - число експериментів;
f (Xk) = min f (Xi), 1? i? n,
де K - номер експерименту, якому відповідає мінімальне значення f (Xi). Тоді отримаємо:
X2 - X1, k = 1;
Ln (X1, X2, ..., Xn, к) = Xk +1 - Xk-1, 1? k? n;
Xn - Xn-1, k = n.
Т.ч., Ln залежить як від вибору способу розбиття [a, b], так і від поведінки f (X).
Пасивний пошук
У пасивному пошуку всі експерименти проводяться одночасно. Без обмеження спільності покладемо X1 = a = 0; Xn = b = 1;
Розглянемо n = 4; 0
Тоді Ln = max {X2 - 0, X3 - 0, 1 - X2, 1 - X3} = max {X3, 1 - X2}
1? k? 4 = min max {X3, 1 - X2}
0 k = 2,3
Так як X2 = ВЅ -? /2, X3 = ВЅ +? /2, а відповідне Ln = ВЅ +? /2 ( рис.8, а).
Під ? > 0 розуміють мінімальне число, яке робить 2 експерименту X2 і X3 різними.
