3 часть (1081356), страница 47
Текст из файла (страница 47)
Дх) = (х+ 1)4 — 2хг, [ — 3, :— 2]., е = 0,05. 17.60. у'(х) = 3(5 — х)Мз + 2хг, [1.,5; 2], е = 0,025. 17.61. у (х) = — ха+3(1+х)[1п (1+ х) — Ц, [ — 0,5; 0,5], я = 0,05. 17 62 ) (х) 2+хг+хг)з )п (1 + хг/3) 2 > а с1~х>)з [О 5. Ц е = 0,025. В прямых методах минимизации, рассмотренных выше, требуется, чтобы функцин у'(х) была унимодальной. Если у(х) этим свойством нс обладает, то применение указанных методов приводит, вообще говори, к неверному реаультату. Кроме того, во многих случаях доказательство унимодальности функции >"(х) бывает затруднительно. Мс>иод ломаных является последовательным методом, рассчитанным на минимизацию произвольных (не обязательно унимодальных) функций, удовлетворяющих условию Липшнца.
Говорят, что функ- Гл. 17. Методы оптимизадии 334 цпя у(х) удовлетворяет на отрезке [а; Ь) условию Линишио, сгли суще- ствует такое число! > О (константа Липшица), гго ] Дх') — Е(х ') [ < В [х — х '] (8) для всех х', хв Е [а; Ь). Для проверки условия Липшнца на практике использук~т следующий факт; если 1)гуккция г(х) имеет но отправке [а; Ь] овуюкичсниукг производную, гяо ока удовлетворяет услоогсю (8), где г'. > п1ах]~'(х)]. (л, ь) Пусть функция у(х) удовлетворяет на [а; Ь) условикг Липшпца с константой В, Опишем метод ломаных для ьшнпмизации у(х). Положим х[ — — — Яа) — г" (Ь) + В(а + Ь)), р,* = — [у'(а) + У(Ь) + г",(а — Ь)) 1 1 и роализусм следующую схему вычислений: Ш а г 1. Вместо пары чисел (х*,, р',) образуем две новые пары (х'„р1) и (х",, р1) следующим образом: т.', = х*, — йы х~' — — х1+ йм р1 — — -[у(х") +р',), 1 где гл1 — — — [у(х*,) — р,*], Шаг 2.
Из полученных двух пар (х[, р1) и (х",, р|) выберем ту, у которой вторап компонента минимальна. Обозначим се (хг, р.',) и исключигл из рагсматривасмого множества (очевидно, на данном шаге в качестве (хг, р.") можно взять любукг пз пар (х',, р, ), (хы р~)). Вместо пары (хг, рг) добавляем две новые пары (хг, рг) н (хг, рг), компоненты которых находятся по формулам 1 хг = хг Ьг, хг = хг+ ь1г Рг = [г(хг) Рг] 2 1 где л г = [гс(хг) Рг].
В результате полу шга множество, состоящее пз трех пар чисел (х, р). Ш з г п, Из н полученных на предыдуших шагах пар (х, р) выбираем ту, у которой вторая компонента р минимальна. Обозначим ее (х,",, рв), Исключаем вту пару из рассматриваемого гвножества и добавляем вместо нее две новые пары чисел (хв, р„) и (х",„рл) по формулзм „вЂ” Ь„, х'„' = х'„+Ьв, Р, = — [,У(х„) — Р„) (9) 2 1 где л„ = [,У(хл) — Рв).
9 1. Численные методы минимизации функций одной переменной 335 Полагая х' х„', у'* — у'[х*„), получаем приближенное решение задачи минимизации. Точность ойределення у' характеризуется неравенствами 0 < у'[х„") — у'* < 2СЬ„. Геометрически метод ломаных состоит в построении последовательности ломаных, приближающихся к графику функции Дх) снизу и имеющих угловые коэффициенты всех звеньев, равные ху. (рис. 24).
Рч а х,* Ь х ах,'=-х2*х~ х" ,Ь х а х[ х) х,* Ь х 2 Ркс. 24 П ример 7. Методом ломаных найти минимум у' функции Дх) = япх = — на отрезке [10; 15] с точностью 0,01 и точку минимума х*. х < Функция у[х) дифференцируема на указанном отрезке. Так как хсовх — япх х]совх]+]япх] х+1 ]У'(х)[ = < « — О 11прих Е хэ хэ хэ Е [10; 15], то у'[х) удовлетворяет условию Липшица с константой 5 = = 0,11. Найдя х*, = 12, 056, р; = — О, 281, продолжим вычисления, используя соотношения (9). Результаты вычислений представим в таблице 1.4.
Таблица 1.4 Включенные пары 1х, Р) Исключаемап пара 1х, р) х„ а х„ х„" 1 2 3 4 5 б 7 8 9 10 12,056 10,963 13,149 10,646 11,280 10,474 10,818 11,094 11,466 10,891 — 0,281 -0,161 — 0,161 -0,126 — 0,126 -0,107 -0,107 -0,106 -0,106 — 0,099 0,240 0,070 0,203 0,038 0,041 0,024 0,160 0,016 0,028 0,008 < е 10,963 10,646 12,227 10,474 11,094 10,364 10,745 11,020 11,338 13,149 11,280 14,071 10,818 11,466 10,584 10,891 11,168 11,594 -0,161 — 0,126 — 0,096 -0,107 -0,106 — 0,095 -0,099 -0,098 — 0,092 336 Гл.
17. Методы оптимизации Из таблицы 1.4 находим х' — 10,89, ('*,(Я(10, 89) = 0,091. Отметим, что 7(х) ф () [10; 15], поэтому из методов минимизации, рассмотренных выше, в данном случае применим только метод ломаных. > 17.63. Показать, что если функция у"(х) удовлетворяет условию Липшица (8), то модуль углового коэффициента любой хорды или касательной к графику Дх) не превосходит константы Липшица 1'. 17.64. Показать, что если функция удовлетворяет условию Липшица (8), то она непрерывна на [а; 6]. 17.65.
Найти наименьшую из констант Липшица функции 1 ['(х) = -хз + 2хэ — 5х + 6 на отрезке: а) [О; Ц; б) [О; 10]. 3 17.66. Показать, что функция Дх) = ~/х на отрезке [О; Ц нс удовлетворяет условию Липшица. В задачах 17.67-17.71 методом ломаных найти минимум у"" функции Дх) на отрезке [а; 6] с точностью е( 17.67. ~((г) = —, [7; 1Ц, е = О, 01, П6В. Д( ( = — '20.. ~~ьыН,(9; ~Ц, =005. 17.69. 1(х) = (0,1х — 5)а+ сов(0,02х), [49; 5Ц, е = 0,02. 17.70.
1(х) = 1пх+ 0,1э(п(0,1х), [10; 12], е = 0,01. 1771 У( ) (. 0 9)з+(. 1 1)4 [08. 1 2] . 005 2. Методы минимизации, основанные на использовании производных функции. Если вычисление или изл4ерение производных функции у(х) не представляет больших затруднений, то при решении задачи минимизации можно применять непрямые методы, основанные на использовании производных у(х).
Во многих случаях эти методы обеспечивают более быструю сходимость, чем прямые метоцы минимизации. Метод касательных применяется для минилшзации выпуклых дифференпируемых функций. (рункпия 7(х) называется выпуклой на отрезке [а; 6], если у[ох'+ (1 — о)хн] < (я("(х') + (1 — о)Дхн) (10) для произвольных х', хн е [а; 6] и о б [О; Ц. Проверка условия (10) почти всегда вызывает затруднения, поэтому на практике используют следующий критерий выпуклости: Для того чтобы дважды дифферениируелсс я на отрезке [а; 6] функция Д(х) бь(ла выпуклой на отрезке [а; 6], необходима и достато (на, чтаобы (а(х) ) 0 яри всех х е [а; 6]. Опишем метод касательных. Пусть у(х) — выпуклая дифференцируемая на отрезке [а; 6] функция, причем у'(а) у'(6) ( О.
Построим с 3 1. Численные методы минимизации функций одной переменной 337 рекуррентными соотношениями ао=а, Ьо=Ь, (11) Ьа ~)~(Ьа ~) — а„ ,1'(а„ ~) + 1(а„ ~) — 1(Ь, ~) Г(Ь -~) — 7"'( — ) а„= а„м Ь„= с„~ при ~'(с„~) > О, (12) а„= с„ы Ьа = Ь„~ при 7'(с„~) < О. После а шагов полагаем х* с„, 7' ю у'(с„). Требуемая точность минимизации ((х) считается достигнутой, если производная у'(с„) достаточно близка к нулю, т.е. ]Д'(с„)] < с, где е > Π— заданное число, характеризуюшее точность.
Метод касательных имеет простой геометрический смысл: величина с„~ из (11) — зто абсцисса точки пересечения касательных к графику у(х), проведенных в граничных точках отрезка [а„~,Ь„~] (рис. 25). Рис. 26 и 27 поясняют формулы (11) для случаев у'(с„~) > О х а„х* Ь„ а„хе Ь„ Рнс. 27 Рис. 25 Ркс. 26 и ('(с„~) < О соответственно. Отрезок [а„; Ь„] выбирается так, чтобы х* б [а„; Ь„].
Если условие у'(а)у'(Ь) < О не выполняется, то а) х* = а при ('(а) > О, ~'(Ь) > О; б) х* = Ь при 7"'(а) < О, у'(Ь) < О; в) х' = а, если у'(а) = О, и х' = Ь, если 1'(Ь) = О. Пример 8. Убедиться, что функция у'(х) = хт + е* выпукла на [-1; 1) и минимизировать ее метод касательных с точностью ]у'(с„)~ < <О,О5. 4 Так как уа(х) = 2+ с* > О, то у'(х) — выпуклая функция; кроме того, У'(а)у'(Ь) < О.
Проведем вычисления по формулам (11), (12), поместив результаты вычислений в таблицу 1.5. 338 Гл. 17. Методы оптимизации Таблица Кб Из таблицы 1.5 находим х* сэ = 0,278; у'* Дел) = 0,835. > 17.72. Показать, что если функция Дх) выпукла на отрезке [а; Ъ], то на любом отрезке [х', хп] С [а; Ь] график 1(х) лежит не выше хорды, проходящей через точки графика с абсциссами х' и х". 17.73**. Показать,что если 1(х) — выпуклая дифферснцируемая функция, то любая касательная к графику 1" (х) лежит не выше этого графика. 17.74.
Показать, что выпуклая дифференцируемая на отрезке [а; Ь] функция унимодальна на этом отрезке. 17.75. Показать, что если функция Дх) выпукла на отрезке [а; Ь], то на этом отрезке любая точка локального минимума является и точкой глобального минимума Дх). В задачах 17.76-17.83, убедившись в выпуклости функции 7'(х) на отрезке [а; Ь], найти ее точку минимума х* и минимальное значение у* методом касательных, используя в качестве условия достижения требуемой точности неравенство ]у'(сп)] < О, 01: 17.76. 1(х) = х — 1пх, [0,1; 2].
17.77. 1(х) = х~ — э1пх, [О; я/2]. 1778 г( ) 4+ .2+ +1 [ 1. 2] хт 17.79. 1(х) = — — сов х, [О; 3]. 17.80. ('(х) = Я+ хт + е э*, [О; 1]. 17.81. 1" (х) = е*+ —, [О, 1; 2]. 1 17.82. 1(х) = (х —, 4)~ +1пх, [3; 5]. 17.83. 1(х) = хл+ е *, [О; 1]. Мепьод Ньютпона использующий не только первую, но и вторую производные функции У(х), прн определенных условипх обеспечивает значительно более высокую, чем рассмотренные выше методы минимизации, скорость сходимости к точке минимума х'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
