Интервал локализации

Однако теперь обе задачи — найти у и решить задачу (3) — существенно осложняются. Начнем с задачи (3). Для ее решения разработаны алгоритмы последовательных испытаний, т.е. вычислений <р (s) в некоторых специально выбираемых точках sk, имеющие целью локализацию точки минимума ценой наименьшего числа испытаний. Но эти алгоритмы работают только при определенных предположениях, Пусть ищется минимум функции унимодальная функция, т. е. имеющая единственную точку минимума s. На интервале [0, s ] 9 монотонно убывает, на [s, 1] — монотонно возрастает непрерывность ср не предполагается, s может совпадать с любым концом интервала [О, 1]. Пусть на приближенное определение точки минимума <р (s) выделено определенное число п испытаний. Ставится задача так выбрать точки [slt s2,. . . . . ., sn последовательных испытаний, чтобы после их проведения можно было указать интервал локализации [а, [3] с [О, 1], на котором заведомо находится точка минимума <р. Обозначим длину интервала локализации после п испытаний через ln (s1, s2,. . . ч 1 т)- Тогда задача наилучшей организации испытаний ср, т. е. использования результатов уже проделанных вычислений при выборе очередной точки sft, может быть формализована следующим образом  [c.408]


В самом деле, вычислим ср в точках s = — jp- — е, s — — g-i--j-s, где е >0 — очень малая величина. Тогда, если у (s )< [c.409]

Алгоритм золотого сечения при том же числе испытаний дает более точную локализацию точки минимума. Обозначим через [<х0, р ] первоначальный интервал локализации (в нашем случае [О, 1]) и проведем испытания в двух точках а Ь причем al и bl распо-  [c.409]

Сравнением значений ср (%) и ф (Ьг) мы можем сократить интервал локализации, выбирая в качестве [ ц PJ либо [а0, bt] (при Ф ( i) < Ф (bi)), либо [OL Р0] (при ср (bj) < 9 (aj)) случай ср (%) = = ф ( х) не рассматривается как маловероятный и слишком удачный при этом [ , Pjl fai, bj]. В обоих случаях длина интервала  [c.409]

Опущенный при анализе случай ср (ai) = ( x) приводит к интервалу локализации [a1 (3J длиной 0,236 (Р0— ао)- В этой ситуации следует начинать процесс как бы с начала если такие ситуации будут встречаться, они только улучшат оценку. Таким образом, алгоритм золотого сечения лучше алгоритма деления интервала пополам в последнем длина интервала локализации  [c.410]


Лемма 1. Пусть так или иначе получен некоторый интервал [а, Р] локализации точки минимума (s [а, Р]). Тогда с помощью двух испытаний его длина может быть сокращена вдвое.  [c.409]

Теорема 1. Алгоритм золотого сечения позволяет ценой п вычислений функции у довести интервал локализации точки минимума ср (s) до размера (OjGlS)""1 ([30 — а ).  [c.410]

Например, при 20 испытаниях алгоритм золотого сечения даст интервал локализации примерно в 12—13 раз меньший, чем алгоритм деления пополам. Выше упоминался оптимальный алгоритм Кифера. Используя его, вычислитель не получит существенного выигрыша интервал локализации уменьшится (по сравнению с тем, что дал алгоритм золотого сечения) разве лишь на 2— 3%. Таким образом, алгоритм Кифера имеет в основном теоретическое значение, показывая, что алгоритм золотого сечения практически оптимален.  [c.410]

Смотреть страницы где упоминается термин Интервал локализации

: [c.409]    [c.409]    [c.484]    [c.178]   
Приближенное решение задач оптимального управления (1978) -- [ c.408 ]