1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 21
Текст из файла (страница 21)
Рассмотрим задачу условнойоптимизации для метода зависимых испытаний (алгоритм 8.3). В качестве базисных функций (8.26) рассмотрим «абсолютно-устойчивые»финитные функции мультилинейной аппроксимации (или аппроксимации Стренга – Фикса [18] с производящей функцией β (1) (u), являющейсяB-сплайном первого порядка) на регулярной сетке с шагом h по каждойкоординате:!!(d)(1)xx(1)(d)− ji× ...
× β (1)− ji;(8.37)χ(i) (x) = β (1)hh u + 1, при − 1 ≤ u ≤ 0;−u + 1, при 0 ≤ u ≤ 1;β (1) (u) =0 иначе;(1)(d) (k)x = x(1) , ..., x(d) xi = ji h, ..., ji h ; ji – целые числа;здесь множество X̂, на котором происходит приближение решения ϕ(x)уравнения (7.7), представляет собой прямоугольный параллелепипед.Для базиса (8.37) при использовании C-подхода к оценке погрешности (см. [9, 26]) рассматриваемого алгоритма 8.3 с вероятностью, близкой к единице, имеемδ(M, n) = kϕ − L(M ) ϕ̃kC(X) ≤ kϕ − L(M ) ϕkC(X) + kL(M ) ϕ − L(M ) ϕ̃kC(X) ≤H2H1≤ H̃1 h2 + L̃ max ϕ̃(i) − ϕ(xi ) ≤ U P (M, n) = 2/d + √ ;i=1,...,MnM131(8.38)здесь H̃1 , H1 , H2 = const, а L̃ – константа Лебега [26] (для базиса (8.37)она равна единице).Заметим, что порядок h2 детерминированной компонентыkϕ − L(M ) ϕkC(X) (см.
[9, 26, 28]) погрешности (8.38) обеспечивает выбори последующее приближение простейших коэффициентов w(i) = ϕ(xi )(см. второе из соотношений (8.30)).Трудоемкость рассматриваемого алгоритма 8.3 имеет видS(M, n) = H × M × n; H = const. Зададим уровень погрешности γи рассмотрим уравнение типа (8.36):H2H1+ √ = γ.2/dnM(8.39)2Выразив n через M из соотношения (8.39): n = H22 / γ − H1 /M 2/d ,получим функцию одного переменногоS̃(M ) =HH22 Mγ − H1 /M 2/d2 .Приравняв нулю производнуюdS̃(M )HH22=3dMγ − H1 /M 2/dd+4H1γ − 2/d ×,dMполучаем выражения для условно-оптимальных параметров и минимальной трудоемкости:Mopt =H1 (d + 4)dd/2γ −d/2 ; nopt =[H2 (d + 4)]2 −2γ ;16d/2HH1 H22 (d + 4)2+d/2 −2−d/2γ.(8.40)16dd/2Заметим, что если нас интересует только порядок по γ величин Mopt ,nopt и Sopt , т.
е. соотношения видаSopt =Mopt γ −d/2 , nopt γ −2 , Sopt γ −2−d/2 ,и трудоемкость S(M, n) пропорциональна произведению M × n, то достаточно приравнять детерминированную компоненту (в уравнении (8.39)это H1 /M 2/d ) и стохастическую компоненту (в уравнении (8.39) это132√H2 / n) верхней границы погрешности U P (M, n) и получить требуемый порядок из соотношения типа (8.39).Кроме того, заметим, что в практических вычислениях содержательную проблему представляет собой выбор констант H, H1 , H2 из соотношений (8.40).
Описание примера 8.1 закончено.Интересна (и весьма непросто разрешима) так называемая задачаполной оптимизации [26], в которой при минимизации трудоемкостиS(M, n) кроме параметров Mopt , nopt оптимальным образом выбираются начальная плотность π(x) и переходная функция p(x0 , x), определяющие используемую в расчетах прикладную цепь Маркова (7.22).Проблемы проведения рассуждений по условной оптимизации проекционныхметодов (типа алгоритма2.2) связаны с наличием «хвостов» χ(M +1) (x), χ(M +2) (x), .
. . бесконечных ортонормированных систем функций и необходимостью их оценки для построения верхнихграниц погрешности вида (8.35). Кроме того, проведенные в последнее время исследования показывают вполне определенную численнуюнеустойчивость рандомизированных проекционных функциональныхалгоритмов, что означает большое влияние ошибок при вычисленииприближений коэффициентов (8.25), (8.28) на общую погрешность методов.В этом смысле гораздо проще (и, возможно, эффективнее) использовать проекционно-сеточные методы (типа алгоритма 8.5), для которыхнахождение условно-оптимальных параметров не является сверхсложной задачей.Например, для многомерного аналога полигона частот (т.
е. для алгоритма 8.5, в котором в качестве специальных функций (8.33) берутсякусочно-постоянные функции вида 1при x ∈ G(xi ,h) ;(xi )hdh (x) =0 иначе;no (s)(s)G(xi ,h) = x = x(1) , ..., x(d) : xi −h/2 ≤ x(s) ≤ xi +h/2; s = 1, . . . , d ,(1)(d) где xi = xi , . . . , xi , а в качестве базисных функций (8.26) выбраныфункции (8.37)), можно получить следующие выражения для условнооптимальных параметров"MoptĤ1 [(2ν + 1)d + 4]=(2ν + 1)d133#d/2γ −d/2 ,d/2nopt =Ĥ22 Ĥ1[(2ν + 1)d + 4]16[(2ν + 1)d]d/22+d/2×(2 ln Mopt −ln ln Mopt + Ĥ3 )×γ −2−d/2для специально подобранных констант Ĥ1 , Ĥ2 , Ĥ3 и ν [26, 28].В любом случае требуется дополнительный сравнительный анализрандомизированных проекционных и проекционно-сеточных методовкак с позиций теории условной оптимизации, так и с точки зренияэффективности их применения для численного решения интегральныхуравнений Фредгольма второго рода (7.7), возникающих при исследовании актуальных прикладных задач.8.8.
Другие задачи теории и приложений алгоритмовчисленного статистического моделирования. Ограниченность данного пособия не позволяет «объять необъятное» и представить полновесный и подробный обзор теоретических разработок и актуальных приложений метода Монте-Карло.Тем не менее, в пособии представлена методически важная задача вычисления многократного интеграла, а также основные проблемырешения практически значимых интегральных уравнений Фредгольмавторого рода.Вне подробного рассмотрения в данном пособии остались теоретические и прикладные аспекты рандомизированных численных методов решения краевых задач математической физики и кинетических уравнений (в том числе, нелинейных), векторных алгоритмов метода МонтеКарло и алгоритмов с ветвлением траекторий, алгоритмов решениястохастических дифференциальных уравнений (с приложениями в математической физике и финансовой математике), смешанных дискретно-стохастических численных методов, специальных алгоритмов моделирования случайных процессов и полей и многих других задач.Для дополнительного изучения перечисленных тем можно использовать как материалы учебника [9], так и специальную литературу.
Следует обратить особое внимание на работы представителей новосибирскойшколы методов Монте-Карло (фамилии этих специалистов перечислены в подразделе 1.2 данного пособия).В оставшихся разделах и приложениях данного учебника будут представлены дополнительные детали, связанные с вопросами численногомоделирования выборочных значений случайных величин.В частности, будут рассмотрены:– алгоритмы реализации стандартных случайных чисел на ЭВМ(раздел 9),134– численные методы моделирования дискретных случайных величин(раздел 10),– альтернативные (отличные от стандартных) алгоритмы широкого применения (такие как метод дискретной суперпозиции и мажорантный метод исключения – раздел 11) для моделирования случайных величин и векторов,– специальные (использующие специфические свойства конкретныхраспределений) методы (на примере гамма- и бета-распределений –раздел 12 – и гауссовского распределения – раздел 13) для моделирования случайных величин, векторов и функций.Наконец, в материалах раздела 14 будут представлены технологииконструирования моделируемых плотностей распределения и формирования экзаменационных задач; эти материалы целесообразно использовать при проведении семинарских занятий дисциплины (если таковыепредусмотрены) – см.
приложение 3.9. Генераторы стандартных случайныхчисел9.1. Мера управляемости численных итерационныхпроцессов. В этом подразделе мы приведем некоторое «философское»основание использования итерационных алгоритмов (конкретнее, мультипликативного метода вычетов – см. далее формулы (9.4) и подразделы 9.3 – 9.6) для моделирования (реализации на ЭВМ) стандартныхслучайных чисел αi (см., например, [9, 13], а также подраздел 2.4 данного пособия).Рассмотрим численные математические модели систем, описываемых итерационным процессомXn+1 = Y (Xn ); n = 0, 1, 2, ...;(9.1)здесь Xn – некоторый вектор (величина), а Y (.) – некоторая (для векторного случая – многозначная) функция управления.ОПРЕДЕЛЕНИЕ 9.1 [29]. Исследуемую систему и соответствующий ей итерационный процесс (9.1) назовем управляемыми, если существует одновременно непустое и конечное множество предельныхсостояний{X̃ (1) , .
. . , X̃ (L) }, X̃ (l) = lim Xn ;(9.2)n∈Ñ(l)135здесь Ñ(l)S – подпоследовательности множества натуральных чисел N,причем l Ñ(l) = N.Мерой управляемости итерационного процесса (9.1) назовем величину µ = 1/L, где L – количество элементов множества предельныхсостояний (9.2).Отметим, что чем меньше значение L, тем ближе мера µ к единицеи тем более управляемым является процесс (9.1).УТВЕРЖДЕНИЕ 9.1 [29].
Предельные состояния (9.2) итерационного процесса (9.1) образуют циклическую группу.ДОКАЗАТЕЛЬСТВО. В силу того, что состояния(9.2) являютсяпредельными, выполняются соотношения Y X̃ (i) = X̃ (j) , причем дляслучая L > 1 имеем j 6= i, иначе состояние X̃ (i) является единственнымпредельным состоянием процесса (9.1). Утверждение 9.1 доказано.Не ограничивая общности, можно считать, чтоX̃ (l+1) = Y X̃ (l) при l = 1, .
. . , L − 1 и Y X̃ (L) = X̃ (1) .(9.3)Это означает, что введенная нами мера управляемости процесса (9.1)обратно пропорциональна порядку циклической группы равновесныхсостояний (9.3).В данном разделе, в частности, будут приведены примеры последовательностей (9.1) с малым значением меры управляемости µ, которыешироко используются для моделирования «неуправляемости» (хаоса,случайности).Речь пойдет о мультипликативном методе вычетов по модулюK = 2m с множителем вида Q = 52p+1 для натуральных m и p:xn+1 = xn × 52p+1 ; x0 = 2−m ;(9.4)здесь {A} обозначает дробную часть числа A (см.