УНІВЕРСАЛЬНИЙ АЛГОРИТМ РІВНОМІРНОГО РОЗПОДІЛУ ТОЧОК НАДОВІЛЬНІ АНАЛІТИЧНІ ПОВЕРХНІ
Проблема рівномірного розподілу точок на різних поверхнях має велике значення для багатьох прикладних досліджень. Вона має значення таких напрямів, як математичне моделювання, чисельні методи, комп'ютерна графіка, технології армування і флокування структурно-неоднорідних середовищ тощо.
Завдяки своїй варіативності та великим прикладним можливостям, в даний час проблема вийшла за рамки допоміжного завдання приватних інтерпретацій та почала набувати відтінків загальнотеоретичного значення. Географія робіт, присвячених цій проблемі, досить широко представлена, а кількість робіт постійно зростає.
Найбільш чітко постановка завдання, можливі шляхи її вирішення ілюструються на одному з окремих випадків – проблемі рівномірного розподілу точок на поверхні сфери [9, 11–13]. З середини XX століття у провідних світових наукових фахових виданнях, таких як журнали «Biometrics», «Annals of Mathematical Statistics» тощо, почали з'являтися роботи, що описують різні підходи до вирішення проблем рівномірного розподілу точок на поверхні сфери. Як результат багаторічного дослідницького процесу ці алгоритми стали входити до праці, що вже стали класичними, з теорії ймовірності, математичної статистики та методів Монте-Карло [11]. Також слід зазначити, що завдання рівномірного розподілу точок на поверхні сфери тісно пов'язане з однією з найбільших математичних проблем ХХІ століття, включених до списку Стівена Смейла (seventh Smales's problem [7, 8]). Проблемі також присвячена окрема сторінка у популярній математичній інтернет-енциклопедії Wolfram MathWorld [13]. Поряд із феноменологічними підходами до вирішення задачі рівномірного розподілу точок на поверхні сфери [7, 8] застосовуються методистатистичного моделювання [9, 12, 13]. Крім алгоритмів рівномірного розподілу точок на поверхні сфери у тривимірному «фізичному» просторі також чимало робіт присвячено вирішенню аналогічного завдання для випадку з багатовимірним простором. Особливо варто відзначити роботу "Simulation of random distributions on surfaces" (G. Melfi, G. Schoier, [10]), в якій пропонується метод рівномірного розподілу точок вже на поверхнях, заданих явно у вигляді функції z = z (x, y ).
В основу алгоритму покладено метод статистичного моделювання, що полягає в генеруванні координат точок за аналітичною обчислюваною функцією щільності спільного розподілу параметрів, що відповідає рівномірному розподілу точок на поверхні. Для генерування значення двовимірної випадкової величини використається узагальнений метод Неймана [8]. Всі алгоритми реалізовані в системі комп'ютерної математики (СКМ) Wolfram Mathematica 7.0, в ній отримані і всі візуальні моделі.
Загальна постановка задачі та методологія її вирішення
Вочевидь, що рівномірно розподіляти точки на площині неважко, досить поміщати в вузли координатної сітки, або генерувати координати з допомогою еталонного генератора випадкової величини з рівномірним розподілом на заданому відрізку. Також просто вирішується завдання про рівномірний розподіл точок на поверхнях, що розгортаються, таких як конуси, циліндри, торсові поверхні. У випадку ж з поверхнями, що не розвертаються, - еліпсоїд, сфера, тор, параболоїд і т.д. - Завдання значно ускладнюється.
Метою дослідження було отримання універсального алгоритму рівномірного розподілу точок на аналітичних поверхнях ненульової Гаусової кривизни, заданих параметричним способом, та ілюстрація рівномірнихрозподілів на поверхнях сфери, тора, гелікоїда, «Падає краплі», пляшки Клейна.
Зазначимо, що під поняттям «рівномірний розподіл точок на поверхні» розуміється такий розподіл, при якому на двох довільних елементах поверхні з однаковими площами розташовується однакове число точок. Оскільки передбачається розподіл великої кількості точок, то вирішення завдання застосовуються методи статистичного моделювання. Для кожної поверхні знаходиться функція щільності спільного розподілу параметрів, що задовольняє рівномірному розподілу точок на поверхні, що розглядається.
Для знаходження функції густини спільного розподілу використовуються можливості символьної математики пакета Wolfram Mathematica 7.0. Ці засоби дозволяють посилювати чисельні алгоритми (чисельне інтегрування, знаходження екстремумів функцій тощо) символьними обчисленнями (наприклад, знаходження похідних у вигляді), що робить алгоритми гранично універсальними.
Знаходження функції щільності спільного розподілу ймовірностей в описах рівномірного розподілу точок на довільних поверхнях
Нехай поверхня задана параметричними рівняннями x = x (u, v), y = y (u, v), z = z (u, v) в області D = . Необхідно знайти аналітично f(u, v) – функцію щільності спільного розподілу параметрів u, v, що відповідає рівномірному розподілу точок на поверхні, що розглядається.
У разі коли точки рівномірно розподіляються на поверхні, ймовірність попадання довільної точки А на елемент поверхні dS з одного боку дорівнює:
де, згідно [1, 3],
(E, F, G – коефіцієнти першої квадратичної форми поверхні). Отже,
З іншого боку, ймовірність влучення точки Ана елемент поверхні дорівнює
Зважаючи на вищевикладені співвідношення, отримуємо рівність:
Звідки остаточно знаходимо потрібну функцію щільності спільного розподілу параметрів, що відповідає рівномірному розподілу точок на поверхні, що розглядається:
Генеруючи значення параметрів u, v з використанням функції f(u, v), отримаємо рівномірний розподіл точок на поверхні.
Метод Неймана генерування багатовимірної випадкової величини за відомою функцією щільності спільного розподілу параметрів
Для моделювання одновимірної випадкової величини функції щільності розподілу застосовуються різні методи [5, 11]. Наприклад, спосіб взяття зворотної функції зручний у випадках, коли можна отримати аналітично зворотну функцію. Однак застосування цього методу ускладнюється у випадках багатовимірних розподілів залежних випадкових величин. Універсальним методом генерування випадкових величин за відомими щільностями розподілу є метод Неймана (метод усічення), суть якого розглянемо спочатку з прикладу одновимірної випадкової величини. У цьому випадку алгоритм реалізується так [5, 11]:
1. Функція густини розподілу вписується у прямокутник.
2. Генеруються два незалежні числа еталонним генератором випадкової величини з рівномірним розподілом на інтервалі (0, 1) і масштабуються по сторонах прямокутника.
3. Якщо отримана точка потрапляє в область під графіком густини розподілу, то точка приймається, інакше відкидається.
4. Повторюються дії 2–3, доки не буде згенеровано необхідну кількість точок.
При перехід до багатовимірних випадків процедура генерації зберігається з урахуванням зміни розмірності простору. Для двовимірнихвипадкових величин, відповідних нашому випадку, зберігається наочність алгоритму, оскільки процедура усічення здійснюється у тривимірному «фізичному» просторі. У цьому випадку алгоритм реалізується так:
1. Визначається – максимальне значення функції f(u, v) в області D = .
2. Генеруються числа
, ,
де R - еталонний генератор випадкового числа з рівномірним розподілом на інтервалі (0, 1);
3. Виконується перевірка: якщо
,
де R – еталонний генератор випадкового числа з рівномірним розподілом на інтервалі (0, 1), то точка приймається, інакше відкидається.
4. Повторюються дії 2–3, доки не буде згенеровано необхідну кількість точок.
Описані вище алгоритми були реалізовані в пакеті Wolfram Mathematica 7.0, який дозволяє будувати візуальні моделі, що є зручним для контролю роботи програми та демонстрації результатів. Нижче наведено деякі візуальні результати роботи алгоритму.
На рис. 1 представлена поверхня сфери та рівномірний розподіл 15000 точок на ній. Поверхня сфери задана рівняннями:
де 0 ≤ u ≤ π, 0 ≤ v ≤ 2π.
Мал. 1. Рівномірний розподіл 15000 пікселів на поверхні сфери, ViewPoint:
На рис. 2 представлена поверхня тора та рівномірний розподіл 20000 точок на ній. Поверхня тора задана рівняннями:
де 0 ≤ u ≤ 2π, 0 ≤ v ≤ 2π.
Мал. 2. Рівномірний розподіл 20000 пікселів на поверхні тора, ViewPoint:
На рис. 3 представлена поверхня гелікоїда та рівномірний розподіл 15000 точок на ній. Поверхня гелікоїда задана рівняннями:
де 0 ≤ u ≤ 2π, 0 ≤ v ≤ 2π.
Мал. 3. Рівномірнерозподіл 15000 пікселів на поверхні гелікоїда, ViewPoint:
На рис. 4 представлена поверхня «Падає крапля» і рівномірний розподіл 20000 пікселів на ній. Поверхня «Падаюча крапля» задана рівняннями [4]:
де 0 ≤ u ≤ 2π, 0 ≤ v ≤ 1.
Мал. 4. Рівномірний розподіл 20000 пікселів на поверхні «Падаюча крапля», ViewPoint:
На рис. 5 представлена поверхня пляшки Клейна та рівномірний розподіл 20000 точок на ній. Поверхня пляшки Клейна задана рівняннями [6]:
де –π/2 ≤ π/2 , 0 ≤ v ≤ 2π.
Мал. 5. Рівномірний розподіл 15000 пікселів на поверхні пляшки Клейна, ViewPoint:
Візуальний аналіз одержаних результатів рівномірного розподілу точок на поверхнях різних типів підтверджує правильність роботи алгоритму.
Наведені конкретні приклади реалізації запропонованого методу рівномірного розподілу точок на аналітичних поверхнях підтверджують його високу ефективність та універсальність. Візуальний аналіз одержаних графічних результатів свідчить про рівномірний розподіл точок на поверхнях. Запропонований алгоритм може бути узагальнено для генерування нерівномірного розподілу точок на заданій поверхні.
Рецензенти:
Берестова С.А., д.ф.-м.н., доцент, завідувач кафедри теоретичної механіки Інституту фундаментальної освіти Уральського федерального університету імені першого Президента України Б.М. Єльцина, м. Єкатеринбург;
Сесекін О.М. д.ф.-м.н., професор, завідувач кафедри прикладної математики Уральського енергетичного інституту Уральського федерального університету імені першого Президента України Б.М. Єльцина, м. Єкатеринбург.