![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем.
Разобьем отрезок [ а; 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; Прочитано: 829 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!