2. 3 Методы одномерной оптимизации
жүктеу/скачать 33.79 Kb.
|
|
<== Возврат к содержанию раздела 2.3 Методы одномерной оптимизации К числу наиболее популярных численных методов одномерной оптимизации, т.е. поиска экстремума функции f (x), относятся: метод Больцано (деления интервала пополам), метод "золотого сечения" и пошаговый метод. Первые два метода ориентированы на поиск ext f (x) внутри фиксированного интервала (а;b) оси х, последний – на поиск ext f (x) в окрестности заданной точки х0. Будем рассматривать эти методы как методы поиска min f (x) (поиск max f (x) можно заменить поиском min [–f (x)] . М 
Рисунок 2.6 Иллюстрация к методу Больцано етод Больцано при поиске минимума функции f (x) предусматривает следующие действия (рисунок 2.6): 1) определяется средняя точка интервала (а;b) с = (a+b)/2; 2) выбирается число (b-a)/2 (наиболее популярная рекомендация: =(b-a)/4) и определяются точки x1=c- и x2=c+ ; 3) вычисляются значения функции в этих точках f (x1) и f (x2); 4) если f (x1) f (x2), то интервал (а;b) стягивается в свою левую половину: b c, в противном случае – в правую: а с. Для нового интервала (а;b) вновь выполняются действия п.п. 1)-4). Процесс деления интервала продолжается до тех пор, пока его длина не станет меньше заданной точности: b-а . При завершении процесса поиска за точку минимума f (x) принимается середина последнего отрезка: x*=(а+b)/2. Достаточные условия сходимости алгоритма метода Больцано: а) функция f (x) непрерывна внутри интервала (а;b) оси x; б) f (x) унимодальна на интервале (а;b), т.е. имеет внутри него единственный экстремум; в) в некоторой окрестности искомой точки х* f (x) является монотонной (с одной стороны возрастает, с другой - убывает). При тех же условиях сходится алгоритм метода "золотого сечения".
Следовательно, для отрезка единичной длины: 1/t = t/(1-t) t2+t-1=0, откуда Алгоритм метода "золотого сечения" при поиске минимума функции
1 
Рисунок 2.7 Иллюстрация к методу "золотого сечения"
2) вычисление значений функции f (x1) и f x2); 3) при f (x1) f (x2) – отсечение от интервала (а;b) его правой части: b x2, x2 x1; в противном случае – левой: a x1, x1 x2; 4) если b x2, то определяется точка х1 нового интервала (а;b), а если а х1, то точка х2, по правилам п.1). Для нового интервала (а;b) вновь выполняются действия п.п. 2)-4), причем в п.2) значение функции f (x) вычисляется один раз: только для вновь определяемой точки х1 или х2. Процесс деления интервала продолжается до тех пор, пока не выполнится условие b - а . При завершении процесса поиска за точку минимума f (x) принимается значение х* = (а+b)/2 . Число модификаций исходного интервала (a;b) при использовании метода “золотого сечения” больше, чем при использовании метода Больцано (от интервала отсекается не половина, а 0.382 его длины), но количество вычислений значения функции f (x) существенно меньше. Поэтому в случаях, когда значение f (x) вычисляется достаточно долго, метод “золотого сечения” имеет заметное преимущество перед методом Больцано. Пошаговый метод применяется в тех случаях, когда интервал (а;b) оси х, содержащий точку экстремума функции f (x) неизвестен, но известно, что экстремум находится в окрестности экспериментально найденной точки х0. Этот метод применяется на практике значительно чаще методов Больцано и "золотого сечения", т.к. условие сходимости его алгоритма намного проще: достаточно, чтобы функция f (x) была непрерывна в окрестности т. х0. П 
Рисунок 2.8 Иллюстрация к пошаговому методу ри поиске минимума f (x) метод заключается в следующем (рисунок 2.8): 1) выполняется пробный шаг от точки х0 с целью выбора направления поиска: x = x0 +x (x~0.5) и вычисляются значения f (х0), f (х); 2) если f (х) < f (х0), то величина основного шага, с которым осуществляется движение в направлении убывания функции, положительна (h > 0), в противном случае – отрицательна (h < 0); 3) движение в выбранном направлении с шагом h: xk+1= xk+h, k=0,1, ... осуществляется до тех пор, пока f (xk+1) < f (xk); 4) если f (xk+1) ≥ f (xk), то при выполнении условия h < ε процесс поиска заканчивается: x* =(xk+1+xk)/2; если h ε, то шаг уменьшается h=|h|/p, p > 1 (часто используют p = e 2,71828) и осуществляется возврат к п. 1) с начальной точкой х0 = xk . <== Возврат к содержанию раздела жүктеу/скачать 33.79 Kb. Достарыңызбен бөлісу:
|
)/2, x2=b-(b-a)(3–