The Title of an Article for the Bulletin of the AMS

The Author

The Date

Abstract:Replace this text with your own abstract.

Самоподобные множества

-- подготовил Е.М. Горбатенко

Введение:
гномоны, многоугольные числа, числа Фибоначчи, золотое сечение+
Самоподобные треугольники, четырехугольники и квадраты +
Самоподобные множества и их обобщения. Границы самоподобия . Структуры самоподобия !!!
Самоподобные множества в арифметике(добавить оцифровку и исчисление в плоскости Гауссовых чисел)
Самоподобные структуры в алгебре и анализе здесь Kigami, фракт. группа,
Метод исчерпания, как способ построения самоподобных множеств+
Метрика и мера на пространстве адресов
МетрикаХаусдорфа на пространстве компактов(скейлинг свойство для метрики Хаусдорфа) $\pm$
Системы итерируемых функций (СИФ)+рекурр система итер ф и их аттракторы
Условие открытого множества и его обобщения
Числовые и комбинаторные инварианты самоподобных множеств (теоремы Перрона и Фробениуса)
Фрактальные интерполяционные функции и теорема о коллаже!!!
Использование Maple для изображения фрактальных самоподобных множеств (добавить собственно программы с рисунками)
Список литературы!!!

Введение

Пособие содержит вводный материал по с/к Геометрия фрактальных множеств, а отдельные темы излагались в курсе концепции современного естествознания. Отметим, что в живой природе фракталы не встречаются, хотя самоподобие наблюдается, так сказать, невооруженным глазом. Кроме того, для прикладных задач более подходящей является концепция случайного фрактального множества, более удовлетворительно описывающая многообразие форм в биологии. Однако, в чистой математике начиная с 19века постепенно рос список примеров экзотических множеств, отчасти связанный с родовыми муками математического аанализа перед появлянием теоретико-множественной топологии, большая часть этих множеств являлись самоподобными и среди них выделялось универсальное самоподобное множество -- множество Кантора и его "многомерные" варианты. Оно быстро нашло применение в в теории формальных языков, анализе, топологии, теории динамических систем.

С общеметодологической точки зрения бурный расцвет теории фрактальных самоподобных множеств основан на изоморфизме абелевых непрерывных групп $\U{211d} _{>}$ и $\U{211d} _{+}$ , заданным логарифмической функцией . По этой причине методы линейного анализа с соответствующими изменениями более или менее успешно применяются в этой новой науке. Не менее важным является лучшее понимание явления хаоса в динамических системах, моделируемого с помощью системы итерируемых функций. Наконец, компьютерное моделирование фрактальных множеств успешно использует рандомизированные алгоритмы, так что даже в довольно элементарных ситуациях реализуется основная концепция синергетики: образование упорядоченных структур в открытых системах.

В пособии содержится материал, собранный (в основном) по большей части по причине его (относительной) элементарности. Мы делаем упор именно на структуре самоподобия, не привлекая каких-либо глубоких результатов из геометрической теории меры и теории случайных процессов, хотя совсем обойтись без небольших заимствований из этих двух дисциплин представляется невозможным. Оставлена в стороне теория динамических систем и уже довольно развитая теория фрактальных или самоподобных групп, а также анализ и теория дифференциальных уравнений на фракталах.

Материал пособия распадается на три части: в первой -- §1-§5 обсуждается концепция самоподобия, во второй -- §6-§13 вводятся и исследуются числовые инварианты самоподобных множеств, наконец, в третьей части §14 обсуждается реализация самоподобных фрактальных множеств в среде Maple.

1геометрия подобия и гномоны

2 разбиение простых фигур на себе подобные

3Общее определение структуры подобия и их воплощение в алгебре геометрии анализе

4 метод исчерпания построения фрактальных самоподобных множеств

Гномоны, многоугольные числа, числа Фибоначчи, золотое сечение

Исследование самоподобных множеств, сконструированных из выпуклых многогранников или выпуклых многоугольников в плоском случае относится к комбинаторным задачам геометрии группы подобий. Если вообразить жизнь в мире, состоящем из самоподобных множеств, то деятельность Шерлока Холмса вооруженного лупой всегда приводила бы к быстрому успеху в мире самоподобных множеств: в таком мире малая часть подобна целому и следует лишь угадать (в чем Шерлок Холмс не имел равных) принцип подобия для восстановления полной картины события.

В античной математике свойство самоподобия проявилось в понятии гномона, позволявшего разбить геометрическую фигуру на бесконечное число подобных ей частей или дополнить регулярным образом геометрическую фигуру до подобной ей.

Definition (Герон Александрийский)

Гномоном называется фигура, которая будучи добавлена к исходной фигуре образует новую фигуру, подобную первоначальной.

Понятие гномона может быть перенесено и на теорию чисел в форме построения так называемых многоугольных чисел

Рассказ о многоугольных числах начнем с очевидной формулы MATH

Для небольших целых значений можно построить таблицу

MATH

и изобразить графически MATH

L-образная фигура, составленная из темных кружков, сохраняет подобие, несмотря на рост ее размеров. Это отличительные признаки гномона, появившегося при построении ряда "квадратных" чисел $a^{2}$ .

Построение ряда "треугольных" чисел основано на свойствах суммы первых членов натурального ряда: MATH

Для небольших целых значений можно построить таблицу

MATH

и изобразить графически

MATH

Здесь горизонтальные отрезки, образованные закрашенными кружками удовлетворяют определению гномона.

Exercise

Изобразить графически последовательность и ее гномон.

Exercise

Для построения гномона произвольного прямоугольника достаточно провести диагональ (или ) и опустить из вершины (или ) перпендикуляр (или ) к (или ) который пересечет сторону прямоугольника в точке (соответственно ). (соответственно ) есть диагональ прямоугольника подобного , а искомый гномон.

Exercise

Доказать, что точка пересечения диагоналей и из предыдущего упражнения есть полюс логарифмической спирали, проходящей через вершины первого прямоугольника и через соответствующие точки всех остальных, возрастающих или убывающих прямоугольников.

Exercise

В треугольнике $\bigtriangleup ABC$ можно построить подобный ему треугольник и его гномон. Достаточно провести прямую , отсекающую угол $\angle ABD$ , равный углу $\angle BCA$ , чтобы получить треугольник $\bigtriangleup ABD$ , подобный $\bigtriangleup ABC$ , следовательно $\bigtriangleup BCD$ и есть гномон.

По аналогии с прямоугольником золотого сечения, можно говорить о треугольнике золотого сечения: остроугольном-- с углами 36 $^{0}$ , 72 $^{0}$ и 72 $^{0}$ и тупоугольном -- с углами 108 $^{0}$ , 36 $^{0}$ и 36 $^{0}$ .

Exercise

Показать, что гномоном остроугольного треугольника золотого сечения является тупоугольный треугольник золотого сечения. Доказать, что все вершины треугольников, полученных построением их гномона лежат на логарифмической спирали.

Напомним, что стороны прямоугольника MATH

образуют золотое сечение, если отношение длины большей стороны прямоугольника к меньшей равно . Сам прямоугольник в этом случае называется золотым.

Обратимся, впрочем, к классическому определению. Точка делит отрезок в среднем и крайнем отношении или образует золотое сечение отрезка, если отношение большей части отрезка к меньшей равно отношению всего отрезка к большей части. Обозначая через $\tau$ отношения , выводим,что $\tau$ удовлетворяет квадратному уравнению $x^{2}-x-1=0$ .

Exercise

Если построить квадрат со стороной , найти середину отрезка и провести дугу окружности радиусом с центром в точке до пересечения с продолжением стороны в точке , то точка разделит отрезок в среднем и крайнем отношении. Доказать.

Вернемся к нашему золотому прямоугольнику. Если отсечь от него квадрат со стороной, равной меньшей стороне прямоугольника, тогда получим новый прямоугольник, подобный первоначальному.

Обратная процедура заключается в присоединении к прямоугольнику квадрата, со стороной равной большей стороне исходного прямоугольника. Таким образом, гномоном для "золотых" прямоугольников является квадрат.

Объяснение этому явлению заключается в том, что есть корень уравнения MATH

В самом деле, MATH

Примем, что б\ольшая сторона прямоугольника равна $\tau$ , а меньшая -- равна .

Легко вывести из уравнения (1), что MATH

это соответствует операции отсечения единичного квадрата от прямоугольника,

либо переписать последнее соотношение в виде MATH

что соответствует операции присоединения квадрата со стороной $\tau$ к первоначальному прямоугольнику. Последнее соотношение позволяет представить $\tau$ как бесконечную цепную дробь: MATH

Последовательные подходящие дроби дают значения

,, , MATH ,..., представляющие (если контролировать числители дробей) начальный ряд последовательности Фибоначчи.

Самоподобные треугольники, четырехугольники и квадраты

Самоподобные треугольники

Рассмотрим равносторонний треугольник $\triangle ABC$ и представим его в виде объединения четырех равных равносторонних треугольников , , где первые три треугольника примыкают к вершинам, а четвертый находится в центре, тогда это разбиение индуцирует три гомотетии $f_{i}$ , с коэффициентом $\frac{1}{2}$ и с центрами в вершинах треугольника и одно спиральное подобие $f_{4}$ с центром в центре симметрии треугольника, коэффициентом сжатия $\frac{1}{2}$ и углом поворота против часовой стрелки на 60 $\U{b0}$ . Если считать треугольник заполненным, пишем $\blacktriangle ABC$ , то есть представлять его заполненым 2-мерными симплексами , тогда MATH

Рассмотрим два случая разбиения прямоугольных треугольников на два и три подобных ему

img/image/SelfSimilarFe55__126.png img/image/SelfSimilarFe55__127.png

Для произвольных треугольников проводя подходящие средние линии возможны следующие три способа разбиения на 4, 6 и 7 подобных треугольников.

img/image/SelfSimilarFe55__128.png img/image/SelfSimilarFe55__129.png img/image/SelfSimilarFe55__130.png

, то есть

, если

. По симметрии, если

, тогда

.Из определения метрики Хаусдорфа, приведенного в замечании после теоремы следует, что

. Из определения метрики Хаусдорфа следует, что

, если

. Таким образом, MATH

Приведем еще одно доказательство последнего неравенства.

В следующем треугольнике, разбитом на пять подобных треугольников, углы равны $\frac{\pi }{6}$ или $\frac{2\pi }{3}$ .

img/image/SelfSimilarFe55__133.png

Бесконечный самоподобный треугольник см. упражнения по теме "гномон"

Exercise

Как разбить треугольник на 11 подобных ему?

Exercise

Выписать гомотетии и спиральные подобия (возможно, несобственные) во всех приведенных случаях разбиения треугольника на 2,3 (прямоугольные), 4,6,7 (произвольные) подобных треугольников.

Будем говорить, что треугольник -самоподобен, если он допускает разбиение на подобных ему треугольников.

Справедлива следующая теорема [Hartel]

Theorem (Hartel)

Всякий треугольник -самоподобен для и $k\geq 6$ .

Треугольник является -самоподобным, если и только если он прямоугольный.
Треугольник является -самоподобным, если и только если он прямоугольный.
Треугольник является -самоподобным, если и только если он прямоугольный, либо имеет углы $\frac{2\pi }{3}$ и $\frac{\pi }{6}$ .

Самоподобные четырехугольники

Osburg

Четырехугольник является в точности тогда 2-самоподобным, когда он является параллелограммом с отношением сторон $1:\sqrt{2}$
Четырехугольник является в точности тогда 3-самоподобным, когда он является:
1. параллелограммом с отношением сторон $1:\sqrt{2}$ , $1:\sqrt{3}$ , $2:\sqrt{3}$ , или ;
2. трапецией с углами при основании $\frac{\pi }{2}$ , $\frac{\pi }{4}$ , и отношением параллельных сторон ;
3. вписанным четырехугольником , в котором диагонали пересекаются так, что точка пересечения диагоналей делит вторую диагональ в отношении квадрата пропорций деления первой.
Четырехугольник является в точности тогда 4-самоподобным, когда он является:
1. параллелограммом;
2. трапецией, отношение оснований которой составляет и углами при основании $\frac{\pi }{2}$ , $\frac{\pi }{4}$ , или $\frac{\pi }{2}$ , $\frac{\pi }{3}$ , или $\frac{\pi }{3}$ , $\frac{\pi }{3}$ ;
3. трапецией, у которой при длинах оснований и длина боковой стороны равна $c=\sqrt{ab}$ .

Самоподобный квадрат и бесконечный самоподобный квадрат

Здесь просто предъявлены два вида разбиений квадрата: в первом случае происходит разбиение на меньшие квадраты попарно не равные друг другу и имеющие ребра целочисленной длины, этот случай подробно описан в [Гарднер]с изложением истории вопроса, второе (бесконечное) разбиение порождено золотым прямоугольником и основано на том, что гномоном золотого прямоугольника является квадрат. Сопровождающая разбиение пара логарифмических спиралей показывает динамику замощения все более уменьшающимися квадратами

Самоподобные целочисленные параллелепипеды

В том случае, когда параллелепипед не является кубом, либо в случае плоскости квадратом, исследовать возможные свойства самоподобия такого геометрического объекта несколько легче и все сводится к линейной алгебре и проверке с помощью некоторой целочисленной матрицы , свойства параллелепипеда являться объединением копий заданного параллелепипеда .

стр 92-96 Malone

5.4 параллелепипеды как самоаффинные тайлы,

Для расширяющей матрицы иногда возможно выбрать набор цифр так, что он порождает простой тайл, который является параллелепипедом. Однако не для любого набора цифр это так. Числовые эксперименты, в случае $2\times 2$ матрицы и , казалось бы указывают, что может произойти, когда след . По теореме Гамильтона-Кэли получаем $A^{2}=kI.$ (Случай был исследован, потому что имеется совсем небольшой выбор цифрового множества; мы можем всегда гарантировать цифру 0 трансляцией, и аффинным преобразованием выбрать почти однозначно оставшуюся цифру.

Лемма 5.2. Предположим, что у нас есть матрица и параллелепипед такие, что есть дизъюнктное объединение (с точностью до множеств нулевой меры)параллелепипедов, конгруэнтных , то есть MATH тогда каждая вершина (каждый узел) параллелепипеда в смысле теории выпуклых многогранников, находится в точно одном из , , $\ldots$ , .

Доказательство. Мы можем преобразовать проблему так, чтобы было единичным кубом и так, чтобы вершина , которую мы собираемся исследовать, был вершиной самого нижнего и самого левого основания в смысле, что она является наименьшей вершиной относительно лексикографического упорядочения: по определению если и только если для некоторого $1\leq r\leq n$ . Поскольку лексткографическое упорядочение является полным, мы всегда можем теперь выбрать наименьшую вершину $\overrightarrow{d}$ для и наименьший вектор смещения . Заметим, что самая крайняя точка любого параллелепипеда будет его вершиной, и таким образом, самая крайняя точка в есть $\overrightarrow{c}$ , и крайняя точка в объединении будет $\overrightarrow{d}$ Таким образом, $\overrightarrow{c}$ , и $\overrightarrow{c}$ - также принадлежит .

Предположим, что $\overrightarrow{c}$ . Тогда $\overrightarrow{c}$ = для некоторого . Однако, векторы трансляций различны, так что и $\overrightarrow{d}$ , из этого неравенства следует MATH

что невозможно.

Теорема 5.3. Предположим, что у нас есть матрица и параллелепипед так что:

MATH

-- дизъюнктное объединение (с точностью до множеств нулевой меры), тогда подобна взвешенной матрице перестановки множества .

Доказательство. Выберите любой угол , тогда $\overrightarrow{c}$ должен быть образом некоторого угла . Пусть ребра исходящие из имеют вид ,... ,. Тогда, применяя к ребрам матрицу находим что ребра для имеют вид MATH , ..., MATH , а это в точности ,... , .

Используя Лемму 5.2 мы можем также представить этот угол как . Ребра в $\overrightarrow{d}$ должны быть теми же самыми, что и в $\overrightarrow{b}$ , возможно направленные в противоположную сторону, таким образом они имеют вид MATH

где $s_{n}=\pm 1$ . Таким образом, ребра $\subset AP$ имеют вид,..., . Помня, что является единственной частью формирования объединения в $\overrightarrow{c}$ , эти ребра должны быть параллельными, но могут быть более короткими, чем ребра ,... , . Таким образом , где . Мы заключаем что , и таким образом переставляет ребра с некоторыми весами. Поскольку ребра формируют базис для $\U{211d} ^{n}$ , мы видим, что - взвешенная матрица перестановки.

Следствие 5.4. Если такая же как в Теореме 5.3 тогда, $A^{m}$ подобна диагональной матрице для некоторого , делящегося НОК $(1,\ldots ,n)$ . Следовательно - диагонализуема.

Доказательство. Рассмотрим перестановку ребер и проигнорируем веса; мы получаем перестановку $\sigma \in$ $S_{n}$ . Мы можем записать эту перестановку как произведение непересекающихся циклов, имеющих длины между и . Беря наименьший общий делитель длин этих циклов получаем порядок перестановки $\sigma$ . Теперь = $\beta _{i}^{m/l}$ , где $\beta _{i}$ - произведение весов циклов, содержащих , и - длина этого цикла. Таким образом $A^{m}$ подобен диагональной матрице с $\beta _{j}$ вдоль диагонали. Пусть $SA^{m}S^{-1}$ -- диагональная матрица. Пусть $\lambda _{j}$ для $j=1,\ldots ,r$ -- ее различные диагональные элементы, так что MATH

мы можем разложить на множители каждый сомножитель этого произведения и получаем MATH

где $\omega _{j}$ - корни -ой степени из единицы. Каждый из этих коэффициентов отличен от других, поскольку если два было то же самое тогда $\lambda _{j}$ не мог быть отличным от других. Таким образом, минимальный многочлен матрицы $SAS^{-1}$ может быть разложен на попарно различные линейные множители и, таким образом, $SAS^{-1}$ является диагонализуемой.

Заметим, что, осуществив перенумерацию мы можем гарантировать, что каждый цикл соответствует блоку диагональной матрицы. Кроме того, если имеется единственный цикл длиной , то справедливо для базисных векторов в $\U{211d} ^{n}$ и, таким образом, $A^{m}$ $\beta I$ .

Теперь рассмотрим, как параллельных перемещений заполняют . Мы можем подсчитать, сколько копий расположены вдоль каждого ребра. Должно быть целое число копий , поскольку они не перекрываются и они точно заполняют . Кроме того, произведение числа копий вдоль каждого ребра дает $\det (A)$ , так как мы свели задачу к случаю единичного куба, а эта суммарная величина должна показывать, насколько параллелепипед больше , чем . Если -- простое число, то единственный способ упаковать их состоит в применении трансляций к вдоль одного ребра и вдоль остальных.

Лемма 5.5. Если матрица такая же, как в Теореме 5.3 тогда она подобна взвешенной матрице некоторой перестановки, причем веса - целые числа.

Доказательство. Как мы уже видели, сторона , параллельная , должна быть целым кратным , но эта сторона есть в точности: MATH

поэтому

Теорема 5.6. Если - расширяющаяся матрица с $det(A)=\pm p$ , --простое и -- такой параллелепипед, что:

MATH

тогда $A^{n}=\beta I$ .

Доказательство. Как отмечено выше, сформировано -кратной упаковкой параллелепипеда , а имннно, его параллельным перенесением вдоль одного ребра . Это означает что для какого-то одного значения и для всех других ребер.

Предположим, что перестановка, произведенная , не состоит из единственного цикла длины , тогда есть некоторый цикл для который вся передача

я 1 и так я для этого цикла 1. Тогда, Заключением 5.4, $A^{m}$ подобен матрице с собственным значением 1 и таким образом у есть собственное значение модуля 1 спектральной теоремой отображения. Это противоречит быть расширяющимся, и таким образом перестановка состоит из единственного цикла длины . Таким образом, как наблюдается выше, = Я.

Условие в Лемме 5.5 фактически достаточно для, чтобы иметь параллелепипед как элемент мозаичного изображения.

Теорема 5.7. Предположите, что подобен взвешенной матрице перестановки, где веса - ненулевые целые числа, тогда там существует параллелепипед и направляет ~ki таким образом что:

Доказательство. Пусть $SAS^{-1}$ -- взвешенная матрица перестановки с целочисленными весами. Позвольте ~ei быть

Рассмотрите параллелепипед с одним углом в начале координат и ~ $e_{j}$ как края от начала координат. Тогда - параллелепипед с ребрами, параллельными ., Исследующему углы , есть углы с ребрами, дающими все возможные ориентации $\pm e_{1}$ ,..., $\pm e_{n}$ , таким образом это возможно, чтобы выбрать некоторый угол, ориентация которого - все положительные явления. Мы транслируем угол в начале координат к этому углу и называем это . Если мы сравниваем длины сторон с длинами сторон , мы можем ясно расположить в стеке j

копии ij P вдоль края край

i~ej и ll все AP точно как

где ri между 0 ri <j

ij.

Если мы хотим ~0 быть цифрой, то это - простой вопрос трансляции P (я 􀀀 A) ~k0 в конец вычисления. Отметьте, что мы не показали, что мы можем выбрать эти ~ki так, чтобы их координаты были целыми числами в правильном основании. 5.

Самоподобные множества и их обобщения. Границы самоподобия . Структуры самоподобия

В этом параграфе мы по возможности будем избегать пользоваться топологическими операциями, а ограничимся чисто теоретико-множественными конструкциями.

Definition

Пусть -- некоторое множество семейство отображений. Непустое подмножество будем называть $\QTR{cal}{F}$ -самоподобным, или самоподобным относительно системы отображений , если справедливо равенство MATH

Example

Предположим дополнительно, что попарно не пересекаются и для всякого заданы такие отображения , $k=1,\ldots ,a_{ji}$ , что полагая всякое множество $K_{i}$ представлено в виде объединения $a_{1i}$ попарно непересекающихся подмножеств итд, $\ldots ,a_{in}$ попарно непересекающихся подмножеств , MATH . Обозначим через целочисленную неотрицательную матрицу и будем говорить, см [] , что семейство является -совершенным, если матрица является примитивной, то есть некоторая степень $A^{m}$ матрицы положительна.

Definition

Пусть и некоторое множество и -- подмножество $\times V\times V$ . Полагаем . Для любой пары обозначим через $E_{ji}$ множество . Соответственно через $E_{i}$ обозначим объединение $\cup _{j}E_{ji}$ . Будем говорить, что множество есть множество вершин мультиграфа $\Gamma$ , а $E_{ji}$ является множеством ориентированных ребер мультиграфа $\Gamma$ с началом в и концом в . Тогда множество $E_{i}$ есть множество всех ребер мульттиграфа $\Gamma$ , входящих в вершину . Будем называть граф связным (сильно связным), если существует цикл (ориентированный цикл) проходящий через любые две заданные вершины графа.

Definition

Пусть -- некоторый мультиграф, и задано семейство (далее используется термин -- мультимножество) множеств $X_{i}$ , $i\in V$ , причем каждому ребру поставлено в соответствие отображение . Полагаем , , . Тогда можно записать . Непустое мультимножество , , $K_{i}\subset X_{i}$ , $i\in V$ назовем $\Gamma$ -самоподобным, если MATH

Definition

Непустое подмножество $K\subset X$ назовем -самоподобным, если для некоторого $\Gamma$ -самоподобного мультимножества , выполняется соотношение MATH

Заметим, что $\QTR{cal}{F}$ -самоподобное множество из определения 1 соответствует мультиграфу с одной вершиной и ребрами.

Из анализа разобранного выше примера понятно, что если через обозначить множество вершин мультиграфа, а отождествить с множеством ребер, соединяющих вершины и , причем , и все $f_{i}$ являются биекциями, тогда является $\Gamma$ -самоподобным.

Для самоподобных множеств имеет смысл понятие границы подобия самоподобного множества как аналога границы в топологии.

Definition

Пусть множество $K\subset X$ является $\QTR{cal}{F}$ -самоподобным в смысле определения 1. Тогда его границей подобия называется множество MATH

в следующих двух леммах используются обозначения , $U=K\backslash B$ .

Lemma

Definition

Полагаем MATH -- пространство бесконечных слов алфавита . Будем предполагать далее, что множество является конечным множеством и его можно отождествить с множеством , после перенумерации всех элементов из . Поэтому, когда путаница исключена, пишем $W_{N}^{\infty }$ вместо $W_{G}^{\infty }$ . Определим отображения условием MATH

Ясно, что $W_{G}^{\infty }$ является самоподобным множеством относительно системы отображений .

Определим понятие структуры самоподобия, следуя Kigami []

Definition

Пусть -- $\QTR{cal}{F}$ -самоподобное множество и задано отображение , удовлетворяющее условию MATH

Набор называется структурой самоподобия, а отображение называется адресным отображением из пространства адресов $W_{N}^{\infty }$ в самоподобное множество .

Полагаем MATH , , .

Множество $C_{\QTR{cal}{S}}$ называется критическим множеством структуры самоподобия, а -- ее посткритическим множеством. Полагаем также

Definition

Структура самоподобия называется посткритически конечной (p.c.f. -- post critically finite), если множество является конечным множеством.

Пространство адресов и адресное пространство в том случае, когда задано -самоподобное множество , подчиненое $\Gamma$ -самоподобному мультимножеству устроено более сложно.

Полное пространство адресов определяется следующим образом

MATH

Обращаем внимание, что является -самоподобным множеством, подчиненым самоподобному мультимножеству

Естественная нумерация компонент бесконечного слова соответствует отрицательным целым числам

Мы можем построить (указать) адрес для всякой точки из следующим образом. Пусть $x\in K$ . Тогда найдется номер $i\in V$ , что $x\in K_{i}$ . Полагаем $\ x_{1}=x$ .

Поскольку мультимножество является $\Gamma$ -самоподобным, то , поэтому для некоторого выполняется и поэтому $x_{1}$ имеет вид . Поэтому полагаем Для элемента $x_{2}$ повторяем процедуру поиска и находим ребро . Действуя так шаг за шагом, строим набор , который является элементом .

Структура самоподобия для $\Gamma$ -самоподобного множества , порожденного $\Gamma$ -самоподобным мультимножеством определяется отображениями , подчиненными соотношениям MATH

Каждый конечный начальный фрагмент бесконечного слова $\alpha$ соответствует однозначно определенному пути на графе из вершины в вершину и в качестве метрики между элементами полагаем , где .

В работе [20] R. Daniel Mauldin& S. C. Williams определили рациональную самоподобную схему следующим образом

полагаем и для всякого целого $p\geq 2$ , пусть MATH

На множестве зададим частичный порядок, полагая $\sigma <\tau$ , если $\sigma$ -- суффикс $\tau$ .

Самоподобные множества в арифметике

Идея рассматривать самоподобные подмножества из $\U{2124}$ принадлежит O. Naghshineh, который предложил следующую задачу к международной математической олимпиаде, проходившей в Шотландии в июле 2002 года.

Exercise

Пусть бесконечное подмножество $\U{2124}$ , причем такое, что для целых чисел $a_{i}$ и $b_{i}$ , где $a_{i}F+b_{i}$ и $a_{j}F+b_{j}$ не пересекаются при $i\neq j$ и для всех . Доказать, что MATH

Далее для встречающихся в этом параграфе самоподобных множеств будем использовать термин арифметический фрактал. Следующее ниже решение поставленной задачи заимствовано из [13].

Definition

Пусть для $i=1,\ldots ,n$ заданы линейные отображения вида , где $a_{i}$ и $b_{i}$ целые, причем . Подмножество называется арифметическим фракталом относительно , если является объединением его непересекающихся образов относительно отображений $\phi _{i}$ .В этом случае можно записать и определить размерность $\dim F$ как такое вещественное число, что MATH

Remark

Основным примером арифметических фракталов в $\U{2124}$ служит множество целых чисел в разложении которых по выбранному основанию выпущено некоторое количество цифр. Самое замечательное во введенном понятии размерности заключается в том, что оно не зависит от конкретного представления в виде . Кроме того, меньший арифметический фрактал имеет меньшую размерность. Если это свойство доказано, легко решить сформулированную выше задачу. Заметим для этого, что $\U{2124}$ является арифметическим фракталом размерности . Тогда арифметический фрактал имеет меньшую размерность, что и решает задачу.

Lemma

Пусть удовлетворяет условию , где $\phi _{i}$ те же, что и выше. Если такое вещественное число, для которого справедливо неравенство , тогда число элементов множества в шаре $B\left( x\right)$ ограничено сверху величиной $cx^{s}$ для некоторой константы и достаточно больших .

Proof

Полагаем и пусть $N\left( x\right)$ и обозначают число элементов из и $F_{i}$ в шаре $B\left( x\right)$ соответственно. Мы имеем MATH и поскольку для $f\in F_{i}$ и мы имеем , можно записать MATH Если положить тогда приходим к следующей оценке MATH

Определим функцию , полагая и покажем сейчас, что эта функция ограничена. Выведенная выше оценка переписывается в виде MATH

Подберем такую константу , что для имеем для всех и для таких будет выполняться неравенство MATH

Предположим теперь, что и зададим по индукции последовательность, полагая и для $j\geq 1$ . Такая последовательность $x_{j}$ является неограниченной убывающей последовательностью. Прежде всего функция ограничена на и мы по индукции покажем, что она имеет ту же границу на : в самом деле,

если , тогда и если по предположению индукции имеем для всех , тогда MATH

Осталось заметить, что также ограничена на $\left[ 1,M\right]$ .

Lemma

Пусть удовлетворяет условию , где $\phi _{i}$ те же, что и выше. Если такое вещественное число, что , тогда число элементов множества в шаре $B\left( x\right)$ ограничено снизу величиной $cx^{r}$ для некоторой постоянной и достаточно больших .

Proof

Используем обозначения из доказательства предыдущей леммы. Поскольку для $f\in F_{i}$ и имеем и тогда MATH где . Теперь достаточно показать, что определенная условием ограничена снизу, что доказывается по той же схеме, как и в предыдущей лемме.

Theorem

$\$ Пусть . Тогда понятие размерности определено корректно и .

Proof

Предположим, что , где $\phi _{i}$ и $\psi _{i}$ линейные функции $a_{i}x+b_{i}$ и $c_{i}x+d_{i}$ . Предположим, что . Мы должны показать, что $\alpha =\beta$ . Предположим, напротив, что $\alpha <\beta$ . Вставим между ними числа : $\alpha <s<r<\beta$ . Поскольку и мы получаем для достаточно больших , и поскольку и , то приходим к неравенству для достаточно больших , что противоречит сделанному допущению. Итак, $\alpha =\beta$ .

Предположим, что арифметические фракталы представлены в виде и для таких же функций $\phi _{i}$ и $\psi _{i}$ как и выше. Пусть . Покажем, что $\alpha \leq \beta$ . Предположим, что $\alpha >\beta$ и вставим между ними вещественные числа : $\beta <s<r<\alpha$ . Рассуждая как выше, приходим к противоречию.

Самоподобные структуры в алгебре и анализе

2.Самоподобная группа

3.Разложение по комплексному основанию

Теорема (Гильберт [32]), Если (b, D) - действительный базис, то D - полная система вычетов для $\U{2124} [i]$ и следовательно содержит элементов.

Доказательство Предположим , $a_{j}\in D.$ Тогда $z\equiv a_{0}$ . Следовательно содержит полную систему вычетов для . Теперь, предположим, что $c,d\in D$ неравны и . Тогда пусть , $a_{j}\in D.$ так, что . Следовательно, $(c)_{b}$ и , - два отличных адреса , откуда следует, что не действительный базис. '

Теорема 1.3.10 (Гильберт [34]) Каждый $z\in C$ имеет бесконечное разложение по степени основания в действительном базисе. Однако, это расширение может не обязательно быть единственным.

Доказательство использует то, что, если - действительный базис для $\U{2124} [b]$ , то каждый элемент имеет бесконечное разложение по основанию системы счисления . Здесь используется специальная норма на . Из того факта, что изоморфно $\U{2102}$ следует теорема.

Таким образом, имеет смысл ввести понятие фундаментальной или главной плитки действительного базиса.

Definition

Для заданного действительного базиса определим фундаментальную или главную плитку как множество комплексных чисел с нулевой целой частью в этом базисе.

По теореме .Гилберт показывает, что фундаментальные плитки комплексного базиса могут быть порождены с помощью СИФ. В самом деле, фундаментальная плитка комплексного базиса есть аттрактор СИФ вида MATH

MATH

MATH

MATH

MATH

Есть различные алгоритмы для того, чтобы определить представление Гауссовых целых чисел в действительном ядре. Они происходят из-за Гильберта [30, 33, 34, 35

Алгоритм 1.3.16 (Основной Конверсионный Алгоритм) (Гильберт [34]) Позволял (b, D) быть действительным ядром. Так как - полная система остатка для тогда, для заданного , существует единственные целые числа и $a_{j}\in D$ , , $t\in \U{2115} _{+}$ таким образом, что

Учитывая рациональное число, есть Длинный Алгоритм Раздела для того, чтобы найти представление [35]. Алгоритм 1.3.18 (Длинный Алгоритм Раздела) Позволял (b, D) быть действительным ядром для C. Учитывая Гауссовы целых числа v и w = 0, там существует ∈ Z [я], и цифры aj ∈ D, таким образом что

Так как целочисленная часть A может быть представлена в ядре (b, D), мы получаем представление v/w в этом ядре. Кроме того, любое расширение может быть получено таким образом. Проверьте разделитель внутренних полей использования доказательства. Это также использует Алгоритм Времени Escape, чтобы показать что, с данным набором остатка, последовательностью ограниченного пребывания остатков.

Есть также алгоритм для того, чтобы найти, что остаток установил [35]. Этот набор может быть найден, рассматривая ориентированный граф по Z [я]. Однако, это вовлекает определение, какие целые числа в шаре радиуса M\w \ / (\ b \ - 1), где М. является наибольшим модулем элементов D, являются остатками. Так как b установлен, этот шар растет быстро с \w \. Например, учитывая ядро (-1 + я, {0, 1}) и w = 1000, шар содержит приблизительно 2 Ч 106 целых чисел. Огромное количество вычисления обязано встраивать этот граф. Действительно, наша первая попытка связать небольшие волны и сложные ядра использовала этот подход. Для 512 Ч 512 изображений, w = 512. Используя Альфу в КОРПОРАЦИИ DIGITAL, оценки указали, что неуправляемые времена вычисления будут обязаны выполнять алгоритм набора остатка, уже не говоря о выполнить длинный раздел. Быстрый алгоритм, названный Очищающимся Алгоритмом, также существует для того, чтобы найти расширение целых чисел в ядрах формы (b, D) где D ⊂ Z. Для простоты мы рассматриваем только ядра (-n + я, {0, 1..., n2}), n ∈ N +. Читатель упомянут [30] для общего результата

Алгоритм 1.3.19 (Очищающийся Алгоритм) (Гильберт [30]) Рассматривает действительное ядро (-n+ я, {0, 1..., n2}), и позволяют p (x) быть минимальным полиномиальным из b = -n + я. Таким образом

Тогда представление любого целого числа z ∈ Z [я] в ядре могу быть получен следующим образом: Начните с z = м. (b) = akbk + . . . + a1b + a0, расширение z в степенях b с целочисленными коэффициентами. Например, любое Гауссово целое число c + система обнаружения атак может быть расширено в степенях b = -n+i как c+id = децибел + (c+nd). Рассмотрите это расширение как элемент м. (b) полиномиального кольца Z [b]. Позвольте r быть наименее целочисленным таким образом что площадь / ∈ D. Если никакой такой r не существует, то м. (b) является уникальным расширением z в ядре. Мы называем такое полиномиальное ясное. Если r существует, то s, которым позволяют, - целое число таким образом что 0 ≤ площадей + s (n2 + 1) ≤ n2. Добавьте sbr времена p (b) к м. (b). Помните, что мы выполняем эту операцию в полиномиальном кольце Z [b]. Назовите этот новый полиномиальный m1 (b). Однако, p (-n + i) = 0, таким образом м. (b) и m1 (b) равен в C. Следовательно, m1 (b)

расширение z в Z [b]. Кроме того, коэффициент r-th мощности b в m1 (b) является цифрой. Мы говорим, что площадь была очищена. Повторите процесс очищающихся коэффициентов, индукцией на r, пока ясное полиномиальное не получено. Получающееся полиномиальное обеспечивает расширение z в (b, D). Этот процесс должен закончиться после конечного числа шагов. Пример 1.3.20 Определяет расширение 5 + 12i в ядре (-2 + я, {0, 1, 2, 3, 4}). Минимальный полиномиальный из b = -2 + я - x2 + 4x + 5. Следовательно, b2 + 4b + от 5 до 0 и, неправильным обращением примечанием, мы можем написать этому как (1 4 5) b = 0. (Отметьте, что 5 не находится в.) набора цифры, Начинаются с расширения 5 +12i = 12b+29 = (12 29) b. Тогда, мы очищаем полиномиальное в

Следовательно, расширение 5+12i в ядре (-2+i, {0, 1, 2, 3, 4}) (2324). Быстрое вычисление проверяет, что это действительно правильно. Учитывая его общность, мы использовали Основной Конверсионный Алгоритм, чтобы вычислить адреса в наших приложениях, которые будут обсуждены в Главе 3

плитки

стр 28-30 в самой работе Malone. Интересны только картинки

2.5.1 Фрагментации изображения решетки Rn В R наша хорошая функция генерации были характерной функцией для некоторого набора. Возможный способ обобщить это состоит в том, чтобы искать, для других подходящих характерных функций. Один хорошо изученный путь (см. [15]) выполнения этого состоит в том, чтобы искать компактный Г набора со следующими свойствами (до нуля меры): 1. У г есть отличные трансляции, то есть. Г \(Г + ~r) =; для ~r 2 Зоны n f0g. 2. AG, которая расширенная версия Г может быть написана как объединение ее трансляций, то есть мы можем без обозначения даты пункты ~k1;:::; ~kq так, чтобы:

3. Г покрывает Rn трансляцией.

rst этих условий говорит нам что транслирование Г являются ортогональными. Второе говорит нам что Г достаточно es уравнение расширения и последнее говорят нам, что мы можем добраться до любой части Rn. Фактически ~k1;:::; ~kq оказываются представители эквивалентных классов AZn=Zn, которого есть q = j detAj. Замечательно, набор с этими свойствами даже генерирует анализ мультиразрешающей способности. Существование таких наборов - даже бетон

воздух. Любой кандидат на такой набор, как могут показывать, имеет форму:

Об этом суммировании можно думать как ядро расширение пунктов в Rn использование цифр ~k1;:::; ~kq и по этой причине набор f~k1;:::; ~kqg упоминается как набор цифры. Для примера, если мы берем = 2 и k1 = 0; k2 = 1, тогда мы добираемся:

который является двойным расширением чисел между 0 и 1, таким образом мы добираемся [0; 1) назад снова. У этих наборов кандидата есть желательные свойства i

их мера 1. Иллюстрация 2.2 показывает различный Г наборов с их расширениями A и наборы цифры. Отметьте, что тот же самый A может произвести радикально di

Г erent, если di

наборы цифры erent выбраны. Следующий вопрос: Данный A, когда мы можем выбрать набор цифры, который произведет Г меры 1 использование вышеупомянутый рецепт? В литературе ответ к этому вопросу выглядит скорее сложным. Чтобы подвести итог параграфа [49], ответ - `Always' в $\U{211d} ^{n}$ для n = 1; 2; 3 и `Always', если j detAj> n; однако, ответ - вероятно `Sometimes' вообще. Ко времени [28] был издан, контрпример в $\U{211d} ^{4}$ был найден Potiopa:

Метод исчерпания, как способ построения самоподобных множеств

Метод исчерпания понимается здесь в том смысле, что образуется последовательность $K_{n}$ вложенных друг в друга компактов, содержащих выделенный набор точек , причем части содержашие эти точки становятся с ростом все более похожими на весь компакт $K_{n}$ . В пределе, то есть в множестве $K=\cap K_{n}$ выполняется свойство , причем $K_{\infty ,i}$ подобны . Каждый последующий компакт получается из предыдущего удалением из него относительно открытого в $K_{n}$ подмножества $U_{n}$ : , $\ldots$ .

Приведем примеры.

Салфетка Серпинского

Ковер Серпинского

Пятиугольная салфетка.

Кривая Коха

Та же идея исчерпания может быть использована, если задан набор попарно непересекающихся компактов

удовлетворяющих следующему условию: существует такое $\xi >0$ ,что для всех $j=1,\ldots ,\nu$ компакт $E_{j}$ является дизъюнктным объединением $a_{1j}$ частей подобных $E_{1}$ с коэффициеном подобия $\xi$ , далее дизъюнктным объединением $a_{2j}$ частей подобных $E_{2}$ с коэффициеном подобия $\xi$ , ...и дизъюнктным объединением $a_{i\nu }$ частей подобных $E_{\nu }$ с коэффициентом подобия $\xi$ .

Таким образом, $E_{j}$ состоит из попарно не пересекающихся частей. Если предполагать, что матрица с целыми неотрицательными коэффициентами является примитивной, то есть некоторая степень матрицы является положительной, тогда говорим, что семейство компактов есть -совершенное семейство (-parfaits).

§ числовые инварианты

По теореме Перрона-Фробениуса транспонированная матрица $A^{t}$ имеет собственное число $\lambda >0$ ,

превосходящее по модули все другие собственные числа. Полагаем . Тогда $\alpha$ является

размерностью Хаусдорфа всякого компакта $E_{j}$ . См.[].

В результате получается самоподобное множество, внешне тесно связанное с конкретным процессом построения монотонно убывающей последовательности компактов. Однако, если ввести на пространстве всех непустых компактов метрику так, чтобы монотонно убывающая последовательность компактов являлась сходящейся в этой метрике и установить полноту такого метризованного пространства компактов, тогда появляется значительный произвол в выборе сходящейся последовательности, что представляет несомненное удобство при реализации изображения самоподобного множества. Все это реализуется введением метрики Хаусдорфа.

Метрика Хаусдорфа

Пусть $\left( E,d\right)$ метрическое пространство. Если $x\in E$ , $A\subset E$ -- подмножество, полагаем MATH

, .

Отметим, что

Если $A\neq \varnothing$ , тогда
является открытой окрестностью множества .

Proof

если . Отсюда . Мы заключаем

$\forall z\in A$ откуда

. Аналогично . Отсюда выводим неравенство .
Так как и , то , откуда следует, что открыто.

Definition

Метрическое пространство называется вполне ограниченным, если для всякого $\varepsilon >0$ существует конечное покрытие пространства множествами диаметра меньшего $\varepsilon$ .

Хорошо известно, что следующие три условия эквивалентны:

Пространство компактно.
Любая бесконечная последовательность в имеет по крайней мере одну предельную точку.
Пространство является полным и вполне ограниченным.

Пусть $C\left( E\right)$ -- множество всех непустых компактных подмножеств метрического пространства . Для положим MATH

является метрикой (она именуется метрикой Хаусдорфа)
,
Если $\left( E,d\right)$ -- полное метрическое постранство, тогда также полное метрическое пространство
Если компактное метрическое пространство, тогда $C\left( E\right)$ также компактное метрическое пространство.

$\Longrightarrow$ . Таким образом, $\Longrightarrow$ . Так как компактно, то оно и замкнуто. Поэтому влечет $x\in B$ . Итак $A\subseteq B$ . По симметрии $B\subseteq A$ , следовательно .Симметричность очевидна. Проверим справедливость неравенства треугольника. Пусть . ТогдаКроме того, . Отсюда . Аналогично . Отсюда следует
Действительно, . Вместе с тем, . Аналогично, .Отсюда следует утверждение.
Пусть $X_{n}$ последовательность Коши в $C\left( E\right)$ , то есть последовательность компактов в . Полагаем . Из определения последовательности следует, что для всех . Но в полном метрическом пространстве всякая убывающая последовательность замкнутых множеств имеет непустое пересечение. Полагаем $\cap Y_{n}=X$ . Покажем, что $\lim X_{n}=X$ . Пусть , $y\in Y_{n}$ , . Поскольку и последовательность $X_{n}$ фундаментальная, то , что . В этом случае , откуда .Но тогда . Итак, . Осталось показать, что $Y_{n}$ компактные множества. Пусть число таково, что для всех . Для всякого $X_{n}$ , найдется конечное множество $F_{n}\subset X_{n}$ , что для всех $x\in F_{n}$ . Рассмотрим множество . Ясно, что это множество вполне ограниченное и замкнутое и потому компактное. Если $x\in X_{n}$ , , тогда и поэтому . Итак, , откуда следует, что $Y_{n}$ замкнутое и ограниченное множество, а следовательно компактное для всякого
Пусть $\varepsilon >0$ . Найдется такое конечное , что для всех $x\in E$ . Пусть . Пусть . По условию для всякого $y\in A$ найдется $x_{0}$ , что . Отсюда . Таким образом, множество обладает свойством $\varepsilon$ -сети. Это означает, что $C\left( E\right)$ вполне ограничено и на основании предыдущей теоремы является компактом.

Рассмотрим теперь произведение метрических пространств ( раз) и определим метрику $h^{N}$ , полагая MATH

Theorem

Метрическое пространство является полным метрическим пространством

Метрика на пространстве адресов

Системы итерируемых функций (СИФ)

Система итерируемых функций, как идея, содержится в конструкции разложения вещественного числа по заданному основанию. Менее тривиально разложение числа по комплексному основанию, например по основанию . Более точно, всякое комплексное число $z\in \U{2102}$ возможно представить в виде MATH

В представленном разложении слагаемые с неотрицательными степенями основания образуют так называемую целую часть . Множество всех комплексных чисел с нулевой целой частью образует так называемую фундаментальную область числовой системы и это множество является двойным драконом, см. § Самоподобные структуры в алгебре и анализе, поскольку оно удовлетворяет условию самоподобия MATH

Definition

Пусть $\left( E,d\right)$ -- полное метрическое пространство и - семейство сжимающих отображений . Такое семейство называется (iterated function system)-- системой итерируемых функций или СИФ.

Дальнейшее изложение требует обращения к известному принципу сжимающих отображений. Для удобства напомним его точную формулировку.

Отображение $f:E\rightarrow E$ называется сжимающим с коэффициентом сжатия , , если для всех $x,y\in E$ выполняется неравенство MATH

Theorem

(Банаха о неподвижной точке). Если -- полное метрическое пространство и отображение $f:E\rightarrow E$ -- сжимающее, тогда существует единственная неподвижная точка $x_{0}$ отображения . Кроме того, какова бы не была начальная точка $x_{1}\in E$ , последовательность точек определяемая индуктивно правилом , $n=1,2,\ldots$ , сходится к неподвижной точке $x_{0}$ .

Теорема Банаха о неподвижной точке или принцип сжимающих отображений применимо к пространству компактов с метрикой Хаусдорфа , поскольку в предудущем параграфе была установлена его полнота.

Theorem

(Hutchinson 1981). Пусть -- полное метрическое пространство и - семейство сжимающих отображений . Существует единственное компактное множество $K\subset E$ , причем MATH

Proof

Определим отображение (отображение Хатчинсона) MATH

полагая MATH

Покажем, что отображение $\digamma$ является сжимающим с коэффициентом сжатия относительно метрики Хаусдорфа . В самом деле, если , тогда если и только если существует $a\in A$ , причем . Действительно, если , тогда . В силу непрерывности функции , $a\in A$ и компактности , найдется элемент $a\in A$ для которого . Обратно, если для некоторого $a\in A$ выполняется , тогда , то есть . Если , тогда . В самом деле, если , тогда найдется $b\in B$ для которого . Итак, ; для этого элемента выберем , где $b\in B$ уже выбран ранее. Тогда . Тогда согласно а откуда и следует включение.

Очевидно, что для всех $i=1,2,\ldots ,m$ . Отсюда вытекает включение , то есть , если . По симметрии, если , тогда .Из определения метрики Хаусдорфа, приведенного в замечании после теоремы следует, что , . Из определения метрики Хаусдорфа следует, что , если и . Таким образом, MATH Приведем еще одно доказательство последнего неравенства.

Lemma

Для MATH В общем случае, для MATH

Если , тогда и . Поэтому . Аналогично . Следовательно, . Отсюда следует первое неравенство. Второе неравенство следует из первого индукцией по .

Lemma

Если является сжатием с коэффициентом сжатия , тогда для любых справедливо неравенство MATH

Если и , тогда . Аналогично, . Таким образом, откуда и следует лемма.

Поскольку пространство $C\left( E\right)$ полно в метрике Хаусдорфа, а отображение Хатчинсона $\digamma$ по отношению к этой метрике является сжимающим, то по теореме Банаха существует единственная неподвижная точка : . Но это соотношение равносильно утверждению теоремы.

Remark

Построенное в теореме компактное множество называется также притягивающим множеством для СИФ или аттрактором. Оно является самоподобным в том смысле, что является конечным объединением подобных себе частей. Далее будет показано, что несет также структуру самоподобия в смысле Кигами (Kigami []).

Разберем теперь вопрос о непрерывной зависимости аттрактора $K\left( F\right)$ при непрерывном изменении СИФ .

Theorem

Пусть -- метрическое пространсво, -- полное метрическое пространство, -- семейство сжимающих отображений с пространством параметров . Иными словами, $f_{p}:$ является сжимающим отображением с коэффициентом сжатия $r_{p}$ для всякого $p\in P$ . Кроме того, -- непрерывная функция для всякого фиксированного $x\in E$ . Тогда неподвижная точка $x_{p}$ отображения непрерывно зависит от параметра .

Proof

Пусть $p\in P$ и $\varepsilon >0$ . Тогда для всякого $q\in P$ MATH Эти соотношения следуют из определения сжимающего отображения и неравенства треугольника. Таким образом, MATH Отображение непрерывно для всякого фиксированного $x\in E$ , и поэтому найдется такое $\delta$ , что MATH как только (при условии) .Поэтому если , тогда MATH Это показывает, что является непрерывным отображением.

Theorem

Пусть -- компактное метрическое пространсво, -- полное метрическое пространство, , $i=1,\ldots ,n$ -- семейство непрерывных отображений и --отображение Хатчинсона MATH Тогда непрерывно для всякого .

Proof

Пусть $\varepsilon >0$ и . Функции $f_{i}$ непрерывны на компакте $P\times C$ и поэтому равномерно непрерывны. Поэтому найдется такое $\delta$ для которого как только . Предположим, что . Тогда для всех $c\in C$ . Поэтому из определения метрики Хаусдорфа вытекает и следовательно . Поэтому отображение непрерывно для всякого .

Theorem

Пусть -- метрическое пространство, -- полное метрическое пространство, , $i=1,\ldots ,n$ -- семейство непрерывных отображений. Пусть -- аттрактор СИФ , $p\in P$ . Тогда отображение непрерывно.

Proof

По теореме $\digamma$ непрерывно зависит от для всякого фиксированного . По теореме его неподвижная точка непрерывно зависит от .

Theorem

Пусть и -- метрические пространства, , --непрерывное семейство сжимающих преобразований подобия, то есть MATH Тогда функция является непрерывной.

Proof

Пусть $\varepsilon >0$ и пусть $x,y\in E$ , причем $x\neq y$ . Тогда MATH Аналогично MATH Вычитая и комбинируя выведенные выше неравенства мы получаем MATH Выберем такое $\delta >0$ , что в случае тогда выполняется неравенство MATH Поэтому, если , то MATH Поскольку -- преобразование подобия, отсюда MATH и тем самым . Таким образом, функция является непрерывной.

Непрерывная зависимость инвариантов СИФ в метрике Хаусдорфа тесно связана с теоремой о коллаже, а именно

Definition

Скажем, что СИФ удовлетворяет условию OSC или условию открытого множества (OSC -- open set condition) , если существует такое относительно компактное открытое непустое собственное множество , что выполнены условия 1 и 2

, $i=1,\ldots ,m$
если $i\neq j$

Будем говорить, следуя Barnsley, что является бассейном притягивающего множества $K\left( F\right)$ .

Example

Рассмотрим пространство бесконечных слов $W_{N}^{\infty }$ и зададим на нем метрику, в которой оно полно, а отображения $\sigma _{i}$ являются сжимающими.

Для двух слов $\alpha$ и $\beta$ обозначим через такое число для которого MATH Если , тогда , если для всех $m\geq 1$ , тогда .

Для $0<\delta <1$ полагаем MATH

Возможно некоторое обобщение этой конструкции. Зададим набор чисел , $0<\delta _{i}<1$ , $i=1,\ldots ,N$ , и, используя те же обозначения, полагаем MATH

Theorem

Отображение является метрикой, метрическое пространство является компактным метрическим пространством, а отображения $\sigma _{i}$ являются сжимающими с коэффициентом сжатия $\delta _{i}$ .

Example (Геометрическая орграф-конструкция)

Геометрическая орграф конструкция в $\U{211d} ^{m}$ по [20,p.811]состоит из

конечной последовательности непересекающихся компактных подмножеств в $\U{211d} ^{m}$ : таких, что каждое $J_{i}$ имеет непустую внутренность
орграфа с вершинами и преобразованиями подобия $T_{i,j}$ пространства $\U{211d} ^{m}$ , где и $t_{i,j}$ -- их коэффициенты подобия, причем
1. для всякого , $1\leq i\leq n$ , найдется такое , что ,
2. для всякого , $1\leq i\leq n$ множество состоит из непересекающихся подмножеств и
3. если путь в графе является циклом, то есть $i_{q}=i_{1}$ , тогда

взвешенная матрица инциденции или матрица (геометрической) конструкции , ассоциированная с орграф конструкцией есть матрица , где мы следуем соглашению, что $t_{i,j}=0$ , если . Для всякого $\beta \geq 0$ , пусть $n\times n$ - матрица, заданная условием $A_{\beta }=$ . Пусть -- спектральный радиус матрицы $A_{\beta }$ . Согласно теореме Перрона-Фробениуса величина равна наибольшему неотрицательному собственному значению матрицы $A_{\beta }$ .

Theorem

, функция $\Phi$ непрерывная, строго монотонно убывающая и . Более точно, существует такое , , что для всех $\beta \geq 0$ и $\varepsilon >0$ ,.

Theorem

Если -- строго связные компоненты графа , тогда MATH

Example (Единичный отрезок)

Единичный отрезок является аттрактором СИФ , где , MATH Открытое множество удовлетворяет условиям 1,2 и поэтому СИФ $F_{C}$ удовлетворяет условию открытого множества.

Example (Квадрат)

Квадрат является аттрактором СИФ , где , MATH

Example (Множество Кантора)

Канторово множество является аттрактором СИФ , где , MATH

Открытое множество удовлетворяет условиям 1,2 и поэтому СИФ $F_{C}$ удовлетворяет условию открытого множества.

Example (Салфетка Серпинского)

. Рассмотрим три точки на плоскости , , , не лежащие на одной прямой. Зададим СИФ , где , , условием MATH

Аттрактор СИФ $F_{S}$ совпадает с салфеткой Серпинского.

Example (Кривая Х. Коха (1927))

. Кривая Коха является аттрактором СИФ , где , MATH

Заметим, чтоявляются СИФ из примера 1. Ниже изображена так называемая снежинка Коха -- результат трехкратного повторения кривой Коха по отношению к сторонам равностороннего треугольника

Example (Dragon Heighway)

Дракон Хартера-Хэтуэя является аттрактором СИФ , где , MATH

D:\fractals\Fractals\Programs\IFS Builder3D1.6-win\IFS Builder 3d v1.6

Remark

В работе 100404\1\+23paper.ps Sze-Man Ngai and Nhu Nguyen The Heighway dragon revisted 2001 26pp доказано, что дракон является счетным объединением плоских дископодобных плоских множеств, которые персекаются между собой друг с другом в линейном порядке: любые два персекаются не более чем в одной точке и для любых трех дисков по крайней мере два не пересекаются (не имеют общих точек)

Remark

Можно поставить общую задачу: задан СИФ . Извлекаем из каждого корень -ой степени. Получаем в общем случае ,, $p\geq 1$ . Как меняется вид аттрактора при росте ? Более продуктивным является понятие сдвинутого(смещенного) корня, см. дипломную Болек

Example (Levi's dragon)

Кривая Леви. Эта "кривая" является аттрактором СИФ , где , MATH

Example

Ветка Хата (Hata's tree-like set) MATH ,где ,. На рисунке $c=0.4+0.3\sqrt{-1}$ .

Example

В этом примере объясняется, ким образом можно поднять самоподобное множество с плоскости в группу Гейзенберга $\QTR{Bbb}{H}$ . В явном виде $\QTR{Bbb}{H}$ отождествляется с , а групповой закон умножения $\ast$ задается правилом MATH где --оператор умножения на мнимую единицу MATH и стандартное скалярное произведение в $\U{211d} ^{2}$ . Группа Гейзенберга снабжена неевклидовой метрикой -- так называемой метрикой Гейзенберга. Это левоинвариантная метрика на $\QTR{Bbb}{H}$ , определенная следующим образом MATH где $\ast$ обозначает определенное выше произведение в группе, а обозначает норму Гейзенберга MATH пусть аффинное отображение вида MATH где является $2\times 2$ матрицей, и . В этом случае является липшицевым по отношению к метрике $d_{H}$ если и только если выполняются соотношения MATH Таким образом, всякое липшицево аффинное отображение является поднятием аффинного отображения с $\U{211d} ^{2}$ на $\QTR{Bbb}{H}$ и оно задается правилом MATH где MATH и $\tau$ -- вещественная константа. Константа Липшица для как отображения в группе Гейзенберга с инвариантной метрикой равна константе Липница для как отображения в . Далее, является подобием относительно $d_{H}$ если и только если выполяются выписанные выше соотношения и является конформной матрицей, в этом случае константа Лишица совпадает с операторной нормой линейной части .

Системы итерируемых функций на комплексной плоскости, состоящие из двух сжимающих подобий допускают следующую простую классификацию: если считать, что у каждой пары неподвижными точками являются и , тогда эти пары разбиваются на четыре класса, где , а замыкания образов решений соответствующих функциональных уравнений представляют самоподобные множества бинарной системы итерируемых функций

Definition

Компактное множество называется рацинальным -замощающим множеством () на плоскости $\U{2102}$ , если оно удовлетворяет уравнению MATH

для некоторых и $a_{j}\in \U{2102}$ , причем все разности являются рационально кратными $\pi$ . Рацинальным n-замощающее множество называется рацинальньным n-rep-тайлом, если оно является n-rep-тайлом.

Мы будем использовать в этом случае также термин рациональная фрактальная n-плитка.

В случае СИФ, задающая -тайл имеет вид , где MATH

Theorem

Пусть рациональное 2-замощающее множество, удовлетворяющее каноническому уравнению MATH

Тогда является 2-rep-тайлом, если и только если принимают одно из следующих значений

(a) $\phi =k\pi /4$ , $\theta =l\pi /2$ , где и $l\in \U{2124}$ и, кроме того, -- нечетное

(b) $\phi =k\pi /2$ , где -- нечетное, $\theta =0$ , или $\theta =\pi$

(\c) , где , $\theta =0$ или $\theta =\pi$ .

Будем говорить, что два тайла эквивалентны если один получается из другого композицией операций растяжения, параллельного переноса, поворота и отражения

Theorem

Имеется в точности шесть неэквивалентных рациональных 2-рептайлов на плоскости. Эти классы эквивалентности имеют параметры , представленные следующими парами MATH

Таким образом, СИФ рационального 2-рептайла и ее аттрактор имеет один из следующих видов:

№ 2-рептайл

1 двойной дракон (twindragon)

2 дракон Леви (Lévy dragon)

3 Heighway dragon

4 triangle

5 rectangle

6 скучный двойной дракон (tame twindragon)

Здесь весьма уместно напомнить определение функции Вейерштрасса $w\left( x\right)$ -- непрерывной и не имеющей производной ни в одной точке MATH указать функциональное уравнение, которому она удовлетворяет

MATH и для , построить график функции Вейерштрасса .

График

является , грубо говоря, самоаффинным, в том смысле, что и это заставляет предполагать, что . Для выбранных значений и размерностьХаусдорфа оценивается как

Перейдем теперь к более сложной конструкции граф-ориентированной СИФ

Рассматриваем адресное отображение вида MATH

где множества всех ребер, входящих в вершины с номерами $1,\ldots ,N$ соответственно

MATH

Если отождествить , тогда элементы этих множеств можно считать целыми числами, снабженными индексом, указывающим на номер алфавита.

Theorem

Определенное выше отображение $\Psi$ является сжимающим, а его неподвижная точка -- мультимножество обладает структурой $\Gamma$ -самоподобия.

Числовые и комбинаторные инварианты самоподобных множеств

характеристика Э-П

граф смежности для замощения

фрактальные группы

Определим несколько элементарных и полезных для практических оценок числовых инвариантов самоподобного (или близкого к самоподобному) компакта -- так называемые "размерности".

Пусть $K\subset E$ , $\delta >0$ , , $A_{i}\subset E$ открытые подмножества,, -- мощность множества $\Lambda$ , . За исключением случая конечного множества величина при . Полагаем (так называемая верхняя граница (верхняя бокс-размерность).)
Аналогично определяется нижняя бокс-размерность компакта .
Наиболее известна размерность самоподобия (бокс-размерность) или размерность Минковского
Размерность Хаусдорфа также определяется через покрытия, но несколько сложнее. Обычное определение размерности Хаусдорфа борелевского множества следующее. Для $s\geq 0$ и $\delta >0$ определим

где обозначает диаметр непустого множества и $\inf$ берется по всем счетным наборам множеств для которых и . При убывании $\delta$ , не убывает и и поэтому имеет предел, (возможно, бесконечный) при . Определим MATH

Величина известна как -мерная мера Хаусдорфа множества . Можно показать для заданного , что существует величина для которой при и для . Размерность Хаусдорфа определена как такое число , то есть MATH

Отметим несколько простых свойств мер Хаусдорфа глава1 стр 6,7

Theorem (Скейлинг свойство)

Если и $\lambda >0$ , тогда MATH где .

Proof

Если открытое $\delta$ -покрытие , тогда является открытым $\lambda \delta$ -покрытием множества $\lambda F$ . Поэтому, MATH Вычисляя $\inf$ суммм получаем неравенство MATH Чтобы установить противоположное неравенство начнем с очевидного неравенства MATH и умножим обе части на $\lambda ^{s}$ . Мы видим, что MATH поскольку . Снова вычисляя $\inf$ сумм мы получаем, что MATH из () и() видим что . Устремляя $\delta$ к получаем требуемое равенство .

Множество $\lambda F$ является образом относительно гомотетии $x\mapsto \lambda x$ и доказанная только что теорема указывает связь меры Хаусдорфа множества с мерой его образа $\lambda F$ . Если отображение MATH имеет равномерный ограниченный рост, а именно, удовлетворяет свойству MATH тогда возможно лишь указать неравенство между мерами Хаусдорфа образа и прообраза.

Theorem

Если отображение $f:F\rightarrow F$ обладает свойством MATH для некоторых $\alpha >0$ и , тогда для всякого выполняется неравенство MATH и неравенство MATH между размерностями Хаусдорфа образа и прообраза.

Proof

Пусть , где $x,y\in U_{i}$ и выполнятся неравенство . Таким образом, если открытое $\delta$ -покрытие , тогда является $\varepsilon$ -покрытием образа $f\left( F\right)$ при . Отсюда заключаем, что из следует . Таким образом, MATH Вычисляя $\inf$ сумм мы видим, что MATH переходя к пределу при , получаем требуемое неравенство.

Доказательство второй части теоремы разбивается на три основных случая, поскольку -мерная мера Хаусдорфа может быть конечной, равной нулю или $\infty$ .

Пусть . Тогда по определению -мерной меры Хаусдорфа MATH . Отсюда видим, что , поскольку мера множества больше нуля. Снова пользуясь определением заключаем, что . Вычисляя по всем , мы видим, что .

теперь предположим, что $s<\dim _{H}F$ . В этом случае . Это означает, что либо равно , либо положительное и конечное, либо равно $\infty$ . Разберем по отдельности все три случая.

: Это почти тривиально. По предположению $s<\dim _{H}F$ , поэтому
: Этот случай подобен случаю выше.
: Поскольку , то так как .

Следующая теорема описывает зависимость размерности Хаусдорфа от непрерывного параметра в системе итерируемых функций.

Theorem

Пусть и метрические пространства. Пусть система итерируемых функций непрерывно зависящая от параметра $p\in P$ . Предположим, кроме того, что функции являются сжимающими преобразованиями подобия и удовлетворяют условию открытого множества для всякого $p\in P$ . Пусть $K\left( p\right)$ аттрактор . Тогда размерность Хаусдорфа самоподобного множества $K\left( p\right)$ является непрерывной функцией от .

Proof

Пусть задано условием . Пусть . Так как (поскольку) и найдется $s\in \U{211d} _{+}$ для которого на основании теоремы о промежуточных значениях. Так как строго убывающая функция по переменной , существует единственное удовлетворяющее этому уравнению. Обозначим так определенную функцию через . Поскольку MATH для всякого , теорема о неявной функции влечет непрерывность функции по переменной . В силу произвольности функция непрерывна всюду. Пусть коэффициенты сжатия для преобразований подобия . Полагаем . На основании предыдущих результатов функция является непрерывной. Таким образом, композиция -- непрерывная функция. Поскольку выполняется условие открытого множества, является размерностью Хаусдорфа аттрактора $K\left( p\right)$ СИФ . Теорема доказана.

Такое определение используется для определения верхней границы размерности Хаусдорфа множества .

Верхняя граница может быть получена прямой проверкой с использованием специальных покрытий множествами малого диаметра, и если показано, что конечно для некоторого , тогда . Однако нижнюю границу получить непосредственно более трудно, поскольку должны быть использованы все покрытия .

Другое определение размерности Хаусдорфа может быть получено в терминах -энергии борелевской меры $\mu$ , сосредоточенной на и определяемой как MATH

Можно показать (см. например, [5],[15] и ниже), что если , для всех мер $\mu$ , с носителем на , в то же время, если , тогда существует мера $\mu$ , сосредоточенная на , такая, что .

таким образом, все это можно представить в виде MATH

Proposition

Для кривой Коха как размерность Минковского, так и размерность Хаусдорфа равны .

Proof

Возьмем ,множество $C_{n}$ является объединением $4^{n}$ интервалов длины $3^{-n}$ . Покроем $C_{n}$ кругами диаметра $\varepsilon _{n}$ , окружая каждое ребро кругом радиуса с центром в середине отрезка. Таким образом, .

Далее, легко видеть, что любой круг диаметра $\varepsilon _{n}$ пересекающий $C_{n}$ , может пересечь не более двух интервалов из $C_{n}$ , и поэтому . Для всякого $\varepsilon >0$ мы можем выбрать так, что . Но тогда MATH

Устремляя видим, что . Равенство , будет установлено позже.

Proposition

Для канторова множества , состоящего из тех чисел единичного интервала троичное разложение которых имеет только цифры и , MATH размерность Минковского, а также размерность Хаусдорфа равны .

Proof

Полагая можно покрыть множество Кантора $2^{n}$ интервалами вида MATH

длины $\frac{1}{3^{n}}$ . Осюда заключаем, что .

Далее, легко видеть, что любой интервал длины $\varepsilon _{n}$ пересекающий $V_{n}$ , может пересечь не более двух интервалов из $C_{n}$ , и поэтому . Для всякого $\varepsilon >0$ мы можем выбрать так, что . Но тогда MATH

Устремляя видим, что . Равенство , будет установлено позже.

Example

Ковер Серпинского. пусть MATH

Это связное множество не имеющее внутренности.

Proposition

Для ковра Серпинского размерность Минковского и размерность Хаусдорфа равны

Proof

Полагая можно покрыть множество посредством $8^{n}$ квадратов со стороной $\frac{1}{3^{n}}$ : MATH

далее, легко видеть, что нельзя покрыть $X_{n}$ меньшим числом квадратов. Для всякого $\varepsilon >0$ мы можем выбрать так, что . Но тогда MATH

Устремляя видим, что . Равенство , будет установлено позже.

Меры и принцип распределения масс.

Обычный способ получения нижней границы размерности Хаусдорфа состоит в использовании вероятностных мер. Мера $\mu$ на называется вероятностной мерой, если .

Proposition

Если для некоторой вероятностной меры $\mu$ найдутся и так, что выполняется неравенство для всех $x\in X$ и всех $\varepsilon >0$ , тогда $\dim _{H}X>d$ .

Proof

Пусть $\varepsilon >0$ . Рассмотрим произвольное открытое покрытие образованное такими шарами , $i=1,\ldots ,N$ , что . Поскольку $\mu$ вероятностная мера, имеем MATH откуда . Поскольку $\varepsilon$ была выбрана произвольно, то . Отсюда заключаем, что .

Этот результат можно использовать для того, чтобы завершить сравнение бокс-размерности и размерности Хаусдорфа в рассмотренных выше примерах.

Example

Множество Кантора. Теперь возможно установить равенство . Пусть $\mu$ -- вероятностная мера, которая задается весами $2^{-n}$ на каждом из $2^{n}$ интервалов $X_{n}$ в для любого $n\geq 1$ . Для и $\varepsilon$ удовлетворяющих неравенствам мы видим, что для любого $x\in X$ шар пересекает $X_{n}$ не более чем в двух точках. В частности, легко видеть, что . Поэтому, если положить , тогда . Применяя предложение, заключаем, что .

Example

Салфетка Серпинского. Пусть $\mu$ вероятностная мера, которая приписывает вес $4^{-n}$ каждому из $4^{n}$ квадратов в $X_{n}$ $\$ для всякого $n\geq 1$ . Для , $\$ подчиненого неравенствам мы видим, что для любого $x\in X$ шар пересекает $X_{n}$ не более чем по четырем квадратам. В частности, мы видим, что . Поэтому, если мы положим , тогда MATH

Применяя предложение, мы заключаем, что

Theorem

Для системы итерируемых функций , удовлетворяющей условию открытого множества справедливо равенство .

Proof

Неравенство . очевидно. Поэтому достаточно показать, что . Установим последнее неравенство, воспользовавшись принципом распределения масс. Полагаем . Мы покажем, что существует вероятностная мера $\mu$ на и константы $C_{1}$ , $C_{2}>0$ такие, что MATH

Существование такой меры вытекает из идей теродинамическогог формализма, с которым ознакомимся чуть позже. В частности, если , тогда MATH

Отсюда, на основании принципа распределения масс заключаем, что .

Еще один интересный инвариант является аналогом эйлеровой характеристики симплициального комплекса.

Этот инвариант (число Эйлера) связан с оценкой перекрываемости компонент самоподобного множества и может быть описан как предельная эйлерова характеристика замощения (см метод исчерпания) при измельчении самоподобной симплициальной аппроксимации. Например, для ковра Серпинского такая величина равна . Кроме того, имеется пример двух самоподобных множеств с равными размерностями Хаусдорфа и различными числами Эйлера.

Условие открытого множества и его обобщения

Условие открытого множества в теории самоподобных множеств появилось в 1946 году в работе Морена и далее в 1981 году в работе Хатчинсона было эффективно использовано для описания притягивающих множеств заданной системы итерируемых функций. Позже Шиф показал, что для системы итерируемых функций, состоящих из преобразований подобия евклидова пространства это условие равносильно положительности и конечности -меры Хаусдорфа, где -- размерность самоподобия притягивающего множества. Наконец, в работе Бандта и Графа было сформулировано алгебраическое условие открытого множества в тех же предположениях, что и в теореме Шифа. Позже были даны обобщения этих результатов на случай граф-ориентированных систем итерируемых функций.

Существование фрактальных самоподобных множеств

Theorem

(Hutchinson 1981). Если СИФ удовлетворяет условию открытости, тогда размерность Хаусдорфа аттрактора равна вещественному корню уравнения MATH

Proof

Для простоты, рассмотрим только случай СИФ, состоящей из двух отображений , , . удобно записать их коэффициенты сжатия в виде , , для некоторого $\alpha$ , $0<\alpha <1$ . Мы можем предполагать для простоты, что открытое множество из условия открытого множества является диском вида . Для мы можем рассмотреть покрытие шарами вида $T_{i_{1}}$ $\ldots T_{i_{m}}U$ , где выбрано из условия MATH

Пусть $M_{k}$ полное число таких дисков и пусть число дисков радиуса $\frac{1}{k}$ . Легко видеть, что найдутся константы $C_{1}$ , $C_{2}>0$ так, что MATH Например, мы можем рассмотреть MATH

где -- наибольшее целое меньшее, чем $\alpha n$ .

Если $T_{1}$ встречается раз, для некоторого $\beta$ , $0<\beta <1$ , тогда, для того, чтобы выполнялось неравенство ( $\ast$ ), требуется, чтобы $T_{2}$ встречалось приблизительно раз, всего будет.

Полное число дисков $M_{k}$ связано неравенствами MATH

и чтобы оценить эти неравенства нам требуется оценить .

Из формулы Стирлинга нам известно, при . Поэтому MATH

где $x=\alpha \beta$ , $y=1-\beta$ . Запишем и поставим задачу максимизации функции , подчиненной условию . Используя метод множителей Лагранжа, задача сведется к решению уравнения MATH

В частности, мы получаем , и далее, полагая , приходим к уравнению . Таким образом, MATH

что и требовалось.

1. Функция f(x) = 1 + x является интерполяционной функцией для множества данных {@,1),A,2)}.
  
  Рассмотрим гиперболическую СИФ , где V . Пусть G обозначает аттрактор СИФ. Тогда несложно проверить, что G является отрезком прямой, соединяющей точки @,1) и A,2). Иными словами является графиком интерполяционной функции f(x) на интервале [0,1].
2. Пусть {(x,-, Ft): i = 0,1,2,..., N} система данных. Пусть Let /: [x0, x^] -в\¦U обозначает единственную непрерывную функцию, которая проходит через точки интерполяции и которая линейна на каждом сегменте [x,_i,x,]. Иными словами x for. [*,-i >*,],' = 1,2,...,AT. Функция f(x) называется кусочно линейной интерполяционной функцией. График функции изображен на рисунке. Этот график является притягивающим множеством СИФ вида {K2; wn, n = 1,2,...,N}, состоящего из аффинных отображений. В самом деле, ** - x0) '(jcn - jc0) (xNFn_l - x0Fn) (XN ~x0) for n = 1,2,..., AT.
1. Н.Н. Воробьев Числа Фибоначчи М.,"Наука", 1978, 144с.
2. Мартин Гарднер Математические головоломки и развлечения М. "Мир", 1971, 511с.
3. Мидхат Газале Гномон.От фараонов до фракталов 2002 273с.
4. Ричард М. Кроновер Фракталы и хаос в динамических системах. Основы теории М. "Постмаркет", 2000.-- 352с.
5. М.Шредер Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая.-- Ижевск.: Научно-издательский центр "Регулярная и хаотическая динамика", 2001, 528с.
6. Бенуа Б.Мандельброт Фрактальная геометрия природы 2002 666с.
7. А.Д. Морозов Введение в теорию фракталов 2002 163с.
8. Федер Е. Фракталы М.:Мир, 1991.-254с.
9. Фракталы в физике М.:Мир, 1988.-
10. Kenneth Falconer FRACTAL GEOMETRY Mathematical Foundations and Applications 1990 288pp
11. В.М. Зюзьков Синергетика для программистов Томск Том. гос.ун-т систем управления и радиоэлектроники, 2001. - 194с.
12. Ф.Р.Гантмахер Теория матриц 1954 576с.
13. 040405\M-04-18.pdf Self-similar Fractals in Arithmetic Arash RASTEGAR 2004 14pp
14. Jacob Marie-Andrée and Reveilles Jean-Pierre Gaussian numeration systems 8pp
15. Hertel, E.: Self-similar Simplices. Beiträge zur Algebra und Geometrie 41 (2000), 589-595.
16. 150408\+976487829.pdf Ines Osburg Selbstähnliche Polyeder 2004 82pp
17. David Malone Solutions to Dilation Equations Ph.D., University of Dublin, 2000 117pp для материала по самоподобным многоугольникам 280607fract\malone01solutions.pdf
  
  стр 99-103
  
  117pp для замощений и 2-рептилий стр 35-37
18. Michael F. Barnsley, Andrew Vince The Chaos Game on a General Iterated Function System arXiv:1005.0322 [math.MG] 18pp
19. John C. Hart Iterated Function Systems and Recurrent Iterated Function Systems School of EECS Washington State University May 14, 1996 45pp
20. R. Daniel Mauldin; S. C. Williams Hausdorff Dimension in Graph Directed Constructions Transof the AMS, Vol. 309, No.2 (Oct., 1988), 811-829
21. J. Marion, Mesures de Hausdorff et théorie de Perron-Frobenius des matrices non-negatives, Ann. Inst. Fourier (Grenoble) 35 (1985), 99-125
22. Manav Das, G.A.Edgar Separation Properties for Graph-Directed Self-Similar Fractals Topology and Its Applications 2003 24pp
23. Max Murphy Parameter families of iterated fuction systems and continuity arXiv:math.DS/0608552 6pp
24. Edgar Golds
25. Mainlon
26. J.E. Hutchinson, Fractals and self-similarity, Indiana Univ. Math. J. 30 (1981), 713-747
27. 280906\ +diplom_bader.ps From Logic Programms to Iterated Function Systems S.Bader 2003, 87pp
28. M.F.Barnsley, S.Demko Iterated Function Systems and the Global Construction of Fractals Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences Volume 399, Issue 1817 (Jun. 1985), 243-275
29. 301106\reptile.ps Sze-Man Ngai, Victor F. Sirvent, J.J. Veerman, Yang Wang On 2-Reptiles in the Plane 1999 19pp
30. 050308fract\dgpiche2002.pdf Daniel G. Piché Complex Bases, Number Systems and TheirApplication to Fractal-Wavelet Image Coding 2002 205pp
31. 240607adic\+dissertation.pdf Kiko Kawamura On the classification of self-similar sets determined by two contractions on the plane 25pp

Если , тогда существует такая мера $\mu$ на , что
Обратно, если $\mu$ такая мера на , чтотогда .

Proof

Предположим, что . Мы используем без доказательства следующий факт:

Если , тогда существует такое компактное множество $K\subset X$ , что и для некоторого и достаточно больших .

Пусть $\mu$ ограничение меры на . Для всякого $x\in K$ определим MATH

Эта функция ограничена сверху MATH

некоторой константой . Отсюда заключаем, что MATH

Это завершает доказательство первой части леммы.

Theorem

Справедливы неравенства , где $\dim _{H}K$ -- размерность Хаусдорфа компакта .

Фрактальные самоподобные множества и их обобщения

Термин "фрактал" я образовал от латинского причастия fractus.

Соответствующий глагол frangere переводится как "ломать",

"разламывать", то есть создавать фрагменты неправильной

формы. Таким образом, разумно -- и как кстати! -- будет

предположить, что помимо значения "фрагментированный"

(как, например, в словах "фракция" или "рефракция"), слово

fractus должно иметь значение "неправильный по форме" --

примером сочетания обоих значений может служить слово

"фрагмент".

Б.Мандельброт Фрактальная геометрия природы М., 2002, 666стр

см. стр18 в книге ,

Как отличить фрактальное множество от "обычного", понимая под обычными множествами не слишком изрезанные куски гладких многообразий? Первый шаг в направлении удовлетворительного ответа лежит в использовании структуры самоподобия. Среди самоподобных и безусловно фрактальных множеств должны располагаться множество Кантора и салфетка Серпинского. Учитывая, что с топологической точки зрения всякий компакт является непрерывным образом канторова множества, следует , не стремясь к гладкости и избегая топологической общности остановиться на категории метрических пространств. Одним из важных инвариантов многообразия является его (локальная) размерность. В категории топологических пространств также имеется довольно много определений размерности. Изо всех этих определений мы остановимся на так называемой большой индуктивной размерности. В категории метрических пространств также имеются свои понятия размерности.

Бенуа Мандельброт впервые пытаясь отделить фракталы от нефракталов определил их по несовпадению топологичской размерности и размерности Хаусдорфа. Однако впоследствие на передний план вышла идея самоподобия, так что стали полезными понятия бокс-размерности (верхней и нижней). Наконец, когда был выделен класс самоподобных множеств, удовлетворяющих условию OSC условию открытого множества для структуры самоподобия, постепенно выяснилось, что этот класс объектов способен претендовать на роль правильных фрактальных множеств.

Определение структуры самоподобия по Кигами

квадрат, ветка Хаты, поднятие квадрата в группу Гейзенберга

Обсуждение структуры самоподобия

определение меры и размерности Хаусдорфа

мультимножества,

орграфы обобщенная теорема Хатчинсона,

работа Маулдина-Виллемса

Морозов Введение в теорию фракталов

Распространяется ли лесной пожар ровным фронтом, подобно греческой фаланге? Или в этом фронте имеются выступы и впадины? Имеются, уверяю вас. Более того, линия фронта имеет фрактальную структуру с размерностью Хаусдорфа , заключенной между 1 и 2. На первый взгляд, похожая картина наблюдается в таком явлении как проникновение, известном также под названием образование вязких языков, которое имеет отношение к добыче нефти, и на которые нефтяная промышленность возлагала болльшие надежды, особенно в 70-е годы, когда запасы нефти временно истощились (см. гл. 9). Однако вязкие языки образуются вследстивие неусточивости поверхности раздела двух жидкостей. Что же касается фрактальной структуры фронта лесного пожара, то ее причина кроется в связности -- то есть в соседстве деревьев.

см.стр 449 в книге М.Шредер Фракталы, хаос, степенные законы Ижевск, НИЦ, "Регулярная и хаотическая динамика"2001, 528стр

fractals\Fractals\books\+hunt96hausdorff.pdf The Hausdorff Dimension of Graphs of Weierstrass Functions Brian R. Hunt

Обычное определение размерности Хаусдорфа борелевского множества следующее. Для $s\geq 0$ и $\delta >0$ определим MATH

Такое определение используется для определения верхней границы размерности Хаусдорфа множества .

Верхняя граница может может быть получена проверкой с использованием специальных покрытий множествами малого диаметра, и если показано, что конечно для некоторого , тогда . Однако нижнюю границу получить непосредственно более трудно, поскольку должны быть использованы все покрытия .

Можно показать (см. например, [5],[15] и ниже), что если , для всех мер $\mu$ ,с носителем на , с другой стороны, если , тогда существует мера $\mu$ , сосредоточенная на , такая, что . Таким образом, все это можно представить в виде MATH

Фрактальные интерполяционные функции

стр224 Фракталы повсюду

6.2 FRACTAL INTERPOLATION FUNCTIONS

Definition

Множество данных есть множество точек вида MATH

Интерполяционная функция соответствующая множеству данных есть непрерывная функция MATH

такая, что . Точки называются интерполяционными точками. Будем говорить, что функция интерполирует данные и что график проходит через интерполяционные точки.

Упражнения и примеры

2.2. Let denote a set of data.

denote the unique continuous function which passes through the

interpolation points and which is linear on each of the subintervals

That is

(

The function is called a piecewise linear interpolation function.

The graph of f(x) is illustrated in Figure 6.2.1. This graph, G, is also the

attractor of an IFS of the form where the

maps are affine. In fact

where

Заметим, что СИФ модет и не быть гиперболическим по отношению к евклидовой метрике в $\U{211d} ^{2}$ .

Notice that the IFS may not be hyperbolic with respect to the Euclidean

metric in K2. Can you prove that, nonetheless, G is the unique non-

nonempty compact subset of U 2 such that

2.3. Verify the claims in example 6.2.2 in the case of the data set

{@,0), A,3), B,0)} by applying either the Deterministic Algorithm, Pro-

Program 3.8.1, or the Random Iteration Algorithm, Program 3.8.2. You will

need to modify the programs slightly.

2.4. The parabola defined by f(x) = 2x x2 on the interval [0,2] is an

interpolation function for the set of data {@,0), A, l),B,0)}. Let G

denote the graph of f(x). That is

G= {(;c,2;c-;c2): x e [0,2]}.

Then we claim that G is the attractor of the hyperbolic IFS {R2; wx, w2},

where

0.5

0.25

and

0.25

!)в--

We verify this claim directly. We simply note that for all x e [0, 2]

f(x)

fix)

2{hx) 1 + \x

2A + \x) A + \x)'

1 + \x

/(I + \x

As x varies over [0,2], the right-hand side of the first equation yields the

part of the graph of f(x) lying over the interval [0,1], while the

right-hand side of the second equation yields the part of the graph of

f(x) lying over the interval [1,2]. Hence G = w^G) U w2(G). Since

G g Jf(U2), we conclude that it is the attractor of the IFS. Notice that

the IFS is just-touching.

2.5. Find a hyperbolic IFS of the form {K2; wly w2}, where wl and w2 are

affine transformations in K2, whose attractor is the graph of the quadratic

function which interpolates the data {@,0), A,1), B,4)}.

Let a set of data {(xt, F^: i = 0,1,2,..., N} be given. We explain how

one can construct an IFS in K2 such that its attractor, which we denote by G,

is the graph of a continuous function /: [xQ, xN] -В» K which interpolates the

data. Throughout we will restrict our attention to affine transformations. The

usage of more general transformations is discussed in [Barnsley 1986a],

[Barnsley 1986c], [Hardin 1985], [Massopust 1986].

We consider an IFS of the form {K2; wn, n = 1,2,...,N} where the maps

are affine transformations of the special structure

The transformations are constrained by the data according to

Xn \ I Xn _, \ / XN \ I X,,

and i

The situation is summarized in Figure 6.2.2.

Let n g {1,2,3,..., N}. The transformation wn is specified by the five real

numbers an, cn, dn, en, and /в€ž, which must obey the four linear equations

anx0 + en = xB_j

anxN + en = xn

cnx0 + dnF0+fn = Fn_l

cnxN + dnFN + /в€ž = Fn

It follows that there is effectively one free parameter in each transformation.

We choose this parameter to be dn for the following reason: The transforma-

transformation wn is a shear transformation: it maps lines parallel to the _y-axis into lines

parallel to the j>-axis. Let L denote a line segment parallel to the j>-axis. Then

wn{L) is also a line segment parallel to the j>-axis. The ratio of the length of

wn{L) to the length of L is \dn\. We call dn the vertical scaling factor in the

transformation wn. By choosing dn to be the free parameter, we are able to

specify the vertical scaling produced by the transformation. With dn = 0,

n = 1, 2,...,N, one recovers the piecewise-linear interpolation function. In

this section we will show that these parameters determine the fractal dimen-

dimension of the attractor of the IFS.

Let dn be any real number. We demonstrate that we can always solve the

above equations for an, cn, en, and /в€ž in terms of the data and dn. We find

F.2.1) an = (xn - xn_l)/(xN - x0),

F.2.2) en = (xNxn_l xoxn)/(xN x0),

F.2.3) cB = (Fn - Fn_1)/(xN - x0) - dn(FN - F0)/(xN - x0),

F.2.4) /в€ž = {xNFn_x - x0Fn)/(xN - xQ) - dn(xNF0 - x0FN)/(xN - x0).

аффинные преобразования в , аттрактор которых является графиком квадратичной функции, которая интерполирует данные .

Пусть задана система данных . Мы опишем, как можно построить СИФ в , такой что ее аттрактор, который мы обозначим через , есть график непрерывной функции , которая интерполирует систему данных. В дальнейшем мы ограничимся аффинными преобразованиями. Рассмотрим СИФ вида , где отображения $w_{n}$ являются афинными преобразованиями специального вида MATH

Эти отображения связаны с системой данных соотношениями MATH

Преобразование определяется пятью вещественными числами , которые на основании вышесказанного подчинены четырем соотношениям MATH

Из вида соотношений следует, что имеется один свободный параметр в каждом соотношении. В качестве такого свободного парметра выберем исходя из следующих соображений: преобразование является скользящим (shear) оно трансформирует линии параллельные оси в линии, параллельные оси . Пусть обозначает отрезок, параллельный оси . Тогда также отрезок, параллельный оси . отношение длин этих отрезков равно . Мы назовем вертикальним скаляром растяжения преобразования .

Использование Maple для изображения фрактальных самоподобных множеств

Математическое обоснование игры "Хаос".

10050322

Лемма 3 Пусть собственное метрическое пространство, и пусть $\QTR{cal}{F}$ -- СИФ с аттрактором . Для любого $\varepsilon >0$ найдется такое целое $M=M(\varepsilon )$ , что для каждого найдется целое , для которого MATH Доказательство: поскольку является собственным, и компактен, $A+\varepsilon$ также компактно согласно Лемме 1. Нет никакой потери общности в допущении, что $\varepsilon$ является столь маленьким, что , где - бассейн притяжения . Если , тогда найдется целое такое, что MATH Это - так, потому что . Поскольку X является собственным, из утверждения (2) Леммы 1 следует что непрерывен, следовательно непрерывен. Так как непрерывен, найдется открытый шар $B(\{x\},r_{x})$ (в $C\left( X\right)$ ) радиуса $r_{x}>0$ с центром в $\{x\}$ таким образом, что MATH . в частности найдется такой шар , что MATH . Объединение этого с уравнением 3.1 выше дает MATH Набор шаров { $B(x,r_{x})$ , } является открытым покрытием $A+\varepsilon$ . Поскольку $A+\varepsilon$ компактно, найдется такое конечное подпокрытие { $B(a_{i},r_{a_{i}})$ }, что . Если , тогда для всякого найдется такое , и в этом случае MATH

Определение 3 Пусть $\QTR{cal}{F}$ -- СИФ и $p\in (0,1/N]$ фиксировано. Последовательность {x $_{k}$ } $_{k=0}^{\infty }$ точек в называют случайной орбитой $x_{0}\in X$ , если

, $k\geq 1$ , где $\sigma _{k}$ выбран случайно из $\{1,2...,N\}$ , для , где вероятность что $\sigma _{k}$ больше чем или равна , независимо от предыдущих исходов, для всех $n\in \{1,2...,N\}$ и всех . Более формально, в терминах условной вероятности, MATH Теорема 3 Пусть собственное полное метрическое пространство и $\QTR{cal}{F}$ -- СИФ с аттрактором и его бассейном притяжения . Если {x $_{k}$ } $_{k=0}^{\infty }$ последовательность точек в -- случайная орбита $x_{0}\in U$ порожденная $\QTR{cal}{F}$ , то с вероятностью один, MATH где предел вычисляется в пространстве $C\left( X\right)$ в метрике Хаусдорфа.

Доказательство: Мы сначала утверждаем, что, для всякого $\varepsilon >0$ , есть такое целое число , что

MATH Поскольку пространство является собственным, $\QTR{cal}{F}$ непрерывен по Теореме 1. По Теореме 2 и Лемме 2, MATH Отсюда следует, что, для любого $\varepsilon >0$ , мы можем выбрать так, чтобы MATH что и требуется.

Мы затем покажем, что, для любого $\varepsilon >0$ , найдется такое целое число , что MATH с вероятностью один, для всех $L\geq K$ . Это эквивалентно утверждению теоремы. Чтобы доказать это, зададим $\varepsilon >0$ . Если выбрано так, как выше, то согласно (3.2) имеем для $L\geq K$ . Аттрактор , будучи компактным, вполне ограничен. Пусть такое множество точек, что . Заметим, что как $a_{q}$ так и зависят от $\varepsilon$ . По Лемме 3 найдется такое целое $\U{41c}$ , что, для каждого , найдется такое $m<\U{41c}$ . что . Следовательно MATH для некоторого целого $m<\U{41c}$ . Поэтому найдется такая последовательность символов $\sigma _{L+1}$ $\sigma _{L+2}$ ... $\sigma _{L+m}$ , что

. (Мы принимаем соглашение, что композиция слева равняется $x_{L}$ если .) ) Из этого следует, что MATH или MATH Вероятность, что это событие происходит, то есть, что специальная последовательность $\sigma _{L+1}$ $_{L+m}$ выбрана, больше, чем $p^{M}$ . Повторяя эти рассуждения, мы выводим, что вероятность события MATH больше, чем $p^{M}>0$ , для каждого $q\in \{1,2...,Q\}$ , независимо от того, происходят ли или нет предыдущие события. (Который не должен сказать, что события независимы). Из этого следует, что вероятность, что все эти события происходят, больше, чем $p^{QM}$ . Рассмотрим событие $E_{1}$ заданное условием MATH

Вероятность $E_{1}$ - меньше чем $(1-p^{QM})$ . По тем же соображениям, вероятность события $E_{r}$ , $r\geq 1$ , заданного условием

MATH меньше чем $(1-p^{QM})$ , независимо от того, произошли ли предыдущие события , для . Из этого следует, что вероятность события . $\$ . $\$ . $\ \cap E_{r}$ меньше чем $(1-p^{QM})^{r}$ , для .. Это неравенство выполняется независимо от факта, является ли $E_{r}$ независимым или нет. Чтобы упростить обозначения, полагаем $s=(1-p^{QM})<1$ так, что можно записать MATH Отсюда вытекает, что Следовательно, с вероятностью один, найдется такое , что MATH Так как из этого следует, что, с вероятностью один, найдется такое , что MATH Поскольку - произвольное целое число, большее или равное , MATH Но на основании (3.2) мы также имеем MATH Следовательно, с вероятностью единица MATH

Из этого следует, что MATH почти наверное, для $x_{0}\in U$ и $B\in C(U)$ , например, в случае $B=\{x_{0}\}$ . Мы обращаем внимание на это равенство, потому что оно кажется неожиданным, для $\QTR{cal}{F}$ содержащей более чем одну функцию, ведь семейство {x $_{k}$ } кажется разреженным по сравнению с .

прежде всего, аналоги салфетки Серпинского и всевозможные симметрии,

затем построение ломаной из отрезка и ее итерации см предыдущий параграф

задача 2008

задача 2009 о распространении тепла во фрактальном множестве, или уравнение диффузии на фрактале

задача 2010 построение граф-ориентированного фрактального множества

Здесь начинаем с полного ориентированного графа с 4-мя вершинами .

Здесь MATH

Геометрическая реализация графа является квадратом на плоскости с вершинами , , , , всеми сторонами, диагоналями и вершинными петлями.

Заметим, что ребра , соединяющие вершины с собой здесь присутствуют. Всякому ребру сопоставляем гомотетию $F_{j}$ с центром в вершине вида MATH

На множестве всех упорядоченных четверок компактных множеств плоскости $\U{211d} ^{2}$ определим обобщенный оператор Хатчинсона MATH

Таким образом, если , то MATH

поскольку

Нетрудно установить, что метрическое пространство с метрикой MATH

является полным, а отображение $\Phi$ -- сжимающим с коэффициентом сжатия $\frac{1}{2}$ , так что существует единственное мультимножество для которого , или, подробнее, MATH

Алгоритм "Игра Хаос" устроен почти так же, как и в случае простого СИФ. Начальная точка состоит из упорядоченного -набора точек пространства $\U{211d} ^{n}$ , то есть задается матрицей формата $m\times n$ .

В нашем случае задается начальная четверка точек или матрица $2\times 4$ .

Считаем для простоты, что степень всякой вершины одна и та же и равна . В рассматриваемом случае . Порождаем последовательность случайных наборов из целых чисел в промежутке от до . Формируем последовательность матриц. Рисуем крашенные проекции на координатные подпространства. Рисуем объединение этих множеств.

Более подробно

Задаем число итераций $N\geq 1000$

начальный набор точек .

Вызываем 4 датчика , случайных целых чисел из множества , или датчик порождения случайной матрицы: просто для заданной вершины выбираем номера инцидентных ей вершин и эти пары индексов позволяют выделить набор случайных чисел из построенной матрицы случайных чисел.

Проще всего нумеровать так: вершина с номером имеет 4 смежных $A_{\alpha }$ , $A_{\beta }$ , $A_{\gamma }$ , $A_{\delta }$ и мы приписываем им номера $\left[ i,1\right]$ , $\left[ i,2\right]$ ,, $\left[ i,4\right]$ .

На $\left( i+1\right)$ -ом шаге имеем четверку точек и набор целых чисел порожденный датчиками $r\left[ k\right]$ . Строим четверку точек

MATH

Сформированная последовательность позволяет построить четыре координатных рисунка, а также полный рисунок, являющийся объединением всех координатных рисунков.

№		2-рептайл
1		двойной дракон (twindragon)
2		дракон Леви (Lévy dragon)
3		Heighway dragon
4		triangle
5		rectangle
6		скучный двойной дракон (tame twindragon)

Самоподобные множества

-- подготовил Е.М. Горбатенко

Оглавление

Введение

Гномоны, многоугольные числа, числа Фибоначчи, золотое сечение

Самоподобные треугольники, четырехугольники и квадраты

Самоподобные треугольники

Самоподобные четырехугольники

Самоподобный квадрат и бесконечный самоподобный квадрат

Самоподобные целочисленные параллелепипеды

Самоподобные множества и их обобщения. Границы самоподобия . Структуры самоподобия

Самоподобные множества в арифметике

Самоподобные структуры в алгебре и анализе

Метод исчерпания, как способ построения самоподобных множеств

Метрика Хаусдорфа

Системы итерируемых функций (СИФ)

Числовые и комбинаторные инварианты самоподобных множеств

Меры и принцип распределения масс.

Условие открытого множества и его обобщения

Существование фрактальных самоподобных множеств

Фрактальные самоподобные множества и их обобщения

Фрактальные интерполяционные функции

Использование Maple для изображения фрактальных самоподобных множеств

Математическое обоснование игры "Хаос".

Список литературы