Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 13
Текст из файла (страница 13)
Обозначим через и„точку пересечения касательных у(и, а,) и у(и, Ь„,). Испо, что а„, <и„<Ь„,. Вычислим 1'(и„). Если 1'(и )=О, то и„~(Уч — задача решена, итерации на этом заканчиваются. Если У'(и„)за О, то положим (а„г, У'(и„)) О, )и„, (и„, У' (и„) < О, " )Ьь По построению 1'(а„)<0, У'(Ь„))0, и согласно теореме 8.6 УУ„~(а, Ь). Индуктивное описание метода закончено. Из геометрических построений нетрудно усмотреть (см. рис. 1.5), что этот метод совпадает с описанным выше методом 4е мвтоцы мпнимнзхппп вхгггсдгги оцнон пвгвмвнпои ггл, г касательных, в котором за начальную точку берется и, = а; строгое доказательство этого факта приводится в п.
5. В то же время приведенная схема метода более проста и удобна для реализации на ЭВМ; на каждом шаге метода здесь достаточно хранить в памяти ЭВМ величины а„, Ь, 1(а„), 1(Ь„), 1'(а ), 1'(Ь„). Нетрудно выписать явное вырангепие для точки и в„определяемой условием д(и, а )=у(и, Ь ) пересечения касательных в точках а„, Ь„при 1'(а„) < О, 1'(Ь„)) О: у (а„) — Х (Ь ) + Ь Х'(Ь ) — аьу' (а,) и„.гг .-- ...>г .-1 (и) 3.
Поскольку ломаная из отрезков касательных аппраксимирует функцию 1(и), вообще говоря, лучше, чем ломаные из 4 6, то следует ожидать, что метод касательных для выпуклых функций сходится быстрее метода ломаных из $ 6. Исследуем снорость сходимости метода касательных, считая минимизируемую функцию дважды дифференцируемой. Теорема 2. Пусть функцггя 1(и) дважды непрерывно дифференцируема на [а, Ь), !о1 1" (и) ) О, и — точка минимума иебьь) 1(и) на [а, Ь].
Пусть последовательность (и,1 получена методом касательных при и, =а по схеме (4), (5), а, =а, Ь, = Ь, причем и„чьиа (п =- О, 1, ...). Тогда для лгобого числа е) О существует номер дг = дг(е) такой, что [и„— и. )(((1+ е),2)' ' (Ьк — ак), п)ггг. (6) Доказательство. Из теоремы 8.9 следует выпуклость функции 1(и) на [а, Ь). Крогге того, так как 1'(и) строго возрастает, то множество Ь а состоит из единственной точки ив. Тогда из теоремы ! имеем !пп и„=- ив. Поскольку [а„гп Ь„.„) г= [а„, Ь„) п и =1, 2, ...), то последовательность (а„1 монотонно возрастает, а (Ь.) — мояотонно убывает, причем в„( ие ( Ь„(п = 1, 2,, ). Покангем, что 1ппа„=-1пп Ь„=- и . а п В силу (4) либо (а„1, либо (Ь„1 является подпоследовательностью последовательности (и„) и сходится к ие.
Пусть для определенности !пп а„ = и„. Допустим, что (Ь„) пе сходится к и . Тогда согласно (4) последовательность (Ь„1 не может быть подпоследовательностыо для (и„), т. е. найдется номер пс ~ 1 такой, что Ьв = Ь„„ .гри всех и ) и,. При и — из (5) получим 1(и„) = 1 (Ь ) + 1'(Ь„) (ив — Ь„). В силу теоремы 8.4 это возможно только тогда, когда 1(и)=1(Ь„) + 1'(Ь„)(и — Ь„) (ив(и(Ь„).
Отсюда 1'(Ь„) = 1'(ие) = О, что противоречит условию 1'(Ь, ))О. Тем самым доказано, что обе последовательности (а„), (Ь„1 сходятся к ие. мктод кхсатвльных ь з[ Из представления (5) для точки и„т, с помощью формулы Тейлора имеем / (а„) — х (ь„,) — у' (ь„) (а„— ь„) [ /" ($ ) '( )-'( ) ' ( )'"" /(Ь„) — у(а ) — /'(а„)(܄— а„) [ /" (Ч„) ܄— и„т,— ", "," " " —, „"(܄— а„), где $, т[, р„— некоторые точки из отрезка [а„, Ь ).
Отсюда получаем, что Ь +, — а„+, ~ шах(и„з, — а„; ܄— и„~,) ( д„(܄— а„)/2, где д =шах(/ Я )/У (р ); /" (ц„)/У'(р„)). Поскольку последовательности ($„), (т[„), (р„) вместе с (а„), (Ь„) стремятся к из, то в силу непрерывности функции / (и) и условия (п1 l" (и)) ие[а,ь! ) О имеем Пш д„= 1. Следовательяо, для любого е > О найдется помер У= У(е) такой, что д„~ 1+ в при всех п >Дт. Тогда Ь„ь, — а„„,( д(܄— — а„) (и~5[), где [(=(1+е)/2. Отсюда ܄— а„~о в(Ьв — а„) (и ~ Ж). Следовательно, (и„— и,„)((܄— а,)(д" ~(Ьл — ал), п)Х 4. Оценка (6) означает, что метод касательных сходится со скоростью, не меньшей скорости сходимости геометрической прогрессии со знаменателем д =(1+ е)/2 = 1/2.
Конечно, существуют выпуклые функции, для которых этот метод будет сходиться гораздо быстрее (возможно, например, что точна минимума найдется за конечное число шагов). Однако нетрудно привести пример, показывающип, что на классе дважды непрерывно дифференцируемых функций оценка (6) по порядку не может быть улучшена. Пример 1. Пусть У(и)=и'( — 1~и(2). С помощью формулы (5) легко проверить, что касательные к параболе в точках а„, Ь пересекаются в точке и„т, =(а„+ Ь„)/2. Возьмем и, =а, = = — 1, и, = Ь, = 2.
Тогда и, = 1/2. С помощью индукции нетрудно показать, что а = — 1/2" ', Ь„= 1/2" ', и„+, =1/2" при нечетных п и а„= — 1/2" ', Ь„= 1/2" ', и„т, = — 1/2 при четных п. Отсюда получается точная оценка (и, — из ) = ~ и, ) = 1/2" ', в то время как, используя методику вьзвода оценки (5), имеем (ив — из~(~ (܄— а„= 3/2" ' (и) 1). Таким образом, из примера 1 следует, что метод касательных на классе гладних выпуклых функций не лучше метода деления отрезка пополам.
Более того, для этого класса функций нетрудно предложить вариант метода деления отрезка пополам, требующий лишь вычисления значений производных мияимизируемой функции. 50 ыГТОды ьг1пчггыизлцнн Функций ОднОЙ пкгю|кнноя (Гл. з А именно, положим и, =а, = а, и, = Ь, = Ь, вычислим значения 1'(а,)=1'(а+0), 1'(Ь,)=1 (Ь вЂ” 0).
Коли 1'(а,)>0 или 1'(6,) = О, то по теореме 8.5 имеем аш [У или 6 я(/а — задача решена. Поэтому пусть 1'(и,) < О, 1'(6,) > О. Тогда (Уа с (а„Ь,). Пусть отрезок [а„н 6„,] (и > 2) уже построен, причем 1'(а„,) < < О, 1'(6„,) > О, так что (lа ~ (аи „Ь„г). )Толожим п„=(а„, + + Ь„,) 2 и вычислим 1'(и ). Если 1'(и ) = О, то ин ен Ь в — задача решена.
Если 1 (и„)т'= О, то определим точки а„, Ь„по формулам (4), приняв з пих п„=(а„, + 6„,)/2. По построению 1'(а„) < О, 1'(6„) > О, и согласно теореме 8.0 Па с (ан, Ь„). Кромо тот:, ясно, что 6„— а„=(6„,— п,„,)12 =(Ь,— а,)/2" ', и= [, 2, ... Описанный метод деления отрезка пополам выгоднее применять прп минимизации тех гладких выпуклых функций, у которых зпачешгя производных вычисляются проще, чем значения функции. Кслп же значения и функции, и ее производных вычисляются достаточно просто, то метод касательных может оказаться предпочтительнее — хотя, как мы выше убедились, метод касательных па классе гладких выпуклых функций в целом не лучше метода деления отрезка пополам, по в то же время нетрудно привести примеры таких вьгпуклых функций, для которых метод касательных сходится гораздо быстрее описазгного метода деления отрезка пополам.
5. Метод касательных можно описать и без требоваппя днффсренцнруемостп выпуклоп функции, используя лишь односторонпне пронзнодные во внутренних точкнх отрезна [а. Ь) — сун~ествованно таких производных доказано в т<ореме 8.2. '1тобы гзраптнровать непустоту мновгоства (Уч, потребуем еще, позы )пп 1 (и) = У (а), Иш .У (и) =- 1(Ь).
е ано и ~ — е Положим па= а~ —— а+6. п~ = Ь~ = Ь вЂ” т, где 6, т — достаточно малые поло'квтельные числа: если 1'(а+О) нлн У'(Ь вЂ” О) конечны, то здесь можно взять 6=0 влп у=о соответственно. Вычислим У'(аг+О), У'(Ь| — О). Можеьг считать, что 1'(аг+О) < О, У'(Ь| — О) >О, нбо з протнвпом случае согласно теоРеме 8.6 либо (Уч О [а, а,)чь 8, лноо Па О [Ьг, Ь] чь И вЂ” в обоих слУчаЯх точка нз (Уа находятся с гребу<мой точностью б влн т, н задача решена.
Абсцпссу точкп пересечения касательных Л(и, а~) = 1(а~)+ У'(а~+ О) Х Х (и — а~) н д(и, Ь,) = У(Ь,) + У'(Ь| — О) (и — (и) обозначим через ит. Нетрудно видеть, что точка и~ = Ь| доставляет минимум функция ре(и) = = а(и, ие), а в точке из достнгается мпгюньгум функцпп р>(и) = шах(ре(и); у(и, и,)) 'на [аь Ь~) ° прячем а~ < из < Ьь а (и,а), ива[а,и[, уз (и] .—. д(и, Ь ), и ел [и, Ь [, так что па [аь ит) функцня р~(и) строго убывает, а на [иь ЬΠ— строго возрастает (рве.
Еб). Сделаем индуктивное предположение. Пусть определены точки ие, иь ..., иа ~ (и > 2), найден отрезок [а ь Ь Д такой, что 1'(а ~+ О) < < О, У'(Ь ~ — О)> О, причем а ь Ь ~ совпадают с одной нз точек ие, иь ..., ич ь Пусть и — точка пересечения касательных я(и, а ~) = = 1(а„~) + У'(а,, + О) (и — а ~) н я(и, Ь ~) = 1(Ь ~) + 1(Ь„~ — 0)Х 31ЯТОД КАСАТНЛЬНЫХ Ь Е1 5( Х (и — Ь„>), а функции р,,(и) = шах(р„з(и)1,(и, и„,)) такова, что да †( у[и,аи ), иШ [»о, »„], (7) — У(и, Ьа 1), [»н, Ьн,), р„-~(и) на [аи и„] строго убывает, а на [» . Ь|] — строго возрастает: это значит, что и — точка мшшмума р„~(и) па [аи Ь|]. Вычислим У'(и„+ О), »» а+У=а»г ц 1 у 11 Рпс.
Вб р и (и), ие [а, Ь ]', ~»~, »„], р» (и) = д(и, и„), и~= ~»~, и„], (9) Р где ии, иа — абсциссы точек пересечении соотвотствонпо касательных у(и, и ~) и д(и, и„), у(и, Ь ~) и 8(и, и„). Дадим строгое доказательство форт1улы (9]. Из теоремы 84 следует, что у(и, иг) < У(и) при всех и ш [аь ЬД и 1 = = О, (, ..., поэтому р,(и) < 1(и). В частности, р„,(» ) =. 1(и,]. Допустим, что р ~(и ) = 1(и ). В силу (7) это значит, что точка (и„, 1(и„)) лежит на касательных а(и. а >), а(и, Ь, ~). Согласно теореме 8.4 тогда У(и) = р„1(и] при и ~в [а ь Ь„,], Отсюда вмеен 1'(и — 0) = д'(а„, »„1) = 1'(а„~ + 0) ( О, У'(и + 0) = д'(», Ь„,) = У'(Ь ~ — 0) ) О, что противоречит (8).
Такпп образом, при выполнении (8) нозмогкен лишь случай р 1(и„) ( 1(и ). 1'(и — 0). Гслп 1'(и„+ 0) ) О, 1'(и — 0) О, то по теореме 8,5 имепг »и ш УУа, и задача решена — итерации на этом заканчнваютсн. Поэтому пусть выполнено одно нз условий 1'(и + 0) < О, У'(и — 0) ) О. (8) Положим а = а ь Ь„= и, д(и, и„) = У(и„) + У'(и„— 0) (и — и ) прп 1'(и„— 0) ) 0 (рнс. (.7, а) и а„=и„, Ь„= Ь„и д(и, и„) = У(и„) + +1'(и„+О)(и — и ) при 1'(и„+0) (О (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
