Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 24
Текст из файла (страница 24)
Для функций одной переме1п1ой имеют место формулы 1(2> — 1(О> = у(Е 2>2=~Г(т> >т=) (0>2+ — ', у" (В,2>2, о >'(2) — )'(о) = у" (в.с) 2, о е„е„е, < 1. Полагая в зтих формулах 2=1 и пользуясь равенствами (1), получаем различные формулы для конечных приращений функции многих переменных: 1 Х (и+ Ь) — Х (и) =<Х' (и+01Й), Ь>= ( <Х' (и + й), й> М, (2) о Х (и + й) — Х (и) = <Х' (и), й>+ —, <Х" (и+В,й) Ь, й>, (3) <Х' (и + й) — Х' (и), й> = <Х'"(и + Еой) Ь, й>, где 0< 0„в„в, < 1.
Далее, так как — (Х' (и + 2Ь)) = Х" (и + 2Ь) й, 0:= 2 ( 1, то, интегрируя зто равенство по 2 на отрезке [О, 1[, получаем 1 ( 1 г(,~.о — г(о=[го.~~а)ьо=[[г'( +~1)о>1 (о) о о Подчеркнем еще раз, что в формулах (1) — (5) подразумевается, что точки и, и+й принадлежат множеству У вместе с отрезком и+ ой (0< 2 < 1). В частности, эти формулы верны на любых выпуклых множествах — множествах, которые содер- вспоыоглткльные пгвдложення 93 жат вместе с любыми двумя своими точками и и о и отрезок (и, о) =(и = пи+(1 — и)о, 0< а< 1), соединяющий эти точки (подробнее о выпуклых множествах см. з 4.1). 2.
При описании и исследовании методов минимизации нам часто придется иметь дело с функциями, градиент которых удовлетворяет условию Липшица. Определение 3. Пусть Х(и)~ С'(67). Скажем, что градиент Х'(и) этой функции удовлетворяет условию ХХипшица на множестве У с постоянной Х > О, если !Х'(и)- Х'(о) ! < Ии — о!, и, о я Г (6) Класс таких функций будем обозначать через С''((Х). Лемма 1.
Пусть У вЂ” выпуклое лгнохсество, Х(и)~пС" (ХХ). Тогда (Х(и) — Х(о) — <Х'(о), и — о>! < Ии — о!'/2 (7) при всех и, о ~в Г Д о к а з а т е л ь с т в о. С помощью формулы (2) имеем 1 Х (и) — Х (о) — (Х' (о), и — о) = ) (Х' (о + 1 (и — и)) — Х' (о), и — о) М. о С учетом условия (6) получим Х(и) — Х(о) — (Х'(о), и — о) !( 1 1 ( ) ! Х' (о + 1 (и — о)) — Х' (о) ! ! и — о ! дг (~ ) Ь ! и — о !'1 дг = о о 3. Приведем несколько лемм о числовых последовательностях, которые нам пригодятся при доказательстве сходимости методов минимизации, при оценке скорости их сходимости.
Лемма 2. Пусть числовая последовательность (аь) такова, что аь.Рг(аз + бю бь)0, й = О, 1, ..., ~~ бь(со. (8) к=о ат(аз+ ~; 6;~(аз+ ~ 6; гак 1=к (О) Тогда существует Пш аь(оо. Если (а,) ограничена еще и снизу, то 1пп аь конечен. ь ю Заметим, что если 6,=0 (1=0, 1, ...), то последовательность (а,) не возрастает, и лемма 1 превращается в хорошо известное утверждение о пределе монотонной последовательности.
Д о к а з а т е л ь с т в о. Суммируя первое из неравенств (8), имеем 94 ИГЛ. 3 пгедвлгительные свкдснпя прн всех та> й > О. Пусть 1пп аь =1пп аь„(йч(й„.ьп и = О, ь я 1,...); 1пп й„= оо. Положим в (9) 1с= й„. Получим а - аь„+ и и О~ + ~ч~ бг (ш)й„). Следовательно, 1пп а < а„„+ Д бг длЯвсех в=а п '=ге н = 1,2,... Отсюда при и — ~- оо имеем 1пп а„(1па аь„=1пп а ~г™ м-~с~ Однако всегда 1пп аг,( Иш и . Поэтому 1пп а = 1по а в~ о ив ., " и-м Отсюда следует существование предела (а„).
Далее, при й= 0 из (9) следует ограниченность (а„) сверху. Поэтому, если (а,) огранпчена еще и снизу, то 1пп а„конечен. ь ~а Лемма 3. Пусть числовая последовательность (Ь,) такова, что Ьд.~.,)Ьь — бю бь)0, й=0,1,..., ~; Ьь(оо. а=о Тогда существует 1пп Ьь) — со. Если (Ь,) ограничена еще и ь сверху, то 1пп Ьь конечен. ь м Эта лемма сводится к лемме 2, если принять Ьь= — а„(й = = О, 1, ...) . Лемма 4. Пусть числовая последовательность (а,) такова, что аь' О, й = 0,1,...; аа — ад+,)Аа~ь, й)7с )О, (10) А = сонэ( > О.
Тогда а,=О(й ') (й=1, 2, ...), т. е. найдется постоянная В > 0 такая, что 0-=а„(Вй ', (11) й=1, 2, Доказательство. Ксли а =0 при некотором т>й„то из (10) следует, что а, = 0 при всех й > и, и оценка (11) становится тривиальной — в (11) достаточно взять В = та шах ао 1<гам Поэтому пусть а.>0 при всех п>й,. Тогда из (10) имеем — — — "+' ) —" А ) А ) О, п ) й,. и+1 в я пЬъ э+1 Суммируя этп неравенства по и от й, до некоторого й — 1> й„ получаем аа ~ — аа ~) А(й — йг) или а„< А '(й — 1с,) ' (й > й,). Вспоыоглтнльныв пгвдложкния г 31 95 Но (й — 1с,)-'<(й,+1)й ' при 1с)й„поэтому 0<а,< <(й,+1)А 'й '.
Если 1<й<й„то 0<аз= йаьй '( <й,( шах аь) й ~. Остается в (11) принять В =- шах~(/се+ 1ль~ьо + 1)А ', й, шах аь). ~~како Л ем и а 5. Пусть числовая последовательность (а„) удовсетворяет уеловиялс (12) аь > О, й я Д/ = (1, 2,...); в,', л ад.ь, аь — — + — й ен Х; А у,сР' 0' (13) аь (Вй 'о, й ~ Х,; аз+,(аз+ Сй 'о, йен1„ /с+ 1я 1„ (14) (15) где А, В, С, р — положительные постоянные, р<1, а множества индексов 1„1, таковы, что Х, 0 1, =/Ч, 1,01, =дС (елучаи 1„= 8 или 1, = 8 не исключаются). Тогда существует постоянная Р ) 0 такая, что 0<а,<Рй ", 1с=1, 2, ...
(16) Доказательство. Можем считать, что А ) В+ С, так как если неравенство (13) верно для некоторого А = А, ) О, то оно верно для всех А )А,. Выберем натуральное число й, так, чтобы 4<й~<(й + 1) ~<6. (17) аь т,~(2А(йс + 1) ~. (18) Может случиться, что й, сн 1,.
Тогда воспользуемся неравенством (13). Заьсетим, что функция /„(а)=а — а'А '+Ай " достигает своего максимума на числовой оси при а = А/2, и поэтому /,(а)</,(А/2)=А/4+Ай " для всех а) 1, й= 1, 2, ... Убедимся в том, что такое число существует.
Для этого перепишем (17) в равносильном виде: 4' < й, < 6' — 1, где е = р ') ) 1. Существование такого числа й, будет доказано, если покажем, что длина отрезка (4', 6' — 1) при любом з) 1 не меньше 1, т. е. 6' — 4' — 1) 1 или д(е)= 6' — 4') 2 при всех е ) 1. Но д'(з)= 6'1в 6 — 4'1п 4)1п 6(6' — 4')) 0 (з ) 1), так что д(е) строго монотонно возрастает при е ) 1. Следовательно, д(е)) д(1)= 2 для всех е ) 1. Таким образом, при кахсдом р (О < р < 1) число й„удовлетворяющее условиям (17), существует. Покажем, что 96 пРедВАРддтвлънык сведенддя !Гл.
3 Тогда из (13) с учетом неравенств (17) имеем аь „,<1ь (а„) (А(4+ Ай« '«(А!4+ А~16( ~((5А116)6(йа+ 1) «<2А(й«+ 1) «. Если же й,ди1о то возможно и й,+1~1,. Тогда из (14), (17) следует, что аь,.ьд(В(й«+ 1) д«(В(й«+ 1) ~/4(2А(й«+ 1) « Если й,дя1ь но й,+1дн1„то из (14), (15), (17) получим аь +д (~ Вйо д«+ Сй««~ (Айв «< 2А (й«+ 1) « Оценка (18) доказана. Далее, сделаем индуктивное предположение: пусть при некотором й ) й, + 1 верна оценка а„<2Ай-'.
Возможно, что йдн1,. Тогда с учетом (17) имеем аь(2АЙ «(2АЙ,«(А~2. Поскольку 1„(а) монотонно возрастает на отрезке [О, А/2), то из (13) следует, что а,„., < ~,(а,)< < Я 2АЙ ') = 2Ай ' — 3АЙ " < 2А (й ' — й ") . Но при О < р < 1 справедливы соотношения й-«й-д«<(йг+ 1)-д <(й«.1 й«-д)-д =й '+'(й+1) '< (й+1) ', (19) поэтому а,+, < 2А(й+ 1) '. Если же Й~1, и 1с+1 ~ 1„то из (14), (17) получим ад+д <В(й+ 1) -'«< В(й+ 1) г(йо+ 1) г < 2А (й+ 1) Если й дн 1о но й+ 1 ~ 1., то нз (14), (15), (17), (19) имеем адьд((В+ С)й т«(Ай «(А(й« вЂ” 1)й «<А(й« вЂ” 1) й = А(й « — й '«) (2А(й+ 1) «. Тем самым показано, что ад< 2АЙ ' при всех й > й, + 1. Если 1 <й < й„то аь = й«аьй ~~(й«й «шах аь.
Остается в (16) прид~"~до нять П= шах~2А; й, шах аь~. двьвьо Лемма 6. Пусть числовая последовательность (н,) такова, что й=1, 2, ..., ьд,)0, (20) О < до„.д < (1 — гд) ьдд+ дд, где 0<гг(1, дь)0, й =- 1,2,..., ~д гь — д-оо, ь=д (21) 11т Иь/г„= О.
ь ~» Тогда 1пп ыь = О. ь аа Вспоъсогйтельные пгедложкния 97 Доказательство. Поскольку 1 — х<е-* при 0<х(1, то 1 — г, ( е '". Из неравенства (20) тогда имеем 0(в»+с( <вйе '»+ д» (/с = 1, 2, ...). Отсюда с помощью индукции нетрудно получить, что 0<в„,< в, + ~~'.) с/сехр 2,' г; ехр — ~~ г/, /с=1,2, (22) Далее воспользуемся известной теоремой Штольца ([165, ч. 1, с. 88)), представляющей собой разностный аналог правила Лопиталя и гласящей, что если последовательность (у,) монотонно возрастает, предел Иш (х» — хй й)/(уй — у»-й) существует, 11ш уй = й»» й-» = оо, то существует и предел 1пп хй/уй, причем й хй/уй = 11 (хй — х — )/(у» — у — ).
й» Положим уй=ехр~Дг;~, х»=в,+ ~~,',д»ехр~~г, (й=1, й 1 й ( с /=г »=1 1=1 2, ...). Из условий (21) следует, что (уй) монотонно возрастает и стремится к бесконечности. Кроме того, "» . / "»й = 1пп = 1пп — = О, й-» 1 — е й» 1 — е — ) — 'й так как функция х/(1 — е ") ограничена на множестве 0<х< -= 1. По теореме Штольца с учетом неравенства (22) получим 1пп ⻠— — 1пп х»/уй = 1пп (х» — хй,)/(у» — уй,) = О. й /с=1, 2, ..., в,>0, (23) 2, ..., вирд»/г» = с(со. (24) »н1 0 ~ св»а ~ (1 — гй) ай+ с/й, где 0(ге(1, с/»)О, /с=1, Тогда (25) й = 1, 2, 0(вй ( в,+с, Заметим, что неравенство (22) по существу представляет собой оценку скорости сходимости последовательности (в„).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
