Метод деления пополам

Метод перебора

Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем.

Разобьем отрезок [a, b] на n равных частей точками деления:

xi=a+i(b-a)/n, i=0,...n

Вычислив значения F(x) в точках xi, путем сравнения найдем точку xm, где m - это число от 0 до n, такую, что

F(xm) = min F(xi) для всех i от 0 до n.

Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит величены Eps=(b-a)/n.

Метод поразрядного поиска

Можно усовершенствовать метод перебора с целью уменьшения количества значений F(x), которые необходимо находить в процессе минимизации. Во-превых, если оказывается, что F(xi)< = F(x[i+1]), то отпадает необходимость вычислять F(x) в точках x[i+2], x[i+3] и т.д.. Во-вторых, разумно было бы сначала определить отрезок, содержащий оптимальную точку, грубо, т.е. найти точку xm с небольшой точностью, а затем искать ее на этом отрезке с меньшим шагом дискретизации, повышая точность. Эти возможности улучшения и реализованы в методе поразрядного поиска. В этом методе перебор точек отрезка происходит сначала с шагом sh=x[i+1]-xi > eps до тех пор, пока не выполнится условие F(xi) < F(x[i+1]) или пока очередная из точек не совпадет с концом отрезка. После этого шаг уменьшается (обычно в 4 раза), и перебор точек с новым шагом производится в противоположном направлении до тех пор, пока значения F(x) снова не перестанут уменьшаться или очередная точка не совпадет с другим концом отрезка и т.д. Описанный процесс завершается, когда перебор в данном направлении закончен, а использованный при этом шаг дискретизации не превосходит eps.

Алгоритм метода поразрядного поиска

Шаг1. Выбрать начальный шаг sh=(b-a)/4. Положить x0=a. Вычислить F(x0).
Шаг2. Положить x1=x0+sh. Вычислить F(x1).
Шаг3. Сравнить F(x0) и F(x1). Если F(x0)> F(x1), то перейти к шагу 4, иначе -- к шагу 5.
Шаг4. Положить x0=x1 и F(x0)=F(x1). Проверить условие принадлежности x0 интервалу [a, b]. Если a < x0 < b, то перейти к шагу 2, иначе -- к шагу 5.
Шаг5. Проверка на окончание поиска: если |sh| < = eps, то вычисления завершить, полагая xm=x0, Fm=F(x0), иначе -- перейти к шагу 6.
Шаг6. Изменить направление поиска: положить x0=x1, F(x0)=F(x1), sh=-sh/4. Перейти к шагу 2.

Метод деления пополам

Рассмотрим функцию F, которую требуется минимизировать на интервале [a1, b1]. Предположим, что F строго квазивыпукла. Очевидно, что наименьшее число вычислений значений функции, которые необходимы для сокращения интервала неопределенности, равно двум. Одной из стратегий является выбор этих двух точек симметрично на расстоянии eps> 0 от середины интервала. Здесь число eps настолько мало, чтобы длина нового интервала неопределенности eps+(b1-a1)/2 являлась достаточно близкой к теоретическому значению (b1-a1)/2, и в то же время такое, чтобы значение функции в этих двух точках были различимы.

Алгоритм дихотомического поиска