Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 12
Текст из файла (страница 12)
44 методы минимизации Функции ОднОЙ негеменнои (гл. г Д о к а з а т е л ь с т в о. Необходимость доказана в теореме 4, так как в рассматриваемом случае 1(о) У (о) (о~[а, Ь]). Достаточность. Пусть У'(и) не убывает на [и, Ь]. Пусть а< о< и < лУ < Ь. Применяя формулу Лагранжа, имеем (У(и) — У(о))/(и — о)=У Д~), о<$,<и, (У(Уо) — У(и) )/(пУ вЂ” и) =У'(б,), и < 3, < и По условию У (й,) < У ($е), поэтому из предыдущих равенств следует одно из неравенств (2), что согласно теореме 1 равно- сильно выпуклости У(н) па [а, Ь].
Т е о р е м а 9. Для того чтобы двазсды диффервнууируемпя функция У(н) на отрезке [а, Ь] была выпуклой, необходимо и достаточно, чтобы У" (и) ~ 0 на [а, Ь]. Доказательство. Условие У" (н)~0 является необходи- мым и достаточяым для неуоывания У'(и) на [а, Ь]. Отсюда н из теоремы 8 следует требуемое. Используя теоремьг 8, 9, легко проверить, что функции У(и)= а, У(и)= — 1пи, У(и)= и1пи выпуклы на любом отрезке из области своего определения; функции У(и) = и' прн т> 1, т < 0 и У(п)= — и" при 0<У <1 выпуклы на любых отрезках [а, Ь] (О < о < ь < ) . Функция У(и) = з(п и выпукла на отрезке [ — н, О], но певыпукла па [ — н, и]. у и р а ж и е ни я.
(. 1(оказать, что если функция 1(и) выпукла яа отрезке [а, Ц, то 1'(и-';О) =- (п( (1 (и+ Ь) — 1 (и))УЬ, 1'(и — О) = ь ые = вор(1(и) — У(и — Уг))УУг при всех ищ [а, Ь]. Ь)е 2. Пусть функция 1(и) выпукла на отрезке [а, Ь]. Доказать, что тогда У'(и+О) непрерывна слева а 1'(и О) непрерывна справа при всех и (а<и<5). У к а э ание: воспользоваться непрерывностью 1(и), следствием 1 и упражнением О 3.
Пусть 1(и) выпукла на [а, Ь], Доказать, что У'(и — О) < 1'(и+ О) < < Х (и — О) < 1 (и+ О) ири всех и, и (а < и < и < Ь). Пользуясь этими норавеяствамц, показать, что 1(и) диффереицируема в точке и (а < и < Ь) тогда и только тогда, когда одна из функций 1'(и+ О) или У'(и — О) непре- рывка в точке г. 4. Пусть 1(и) выпукла па [а, Ь]. Пользуясь упражнениями 2, 3, дока- вать, что мпогкества точек непрерывности функции 1'(и+ О) и 1'(и — О) совпадают. Выаестя отсюда, что множество точек, в которых Х(и) недиф- фереяцяруема,ие более чем счетно. 5.
Пусть функция 1(и) непрерывна иа отрезке [а, Ь), диффереицируема па отрезках [а, а~], [аи ае],..., [а„ь а ], [а„, Ь](а < а~ <... < а < Ь), причем иа каждом таком отрезке производная 1 (и) суммируема, ие убы- вает и У'(а; — О) <1'(аг+О) (У = (, ..., и). Доказать, что тогда Х(и) вы- пукла яа [а, Ь]. О. Для выпуклости функции 1(и) на интервале (а, Ь) необходимо и до- статочно, чтобы существовала функция Ци) (и гя (а, Ь)) такая, что 1(и) ) ) 1(г) + У(и) (и — и) при всех и щ (а, Ь). Необходимость доказана в тео- реме 4.
докаягите достаточность. Покаггсите, что У(г) = Х'(и) почти всю- ду па (а, Ь). 7, Пользуясь теоромой 3, доказать, что выпуклая иа отрезке [а, Ь] функция Х(и) абсолютно непрерывна на любом отрезке [а, 3) ~: (а, Ь) 9 з) мвтоды кАслтГльньтх 45 8. Если функция 1(») возрастает ва отрезке [а, Ь] и суммируома на и этом отрезно, то функция Х(и) = ~1(1)»(1 выпунла па [а, Ь]. Доказать. а Верно ли обратное утверждение? 9. Пусть Х(и) выпукла на [а, Ь] и имеет обратную функцию.
Можно ли утверждать, что обратнан функция также будет выпуклой? Рассмотреть функции У(и) = е", У(и) = е ". 10. Пусть У(и) выпукла на [а, Ь] и )пп Х(и) = У(а), )пп Х(и) = и «ее и ь-е = Х ((), а (Х« — множество точен минимума У(и) на [а, Ь]. Доказать, что П«й [и р] чь И ((г« ~)пг [а, р]) тогда и только тогда, ногда Х'(а — 0) < < О, У'(р+ 0) > О (У'(а — 0) < О, У'(5+ 0) > 0); здесь а < а < 5 < Ь.
11. Доказать, что выпуклая на отрозке [а, Ь] функция У(и), отличная от постоянной, не можот достигать своей верхней грани внутри отрезка [а, Ь]. 12. Пусть функция Х(и) выпукла и монотонно возрастаот на отрезке [а, Ь], а функция з(з) выпунла на [с, »(], прпчом з(з) ж [а, Ь] при всех х ш [с, »(]. Доказать, что тогда сложная функция д(х) = Х(з(з)) выпукла на [с, ь?]. 13. ~азовеи функцию У(и) выпуклой иа отрсзко [а, Ь], если У((и+ е)У2) < (Х(и) + У(г))?2 при всех и, г»ы [а, Ь]. Доказать, что для непрерывных функций зто определенно выпуклой функции равносильно определению 1. Если пе требовать непрерывности У(и), то новое определение выделяет более широкий класс функций — см.
пример из [312, с. 119]. 14. Пусть У(и) — выпуклая функция при и > О, У(0) < О. Доказать, что тогда функция»р(и) = У(и)Уи монотонно возрастает при и > О. На примере функции У(и) = 1+ и' убедиться, что при У(0) > 0 зто утворждепне неверно.
У к а з а н и е: воспользоваться равенством Х(и)=У вЂ” (ий-Ь)+ — 0) (Ь>0). (и-»-Л и+Ь 15. Пусть функция У(и) выпукла и дважды днфферонцируема при и )~ > О, причем )пп (иХ'(и),—.Х (и)) ~< О. Доказать, что тогда»г(и) = У(и)»и и-ь монотонно убываег прп и > О. Указ аппо: вычислить производные функций Чь(и) и иУ'(и) — У(и). Я Доказать, что (а + Ь)" < 2" — '(а" + Ь ) при всех и > 1, а > О, Ь > О. У к а з а н и е: воспользоваться выпуклостью функции У(и) = и" прн и>0, л>1. в й. Метод касательных 1. Пусть функция 1(п) выпукла и дифференцируема яа отрезке [а, Ь]. Согласно теоремам 8.3, 8.7 такая функция удовлетворяет условию Липшица и унимодальна на [а, Ь[.
Поэтому для минимизации 1(и) на [а, Ь] применимы почти все описанные выше методы, в частности, метод ломаных из 3 6. Однако если значения функции 1(и) и ее производной 1'(и) вычисляются достаточно просто, то здесь можно продлоя»ить другой, вообще говоря, более эффективный вариант метода ломаных, когда в качестве звеньев ломаных берутся отрезки касательных к графику 1(п) в соответствующих точках. Зафиксируем какую-либо точку п»и[а, Ь] и определим функцию д~п, п)=1(п)+1'(и) (и — п), а < и - Ь. 46 31етоды м!пшмизлцпн Функции одной негев!енпон 1гл. 1 Согласно теореме 8.4 д(и, и)~У(и) )1 вы[а, Ь[.
В качестве начального приблилкения возьмем любую точку и,ю ы [а, Ь[ (например, и, = а), составим функцию р,(и) = у(и, и«) и определим точку и, 1н[а, Ь) нз условия р,(и,) = п11п (и ии)«,ь) (ясяо, что при Т (и,) т-- 0 будет и, = а или и, = Ь). Далее, берем пову1о фупкци1о р,(и) =шах(р,(и); д(и, и,)) и следующую точку и, ы [а, Ь) найдем из условия р, (и,) == — ш1п р,(и), и т, д. Если точки и„и„..., и„(и~1) уже иирьь! ПЗВЕСтпЫ, тО СОСтаВЛЯЕМ ФУНКЦИЮ Ри(и)=В1ат(Р«-1(и); И(и, и„))= = шах д(и, иг), и слеДУюЩУю точкУ и„ы опРеДелЯем из Усло- О«1<и вий р (и„+,) = ппп р (и) (и ч.ген [а, Ь)). Если при каком-лиоо им)«,ь) и ~ 0 окажется, что 1' (и„+ + 0) > О, л'(и„— 0) =- 0 (если а ( и„( Ь, то это п равносильно условию Ф--- л'(и„) = 0), то согласно теореме 8.5 ии ~ Ь1и— в этом случае задача мп,й нимизации уже решена и итерации на этом закапчиваются. н.,««,„, „д„,, „, в р ' '1 ', ":.
«««=«1 р р„(и) — непрерывная ку- Г сочно линейная функция и ее график представляет собой ломаную, состоящую из отрезков касательных к графику функции л(и) в точках и„ иь „ и (рис. 1.5). 11оэтоиу опи- Н санный метод естественно Рве. Х5. А — гэьфвк г(и, и,), С)) — тра- назвать методол1 касафвк Г(и, и ), АИ) — графвк р1(и), Рч' — тра- тельных. фвк Е(и, и«), ЛЛ1Г1Р— график р«(и), рй— график е(и, и ), А1гпч)1 — график р,(и) е о Р о м а 1 лл усть функция 3(и) на отрезке [а, Ь) выпукла и дифференцируема, а последовательность (и„) получена описанным выше методом касательных, причем иф с) (п = О, 1, ...).
Тогда: 1) )гш л' (и„) = )шг р«(ги.ь1) = «'и и справедлива оценка О < Х(и .Е1) — л'и ( Х(ии~ь1) — р„(и„ь1), и = 1, 2, 47 митод клслткльных 2) (пп р(игь Пь) = О, или точнее, (и„) имеет не более двух и предельных точен, совпадающих с и = гп1 П или о = зпр(У,„. Д о к аз а т е л ь с т в о. Поскольку величины 1 (а+ 0), У'(Ь вЂ” 0) конечны по условию, то в силу теоремы 8.3 функция У(и) удовлетворяет условию Липшица с постоянной У = шах (~У' (а) ~; )1'(Ь) ~). Кроме того, согласно (1) и определению функции р„(и) имеем р„,(и)<р (и)<1(и), иш(а, Ь), п=1, 2, ... (2) Тогда 1(иг)= у(иь и,)< р„(и;)<1(и,), т. е. 1(и,)= р„(и,), г=О, 1, ..., и. (3) Наконец, угловые коэффициенты касательных у(и, и,) равны 1'(и,), причем ~1'(иг) ~ < У.
Из теоремы 6.1 тогда слодует, что р„(и) удовлетворяет условию Липшица с постоянной У. Отсюда с учетом (2), (3) с помощью тех же рассуждений, которые применялись при доказательстве теоремы 6.3, нетрудно убедиться в справедливости всех утверждений доказываемой теоремы. Остается лишь заметить, что пз того, что фушсция 1(и) уяимодальпа и и ф(У = (иа, оь) (п)~0), равенство Ппгр(и„, (У,„) ==-0 вози можно только в том случае, если предельными для (и„) могут быть лишь точки ггч или о„. 2. Метод касательных обладает всеми достоинствами метода ломаных из $ 6.
Недостаток этого метода: он применим лишь в случае, когда минимизируемая функция выпукла и значения функции и ее производных вычисляются достаточно просто. Можно предложить более удобкуго для использования па ЗВМ вычислительную схему кгетода касательных, которая пе требует храпения в машвнной памяти информации обо всей ломаной р„(и) прп и ~(а, !г). А именно, возьмем а, =а, Ь, = Ь, вычислим 1'(а,)=1'(а+ 0), 1'(Ь,)=У'(Ъ вЂ” 0). Если 1'(а,)~ О или 1'(Ь,)- <О, то по теореме 8.5 ая(1„или ЬяЬг„— задача решена. Поэтому, пусть 1'(а,) < О, 1'(Ь,)) О, что согласно теореме 8 6 означает (Уч~(а, Ь). Пусть отрезок (а „Ь„,) (гг) 2) уже построея, причем 1 (а,)<0, 1'(Ь„,)>0, (гас:(аг-м Ь г).