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