Лекция: МЕТОД ПЕРЕБОРА

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

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

(2.9)

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

Замечания:

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

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

а) т.е. ;

б) т.е. .

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

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

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

. (2.10)

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

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

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

Таблица 2.1

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