Лекция: Метод поразрядного перебора

Этот метод представляет собой усовершенствование метода перебора. Поиск точки минимума функции осуществляется с переменным шагом. Вначале шаг полагается достаточно большим и грубо находится отрезок, содержащий точку минимума. Затем с более высокой точностью на этом отрезке находится искомая точка минимума.

Изложенная идея реализуется в методе поразрядного поиска следующим образом. Перебор точек отрезка происходит сначала с шагом D = xi+1– xi>e до тех пор, пока функция не начнет увеличиваться, т. е. не выполнится условие f(xi+1) ³ f(xi) или пока очередная точка не совпадет с правым концом отрезка [a, b], на котором ищется минимум функции f(x). После этого шаг уменьшается (обычно в четыре раза) и перебор точек производится в обратном направлении, справа налево, пока значения функции f(x) снова не станут увеличиваться или очередная точка не совпадет с левым концом отрезка и т. д. Процесс завершается, когда перебор в данном направлении закончен, и величина шага не превосходит заданной точности e.

Алгоритм метода:

Шаг 1. Ввести исходные данные: a, b, e.

Шаг 2. Выбрать начальный шаг D =. Положить x0= a. Вычислить f(x0).

Шаг 3. Положить x1 = x0+ D. Вычислить f(x1).

Шаг 4. Сравнить f(x0) и f(x1). Если f(x0) > f(x1), то перейти к шагу 5, иначе – к шагу 6.

Шаг 5. Положить x0= x1 и f(x0) = f(x1). Проверить условие x0Î (a, b), т. е. a < x0< b. Если условие выполнено, перейти к шагу 3, иначе – к шагу 6.

Шаг 6. Проверка на окончание поиска. Если êDê£e, то вычисления завершить, положив x* » x0, f(x* )» f(x0), иначе – перейти к шагу 7.

Шаг 7. Изменение направления и шага поиска. Положить x0= x1 и f(x0) = f(x1), D = –. Перейти к шагу 3.