Файл: Брандин, В. Н. Основы экспериментальной космической баллистики.pdf

На рис. 9.1.1 приведена одномерная функция самого общего вида, для которой начнем рассмотрение метода.

Одномерная функция а(?) в интервале (?mn, ?тах )= Щ ?)

имеет абсолютный минимум, если существует значение ?, при­ надлежащее Q (q), такое, что для любого другого значения q ^Q (q ) выполняется условие

Иначе говоря, в точке абсолютного минимума

2( ? )

Данное определение относится к абсолютному минимуму функции. Аналогично определяется понятие абсолютного макси­ мума.

Ненаправленный случайный поиск минимума функции а (?) в интервале Q(?) длиной I заключается в следующем. Пусть имеется последовательность ?б), ..., qW независимых случайных точек, равномерно распределенных на интервале Q(?). Случай-- ные точки могут выбираться в соответствии с формулой

? = /Л,

где 1] — независимые случайные числа, равномерно распределен­ ные на интервале [0, 1].

Далее определяются значения функции а (???) в этих точках

т. е. aft(?) —min а (?<•')). >

(?)

При некоторых предположениях можно утверждать, что с ве­ роятностью, сколь угодно близкой к единице, последователь­

ность (аД?)} при k >-оо сходится по вероятности к а(?), а соот­ ветствующая ей последовательность точек сходится по вероят­

ности к ?. Для этого достаточно предположить непрерывность - функции в экстремальной точке,, Тогда любому малому положи­ тельному числу б будет соответствовать множество

с ненулевой мерой Г(6). Обозначим отношение этой меры к I через у(б). При равномерном распределении точек в интервале Q(?) вероятность попадания точки ??? на множество ш(?) будет

250

равна у (б). Вероятность попадания хотя бы одной точки последо­ вательности qW, ..., q<h\ ... на множество со(^) равна

Пусть р0— требуемая вероятность решения задачи, тогда для

необходимого числа испытаний k получаем из (9.1.4) следующую приближенную оценку:

Аналогично одномерному случаю многомерный поиск заклю­ чается в построении последовательности {ah ( q ) ) в соответствии с правилом

fOjufaO, если a,(qw ) > ak_ x(q)\

(9.1.7)

1а(?('г)),. если а (qw ) < ак_ х (q),

если отыскивается абсолютный минимум функции. Соответству­ ющая ей последовательность векторов

сходится по вероятности к вектору q .

В многомерном случае, однако, возникают трудности в полу­ чении независимых случайных точек, равномерно распределен­ ных 6 области Q(q)- Если область Й (^) имеет простую конфигу­ рацию, например, представляет собой г-мерный прямоугольный параллелепипед

Я] т ' ш ‘' С Я} Я] max {J Е - - - >

то координаты случайной точки могут быть выбраны в соответ­ ствии с выражением

где lj — длина /-й стороны параллелепипеда; тр,-— независимые случайные числа с равномерным распределением из интервала

[О, 1].

251

Для произвольного выпуклого многогранника получить рав­ номерно распределенные точки гораздо труднее. Задача стано­ вится проще, если отказаться от требования равномерности рас­ пределения. Тогда координаты случайной точки могут быть вы­ браны при помощи случайных независимых чисел (k= 1, ..., т), равномерно распределенных в [0, 1], в соответствии с законом

Числа щ называются в этом случае барицентрическими коорди­ натами точки д. Получаемая неравномерность распределения точек естественно ухудшает сходимость метода.

Для области произвольного вида равномерное распределение точек можно получить путем вписывания этой области в парал­ лелепипед и выбора точек в соответствии с законом (9.1.9). Те из точек, которые не содержатся в Q(g'), необходимо исключить из рассмотрения. Это в значительной степени снижает эффектив­ ность метода, если область П (^) занимает малую часть объема параллелепипеда. Кроме того, процесс поиска усложняется не­

обходимостью проверки принадлежности случайной точки д пространству Д (^).

Итак, основными достоинствами ненаправленного случайного поиска являются относительная простота и абсолютная универ­

сальность. Основным недостатком является сравнительно низ­ кая эффективность.

§ 9.2. МЕТОД ФИБОНАЧЧИ

Наиболее эффективным и имеющим достаточно широкую об­ ласть применения последовательным детерминированным мето­ дом является метод Фибоначчи. Хотя метод был предложен Ки­ фером в 1953 г., теоретически он тесно связан с работами мате­

матика XIII века Фибоначчи и поэтому известен в литературе под этим именем.

Последовательность поиска экстремума этим методом сво­ дится к вычислению исследуемой функции в каких-то точках об­ ласти ее определения, сравнению вычисленных значений между собой и выбору на основании этой информации новых опытных точек в области определения функции. В основе метода поиска лежит свойство унимодальных функций: или строго убывать (для функций, имеющих максимум), или строго возрастать (для функций, имеющих минимум) при удалении от экстремальной точки. Последнее не требует дифференцируемости и даже обыч­ ной непрерывности исследуемой функции, так что область при­ менения метода Фибоначчи достаточно широкая.

252

На рис. 9.2.1 приведена унимодальная функция общего вида, для которой может быть использован метод Фибоначчи.

Рассмотрим одномерный случай. Одномерная функция a(q) в интервале Й(<7) унимодальна, если существует значение q, при­ надлежащее Q(q), такое, что a(q) или строго убывает при q-^'q

a(?i) > a (q 2) при условии q%<q. Oil•*

Рис. 9.2.1. График унимодальной функции

Рис. 9.2.2. Иллюстрация процесса поиска экстремума по методу Фи­ боначчи

•Процесс поиска минимума функции a(q) в интерзале !2(<7)

сляется значение функции в этой точке a(q^1'>). Далее произво­

исключается из дальнейшего рассмотрения.

253

Обозначим длину оставшегося для исследований интервала

внутри интервала, относительно его центра. После этого вычис­ лим значение функции а (ф 3)) и сравним его с наименьшим из значений сцфД, а(Ф 2>). Из двух вновь полученных интервалов оставляем тот, который содержит внутри себя точку, соответст­ вующую минимальному значению функции из найденных.

Четвертый опыт заключается в проведении той же процедуры относительно этой точки на интервале неопределенности с дли­ ной /3. Описанная процедура наглядно представлена на рис. 9.2.2. Оказывается, что такая е-минимаксная последователь­ ность интервалов неопределенности связана соотношением [60]

Отсюда можно найти положение первого эксперимента ф1) на интервале П(^); точка ф1) должна располагаться на расстоянии 1_2 от одного из концов интервала с длиной П. Для определения h воспользуемся дважды уравнением (9.2.1)

h = Fr- ^ a — Fs_3s

и

h = F j s — F s_ 2е.

Подставив второе равенство в первое, получим

где в]— величина, малая даже по сравнению с е. Отсюда нахо­ дим, что величина р в формуле

Для достаточно больших значений s отношение (9.2 4) при­ ближенно равно 0,618 [60].

Интересно отметить, что с помощью метода Фибоначчи для сокращения первоначального интервала неопределенности менее чем до 1 % его исходной длины требуется всего 11 эксперимен­ тов. Для достижения того же самого результата методом дихо-

254