РОЗДІЛ 2
НОВІ ЗАСТОСУВАННЯ РАНДОМІЗОВАНИХ ОБЧИСЛЮВАЛЬНИХ ТЕХНОЛОГІЙ
2.1. Методика досліджень. Теоретичне обґрунтування рандомізованих обчислювальних схем
Важливу роль у створенні рандомізованих обчислювальних технологій відіграють припущення (гіпотези), на основі яких будуються математичні моделі. В задачах схематизації броунівського руху, безумовно, найважливішою є гіпотеза дифузійної плями (для двовимірних моделей) або дифузійної хмари (для тривимірних). Гіпотеза дифузійної плями (хмари) відкриває нові можливості створення стратегії малої вибірки для оптимізації рандомізованих обчислень на дискретних елементах. Наведемо у якості прикладу одне із формулювань цієї гіпотези: якщо центр дифузійної плями сумістити з центром ваги деякої плоскої області, то границі плями для послідовних моментів часу співпадуть з лініями рівня мильної плівки (поверхні Прандтля), що "натягнута" на контур області. Встановлено, що ця гіпотеза, як і схема Брауна - Маллера блукань "по колах", є наслідком відомої теореми про середнє значення гармонічної функції. Вивчення механізму розповсюдження дифузійної плями дає цілий ряд важливих результатів. Перш за все, це двосторонні оцінки розв'язку граничної задачі, ймовірнісна інтерпретація цікавого, але майже не дослідженого факту існування вузлів суперзбіжності у дискретному елементі, нова наближена формула для обчислення крутильної жорсткості стержня довільного перерізу, спрощений спосіб визначення тангенціальних напружень у будь-якій точці перерізу. Зараз вивчається можливість включення до програми досліджень двозв'язних і кусково неоднорідних областей, врахування теплофізичної і механічної ортотропії. До речі, одна з перших дискретних схем для моделювання неперервного процесу розповсюдження дифузійної плями була запропонована А.М. Колмогоровим, видатним математиком XX сторіччя [89, 90, 91].
Ще одне важливе припущення полягає в тому, що багатовимірні блукання можна представити як суперпозицію одновимірних блукань. Це спрощує задачу маршрутизації багатовимірних блукань і дає можливість розповсюдити на складні процеси відомі класичні результати [55, 92, 93].
Завдяки припущенню про існування статистичного ансамблю і стійкість відносних частот стало можливим обґрунтування МБУ. Комп'ютерні експерименти підтвердили правильність вибору у схемі випадкових блукань апріорних перехідних ймовірностей замість апостеріорних.
Особливе значення у створенні і дослідженні рандомізованих моделей мають аналогії. Перш за все треба згадати схему Брауна - Маллера, яка наштовхнула на ідею аналогічної схеми блукань "по симплексах". Також по аналогії з квадратурними формулами будуються кубатурні формули Ньютона-Котеса для наближеного обчислення подвійних і потрійних інтегралів. Можна побудувати обчислювальну формулу на тривимірному адаптованому шаблоні МСР по аналогії з двовимірним адаптованим шаблоном. Але провідною аналогією дисертації є ймовірнісно - барицентрична аналогія, яка дає можливість в залежності від точки зору розглядати вагові коефіцієнти монте-карловських усереднень як відносні маси системи матеріальних точок або як перехідні ймовірності у схемі випадкових блукань.
Розглянемо з ймовірнісної точки зору відому теорему про середнє для функції двох аргументів. На наш погляд, рандомізоване доведення цієї теореми дає зрозуміти, чому саме коло фігурує у несітковій схемі випадкових блукань Брауна - Маллера. Чудова ідея Брауна - Маллера застосувати коло у якості "транслятора" граничної інформації має просту фізичну інтерпретацію. Поведінку великої кількості броунівських частинок можна спостерігати, якщо випустити у тонкий шар води на плоскому склі краплю чорнил. З часом чорнильна пляма буде поступово збільшуватися, зберігаючи форму кола. Мабуть, саме форма дифузної плями наштовхнула Брауна і Маллера на схему випадкових блукань "по колах".
2.1.1. Рандомізоване доведення теореми про середнє для гармонічної функції двох аргументів.
Теорема. Значення гармонічної в області G функції U(x,y) у центрі O довільного круга, що лежить цілком в G, дорівнює середньому значенню цієї функції на границі Г заданого круга:
, (2.1)
де - значення гармонічної функції U на границі круга Cr радіуса r з центром у точці O(x,y);
dS - елемент дуги кола.
Проведемо із центра О коло Cr радіуса r. Вилучимо на колі елемент дуги dS (рис. 2.1).
Рис.2.1. До рандомізованого доведення теореми про
середнє значення гармонічної функції
Для броунівської частинки, що стартує із O, ймовірність попадання в елемент dS дорівнює dS/2?r. Позначимо через середнє значення функції u(x,y) в елементі dS. Тоді "середня винагорода" за вихід блукаючої частинки в dS дорівнює .
Тепер середня винагорода за вихід частинки на границю круга визначається "підсумовуванням" окремих внесків, що дає криволінійний інтеграл (2.1). Варто звернути увагу на одну особливість цієї схеми. Якщо розбити коло на однакові елементи dS, то ймовірність попадання у будь-який елемент не залежить від напрямку маршруту. Таким чином, блукаюча частинка може за один крок опинитися поблизу границі досліджуваної області. Саме цю можливість використали Браун і Маллер.
Ця теорема у математичному аналізі, як правило, доводиться інакше. Звичайно будуються інтегральні суми з наступним використанням граничного переходу. Можна показати, що і ця методика рандомізується досить природним шляхом.
Розіб'ємо коло Cr довільним способом на n елементів ?Si (i=). Через ?Si позначається i-й елемент кола і його довжина. В кожному елементі ?Si вибираємо точку Mi і будемо вважати, що функція зберігає у межах ?Si постійне значення . Варто звернути увагу, що з самого початку в цій процедурі присутній фактор випадковості на кожному кроці. Випадкова кількість елементів n, випадкова довжина окремого елемента ?Si, випадковий вибір точки Mi у межах i-го елемента. Інакше кажучи, ми виконали статистичний експеримент, результатом якого є вибірка . Якщо змоделювати випадкові блукання