Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 45
Текст из файла (страница 45)
(1) некотоеые двугие зхдхч>н ггл 8 мо ' Чтобы записать эту формулу в компактной форме, введем индексы вершин й, н >гм каждый нз которых может принимать два значения — 0 и 1, Пусть 1 — х! прп I>,=0, с(й) = х, при !г,=1. (2) Тогда (1) можно переписать в виде ! (х>,х,) = ~ с(!г,)с(й.)! (й>, /г,). гч О Точно так же выглядит пнтерполяционпая формула в случае и переменных: ! !(х„...,х„) = ); с(й,) ...с(й„)!(ег, ...,/г„). (3) М, ..., кг=а Расчет по формулам (2) и (3) в принципе весьма прост. Однако количество слагаемых в (3) быстро растет с ростом п и уже при а=30 превышает 10'. Может показаться, что для больших и такая постановка задачи нереальна: невозможно хранить 2м значений функции !.
В действительности это и не нужно: достаточно иметь алгоритм, позволяющий вычислить значения ! в вершинах К'. 1.2. Метод Монте-Карло. Введем и независимых случайных величин $'и, ..., $!">, каждая из которых может принимать два значения — 0 и 1, и пусть Р(~"=О) =1 — х„Р(~!'>=!) =хь Доказательство. Из (2) и (4) нетрудно заметить, что и при й,=О, и при й,=! справедливо равенство Рйг!! А!) =с(й,). Позтому правая часть обычной Совокупность этих величин я'и, ..., В!"') определяет случайную вершину куба К".
Т е о р е м а 1. Мателгатическое ожидание 1(йп>, ... ..., $оо) равно 281 ПРОСТЕЙШИЙ СЛУЧАР<НЬ>Й ПОИСК формулы для математического о>кидания д[(~и> ~< >) > ~ (й„..м йл) Р [$П > = /г ь..., $<"' = й.) а„..., а„=о превращается в правую часть формулы (3),откуда сразу вытекает (5). Соответствующии формуле (5) метод Моите-Карло: при больших >".>' ) (х„..., хл) ж — ~) [ ($, >..., й~ ), где (й>, ..., Е> ) " Дл>, ", й«) — независимые реа<л» < П> <И лизацин случайной величины ($п>,...,5<а>) (или, другими словами, набор случайных вершин куба). В последней формуле легко выразить все $<» через случайные числа 7, так как $<'> = е(х, — у).
Получим формулу 1(х„..., х„) = — ~" 7 (е(х,— у>,,), ...,е(х„— у,,)), (6) м > где все 7>, — независимые случайные числа. Формула (6)' позволяет интерполировать значения [(х>, ..., х„) в нескольких точках, используя одни и те >ке случайные числа у„, (ср. гл. 3, $4). В статьях [179] н [177] построены методы а<опте-Карло для аастрапош>ровання н нелинейной ннтерполяпнн фуннпнн [(хь ... ..., х„) 9 2. Простейший случайный поиск 2.1. Случайный поиск. Рассмотрим ограниченную кусочно непрерывную функцию Ф(Р), определет>ую в замкнутом единичном л-мерном кубе К", так что К"— это куб К" вместе с его границей. Обозначим через Р точку абсолютного максимума Ф(Р) в К", т. е.
такую точку, что Ф (Р) ) Ф (Р) для всех РевК". Простейший поиск точки Р состоит в том, что в кубе задается произвольная последовательность точек Р>..., 19 И.М. Соболь иекотоРые дгугив зАдАчи и'л ..., Р, ..., называемых пробными точками; в каждой из этих точек вычисляется значение Ф(Р,); и находится точка Рь, в которой бг(Р1д = шах Ф(Р,). 1<1ки Точка Ри служит приближением к точке Р. Рассмотрим произвольную область В~К" с положительным и-мерным объемом (т,~О, содержащую точку Р.
Если при 1у'-1- оо хотя бы одча пробная точка попадает в В, то говорят, что процесс поиска сходится. Докажем, что если в качестве пробных точек выбирать независимые случайные точки с плотностью р(Р) )О внутри К", то процесс поиска сходится, Для доказательства фиксируем произвольную область В с (т,)О, содержащую точку Р и обозначим через р, вероятность того, что одна пробная точка попадет в В. Очевидно, р, = ) р (Р) ар > О.
в Вероятность того, что хотя бы одна из М пробных точек окажется в В, равна 1 — (! — р,)" и стремится к 1, когда йГ -г- оо, Следовательно, какой бы коэффициент доверия мы нн выбрали, при достаточно большом Ж с вероятностью, большей чем р, хотя бы одна пробная точка попадет в В. Если никакой предварительной информации о расположении гг нет, то естественно выбрать р(Р)ю1, т.
е. использовать пробные точки Гь равномерно распределен ные в К". Такой поиск называют простейшим случайным поиском (или слепым поиском). Ясно, что процесс поиска можно улучшить, если в ходе поиска менять плотность р(Р) с учетом угке полученных значений. Например, точку Р1 выбирать по плотности р,(Р), которая строится с учетом значений Ф(Р,), ...
..., Ф(Р, 1). На таких более совершенных (но и более сложных) алгоритмах поиска мы здесь останавливаться не будем [22, 66, 72, 1841. Отметим только некоторые ситуации, в которых простейший случайный поиск весьма полезен, $2) ппостеишип случайны|а пОиск 283 а) Функция Ф(Р) достаточно гладкая, но м н о го э кс тр е м альна я. Простейший случайный поиск целесообразно использовать для отбора начальных точек, нз которых моисно локальными методами (метод градиентов, иаискорейший спуск и др.) попасть в ближайший максимум.
Чем тщательнее выбор начальных точек, тем меньше шансов пропустнть абсолютный максимум. б) Требуется найти максимумы нескольких функций Ф2(Р), ..., Ф (Р). Прн простейшсм случайном поиске можно одновременно (по одним и тем же пробным точкам Г,) искать максимумы (и минимумы) всех этих функций. Такая ситуация довольно типична длп задач оптимального конструирования: обьаано качество конструкции можно оценивать по ряду весьма различных критериев, и выбор решающего (или компромиссного) критерия удается сделать лишь тогда, когда известно, чего можно добиться, оптимизируя тот илн иной критерий в отдельности. 2.2.
ЛП-поиск. В полном согласии е идеями гл. 7, можно попытаться использовать н качестве пробных точек для простейшего поиска любые точки, образующие равномерно распределенную последовательность в К" (гл. 7, п. 2.1): чем более равномерно распределены точки, тем лучших результатов можно ожидать от поиска. Сходимость такого поиска легко доказать: так как для любой области В при й(- оо отношение 5 (В)/йГ-+. Ра (см. (10) гл.
7), то В (В) -ЖУ,; следовательно, количество пробных точек, попавших в В, неограниченно ьозрастает с ростом М (если только (У,)0). ДВ-поиском называется простейп()тй поиск, в котором пробными точками служат точки Щ, ..., 1~м..., образующие ЛП,-поеледовательноетв (и. 2А. гл. 7). Сравнение Лйапоиска с простейшим случайным поиском проводилось ыа многих задачах. И неизменно ЛП-поиск оказывался более эффективным.
При мер В табл 1 приведены результаты поиска махсммума неноторой (достаточно сложной) чзунипип бз(Р) от 9 переменных (86]. Обозначении:ГПИ Г~зп Г<22 — три наил>чшие точки, полученные при случайном поиске, а Я~И, Я~~И О,з> — три наилучшие точки полученные при ЛП-поиске а тем же количеством 2У пробных точек 284 [гл в НЕКОТОРЫЕ ДРУГИЕ ЗАДАЧИ 2.3. Поиск в произвольной конечной области. Если функция б>(Р) определена в конечной замкнутой области 6, то для реализации простейшего случайного поиска надо выбирать случайные точки (9), ..., 9.), равномерно Твбпппв ) ечг;» Ф(г( )> Ф(ч',)) (*) Ф((), Ф(т(.» 39,52 40,21 42,29 38,5( 39,52 40,22 47,00 48,(2 48,'12 48,(2 48',81 48,0) 5(' 1024 20(8 37,84 47,83 47,83 42, 29 42,29 43,52 где функции д„— те же, а (,»,...
Я>(,...— точки пг-мер- ной ЛП,-последовательности. 3 3. Решение уравнения Лапласа 3.1. Построение случайных траекторий. Пусть задана ограниченная связная область (т и точка Режа. Определим случайную траекторию (,>о->. Я) — »... — . Яп >-... следующим образом: положим А)в=Рв, далее, если точка Я„известна, то построим окружность произвольного радиуса 1„, расположенную внутри б, и на этой окружности выберем случайную точку Я„+> (рис. 71).
Таким образом, Япв>=Я +1„е>» и=О, 1 2..., распределенные в 6. Делается это с помощью преобразований гл. 2, которые можно записать в форме $,= =ьв(7(,, 7 ), 1 ='Й =.и, где, вообще говоря, т= п. Обозначим через Г=(7>, ..., 7 ) случайную точку, равномерно распределенную в К". Пусть Гь..., Г,...— независимые значения Г. Тогда (-я пробная точка в (т' имеет координаты (д>(Г), ..., д„(Г()), (=1, 2, ..., И, ... Эти же преобразования позволяют осуществить в области (т и ЛП-поиск. При ЛП-поиске координаты (е)) пробной точки равны (д) ((7; ), ..., д, (Щ )), ( =- 1, 2, ..., (У', ..., РЕШЕНИЕ УРАВНЕНИЯ ЛАПЛАСА где оо„= (соз гу., з!и ор„), и угол !р„равномерно распреде лен в интервале (О, 2п). Теорем а 2.
Если функция и(Р) =и(х, у) удовлетво. рлет в области О уравнению Лапласа дои/дхо+ дои/дуо= О, (Т) то при каждом и и при любых (ъ ..., („ математическое ожидание Ми(!!„+,) равно значению и(Ро) в начале траектории. Доказательство. Придадим более точный смысл утверждению о произвольности радиуса („. Будем считать, что задана некоторая плот- ность д„((), которая тождественно равна нулю при всех (, превосходяшнх минимальное расстояние от Я„до границы 6о, а также при ((О; случай д„(!) =6(! — 1„) также допуска- ется; и выбор („ осуществляется в соответствии с плотностью Рис.
7!. у. (() Пусть р.(Р) — плотность распределения точки !',!„в О. Тогда математическое ожидание величины и((!„~~) = ,=иЯ„+(„оо„) равно Ми (!!„-н ) = з р (Р) оР з' Ч„(о! сИ ~ и(Р + о~) 2л с (О й По известной теореме о среднем значении гармонической функции (88! ол — )г и (Р + йо) бор = и (Р). л о Поэтому МНЯ„+ ) = )ги(Р) ро(Р)дР = Ми%„). При п=О точка (то==ро, и(Яо)= — и(Ро) и Ми((22)= =и(Ро). Применяя индукцию, получим утверждение теоремы. г88 НЕКОТОРЫЕ ДРУГИЕ ЗАДАЧИ <гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
