Схема алгоритма

Алгоритм равномерного блочного поиска

Шаг 1. Задаются исходный отрезок неопределенности [ a, b ], e - точность приближенного решения , число экспериментов в блоке – n (нечетное, n= 2 k- 1). Проводим эксперимент в середине отрезка [ a, b ], т.е. вычисляем y_k=f (x_k), где xk =(a+b)/2.

Шаг 2. Проводим эксперименты в остальных точках блока: y_i=f (x_i), где x_i=a+i* (b-a)/(n+ 1), i= 1, 2,.., n, i¹ k. Находим точку x_j, в которой достигается минимум среди вычисленных значений: f(x_j)=min f(x_i), следовательно, точное значение минимума x^* содержится на отрезке [ x_j-1, x_j+1 ].

Шаг 3. Полагаем a=x_j -1, b=x_j+ 1, x_k=x_j, y_k=y_j. Если b-a£ 2 e, то , и поиск заканчивается. Иначе перейти к шагу 2. Если заданная точность e достигнута после т итераций, т.е. после экспериментов в m блоках, то длина отрезка неопределенности после всех N вычислений (N=n+ (m- 1)(n- 1) = (n- 1) m +1) будет:

и

Алгоритм деления интервала пополам

Это вариант предыдущего алгоритма при n= 3.

Схема алгоритма.

Шаг 1. Задаются a, b, e. Производим эксперимент в точке x₂ =(a+b)/2, т.е. вычисляем y₂=f (x₂).

Шаг 2. Проводим эксперименты в остальных точках блока: x₁ =(a + x₂)/2, y₁ = f (x₁), x₃ =(x₂ + b)/2, y₃ = f (x₃).

Находим x_j такую, что f (x_j)= min { f (x_i)}.

1 ≤ i ≤ 3Тогда точное решение x* содержится на отрезке [ x_{j -1}, x_{j +1}]. Предполагается .

Шаг 3. Полагаем a = x_j -1, b = xj +1, x₂=x_j, y₂=y_j. Если b-a £ 2 e, то и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число проведенных экспериментов равно N= 2 к+ 1, а длина получившегося отрезка неопределенности будет , где [ z ] – целая часть числа z. Следовательно, достигнутая точность будет , e=1/2L_N.

Метод дихотомии

Это алгоритм блочного поиска для ni=n= 2, т.е. когда в блоке два эксперимента. Так как пассивная составляющая алгоритма, т.е. блок, содержит четное число экспериментов, то оптимальный выбор точек x_ij, в которых необходимо провести эксперименты, будет неравномерным, в отличие от предыдущих алгоритмов, где число экспериментов в блоке было нечетным и, соответственно, расположение точек равномерным. Если блок содержит два эксперимента, то оптимальное (дельта оптимальное) расположение точек, в которых будут проводится эксперименты, это как можно ближе к середине отрезка. Такое расположение точек позволяет получить наименьший отрезок неопределенностей после экспериментов в блоке.

Схема алгоритма.

Шаг 1. Задаются a, b, e и d - малое положительное число, значительно меньшее чем e.

Шаг 2. Определяется середина отрезка x =(a + b)/2. Производятся эксперименты в двух точках близких середине: y1 = f (x - d), y2 = f (x + d).

Шаг 3. Определяется следующий отрезок локализации, т.е. определяется какой из отрезков [ a, x+d ] или [ x-d, b ] содержит точное решение x*. Если y₁£ y₂, то это отрезок [ a, x+d ] и b=x+d, иначе это отрезок [ x-d, b ] и a=x-d, т.е. выбранный отрезок локализации мы снова обозначили как [ a, b ].

Шаг 4. Если b-a £ 2 e, то x= (a+b)/2, и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число экспериментов будет N =2 к, а длина получившегося отрезка неопределенности . Следовательно, .ъ