Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 46
Текст из файла (страница 46)
Существуют различные постановки задачи минимизации. В самой широкой постановке требуется найти все точки локального минимума и отвечающие им значения функции ~ В приложениях чаще всего возникает задача вычисления конкретной точки локальнОго минимума или точки глобального минимума. Иногда представляет интерес только лишь минимальное значение целевой функции, независимо от того, в какой именно точке оно достигается. 2. Отрезок локализации. Подобно тому, как алгоритмы решения нелинейных уравнений настроены на отыскание одного изолированно- 237 го корня (см. Гл. ) ~ ( ..
4) большинство алгоритмов минимизации осущестдляет лишь поиск точки локального минимума функции ~ Для того предварительно найти содермсащий точку отре [, в зок [о, о], на котором она является единственной точкой локального минимума. Этот отрезок в дальнейшем будем называть отпрезком яоаализацин1 точки х. К сожалению, не сущ ествует каких-либо общих рецептов относительно того, как на ти отрезок й локализации. В одномерном случае полезным может оказаться та улир б рование функции с достаточно мелким шагом н зических соображений, из опыта решения аналогичных задач и т. д.
Для некоторых алгоритмов (например, для метода Ньютона) достаточно иметь не отрезок локализации, о изации а хорошее начальное приближение алло> „. Пример 9.2. Для функции г (т) = язв —,т + е з' произведем локализацию точек локапьного минимума. Из графина функции, изображенного на рис. 9.2, видно, что функция ~(т) имеет две точки локального минимума х~ н х2, первая из которых является и точкой глобального минмума.
Для точки г1 за отрезок локализации можно принять отрезок [-4, -3], а для точки гт — отрезок [О, 1]. Докажем теперь, что на отрезке [О, 1] действительно содержится точка локального минимума. Для этого заметим, что Рис. 9.2 ~'(х) = 3:Р— 1 — е т и Х'(0) = -2 < О, Г'(1) = 2 — е ' > О. Так как значения ~"(0) и ~'(1) имеют разные знаки, то на отрезке [О, 1] содержится точка г, для которой у (з) = . о ~~(х) = з ,г'( ) О. Н ~~( ) = бз'+ е т > 0 для всех т Е [О, 1], Следовательно, ~"(г) > 0 и точка х на отрезке [О, 1] есть единственная точка локального ми- 1В теории о птимнзацнн отрезок [а, Ь] чаще называют интервалом неопределенности. ы понима .
М аем интервал неопределенности иначе (см. з . ). 238 цкмума. Аналогично доказывается, что отрезок [-4, 3] также является отрезк~м локализации. 1 3. Унимодальные функции. Пусть ~ — функция, определенная на отрезке [а, 6]. Предположим, что на этом отрезке содержится единственная точка х локального минимума функции ~ причем функция строго убывает при х ( х и строго возрастает при х > х.
Такая функция называется уни.иодальной'. Возможны три случая расположения точки х на отрезке [а, Ь]: точка х является внутренней для отрезка, х совпадает с левым концом отрезка и х совпадает с правым концом отрезка. Соответственно и график унимодальной функции может иметь одну из форм, схематично изображенных на рис. 9.3. Ьк о к Ьк з Ьк а а> Ф Рис. 9.3 вк, к, к, Ь к Рис, у.~ 3 а м е ч а н и е. Унимодальная функция, вообще говоря, не обязана быть непрерывной.
Например, функция, изображенная на рис. 9.4, унимодальна и имеет три точки разрыва. Приведем достаточное условие унимодельности функций на отрезке [а, Ь]. П р е д я о ж е н и е 9.1. Если для всех х б' [а, Ц выполнено условие Г(х) ) О, то функция уни.иодальна на отрезке [а, Ц. Пример 93. Функция 1'(х) = хз — х + е * унимодальна на каждом из отрезков [-4, — 3] и [О, 1]. Чтобы убедиться в этом, достаточно заметить, что 1 Иногда такую функцию называют строго унимодальной, а унимодальной называют функцию, которая строго убывает при х ч х1, равна постоянной при х~ ~1 х К х2 и строго возрастает при х Э х~ [18]. 239 ~"(х) = бх + е х > 0 для всех х Е [-4, -3], х Е [О, 1], и воспользоваться преМ- ложением 9.1. Для сужения отрезка локализации точки минимума унимодальной функции полезно использовать следующее утверждение.
П р е д л о ж е н и е 9.2 Пусть У вЂ” уми.иодалвкая аа отрезке [а, Ь] фуищия и а 1 а < у < ~9 ~ Ь. То1да: 1о) если ~(а) ~ ~(д), то х Е [а, Д; 2о) если ~(а) Э ~(,О), то х Е [о, Ь]; Зо) если ~(а) 1 ~(у), и ~(у) ~ ~я, то х Е [а, я. и 1о. Предположим противное: х > Р. Тогда вследствие унимодальности у получим ~ (а) ) ~(,8), что противоречит условию. 2о.
Предположим противное: х < а. Тогда вследствие унимодальности 1 получим ~ (а) < ~(Д, что противоречит условию. Зо. В силу п. 1о имеем х Е [а, Д, а в силу п. 2о имеем х Е [а, Ь]. Следовательно, х Е [а, Я. Геометрическая иллюстрация пп. 1о и 2о приведена на рис. 9.5. ° иооый юрооок 4 Рис. 9.5 вайо) (х, о 4 хо х к хок к ххо х Ь) а) 240 Многие алгоритмы одномерной минимизации построены в расчете то, что на отрезке локализации целевая функция унимодальна. В ча тности, такими являются алгоритмы, рассматриваемые в 8 9.3. 4.
Об одном подходе к локализации точки минимума На практике часто бывает неизвестно, является ли данная функция унимодальной. Однако во многих случаях из дополнительных соображений следует, что при х Э хо функция 1 сначала убывает, а затем, начиная с некото- рого значения х = х, становится возрастающей (правда, не исключено, что далее она снова может стать убывающей). Для того чтобы в таком случае локализовать точку х, используют различные нестрогие методы. Один из распространенных подходов состоит в следующем. Выбирают начальный шаг Ь > О, в несколько раз меньший предпола- гаемого расстояния от точки хо до точки х.
Затем вычисляют и сравнивают значения ~(х0) н ~(х1), где х1 — хо + Ь. Если оказывается, что ~(хо) > 1'(х1), то последовательно вычисляют значения функции ~в точках хЬ = хо + 2Ь 'Ь для Ь 1 2. После обнаружения первой же точки, для которой ~(хЬ) 4 ~(хЪ1), за отрезок локализации принимают отрезок [хЬ.п хЬ,|~. В случае, изображенном на рис. 9.6, а, за отрезок локализации принят отрезок [хт, х4~. Если же ~(хо) 1 ~(х1), то последовательно вычисляют значения в точках хЬ = хо + Ь/2Ь ', Ь 1 2. После обнаружения первой же точки хь длЯ котоРой ~(хЬ) С 1(хо), за отРезок локализации пРинимают отРезок [хо, хь 1~.
В случае, изображенном на рис. 9.6, б, за отрезок локализации принят отрезок [хо, хт1. Описанный метод не является строгим и не гарантирует, что отрезок локализации всегда будет найден. Например, для функции, график которой изображен пунктиром на рис, 9.6, а, при выбранном шаге Ь справедливы неравенства ~(хо) > У(х1) > ~(хг) > ~(хз) > ~(х~) и поэтому отрезок локализации точки х обнаружен уже не будет. Тем не менее этот или близкий к нему методы часто используются на практике, Пример ЭА.
Локализуем указанным выше образом точку локального минимума функции ~(х) = хз — х+ е х. Возьмем л~ = -5, Ь = 0.2 и положим х1 = л~ + Ь = -4.8. Так как ~(хв) в ~ 28.4 > ~(х~) Ф 15.7, то будем последовательно вычислять значения функции Ув точках хь = л~ + 2" 1Ь. Из табл. 9.1 видно, что при Ь = 4 впервые выпол"яется неравенство у(ц,) < у(хЬ+1). Поэтому за отрезок локализации следует принять отрезок [хз, лЗ] = [-4.2, -1.8). Таблица 9.1 Й 0 1 2 3 4 5 ху, — 5 -4.8 ~.8 -4.2 -3.4 — 1.8 У(г7с) 28.4 15.7 6.74 -3.30 ~.94 2.02 3 9.2.
Обусловленность задачи минимизации Пусть х — точка строгого локального минимума функции ~ вычисляемой с погрешностью. Будем считать, что в некоторой окрестности точки х вычисляемые приближенные значения ~ (х) удовлетворяют неравенству ~У(х) — 7 (х) ~ ~ Ь = Ь (7" ), т. е. имеют границу абсолютной погрешности, равную Ь. Как нетрудно понять, существует такая малая окрестность (х — е, х + е) точки минимума х, для которой, основываясь на сравнении вычисляу=Юо емых значений 7*(х), нельзя достоверно определить ту точку, в которой действительно достигается минимум функции 7.
Эта ситуация схематично изображена на рис. 9.7. Интервал (х — е, х + е) будем называть интереалол неопределенности х Х+е Рис. 9.7 точки х локального минимума. Оценим величину е радиуса интервала неопределенности в предположении, что функция 7 дважды непрерывно дифференцируема и выполнено условие 7 (х) > О, В этом случае с учетом того, что 7" (х) = О, для значений функции 7" в точках х, близких к х, справедливо приближенное равенство Оценим минимальное расстояние между точками х и х, начиная с которого заведомо будет выполнено неравенство 7*(х) > 7 (х), т. е. точка х перестанет попадать в интервал неопределенности. Имеем 242 Ях) — Ях) = ~ (х) — ~(х) + (~'(х) — ~(х)) — (~(х) — ~(х)) ~ Г'(х) ~ ~ ~® — ~(х) — 2Ь и — (х — х)~ — 2Ь. — Г(х) Следовательно, К"(х) — ~(х) > — (х — х)х — 2Ь и неравенство ю 2 ~'(х) > ~ (г) выполнено, если (х — х)х > 4Ь/~ (х).
Таким образом, к " 2 ~ Ы~" (*). (9.2) Заметим, что любое приближение х' к х, попавшее в интервал неопре- деленности, нельзя отличить от точного значения х точки минимума, используя только вычисляемые значения ~ функции ~ Поэтому (9.3) Итак, рассматриваемую задачу минимизации нельзя назвать хорошо обусловленной. Если задача хорошо масштабирована, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
