Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

Скачать файл (13,51Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 193

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

S 5]

Метод ломаных

Для сравнения с методами Фибоначчи для решения задач А и Б заметим, что при больших п число

Поэтому при достаточно больших п погрешность, получаемая при применении метода золотого сечения к решению задач А и Б, боль ше соответствующей погрешности метода Фибоначчи всего в

	Л 1 + .^ _ У _ ! _ ~					1,1708
	Ч		2	)	/ 5"
раз. Отношение	погрешности метода золотого сечения к погрешности
метода деления отрезка		пополам при решении задачи А равно
	2 _	2		У У 2 ^ (0,87		. . . ) " У 2 .
	/ 5	+	1	)	очень больших п преимущество ме
Отсюда видно,	что уже при не				очень больших п преимущество ме

тода золотого сечения становится ощутимым.

На практике иногда сочетают метод золотого сечения с мето дом Фибоначчи: на первой стадии поиска минимума применяют ме тод золотого сечения, затем, задавшись некоторым натуральным числом п, переходят к плану Фибоначчи Фп и на этом заканчива

ют поиск.			~
Упражнение. Пусть заданы /п чисел: а\,			а2, ..., ащ — и пусть
известно, что минимум minа и = а р достигается			при каком-то един-
1<А<т		... > а р, ap< a p+i<^ . .. ^ 0+.
ственном р, 1 ^ . р ^ т , причем а \ ^ а г^		... > а р, ap< a p+i<^ . .. ^ 0+.
Как организовать п выборок из	чисел	а\, а-2,	..., a,n, чтобы ар =
= minaft найти как можно точнее?	Существует ли наилучшая стра-

тегия определения р?

§ 9. МЕТОД ЛОМАНЫХ

N/B этом параграфе рассмотрим один простой метод минимиза ции функций /(«), удовлетворяющих условию Липшица на отрез ке [а, Ь\ позволяющий найти минимум с любой наперед заданной точностью [85, 182]. Напомним

О п р е д е л е н и е 1-. Говорят, что функция J (и) удовлетворяет условию Липшица на отрезке [а, Ь], если существует такая по

стоянная L ;> 0, что \|/(гг)— J(v) \|^L\|w— v\ при любых и, v^[a,			Ь].
Пользуясь формулой конечных	приращений Лагранжа,		не
трудно показать, что непрерывная	на отрезке функция J	(и) с	ку
сочно-непрерывной производной удовлетворяет условию		Липшица
с константой L = su p [/'(«) \|.

2 *

МИНИМИЗАЦИЯ

ФУНКЦИЙ

ОДНОЙ

ПЕРЕМЕННОЙ

[Гл. 1

Зафиксируем произвольную точку v отрезка [а, Ъ] и определим

функцию К{и,

и )= / ( о ) —L\u— v\ переменной и, а ^ и ^ Ь . Нетруд

но видеть,

что

функция К(и, v)

кусочно-линейна,

K{v, v ) = J ( v ) ,

К(и, v )^ .J(u )

при всех и, а ^ .и ^ Ь .

Опишем

метод

ломаных.

качестве

начального

при

ближения может быть взята любая точка и0 £

[а,

6 ]. Далее

состав

ляем функцию К {и,

«„) =

</(«„)— L |и — и01 и следующую

точку

их

определяем

из

условия min /С(и,

и0) = К (и1,

и0)

(очевидно,

их — а

или и1 = Ь).

Зная иь

а<и< 6

К {и, их), составляем новую функ

определяем

цию Рх(м) =

max К, (и, ис) и находим и.2 из условия Р х (и2) — min Р х(ц)

i = 0 , 1

.. ■,

и „ (я > 1)

уже

”

Тогда

(рис. 4). Пусть точки «0, их,

известны.

составим функцию

Рп (и) =

max К (и, и()

max {/([(ы, «„),

Рп~i («)}

( X i < n

(примем Р0 (и) = К(и, и0)) и следующую точку ип+1

найдем из усло

вия Рп (u„+i) =

min Рп(и)

и т.

д.

Если

min Рп (и) достигается

a<u< 6

a<u<b

нескольких точках,

то

каче

стве нп_)_1 берем

любую

.из

них.

Для доказательства сходи

мости этого метода нам пона

добятся

следующие

свойства

Рп(и), п = 0 ,

2 ,...: 1 )

Р„(и ) —

непрерывная

кусочно-линейная

функция и график ее представ

ляет

собой

ломаную линию,

состоящую

из

отрезков пря

мых

с угловым

наклоном

или — L\

2 ) P n {u).^.Pn+i(u),

Р п ( и ) ^ / ( и )

при

любых

и, а^.и<С.Ь

и любых

я = 0 ,

2 , . . . ;

3) Рп ( щ )= Ц щ )

при

всех

г= 0 , 1

ибо

1 ( щ ) ~

ДВС -график функции К(и.и ),

— К (Hi, Ui'j ^^Рп(^г)

J (^i) t

А;В,-график К (u ,u j, АВС.В,~график

4) Pn (u)

удовлетворяет

усло

р,(и}, АгВг Сг -граф ик К(и,иг),АоОгВг Вг8,-

граф и к Рг (и)

вию

Липшица

на

отрезке

Р и с.

[а, 6 ]

с константой L.

Т е о р е м а

Построенная

выше последовательность

{«„} та

кова, что:

lim

Pn(un+i) = J * =

in iJ(и) = J (и*)\

любая

пре-

п-»оо

a<u<6

S 5]

Метод ломаных

дельная точка ы последовательности {ип} является точкой мини мума функции /(и); 3) если J (и) достигает своего минимума на отрезке [а, b] в единственной точке и*, то вся последовательность {ип} сходится к и*.

Д о к а з а т е л ь с т в о .

Прежде всего заметим, что последователь

ность Р п («„-и)

монотонно возрастает и ограничена сверху;

р п- 1 («„) = minP„_i (ы)’<

Рп-

1 (ы„+1) <

Рп (ип+1),

аКи^Ь

Рп(«и-О =

min Рп (и) < Рп (а*) < J

(и*).

Следовательно,

существует

limP„r(«n+i) = P*k<

У*.

Покажем,

что

/1—>оо

Р* = J*. Пусть

и — произвольная предельная

точка последовательно

сти

{«„}. Тогда

существует подпоследовательность^{«nJ , сходящая к

и,

причем можем

считать,

что

л2< . . .

<C[nk< n k+1 <

) . . . .

Так

как

О < J

(«;) — Рп(“п+О =

р п (Щ) — Рп(«п+ 0 <

L I

— a„+i|

при

любом

/г

любых

0 <Ci<£n,

то

полагая

здесь

i =

nk—\,

n =

nk — \,

получим

0 < J (aBfc_i) — PBjk_, (aftJt) <

L \ua^ x— « „ J.

От

сюда при k -+ oo имеем

J* <

У (Д) =

lim / («„*_,) =

lim Рп,_ ! («„.) = P * < J*,

*-»oo

ft-»oo

t .

lim P„ (u„+ i) =

J* = J

(u).

П—>оо

Первое и второе утверждения теоремы доказаны. Третье утверждение теоремы теперь является простым следствием первых двух. А

Описанный метод ломаных имеет ряд достоинств. Он позволя ет получить приближенное значение точки абсолютного минимума функции J (и) на [а, Ь] и сходится при любом выборе начальной точки «о, лишь бы функция J (и) удовлетворяла условию Липшица. Метод ломаных не требует существования производной J'(u) во всех точках отрезка, наличия строгой квазивыпуклости /(«), кро ме того, функция J (и) может иметь сколько угодно локальных и абсолютных минимумов на отрезке [а, Ь]. Если константа Липшица L функции J (и) известна, то метод ломаных прост и удобен для использования на ЭВМ. На каждом шаге этого метода требуется решить простую задачу минимизации кусочно-линейной функции Р п (и), сводящейся к перебору известных вершин ломаной Рп (и), причем перебор здесь существенно упрощается, ибо ломаная Рп (ц) отличается от Р п-\{и) не более чем двумя новыми вершинами.

МИНИМИЗАЦИЯ ФУНКЦИИ о д н о й ПЕРЕМЕННОЙ

[ Г л. 1

Нетрудно модифицировать описанный метод ломаных так, чтобы последовательность Р п (ип+\) строго монотонно возрастала.

В работе [83] показано, что метод ломаных близок к опти мальным методам поиска минимума на классе функций, удовлет воряющих условию Липшица. Оптимальная стратегия поиска ми нимума строго квазивыпуклых функций, удовлетворяющих усло вию Липшица, рассмотрена в работе [241].

§ 10. ВЫПУКЛЫЕ ФУНКЦИИ. МЕТОД КАСАТЕЛЬНЫХ

. Для минимизации некоторых классов функций можно исполь зовать более эффективные варианты метода ломаных. Опишем одну модификацию метода ломаных, пригодную для поиска мини мума выпуклых функций, когда в качестве звеньев ломаных бе


рутся отрезки касательных к графику функции.
О п р е д е л е н и е	1,- Функция			J{u ), определенная		на	отрезке
а ^ .и ^ Ь , называется выпуклой,			если
J (аи +	[ 1 — а] и) <		а/ (и) -f (1 — а) J (v)				(1)
при всех и, v£ [а, b]	и всех а, 0 <			а < I.
Когда а пробегает отрезок [0,				1], точки (а и + (1 — а) и,			a/(u)-f-
+ (1— a ) J ( v ) ) на плоскости		переменных (и, J)			пробегают хорду АВ,
соединяющую точки	Л = .(а ,	J(u ))		и B — (v,	J (и))	на	графике

функции. Поэтому неравенство (1) имеет простой геометрический смысл: график выпуклой функции на любом отрезке [и, o ] s [ a , 6 ] находится ниже хорды, соединяющей точки графика функции на концах отрезка [м, и]. Примерами функций, выпуклых на любом отрезке из области своего определения, могут служить следующие

элементарные	функции:	и2, и, — и,	\|«\|, еи, е~г\ — lnw.	Функция
sinw выпукла	на отрезке	—	и невыпукла при	О ^ и ^ л .

Более подробное изучение выпуклых функций отложим до сле дующей главы, а здесь отметим лишь некоторые свойства выпук

лых	функций,	необходимые	для описания	метода касательных
(см. также упражнения в конце настоящего параграфа).
	Т е о р е м а	1. Пусть функция I(и ) выпукла и непрерывно диф
ференцируема на отрезке [р,			Ь). Тогда: 1) справедливо.неравенство
		/ (и) > J	(v) -f J' (v) (и — v)	(2)
при	всех и, i>e[a, b] (иначе		говоря, график	гладкой выпуклой

функции лежит выше графика	любой ее касательной); 2 ) произ
водная /'(«) не убывает на [а ,	Ь]\ 3) J (и) удовлетворяет на [а, Ь]
условию Липшица с константой	L = m a x {\| / '(a + 0 ) \|, \|J'(b —0)\|}.

§ щ	Выпуклые	функции. Метод	касательных	39
	Д о к а з а т е л ь с т в о .	Перепишем	неравенство	(1) в виде

J (v-\-a(u— v ) ) —J(v) ^ . a [ J (и) — /(»)]. К левой части этого неравен ства применим формулу Лагранжа о конечных приращениях. По лучим

или

J ’ (v + Qa(u — о)) а (и — н ) < а [J {и) — J

(v)], О < 0 < 1 ,

J' (v +

0 а (« — и)) (и — и) <

J (и) — J

(v)

при

всех

О <

Отсюда

при

а -»■ +

О сразу

придем к неравен

ству (2 ).

Переменные и и v в (2 ) равноправны. Меняя их ролями, по

лучим J(v)

(« )+ / '(« ) (и— и)

при всех и,

и е [а , b]. Сложим по

следнее

неравенство

(2)

почленно. Будем иметь

[J'(u)-^J'(v)]

(и— и) ^

при всех и,

и е [а , Ь],

что равносильно неубыванию про

изводной J'(ti)

на отрезке [а, Ь]. Следовательно,

/'(а+ О )

J'(b —0)

при всех и,

a ^ lu ^ b . С помощью

формулы Лагранжа о

конечных приращениях отсюда имеем

|J (и) — J (v) |=

|/' (£) (и — v) |<

L |и — v |

при

всех

и,

v 6 [a,

6 J,

где

а < £ , < 6 ,

L = max{ |J' (а -{- 0)j,

|Л (6 — 0 )|}. А

Обозначим через U* множество точек глобального минимума

функции

/(«)

на отрезке [а, Ь], т. е.

U * = { и : a ^ . u ^ b , J(u) =

—

(и)}.

Возможны

следующие три

случая:

U* — пус-

тое множество

(примером такой функции может служить J (и) = и

при 0 < и ^ 1 ,

7(0) =

1 'на отрезке [0, 1]); 2)

U* состоит из одной

точки и*

(примером служит функция 7(ы) = и2на отрезке

[— 1, 1]) ;

U* состоит более чем из одной точки

(примером служит 7(ц) =

|ц| + |и— 1 |

на отрезке [—ll, 2]). В последнем случае существу

ет отрезок [р,

y ]sta ,

b], все внутренние точки которого

принадле

ж ат

U*,

а концы этого отрезка могут и не принадлежать

U* (при

мер: J(u )= s0

при O C w ^ l , 7,(0) = 1). В самом деле, если и* и

е У * , и.*фь*,

то

/ *^ / (а М *+ ((1— а) V*) ^ . а / ( « * ) +

(1— a . ) J ( v * )

= 7 * .

Следовательно,

7 (a u * -f (1— a ) u * ) = 7 * при всех a e [0 ,

1], т. е. весь

отрезок [и*, и*]с—U*. Теперь-остается взять p = in f[/ *,

Y=supt/*. А

Т е о р е м а

2 . Всякая выпуклая на отрезке [а, Ь] функция 7 (и),

достигающая своей нижней грани на этом отрезке, принадлежит подмножеству Q*{a, 6 ] строго квазивыпуклых функций на [а, 6 ].

Д о к а з а т е л ь с т в о .	По условию U* непусто.	Обозначим
p=infC/, Y =supf7. Как	было замечено выше, либо U* состоит
из одной точки и* и тогда	P==y = u*< либо P < y и тогда все точ
ки интервала P < w< y принадлежат U, т. е. 7 (ы )= 7		при Р

Смотрите также файлы

Курсовая работа тепловой расчет спирального теплообменника для конденсации насыщенного пара бензола (.docx

Контрольная работа По курсу История хореографического искусства.docx

Жк тасымалдау дегеніміз.docx

9, 11ші сыныпоушыларынорытындыаттестаттауадайындаужмысыныжоспарынбекітутуралы Білім туралы.docx

Этикет приветствий в русском и иностранных языках.docx

Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

Смотрите также файлы

Информация

Списки файлов

Дополнительно