Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 15
Текст из файла (страница 15)
Возьмем отрезки (и»п»1 1, и„пто] (й = 1, 2, ...) и множество )т' (оь), введенные при доказательстве теоремы 1. Если оказалось, что ип»!Ы 1< ов < оець) (й= 1, 2, ...), то с учетом (15) в качестве искомых ПадПОСЛЕдазатЕЛЬНОСтсй МОЖНО ВЗятЬ (им»Ю-1] И (иеиз»]. ОСтаЕтСя раССМОтреть случаи, когда, начиная с какого-либо г-го шага, ь будет совпадать с ОДНИМ Иа КОНЦОВ ОтрЕЗКа (и»ПЬ» — 1, иэи»»].
пусть сначала оь — — и„,!ю (й) )г). тогда подпоследовательность (иэнь») в силу (15) сходится к ое справа. Рассмотрим подпоследовательность (иэпь»-1) при й ш Х (ов). С помощью формулы (16) при 1 = т(й) — 1 6 »е! Л»ИТОД НОНСКА ГЛОБАЛЬНОГО Л»НННМУМА 57 и соотношений (14), (17) имеем Х(о ) — Х(и „) )2 д»,(о — и (,),) 1+ а ( 'т т(Л) — 2) ) = Пл (т(й) — 1) +41 (о~)~< Па (т (й)) +41 (о ),.О й л оо й»и»У(о ) Отсюда с учетом (8], (10) получим, что подпослодоватсльность (и„,л, 2) сходится к о слева. Пусть теперь ое = ит(Ю (й > г).
Тогда (и „ ) сходится к о сл ва. С другой стороны, из (18) при » = т(!») + 1 и из (14), (17) следует, то Х (и ел) — Х (о„) л 2 =- Н (т(й) +1) + 41 (от) ~ (Вь(т(!»)) + 41 (ое)-лО, й-л со, й»и )у(ое). Ото»ода, учитывая (8), (10), имеем (и»л»э») — но при /»-»-оо (йш»у(оэ)). Искомые подпоследовательвости для предельных точек ое (а < ое <Ь) построены. Заметим, что если оя = а, то в силу (15) (и»»л») сходится к о справа, а если о = Ь, то (и„ д л) сходится к о слева. Перенумерусм точки О» (! = О, 1, ..., т) локального экстремума функции 1(и) на [а, Ь] в порядке возрастания: Ое = а < О» « ...
О, = Ь. Тогда на наждом отрезке [О», 0»э»] функция 1(и) строго монотонна, причем при переходе через внутренную точку О» направление монотонности меняется. Пусть ое — произвольная предельная точка (ол). По доказанному существуют подпоследовательности, сходящиеся к оя слева и справа (при оэ = а и оэ =- Ь достаточно односторопной сходимости). Отсюда и из (13) следует, что при переходе через точку оя функция 1(и) меняет направление монотонности, причем 1(и) вблизи от оэ слева строго убывает, справа строго возрастает.
Следовательно, оэ совпадает с одной из точек О» и представляет собой точку локального минимума 1(и) со значонием Х(оэ) = = !!ш Х (оа). л Из теорем 1, 2 и 1Д непосредственно вытекает С л е д с т в н е 1. Пусть функция 1(и) на отрегке [о, Ь] удовлетворяет условию (11), множество П = [и: и»н (о, Ь ],Х (и) = Х = 1п1 Х (о)] соое !а,л! стоит иг конечного числа точек и вне Пя других локальных минимумов 1(и) на [а, Ь] не имеет.
Тогда последовательность (ол), полученная л»стадом (!) — (6), будет минимиэирХ»ю»цей для 1(и) на [а, Ь] и !пп р (он, Пя) = О. Сходимость мотода (1) — (6) можно доказать и без требовании конечности множества точек локального минимума функции. Т с о р е и а 3. Пусть функция 1(и) на отреэке [а, Ь] удовлетворяе~ условию (11); кроме того, пусть е методе (!) — (6), на»и»»ая с некоторой итерации, дл > 21, Тогда последовательность (ол), полученная этим методом, таяова, что: 1) !пп Х(о,) =Х„!пп Р(о„, Ья) =0; ь ь 2) при !п1 д >28 для некоторого йо > 1 все точни иэ П» будут прел>ае дельными точками (ол). Д он аз а те л ь с та о.
Прежде всего ааметим, что случай дл > 21 согласно (2) соотвотствуот парамотрам ч > 21 при 1л = 0 к рл > 21ПХл при Ел > О. Поскольну если йл > О, то пз 1 < Ь, < 1 следует 1 < 610ь < ~ (1/ьа < со прн всех й > йе, и поэтому ясно, '»то пие»отса возл»ожпо"е стп удовлетворить всем условиям (6), сохраняя неравенства йл > 21.
58 метОДьт ъппрпмпзлцпп ФУППЦПЙ ОДпой перев!Генной !Гл. ! Возьмем произвольную точку из ш (>з. ПУсть им»> 1( из <~ и„О,> (й =— = 1, 2, ...). Поскольку Х(и„1.>)+ Х(ица>, )< ! (и,( > — и,р,>,) +2! (пв) то ич (3) с учетом условия д» ) 25 имеем В, (т (й)) ) (И» — 2!.)(итп,> — итп,> ) — 4.! (и ) ) — 4Х (и ], !г= 1, 2, ... (19) Далее, пусть ьв — пакли-либо продольная точка последовательности (о»). Назымом отрезки [и, ~»! — !, и, !»>] (й = 1, 2, ...) и мнол!сство д> (ов), введенные при доказательстве т!орсмы 1 длн точки о .
Поскольку Х(и„)(~ (Х (пз), то иа (14) при ! = т(!.) н из (19) имеем Л»(т(й))) В»(т(й)))~ ) — 4,! (и ) ) — 4Х (гз] (й зиЛ (о„)). Отсюда с учетом равенства (!7) имеем 1!ш В» (т(й]) =-1пп Л»(т(!.)) — — 4Х(и ) = — 4Х (о ), й ш Дг (и ), (20) »-,ю » т. е. Х (ив )= — Х (ов). В силу теоремы ! тогда 1пп Х(г ) = — Х (о ) = Х (ив], а » пз теоремы 1.1 получим !пп р(о>п Ьгв) = О. Наконец, прп зп! д» ) 25 из » " '"о (19), (20] следует 1пп (ит» — и„> ) — — О, и поатопу в качестве под»мю,»ык(г.> ™ последовательности, сходящейся к ив, мо>кно взять (и.а!) или (и !»1-Д.
Сравним метод (1) — (6) с методом равномерного перебора (7,2) на классе функций 4>(5), удовлетворя!ощих на [а, Ь] условию (11) с одное и той жо постопнной й, Согласно теореме 7Н для обеспечения точности (2!) пп(п Х (ит!) — Х ( з иа классе ГХ(!.) перебор па [а, Ь] нужно осуществить по точкам мг = а+ + (> — 1/2)й (! = 1, 2, ...) с шагом 2е/Х. Теорема 4. Вугть !(и) шО(!.), а [с!, ЯС(и: иш(а, Ь), Х(и))Х„+ + 7], где "! ) Π— б!гкгироватгное число, Тогда на [и, Я число поисковых точек метода (!) — (6), реализованного при д» = 2Х (й ) 1), ио крайней мере в 7/(5е) рез меньше числа поисковых точек метода равномерного перебора (7.2); здесь число е ) О взято из (21), 5е ( 7.
Доказательство. ПУсть ившбтв,и(»> <ив(!ге/»>(й=-1,2, ). Тогда из (19) следует, что В»(т(й))~ )— 4Х(ив) = — 4Х„. Далее, для л!обого отрезка [иг-1, и!] ел [и, Я (г = г(й)] справедливо неравопство Х (и!) + Х(и! ) ~ )2Хв+ 27. Поэтому ич (3) при д» = 26 получая Л (!) < — 4Х вЂ” 47+ 57, (и! — и! !)/2. Отсюда ясно, что если и! — и! ! ( < 87/(55), то Л»(т(й] ) — В»(!(й) ) ) 47 — 5/Диз — иг,)/2 ) 0 и на й-и шаге внутри [и! !, иг] новая поисковая точка не появится. Следовательно, для появления позой точки в [и! !, иг] па !г-м шаге необходимо, чтобы и!в — и! ! ) 8"!/(5!.).
Однако тогда появление новой поисковой точки о» в (иг ь иг] приведет к дву»! новым отреакам [иг !, о»] и [г», иД, длина которых согласно (9] прп г!» = 2А, р» = 25/А» ) 2 = р оценивается снизу величиной (и! — иг,)/ 4 ) 27/(55). Ото влачит, что позавпсимо от номера и!агав расстояние между точками иг „ иггн [я, Я удовлотворнет условию иг — и! ! ) 27/(58), и следовательпо, число поисковых точек, попавших на [а, Я при примепеаии метода (1) †(6), не молзет превышать числа 5ь(р — а)/(27).
Остается заметить, что число точок метода равномерного перебора па [а, Я, необходимое для обеспечения точности в смысле неравенства (21), оценивается числом (6 — и)/й ) (и — ЯЬ/(2е). Сравнивая полученные числа, убеждаемся в справодливости теоремы. ее мвтоды миппмпзлцпп фтнкцпи однои пвгвмзннои ~гл.1 Перейдем к описанию одного из вариантов метода парабол для минимизации функции У(и), упимодальной на отрезке (а, Ь]. Пусть Ь > 0 — некоторый начальный птаг, 2Ь ( Ь вЂ” а, а и, ж ж(а, Ь] — начальная точка. Поиск минимума начинаем с вычисления значений У(ио), У(и, + Ь). Если окажется, что У(и, + Ь) ( ~У(и,), то продолжаем вычислять значения У(и,+Ь 2' ') (1= =2, 3, ...) (рис.
Е8); если же Х(и,+Ь)) У(и,), то меняем направление поиска: переобозначаем и,+ Ь через и, и далее вычисляем значения У(и,— Ь 2' ') (1=2, 3, ...) (рис. 1.9). Перед 'е =./а. а и-и и б Ф и Рис. 1.8 а%9 "г Рис. 1.9 вычислением зяачения функции в очередной новой точке и;= = и, + Ь 2' ' (или соответственно и< = и, — Ь . 2' ') прежде всего выясняем, будет ли и;ж [а, Ь]. Если и;ю1а, Ь], то вычисляем значение У(и,) и проверяем, образуют ли последние три точки и, „ и; о и~ выпуклую тройку для 1(и) или нет. В том случае, когда тройка и; и и; „и; невыпукла, переходим к следующей точке иы, и т.
д. Этот процесс закончится отыскиванием такого номера и~1, что: з гц ывтод пАРАБОл 61 1) либо три точки и,, и„„и„образуют выпуклую тройку для У(и) — тогда через три точки (иь У(и,)) (1= и — 2, п — 1, п) проводим параболу и находим точку и ее минимума на К; согласно (3) ю ж(и„„и„) (см. рис. 1.8, и= 4); 2) либо пи одна тройка и~ м и; „ и, при ~ = 2, ..., п не будет выпуклой, а и„„, Ф(а, Ь) — тогда полагаем и=а или ю= Ь в зависимости от того, какой из концов отрезка (а, Ь] блин1е всего к точке и„т, (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
