Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

Разобьем отрезок [ а; 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 (х) =x 4 +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

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.





Дата публикования: 2015-04-07; Прочитано: 827 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...