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

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

Разобьем отрезок [ а; b ] на п равных частей точками деления x_i = а + i (b - а)/ п, i = 0,.., n. Вычислив значения f (х) в точках x_i, путем сравнения найдем точку x_m,0 £ т £ п, для которой

(2.9)

Далее, положим .

Замечания:

1. Погрешность определения точки минимумах x * функции f (х) ме­тодом перебора не превосходит величины .

Предположим, что x_m, из (2.9) является внутренней точкой разбиения отрезка [ а; b ], т.е. (случаи m = 0 и т = n рассматри­ваются аналогично). Тогда из соотношения (2.9) с учетом свойства (2.3) унимодальных функций следует что:

а) т.е. ;

б) т.е. .

Отсюда получаем, что Ç = . Длина последнего отрезка равна 2(6 - а) /п, а точка x_m является его серединой. Поэтому .

Таким образом, чтобы обеспечить требуемую точность e опреде­ления точки х *, число отрезков разбиения п необходимо выбрать из условия , т.е. .

2. Пусть реализация метода перебора потребовала N вычисле­ний функции f (х). Это означает, что отрезок [ а; b ] был разбит на n= N -1 частей и достигнутая точность определением x * составила . Поэтому точность решения e(N), которую обеспе­чивает метод перебора в результате N вычислений f (х),будет

. (2.10)

Пример 2.3. Метод перебора.

Решить задачу f (х) =x ⁴ +e^-x ® min, x Î[0; 1] с точностью до e = 0,1.

Функция f (х)унимодальна на отрезке [0; 1] (проверьте!). Найдем число n отрезков разбиения: , т.е. можно взять n = 10. Вычислим значения f (x_i),где x_i =0,1× i, i = 0,.., 10 и запишем их в табл. 2.1.

Таблица 2.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

В этой таблице подчеркнуто минимальное из вычисленных значений f (x). Та­ким образом, х *» 0,5, f *» 0,67.