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

Этот метод является простейшим из прямых методов минимизации.

Пусть f(x) – унимодальная на отрезке [a, b] функция. Разобьем отрезок [a, b] на n равных частей точками x₀, x₁, x₂, …, x_n, так, что x_i = a + ih, i = 0, 1, … , n, h = . Вычислим значения функции f(x) в точках x_i и сравнив их, найдем точку x_m, для которой f(x_m) = f(x_i).

За приближение x^* примем x_m.

Оценим погрешность метода перебора.

В силу выбора точки x_m справедливы неравенства

f(x_m–1)  f(x_m), т.е. x^*  [x_m–1, b];

f(x_m)  f(x_m+1), т.е. x^*  [a, x_m+1].

Следовательно, x^*  [x_m–1, b] [a, x_m+1] = [x_m–1, x_m+1]. Длина отрезка [x_m–1, x_m+1] равна , и точка x_m является его серединой. Поэтому

x_m – x^* = _n.

Итак, чтобы обеспечить требуемую точность  определения минимума функции f(x) методом перебора, нужно число отрезков разбиения n выбрать из условия  , т.е.

n  . (1.4)

Пример 1.1.

Найдем минимум функции f(x) = x⁴ + e ^–x, x  [0, 1] с точностью до  = 0.1.

Число отрезков разбиения найдем из условия (1.4):

n  = 10.

Определим величину шага h:

h = = = 0.1.

Вычислим значения функции f(x) в точках x_i = a + ih = 0.1 i, i = 0, 1, … , 10. Эти значения представлены в таблице 1.1.

Таблица 1.1

xi	0.0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1.0
f(xi)	1.00	0.90	0.82	0.75	0.70	0.67	0.68	0.74	0.86	1.06	1.37

Из таблицы 1.1 видно, что минимальное из вычисленных значений есть f(0.5) = 0.67. Таким образом, x^*  0.5 и f(x^*)  0.67.

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

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

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

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

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

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

Шаг 3. Положить x₁ = x₀ + . Вычислить f(x₁).

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

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

Шаг 6. Проверка на окончание поиска. Если   , то вычисления завершить, положив x^*  x₀, f(x^* )  f(x₀), иначе – перейти к шагу 7.

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

Пример 1.2.

Методом поразрядного поиска решим задачу, рассмотренную в примере 1.1: f(x) = x⁴ + e ^–x  min, x  [0, 1],  = 0.1.

Положим, что начальный шаг  = = 0.25.

Вычисляем последовательно f(x_i) в точках x_i с шагом  в направлении слева направо (от 0 к 1). Результаты вычислений представлены в таблице 1.2.

Таблица 1.2

xi	0.00	0.25	0.50	0.75
f(xi)	1.000	0.783	0.669	0.789

Вычисления в данном направлении прекращаются, потому что f(0.50) < f(0.75), причем  > . Продолжаем поиск в противоположном направлении, справа налево (от 0.75 к 0). Величину шага уменьшаем в 4 раза, положив  = –0.0625. Результаты вычислений представлены в таблице 1.3.

Таблица 1.3

xi	0.7500	0.6875	0.6250	0.5625	0.5000	0.4375
f(xi)	0.789	0.726	0.688	0.670	0.669	0.682

Так как f(0.5000) < f(0.4375) и  = 0.0625 < , вычисления прекращаются. Таким образом, x^*  0.5 и f(x^*)  0.669.