Автор Рыбаков Д. А (стр. 3 из 5)
[6,C137] Пусть А является произвольным множеством АÌÂn. Рассмотрим последовательность шаров ri < e , i=1,2,3….. , которые покрывают А.
Используя обобщеную формулу объема (или меры в общем случае) шара запишем
Феликс Хаусдорф смог доказать, что существует единственное вещественное число d, для которго S ¹ 0 и S ¹ ¥ при e®0 . Свой вклад в строгое доказательства теоремы внес Абрам Безикович, поэтому размерность d называется размерность Хаусдорфа-Безиковича.
В начале эта величина не вызывала большого интереса у ученых. Но в последующем она сыгарала важную роль в математике фракталов. В математическов литературе она обозначается как dimH(A).
Компютерные модели фракталов
Для большинства физических приложений исследуются одно, двух и трех – мерные множества. Наиболее удобными являются покрытия с помощью отрезков, квадратов или кубов в виде ломанной линии, сетки или решетки соответственно. С помощью ЭВМ невозможно представить фрактал полностью во всех его деталях. Обычно точность вычислений не превышает несколько десятков знаков после запятой, что не позволяет представить мелкие или очень крупные части. Фрактал в ЭВМ можно представить как минимум тремя способами. Приведенное ниже описание легко обобщается на случаи большей размерности.
1) Клеточный, решетчатый или растровый способ. В этом способе пространство представлено в виде програмного массива чисел. Например : var space : array [1..L,1..L] of boolean; Если space[i,j] = true значит элемент принадлежит фракталу и наоборот. i,j – целые числа.
2) Векторный способ. Это более точный способ. Элементы фрактала представлены в виде элементарных фигур, которые задаются векторно. В этом случае для того, что бы определить, принадлежит ли точка (x,y) необходимо перебрать элементы фрактала и вычислить, попадает эта точка хоть в один элемент. x и y – числа с плавающей точкой.
3) Функциональный способ. В данном способе что бы определить принадлежит ли точка (x,y) необходимо вычислить функцию F(x,y) и проанализировать полученное значение. На самом деле все способы сводятся к функциональному способу. Просто, некоторые функции могут вычислятся аналитически, а некоторые обращаться к массивам данных для получения результата. Мы будем ссылаться на этот метод имея ввиду, что исползуются аналитические функции.
Большинство задач на момент написания реферата использует клеточный (растровый) метод №1 для моделирования множеств. Этот метод обладает несколькими недостатками. Для детального моделирования требуется Ln клеток. Где L – количество клеток в одном измерении n-количество измерений. Современная мощность компьютеров позволяет беспрепятственно моделировать 2х-мерные множетва. Для них L~ 103 . Для моделирования 3х мерных множеств требования к ОЗУ резко возрастают. Для таких задач L ~ 100, что явно недостаточно для полноценного моделирования. Альтернативой клеточной модели может служить векторная модель.
Для моделирования 3х-мерных физических стохастических фракталов применим векторный метод. Растровый метод вообще мало применим для 3х мерного моделирования. А аналитические функции, описывающие что-либо физическое стохастическое достаточно редки. Можно придумать пример, основанный на алгоритмах генерации случайных чисей, которые при одних и тех же (х,у,z) возвращают одинаковые значения. Например: F(x,y,z) = f(x,y,z) + MD5(x,y,z, r), где f – аналитическая функция, r – константый случайный параметр, MD5 – функция вычисления MD5 суммы. Но этот способ требует тщательного вероятностного анализа получаемых значений что бы результат был близок к какой-нибудь физической задаче.
Применимость методов моделирования.
| Растровый метод | Векторный метод | Функциональный метод | |
| Геометрические фракталы | В основном 2х мерные задачи | применим | применим |
| Алгебраические фракталы | В основном 2х мерные задачи | применим | применим |
| Стохастические фракталы | В основном 2х мерные задачи | применим | мало применим |
Так же кратко стоит упомянуть о методах постоения фрактала. Для постоения геометрических фракталов используется Система Итерируемых Функций. Для алгебраических используются итерации нелинейных отображений, задаваемых простыми алгебраическими формулами. Для стохастических, все зависит от природы фрактала и сотношения закономерности и случайностей.
Вычисление размерности Минковского с помощью ЭВМ
Следует отметить, что описанным ниже способом вычисляется не только размерность Минковского, но и Хаусдорфа, хотя для некоторых множеств(например для счетных множеств) эти размерности, вычисленные аналитически могут отличаться [КОН 135]. Но в большинсте важных случаев эти размерности совпадают.
За основу берется формула зависимости количества кубов N от длины грани куба e при малых e в покрываещем множестве.
ln const – ln N(e) » d ln e
Как видно из формулы, если построить график зависимости ln N от ln e , то получится прямая с наколном d.
Разберём алгоритм на примере 2х мерного случая. Эта процедура используется для анализа изображений. Большинство изображений представлены в растровом виде, то есть в виде двухмерного массива [6].
Построив сетки для разных e получаем таблицу:
График получается не идеально ровным. Наклон этого графика вычисляется методом наименьших квадратов. В данном примере наклон равен -1.346 , то есть d=1.346
Еще одним недостатком этого метода является то, что используемое покрытие неминимально. Поск минимально покрытия – нетривиальная задача. Затраты на его вычисление могут оказаться огромными, а полученное улучшение небольшим.
Одним из эффектов вычислений может служить следующее ступенчатое поведение графика.
Этот эффект проявляется при плавном изменении e между итерациями. На приведенном рисунке разница e между соседними точками составляет 1%. Эффект проявляется для всех типов фракталов и зависит от алгорима подсчета размерности.
Для наглядности рассмотрим простой случай, когда покрытие состоит из одноги и двух кваратов.
Для клеточных моделей существуют естественные ограниения 1³e³L. Для векторных моделей ограничение менее строгое 0>e³L. Это означает, что e можно достаочно близко приближать к 0, эта близость ограничена только точностью вычислений конкретной ЭВМ. Это приводит еще к одной проблеме. Если модель состоит из конечного количества векторных объектов, то начиная с некоторого момента e может стать намного меньше размера любого объекта. Это приводит к тому, что наклон графика становится равным топологической размерности объектов. То есть проблема состоит в том, что бы выбрать нужный диапазон для e, который имеет физический смысл. От выбора диапазона зависит получаемая величина. Интуитивно можно предположить, что d ³ e ³ L, где средняя d – длина объектов, составляющих множество, а L – размер всего ансамбля. Выбор диапазона может быть договорным для разных типов явлений, пока не будет создана точная математическая теория для фракталов, задаваемых в ЭВМ.
Точечный метод.Точечный метод является альтернативой к предыдущему методу. Этот метод применим к клеточным(растровым) моделям. [6,C143]
[11]. Рассмотрим сетку, покрывающую весь фрактал. Ее узлы будем называть ячейками. Каждую ячейку, имеющую с фракталом непустое пересечение, будем считать за одну точку. Ясно, что именно эта схема реализуется при графическом выводе фрактала на экран как массива пикселов. В этом параграфе «подсчет числа точек в клетке» означает подсчет числа ячеек (или пикселов) в клетке. Это не то же самое, что считать действительное число геометрических точек в клетке — ведь их бесконечно много. Точечный метод принципиально отличается от клеточного; в первом подсчитывается число точек в клетке, а во втором — число клеток, необходимых для покрытия фрактала.
Для упрощения вычислений будем считать клетки квадратными. Размер L клетки означает число ячеек по каждой стороне. Ограничимся нечетными значениями L; в этом случае центральная ячейка клетки будет равноудалена от всех сторон. Сначала вычислим вероятности Р(m, L) того, что клетка размера L содержит m точек (ячеек) фрактала. Для этого вокруг каждой точки фрактала, считая ее центральной, построим клетку размера L и подсчитаем число точек, попавших в нее. Предположим, что фрактал содержит М точек. Тогда P(m, L) равно числу клеток, содержащих m точек, m = 1,...,М, деленному на М. Заметим, что сумма всех вероятностей равна единице: