Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 96
Текст из файла (страница 96)
и, Следующие прпближенил определим по формулам Сь»> = Сь+ р(СА)/5> Се =О, 1, ... (17) теорема 4. пусть функ>йия р(с) ) 0 при всех й, — со < й ( +со, удое.>етворяет условию (15), пусть С» — минимальный корень уравнения (5) в смь>еле определения 1, С») — о». Тогда при любом выборе начального приблихсения Сг, — оо < Сс ( С, последовательность (Сь), определяемая условиями (17), сходится к С». Доказательства Так ьак р(й) )О, то из (17) следует, что последовательность (сь) монотонно возрастает, и поэтому существует 1пп са — а(со. пока>кем, что а = с».
по условию с < с . Допустим, А.»» что при некотором А ) 0 оказалось йь< с». тогда р(с) > 0 прп всех с ( сь Возьмем произвольное й, йь < с ( сьь>. С учетом условий (15), (17) и>сеем р(й) = р(Н) + (р(й) — р(йг)) ) р(Й) — Е(С вЂ” С ) > > Р(йь) — Ь(йьь> — Сь) =О, Сь< С ( йьч>. это аначит, что Р(с) > 0 пРи всех с < сь+>, т. е. са+д< с*. 51онсет слУ- читься, что р(Сьь>) = О.
Тогда СА+с — С» — в атом случае итерации (17) заканчивается. если р(сьь>) > О, то с +> < с н итерации продолжаются далыпе. Таким образом, имеются две возможности, Либо процесс (17) закончится тем, что р(сс) > О,, р(йл->) > О, р(сь) = 0 — тогда са — — с» = а, утверждение теоремы верно.
либо р(сь) > О, та(с», р(й) > 0 при с < йь для всех А = О, 1, ... — в этом случае 1пп сь — — а ( с и р (с) ) 0 при всех А с ( а, покажем, что а = й . если последовательность (сь) неограничена сверху, то а = оо = С». Если >ко Сл < а < с, А = О, 1, ..., то, учитывая непрерывность функции р(с), из (17) при А-»со получим а = а+ р(а)/Ь или р(а) О. Это влачит, что С» = а и при а ( оо.
Теорема доказана. Заметим, что на каждом шаге метода (17) нужно вычислить одно значение функции р(й), и для этого в свою очередь нужно решить задачу минимиаации (18) Ф(и, с) ->- ш1; и еи ссг. 408 ьтктоды минпмизлции сгупкций многих пнрнмкнпых ~гл. ь Поскольку функция (13), вообще говоря, не является гладкой, то это об. стоятельство может вызвать некоторые трудности при решении задачи (18). Однако имеющиеся методы решения негладких задач минимизации (см., например, $3, 11, 12, 17) позволяют надеяться на то, что вычисление приближенного значения р(1) не окажется слишком трудным.
Прп изложении метода (17) предполагалось, что величины р(зг) известны точно. Однако задача (18) на практике, как правило, будет решаться приблиягенно, и точное значение р(зг) удастся вычислить лишь в редких случаях, Поэтому желательно обобгцпть итерационный процесс (17) на случай, когда значения функции известны неточно. Опишем одно из возможных таких оообщеннй (82]. Предположим, что вместо точных значений функции р(з) известны лишь некоторые приближения р,(г) (» = 1, 2, ...), удовлетворяющие усло- виям р (с))0, (р (1) — р(с)]<у», »=1, 2...,; )пп 7 = О. (!9) Пусть гг — начальное приближение, 1 < г .
Пусть (» — 1)-е приближение Ы ~ прп некотором» ) 1 уже иавестно. Для определения следующего приближения ы рассыотрям итерационный процесс г„+, — 1„+ Р, (з,ь)(5, й = О, 1, ...; 2) либо р,(с~г) ) О при всех 5=0, 1, (23) (15), (19) и со- равенство Тогда, как будет показано ниже, при выполнении условий гласованном изменении величин О, и 7. будет справедливо (24) Метод поиска минимального корня уравнения (5) при условиях (15), (19) описан теор ем а 5.
пусть 1дункция р(1) неотрицательная при всех д нв возрастает, удовлетворяет условию (15), а Гг ) — оо — минимальный корень уравнения (5) е смысле определения 1, Кроме того, пусть 1дункция (рт(Г)) удовлетворяет белови м (19) и О,) "(т, »=1,2,... (25) Тогда последовательность (Г„), определяемая методом (20) †(24), сходит- СЯ к тг пРи любом выбоРе начального пРиближениЯ зг, — оо < С < С .
ПРи о илом, если се < сю, то итерации (20) яри каждом»> 1 будут еаканчи- аналогичный процессу (17). Поскольиу функция р„(г) может не обращаться в нуль пи в одной точке даже в том случае, когда уравнение (5) имеет конечный минимачьный корень (так будет, например, если р,(г) = р(г) -)- + 7, ) цл ) О), то процесс (20) следует прекращать не по критерию р,(глг) = О, как было выше в (17), а по условию вида р (г ь) < О„где величина О, ) 0 стремится к нулю при»- со и кан-то согласована с погрешностью 7,. Предположим, что такая последовательность (О,) уже задана (условня согласования (О,) и (7„) будут обсуждаться виже).
Тогда имеют. ся две воэможности: 1) либо найдется номер й = й,) 0 такой, что Р (та))О, й=0, ...,й — 1, Р (Г„„)<0~; (21) в этом случае процесс (20) заканчивается и полагаем г„= 1»ь (22) МЕТОД НАРРУЖЕННИХ ФУНКЦИЙ 40Ч $1Б! вагьсл га конечное число шагов выиолнениеи условий (21); случая (23) воелолсен лишь ири 1„= со. Д о к а э а т е л ь с т в о.
Сначала рассмотрим случай 1» < оо. Тогда при каждом фиксированном т ) 1 имеются две возможности: 1) 1 4(~ 1» ( оо при всех й = О, 1,... В силу монотонности (1»х) тогда существует 11ш 1»4~1»<со. Переходя в (20) к пределу при й-»-со, 4-»» получим 1!ш рч(1 4) =О. Это значит, что за конечное число итераций 4»» процесс (20) закончится выполнением условий (21). 2) Найдется номер 1) О такой, что 1„1 (1 (1 1+д. Тогда с учетом соотношений (15), (19), (20) получим ут1»д = 1»1+ Рч(1»1)/Ь = гш+ [Р»(1»1) — Р(1»1))/б+ ь (Р(1,1) — Р (1,))/б( 1„~- уч/б+ 1, — 1„= 1, -)- у,/б. (26) Далее, в силу монотонности р(1) имеем р(1) = 0 при 1) 1», поэтому Р(г,г+~) = О.
Отсюда и иэ условий (19), (25) следует Р„(1„,»,) = Р„(гы ю) — Р(гш ю) < 3. ( О.. (27) Это значит, что условия (21) выполнятся при некотором й, ( 1+ 1. Объединял обе рассмотренные возможности, заключаем, что при 1» < со процесс (20) прп каждом ч ) 1 заканчивается за конечное число шагов й„ выполнением условий (21), причем в силу (26) 1» 1»4 ~(1»+ у»~ (28) Покажем, что 1!ш 1„=1». Из (28) имеем Нш 1„(1 .
Пусть 1!пх 1 »»» ч-ш ' ч 1!пх 1„= а. Тогда с учетом условий (15), (19), (21) получим г» О<Р(а)-;]Р(а) — Р/1„)]+ [Р/1» )] Р, (1» )]+Рч (1» ) < (б!а — 1, ]+у„+О, — О при г- о, т. е. Р(а) =О. Но 1 — минимальный корень уравнения (5), поэтому а)1„. Счедовательно, 1пп 1„= 11ш 1 )1 ) !па 1.
Это значит, » что !!ш 1,= 1», Случай 1„( оо полностью рассмотрен. ч»» Пусть теперь 1 = со и пусть процесс (20) при каждом ч) 1 заканчивается выполнением условий (21). Покажем, что тогда (1) — со. Возьмем произвольное число Т ) О. Согласно определению 1, если 1» = со, то !ш р(1))0 и р(1) ) 0 при всех 1. Отсюда и из непрерывности функ- 1~ — г» Ции Р(1) следУет, что пх! Р(1) = Рт) О. Так как (6 )-»0, (т,)-»0, то !ат найдется номер те =чг(Т) такой, что 0»+ т ( рт при всех т) чь Тогда р (1) ) р(1) — т ) Рт — т ) 6» для всех 1 ( т и ч ) чг.
это значит, что условия (2Ц не могут выполняться при ! 4(Т, если ч) чс. Тогда согласно (21), (22) 1, ) Т для всех т ) тг =ч,(Т), что означает выполнение равенства Иш 1 оо. ч»» Остается рассмотреть случай, когда при некотором т ) 1 выполняются условия (23). Выше было установлено, что при 1»(оо процесс (20) при всех ч ) 1 закончится выполнением условий (21). Следовательно, если при каком-либо ч ) 1 реализуются условия (23), то 1» = со.
Теорема 5 доказана. 408 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ЦЕРЕЫЕННЬГХ «ГЛ. Э Заметим, что условие (25) в теореме 5 существенно: его нарушение мо. жет привести к тому, что метод (20) — (24) не будет сходиться. Пример 9. Пусть У(п) =и-т!п(; на П=П» (и«нЕ«: п>0)— это частный«случай задачи (1), когда д«(п) пн 0 (или в = 0). Тогда Ф(п, с) = шах (и — «, О), и ) 0 и Р (!) = Ж Ф (н, !) = шах ( — с; 0) (ср.
и)~ с примером 1), Здесь !» = У» = О, п» = О. Если р.(с) = шах( — г; 0) + Т„ и О, < Те то Р„(!) ) т,) О, пРи всех !. ПоэтомУ в методе (20) — (24) реализуется случай (23), и искомый минимальный корень ! = 0 уравнения (5) в рассматриваемом случае не будет найден. Причина атого явления — нарушение условия (25). Заметим, также, что на практике вместо полуоси «с < ! < со часто приходится работать на каиом-то отрезке «с < с < Т, где величина Т ограничена, например, раарядной сеткой ЭВМ.
В атом случае метод (20) — (24) требует модификации. А именно, итерационный процесс (20) при каждом т ) 1 адесь будет ааканчнваться определением номера к„ > 0 такого, что будет выполнено одно ив двух следующих условий: Р (! А)>В««, !«=О, ...,ӄ— 1; Р (! „)<О, ! „<Т, (29) илн Рт(сть)~В»' й 0' ''' ~т 1! 1»з — 1<~~ < ть В качестве юго приближения с„будем брать ! =ш!п«1„: Т«, т=1,2, т ! ть»« (31) Такая замена связана с тем, что функция (32), в отяичие от (13), а также соответствующая ей функция р(!), вообще говоря, не будут монотонными (см, примеры 1 — 8). Справедлива Теорема б.
Пусть функция р(с) нвотрицатсльна нрн всех 1, удовлвтворявт условию (15), а С») — со — минимальный корень уравнения (5) в смысло определения 1. Кроме того, пусть функции (р,(с)) удовлвтво ряют условиям (19), а нослсдоватвльности (О,), (т„) — условию (33). Товдп Если выполнены все условия теоремы 5, то, немного видопзменив доказательство этой теоремы, нетрудно установить, что при ! < !» < Т для достаточно больших номеров т ) тс процесс (20) будет заканчиваться выполнением условий (29) и оценки (28), а последовательность (! ), определяемая методом (20), (29) — (31), сходится к числу ш!и(!»; Т').
Таким образом, метод (20), (29) — (31) позволяет определить, принадлежит лн !» отрезку (ес, Т), и в случае !» ш (сэ, Т) поаволяет найти !» с нужной точностью. Для определенил ! ° при условиях (19) может быть также использовав метод деления отрезка пополам. 5. Кратко остановимся на случае, когда функция р(!) иа (4) определяется с помощью функции Ф(п, с) = ЦУ(п) — !( + 5(Р(п), псы Пс, (32) где Е > О, 31 > О, функция Р(п) взята ив (3) при некоторых р, ) 1 (! = 1,..., в). Поскольку !!У(п) — с! — (У(п) — т!! < /! — т(, то, рассуждая так «ке, как при докааательстве теоромы 3, убеждаемся, что функции Ф(п, !), Р(!) из (4), (32) удовлетворяют условиям (14), (!5).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
