Метод поразрядного поиска
Можно усовершенствовать
метод перебора
с целью уменьшения
количества
значений 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.
