Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 7
Текст из файла (страница 7)
Позтону 6(р„) = зпр 6 (У, рп) < Умй шах (из+1 — и,. ). Пусть шах (из+1 — иг ) = иь+ — и . Возьмем 1агап 1агап функцию Уе = Уь(и) = (и — иь(. Это строго унимодальная функция достигает своей нижней гРанн на отРезке [а, Ь) в точке ие=иаеа [иа 1, из+1[, прпчем 6(Уь. р ) = икю — иэ ь Следовательно, гарантированная погреш- ВОСТЬ МстОда р, На КдаССЕ () раВНа 6(рп) = ШаХ (и1+1 — иг 1). Дпя Папу1авап чения оптимального пассивного метода остается выяснить, достигается лн нижняя грань 1п( 6 (рп) = 6„, где Є— множество всех пассивных метоРпюрп дов, и если достигается, то на каком методе р, ги Р .
Оказывается, здесь нужно различать случаи четного и нечетного и. Т е о р е м а 1. Ври всех нечетных и = 2т + 1 (т > 0) существует бесконечно много оптимальных пассивных методов на классе (); наилучшая еорантированная точность пассивных методов Рэ„ю на этом классе равна (Ь вЂ” а)У(пг + 1). Д о к а з а т е л ь с т в о. Возьмем пассивный метод Р„= (о, ..., о„), где пв ом = а+ 1(6 — а)У(т+ 1) (1 = 1, ..., т), а точки огге~ (1 = О, 1, ..., гв) расположены на отрезке [а.
6) произвольно, лишь бы ом ~ < ом < ем+и хиы — ог, ~ < (6 — а))(т+ 1). Очевидно, 6(р„„) =(Ь вЂ” а)/(та+ 1). С другой стороны, для лгобого пассивного метода рч = (иь ..., и ) (и, = а < <и,«...и,<Ь=и„лип=2тл+1) имеем 6(р„)= шах (иг+1— гагкп — ие ) )~ птах [ь — игю, изю — изтл з, ..., и — из, из — а))~ (ь — а)У(гя + 1). Следовательно, методы рп оптимальны и 6 =(Ь вЂ” а)У(я+1). Т е о р е м а 2. Ври всех четных и = 2т (т > 1) оптимального пассивного метода на классе Чг не существует; наилучшая гарантированная точность пассивных методов Рэ„на этом классе равна (Ь вЂ” а)У(та+ 1).
В качестве е-оптимального метода можно взять рк, = (оь .... оч), где огг 1 = а+ 1(Ь вЂ” а) /(та + 1) — з, ом = а+ 1(Ь вЂ” а)/(ел+ 1) + е (1 = 1, ... ..., и, О < е < (Ь вЂ” а)У(2(тл+ 1))). доказательство, Сначала убедимся в том, что 6(рк) > (Ь а)У у(и+ 1) для лтобого пассивного метода р = (иь .", и ) (ио= а < иэ < ... < и < Ь = и гн п = 2т). Обозначим и = а+ (Ь вЂ” а))(т+1). Имеются две возможности: либо иг > й, лиоо из < и. Если и, > й, то 6(Р„) = шах (иг+1 — ие )>и,— а > и — а=(6 — а)У(т+1). Если же и ~ гасан К и, то 6(р„) = шах (иг< — иг ) > и — а.
В самом деле, еслп бы гкгап шах (и;+ — иг 1)~(из — а, то имю — им 1 < из — а (1 = 1, ..., тл) и, хавин 26 метОды минимизАции Функций ОднОЙ Переменной [гл, ! С помощью индукции легко покаэатгч что и-е число Фнбоваччи предста- вимо в виде [~1+ [ге5)" ($ — )/5)"1 1 н 1 2 (3) Испольауя числа Р„, построим и-точечный последовательный метод, который принято называть методом Фибоиаччи. Этот метод относится к классу симметричных методов, описанных в 4 4, и определяется ааданием ва отрезке [а, Ь) точки и~ = а+ (Ь вЂ” а)Р„,/Р .,г или симметричной ей точки иг = а+ Ь вЂ” иг —— а+ (Ь вЂ” а)Г /Р +ь С помощью индукции нетрудно понааать, что такой симметричный метод обладает свойством (4.4) и на Ь-и шаге (Ь ( и), когда проведены вычисления авачепий функции в точках иг, ..., иь, приводит к отрезку локализации минимума [аь, Ьь) длиной Ль = Ьь — аь = (Ь вЂ” а)Р»-ьег!Р еп причем точка йь (аь < иь ( Ьь) с вычисленным значением Х (и„) =* ш1в е (иг) совпадает с одной иэ точек 1 аьаь Ри — ь + (Ь вЂ” а) Ь'и+1' Р и — а+1 l (Ь вЂ” а) „=а„+Ь„-и„, и+1 Ги — ь иь, —— аа+ (ЬЬ вЂ” аа) Р— —— аа и-ь+т ь и — а+1 иа = а„+ (Ьь — аь) à — — аа + и-ь-г;э расположенных ва отрезке [аь, Ьь) симметрично относительно его середины.
г Как видно из (4), при Ь = и — 1 точки и„, и„г совпадают. Это означает, что при Ь = и — 1 первая часть процесса аакаичнвается вычвсаением значения функции в точке и , и определением отрезка вокализации минимума [а» „Ьь г длины Ь г — а г = (Ь вЂ” а)рь~р ->г = 2(Ь вЂ” а)р„ег, причем точка и„= и„г= и„г совпадает с серединой отреака [а„„ Ь,). В ааключение, несколько нарушая симметричность процесса, последнее и-е вычисление аначення мипимизуемой функции ь'(и) проводится в кроме того, иг — а ( иг — а. Сложив ати неравенства, придем к противоречивому неравенству Ь вЂ” а < (т+ 1) (иг — а) < (т+ 1) (й — а) = Ь вЂ” а.
таким образом, при иг < й имеем 6(р„) = птах (иг+ — иг ) = l г ~ 6 (р„), где р„— пассивный метод на отрезье [иь Ь), составленный иэ точек иг, ..., и метода р,. Но и — 1 = 2т — 1 — нечетное число, поэто) му, применяя теорему 1 к отреаку [иг, Ь), имеем 6 (р„) )~ » (Ь вЂ” и )(т. Тогда 6 (р„) = 6 (р„г) (Ь вЂ” и )ут > (Ь вЂ” и)/т = (Ь вЂ” а) ((т+ 1). Тем самым доказано, что 6(рь) ) (Ь вЂ” а))(т+ 1) при всех р„ьв ьн Р,„. С другой стороны, 6(р„,) = (Ь вЂ” а)/(т+ 1)+ е длн всех э (О < е < ( (Ь вЂ” а)/(2(т+ 1)). Следовательно,бе = (Ь вЂ” а)Пт+ 1).
Из теорем 1, 2 вытекает, что предночтнтельнее пользоваться пассивнымп методамп с четным числом и = 2т точек, поскольку в случае и = 2т+ + 1 наилучшая гарантированная точность остается такой же, как и при и =2т. 4. Перейдем к рассмотрению последовательных методов минимизации увнмодальных функций ва [а, Ь]. Здесь нам понадобятся анаменнтые числа Фибоиаччи, которые, как известно [95), определяются соотношениями Р+г=р+г+Г, и=1,2,...; Рг=рг=1. ОБ ОПТИМАЛЬНЫХ МЕТОДАХ 27 точке и„=й, г+е (или и„=й ~ — е), где 0 ( е ( (Ь вЂ” а)/т" +ь и отрезок [а„, Ь ] локализации минимума определлется по формулам а„= = а„„Ь„= йв-~+ е при 1(й ~) (1(й„г+ з) п а, = й ь Ь„= Ь„, при 1(й„,) ) 1(й -г+ в), так что в худшем случае Ь вЂ” а = (Ь вЂ” а)(/тв.„+ е. Описанный метод обозначим через Ф„. Т е о р е и а 3.
При всех и .м 1 онтимального носледовательного метода на классе унимодальнмх у)дикций не существует; наилучшая гарантированная точность последовательных методов на этом классе равна (Ь вЂ” а)( /Р„ьь В качестве е-оптимального метода можно веять метод Фидоначчи Ф„. Доказательство этой теореыы можно найти в [11, 15, 83, 291]. Заметим, что число г" ~(г" +ь вообще говоря, является бесконечной периодической десятичной дробью, поэтому первая точка и, метода Ф„будет вадаваться на ЭВМ приближенно. Во избежание быстрого роста погрешности иэ-за неточности задания первой точки на практике нужно пользоваться модификацией метода Ф, описанной в $4 для симметричных методов в общем случае.
Следует подчеркнуть, что метод Ф„дли своей реалиаации требует, чтобы число и вычислений значений минимизируемой функции было задано эаранее — выбор первой точки в этом методе невозможен без анания и. В тех случаях, когда число и по каким-либо причинам не может быть задано заранее, можно применять метод аолотого сечения, ие требующий для своей реализации априорного значения и. Для сравнения вспомним, что методом аолотого сечения за и вычислений значений функции мы получали отреаок [а„, Ь„] локалиаации минимума длины ܄— а = ((75 — 1)/2)" ЦЬ вЂ” а) = (2((75+ 1))" '(Ь вЂ” а). С учетом формулы г" +г — (() 5+ 1)/2)в+'(75, вытекающей из (3) при больвпих и, для метода Ф„получаем отрезок локализации минимума, длина которого близка к (Ь вЂ” а)(у,+г яг (2Д75+ 1))"+'(Ь вЂ” а)/)/О.
Отсгода следует, что метод золотого сечения хуже метода Ф„при больших и всего в ((75+1)/2)г(75 = 11708... раз, т. е. на классе унимодальных функций метод золотого сечения близок к оптимальным методам. Интересно также заметить, что гн-г 3 — [I5, гн [/5 — 1 Иш р== г 2 )[ш к „„г„+, а ш' я+Ь т.
е. при достаточно больших и начальные точки иь из ыетодов Фибоначчи и золотого сечения практически совпадагот. Упражнения. 1. Найти гарантированную на классе унимодальных функций точность последовательного (илп пассивного) и-точечного метода р„если в качестве погрешности метода р кри минимизации функции 1 = = 1(и) принята величина А (1, р„) = ] 1в — 1 [ин) ). 2. Сравнить оптимальные и с-оптимальные пассивные методы на классе унимодальных функций с методом деления отрезка пополам.
3. Указать все точки метода Ф на отрезке [О, 1] при н = 2, 3, 4, 5. 4. Нриыенить метод Фг к функциям 1(и) = и, 1(и) = ]и — 1[ на отрезке [О, 2]. 5. Найти наименьшее и, для которого точность метода золотого сечения хуже точности метода Фибоначчи з 2 рава. 6. Доказать, что число Фпбоначчи г" является ближайшим целым числом к ((1+ 75)/2)в(75.
7. Доказатгь что решение уравнения (4И) представиыо в виде А = ( — 1)вг" -йг+ ( — 1)" '/т -г5~ (и = 3, 4, ...). Отсюда вывести аакон изменения погрешности величины Аш если Аь Аз заданы неточно. 8. Доказать, что последовательность (Р,„(гг ьД сходится к т, = = (75 — 1)(2 монотонно возрастая, а [гг г/г"г ) сходится к т~ монотонно убывая. 28 методы ьп1нимизацпи ФункциЙ Одной пегеэ1еннои (гл, 1 9. Используя утверждеппя упражнений 7, 8, доказать, что метод золотого сечения является единственным симметричным методом, удовлет. воряющим условию (4.4) прп всех и = 1, 2, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
