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

[Judit]

Друзья, добрый день!
Прошу помочь с пониманием "как генерировать некий конечный числовой ряд (допустим 100тыс точек), все числа которого принадлежат Канторову множеству / Множеству Фейгенбаума / Множеству из треугольника Серпинского". Я понимаю, что что-то я не понимаю, но что именно - прошу показать мне.

Зачем мне это: хочу поучиться считать размерности и просто поэкспериментировать с рядами, зная их характеристики.

Итак, изложу свое понимание на примере треугольника Серпинского. (Вникала по книге Божокина и Паршина).

1. Пусть есть нулевая точка в комплексном пространстве $z_0$. У меня это:

$$ z_0 = [0, 1/2 + \sqrt{3}/2, 1] $$

2. Есть система итерируемых функций (СИФ) для этого аттрактора "Серпинского":

$$f = [f_1,f_2,f_3]$$

3. Повторяем $N$ раз $z_1 = f(z_0)$, выбирая случайным образом $f_1$ или $f_2$ или $f_3$. Итого имеем $z_n$, принадлежащую множеству треугольника Серпинского.

А теперь вопросы,
1. Ясно, что $N$ бесконечно, но какое можно взять конечное значение? Может есть какой-то способ оценить, насколько полученное множество близко к "идеалу"?
2. Верно ли утверждать, что если мне хочется взять ряд для исследований из 100тыс точек, то мне надо сгененировать любые $z_0$ и пустить их по СИФ, получив в итоге 100тыс $z_n$? Вот тут у меня прям "стопор". Есть подозрение, что вот так просто наобум брать $z_0$ как-то странно. Не получатся ли это точки совершенно разных множеств, пусть и тоже Серпинского. Тут у меня пробел явно в понимании. Прошу направить мысль или растолковать.
3. Если п.2 не верен, надо пускать одну и ту же точку $z_0$ по СИФ, рандомно выбирая $f_1, f_2 , f_3$. Тут меня смущает что вроде как мы управляем процессом движения точки, так как "случайное не случайно" и вообще можно выбрать вероятность выбора уравнений, по которым пойдем. Будет ли это корректно?

Спасибо! Буду благодарна мыслям - объяснениям - наводкам.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы/обозначения (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Aritaborian]

Judit в сообщении #1511258 писал(а):

Множеству Фейгенбаума

А это что за зверь такой?

[arseniiv]

Judit в сообщении #1511258 писал(а):

1. Ясно, что $N$ бесконечно, но какое можно взять конечное значение? Может есть какой-то способ оценить, насколько полученное множество близко к "идеалу"?

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

На пальцах это примерно так:
• Для каждого отображения $f_i$ вычислите коэффициент (линейного) сжатия $A_i$. Так как у нас тут аффинные отображения, он один и не зависит от того, к окрестности какой точки мы применяем отображение.
• В начале игры в хаос примем $A := 1$.
• На итерации, когда мы решаем применять $f_i$, обновляем $A := A A_i$.
• Мы должны как-то вычислять примерные линейные размеры множества, которое получается. Как обычно делают, мы игнорируем несколько первых точек, полученных игрой в хаос (в множество их не помещаем, но $A$ всё-таки обновляем). Пусть оценка линейного размера множества у нас $\ell$.
• Тогда мерой близости очередной точки к фракталу будет $A \ell$: весь фрактал, уменьшенный в $A$ раз, занимает примерно $A \ell$ линейно, то есть точка может гулять примерно не более чем на такое расстояние от него.
• И если вы знаете размеры $\ell_0$ фрактала заранее и начинаете с точки внутри выпуклой оболочки фрактала, то можно просто пропускать генерируемые точки, пока $A \ell_0$ не станет меньше интересующей величины. Если нет, $\ell$ придётся каждый раз оценивать, что-то там мудря, потому что надо будет пропускать какое-то количество начальных точек, но какое именно — мы не знаем.

А ещё я не понял почему у $z_0$ три компоненты. Если вы уже используете комплексные числа, то для треугольника Серпинского (и других IFS из преобразования подобия плоскости) достаточно одного числа. Каждая функция будет иметь вид $z \mapsto r z + s$, и коэффициентом линейного сжатия для неё будет $|r|$. Для треугольника Серпинского они все будут $1/2$, так что вы можете отсчитать примерно столько точек, сколько бит в мантиссе типа плавающих чисел, которые вы используете, и потом с чистой совестью перестать пропускать.

[alisa-lebovski]

Предлагаю лучше вникать по книжкам Мандельброта, он и автор этой теории и хороший популяризатор.

Канторово множество можно сделать так: брать двоичные разложения чисел на (0,1), умножать цифры на 2 и считать это за троичное разложение.

[arseniiv]

Judit в сообщении #1511258 писал(а):

Верно ли утверждать, что если мне хочется взять ряд для исследований из 100тыс точек, то мне надо сгененировать любые $z_0$ и пустить их по СИФ, получив в итоге 100тыс $z_n$? Вот тут у меня прям "стопор". Есть подозрение, что вот так просто наобум брать $z_0$ как-то странно. Не получатся ли это точки совершенно разных множеств, пусть и тоже Серпинского. Тут у меня пробел явно в понимании. Прошу направить мысль или растолковать.

Если все ваши отображения сжимающие, ничего странного нет. Точно во фрактал мы всё равно не попадём из-за численных проблем, но приблизимся к нему настолько, насколько возможно, довольно быстро, если отображения «сжимают хорошо». Представьте выпуклую оболочку $X$ всего фрактала. Каждое отображение даёт нам какую-то уменьшенную выпуклую оболочку $f_i(X)$, объединение которых $\bigcup_i f_i(X)$ заведомо содержит фрактал. То же верно и для $\bigcup_i f_i \left( \bigcup_j f_j(X) \right)$ и т. д.. Эти множества будут иметь всё меньшую меру и всё лучше приближать фрактал в смысле расстояния от точки до множества vs. расстояния от точки до фрактала.

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

-- Пт мар 26, 2021 19:18:21 --

Judit в сообщении #1511258 писал(а):

Тут меня смущает что вроде как мы управляем процессом движения точки, так как "случайное не случайно"

Это отбросьте сразу. Если ваш ГПСЧ проходит статистические тесты (о чём для популярных генераторов обычно широко известно), то он заведомо подходит. Выбирайте генератор с внутренним состоянием побольше и всё будет хорошо. И выбирайте как минимум double для представления всех координат.

Judit в сообщении #1511258 писал(а):

и вообще можно выбрать вероятность выбора уравнений, по которым пойдем

И это важно. Надо использовать функцию тем чаще, чем большую площадь она даёт при применении к какой-то фигурке, похожей на фрактал. Для аффинных преобразований это опять же всегда одно и то же, и для преобразований выше над комплексными числами эта площадь будет пропорциональна $|r|^2$, так что вероятности должны быть тоже. Тогда наше множество будет «равномерно заполненным». Если брать другие веса, то не будет.

[Judit]

arseniiv, alisa-lebovski, благодарю за подробные ответы, что-то стало понятнее, что-то наоборот открыло новый пласт моих "не знаний". Пойду вникать :)

Aritaborian в сообщении #1511314 писал(а):

Judit в сообщении #1511258 писал(а):

Множеству Фейгенбаума

А это что за зверь такой?

имела ввиду логистическое отображение.

arseniiv в сообщении #1511352 писал(а):

А ещё я не понял почему у $z_0$ три компоненты. ...

да, это по книге понравилась идея про генератор, пропуская который через СИФ, получаем всякие интересности. Вот брала "треугольник" (как раз $z_0$ из моего вопроса), "квадрат" и смотрела, что выйдет. И выходило очень интересно. И так и оставила.

[arseniiv]

Тут ключ примерно один и тот же: если у нас есть метрическое пространство, то его (компактные непустые) подмножества тоже образуют метрическое пространство по метрике Хаусдорфа (расстояние между двумя множествами — это инфимум того, насколько их надо «раздуть», чтобы каждое раздутое включало другое нераздутое). Это метрическое пространство очень полезно если и не для всех фракталов, то для IFS точно, так как фрактал для какой-то IFS — это предел некоторой последовательности множеств в таком метрическом пространстве. А именно, если наша IFS $\{ f_1, \ldots, f_m \}$, то мы определяем уже на множествах функцию $F(X) = f_1(X) \cup \ldots \cup f_m(X)$, которая просто применяет ко всем точкам $X$ все функции. Для фрактала $F(X) = X$, но не только для него. Он отличается тем, что это наименьшее из всех таких $X$ по включению замкнутое непустое множество, для которого это верно, то есть это наименьшая неподвижная точка $F$. (Если я не наврал — это уже по памяти.) Отсюда лезут все следствия — и алгоритмы приближения к $X_0$, и оценки, и теорема о коллаже (нарисовать такую IFS, чтобы её фрактал был похож на данное множество) и прочее.

-- Пт мар 26, 2021 20:46:11 --

У Барнсли все эти метрические штуки в книге есть, Мандельброта к сожалению пока не открывал ни разу.

[Judit]

arseniiv в сообщении #1511379 писал(а):

...Он отличается тем, что это наименьшее из всех таких $X$ по включению замкнутое непустое множество, для которого это верно, то есть это наименьшая неподвижная точка $F$...

во как, спасибо!

arseniiv, навскидку как книга Барнсли называется? Нашла "Фракталы везде" и "Суперфракталы" - они?

Мандельброт - он хороший, есть его книга живая, но как-то я там пока не смогла найти ответов. Может не в той книге искала.

[arseniiv]

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

[Judit]

arseniiv, спасибо! Отличных выходных!

[Pphantom]

alisa-lebovski в сообщении #1511354 писал(а):

Предлагаю лучше вникать по книжкам Мандельброта, он и автор этой теории и хороший популяризатор.

Не стоит. Он хороший рекламщик (без всяких отрицательных коннотаций), но разобраться по его книгам с чем-либо затруднительно. Из легкодоступных на русском языке есть книга Енса Федера "Фракталы", лучше использовать ее в качестве базовой.

[ozheredov]

arseniiv в сообщении #1511359 писал(а):

Каждое отображение даёт нам какую-то уменьшенную выпуклую оболочку

Заранее извиняюсь за возможный бред.

В теме я естественно нуб, но разве фрактал может быть выпуклым? Интуитивно кажется, что нет, поскольку при вычислении "размерности" (которая предел логарифма отношения числа "кубиков" к их стороне) получится целое число. Т.е. кажется, что фрактал целиком содержится в выпуклой оболочке (если он вообще имеет конечные размеры -- что мешает рассматривать иное?), которую "стянуть" уже не получится (в смысле при вычислительных "уточнениях" структуры фрактала). Нет?

[geomath]

Мне в свое время книжка Божокина и Паршина "Фракталы и мультифракталы" 2001 г. очень понравилась. Всего 128 страничек, два раздела: фракталы и мультифракталы. Последние, пожалуй, даже интереснее. Правда, авторы - физики, не математики. А книга Федера мне не понравилась, хотя я ее добросовестно прочитал.