Итерированная система функций

Треугольник Серпинского , созданный с помощью IFS (раскрашен для иллюстрации самоподобной структуры)

Цветная IFS, разработанная с использованием программного обеспечения Apophys и визуализированная с помощью Electric Sheep .

В математике системы итерированных функций ( IFS ) представляют собой метод построения фракталов ; получающиеся в результате фракталы часто оказываются самоподобными . Фракталы IFS больше связаны с теорией множеств , чем с фрактальной геометрией. ^[1] Они были представлены в 1981 году.

Фракталы IFS , как их обычно называют, могут иметь любое количество измерений, но обычно рассчитываются и рисуются в 2D. Фрактал состоит из объединения нескольких своих копий, каждая из которых преобразуется функцией (отсюда и «система функций»). Канонический пример — треугольник Серпинского . Функции обычно являются сжимающими , что означает, что они сближают точки и уменьшают формы. Следовательно, форма фрактала IFS состоит из нескольких, возможно, перекрывающихся меньших копий самого себя, каждая из которых также состоит из копий самой себя, до бесконечности . В этом источник его самоподобной фрактальной природы.

Определение

Формально итерированная система функций представляет собой конечное множество сжимающих отображений на полном метрическом пространстве . ^[2] Символически,

${\displaystyle \{f_{i}:X\to X\mid i=1,2,\dots ,N\},\ N\in \mathbb {N} }$

является итерированной системой функций, если каждая из них является сжатием полного метрического пространства . ${\displaystyle f_{i}}$ ${\displaystyle X}$

Характеристики

Построение IFS с помощью игры хаоса (анимация)

IFS создается с двумя функциями.

Хатчинсон показал, что для метрического пространства или, в более общем плане, для полного метрического пространства такая система функций имеет единственное непустое компактное (замкнутое и ограниченное) фиксированное множество S. ^[3] Один из способов построения фиксированного набора — начать с начального непустого замкнутого и ограниченного множества S _{0 и итерировать} действия f i _, принимая Sn ₊₁ за объединение образов Sn под действием f _{. я} ; затем примем S за замыкание предела . Символически единственное фиксированное (непустое компактное) множество обладает свойством ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle X}$ ${\displaystyle \lim _{n\rightarrow \infty }S_{n}}$ ${\displaystyle S\subseteq X}$

${\displaystyle S={\overline {\bigcup _{i=1}^{N}f_{i}(S)}}.}$

Таким образом, набор S является фиксированным набором оператора Хатчинсона, определенного для через ${\displaystyle F:2^{X}\to 2^{X}}$ ${\displaystyle A\subseteq X}$

${\displaystyle F(A)={\overline {\bigcup _{i=1}^{N}f_{i}(A)}}.}$

Существование и единственность S являются следствием принципа сжимающего отображения , как и тот факт, что

${\displaystyle \lim _{n\to \infty }F^{n}(A)=S}$

для любого непустого компакта в . (Для сжимающего IFS эта сходимость имеет место даже для любого непустого замкнутого ограниченного множества ). Случайные элементы, сколь угодно близкие к S, могут быть получены с помощью «игры в хаос», описанной ниже. ${\displaystyle A}$ ${\displaystyle X}$ ${\displaystyle A}$

Недавно было показано, что ИФС несжимающего типа (т.е. состоящие из отображений, не являющихся стягиванием относительно какой-либо топологически эквивалентной метрики в X ) могут давать аттракторы. Они естественным образом возникают в проективных пространствах, хотя классическое иррациональное вращение на окружности тоже можно адаптировать. ^[4]

Набор функций генерирует моноид при композиции . Если таких функций всего две, то моноид можно представить как бинарное дерево , где в каждом узле дерева можно составить ту или иную функцию ( т.е. взять левую или правую ветвь). В общем, если имеется k функций, то можно представить моноид как полное k -арное дерево , также известное как дерево Кэли . ${\displaystyle f_{i}}$

Конструкции

Папоротник Барнсли , ранний сорт IFS.

Губка Менгера , трехмерная IFS.

«Дерево» IFS, построенное с помощью нелинейной функции Джулии

Иногда каждая функция должна быть линейным или, в более общем смысле , аффинным преобразованием и, следовательно, представляться матрицей . Однако IFS также могут быть построены из нелинейных функций, включая проективные преобразования и преобразования Мёбиуса . Фрактальное пламя — пример IFS с нелинейными функциями. ${\displaystyle f_{i}}$

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

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

Хотя теория IFS требует, чтобы каждая функция была сжимающей, на практике программное обеспечение, реализующее IFS, требует, чтобы вся система была сжимающей в среднем. ^[5]

Системы секционированных итерированных функций

PIFS (системы разделенных итерированных функций), также называемые локальными системами итерированных функций, ^[6] обеспечивают удивительно хорошее сжатие изображений даже для фотографий, которые, кажется, не имеют самоподобной структуры, которую демонстрируют простые фракталы IFS. ^[7]

Обратная задача

Существуют очень быстрые алгоритмы для создания изображения на основе набора параметров IFS или PIFS. Это быстрее и требует гораздо меньше места для хранения описания того, как оно было создано, передачи этого описания на целевое устройство и повторного создания этого изображения на целевом устройстве, чем сохранение и передача цвета каждого пикселя изображения. . ^[6]

Обратная задача более сложна: для некоторого исходного произвольного цифрового изображения, такого как цифровая фотография, попытаться найти набор параметров IFS, которые при итерационной оценке создают другое изображение, визуально похожее на оригинал. В 1989 году Арно Жакен представил решение ограниченной формы обратной задачи, используя только PIFS; общий вид обратной задачи остается нерешенным. ^{[8] [9] [6]}

По состоянию на 1995 год все программное обеспечение для фрактального сжатия основано на подходе Жакена. ^[9]

Примеры

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

Ранние примеры фракталов, которые могут быть созданы с помощью IFS, включают набор Кантора , впервые описанный в 1884 году; и кривые де Рама — тип самоподобной кривой, описанный Жоржем де Рамом в 1957 году.

История

IFS в их нынешнем виде были задуманы Джоном Э. Хатчинсоном в 1981 году ^[3] и популяризированы книгой Майкла Барнсли «Фракталы повсюду» .

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

-  Майкл Барнсли и др. ^[10]

Смотрите также

• Математический портал

• Комплексно-базовая система
• Теорема о коллаже
• Бесконечные композиции аналитических функций
• L-система
• Фрактальное сжатие

Примечания

1. Зобрист, Джордж Уинстон; Чаман Сабхарвал (1992). Прогресс в компьютерной графике: Том 1. Интеллект Книги. п. 135. ИСБН 9780893916510. Проверено 7 мая 2017 г.
2. Майкл Барнсли (1988). Фракталы повсюду , стр.82. ISBN Academic Press, Inc. 9780120790623 . 
3. Хатчинсон, Джон Э. (1981). «Фракталы и самоподобие» (PDF) . Университет Индианы. Математика. Дж . 30 (5): 713–747. дои : 10.1512/iumj.1981.30.30055 .
4. М. Барнсли, А. Винс, Игра хаоса в общей итерированной функциональной системе
5. Дрейвс, Скотт ; Эрик Рекейс (июль 2007 г.). «Алгоритм фрактального пламени» (PDF) . Архивировано из оригинала (PDF) 9 мая 2008 г. Проверено 17 июля 2008 г.
6. Брюно Лакруа. «Фрактальное сжатие изображений». 1998.
7. Фишер, Юваль (12 августа 1992 г.). Пшемыслав Прусинкевич (ред.). Конспекты курса SIGGRAPH'92 — Фрактальное сжатие изображений (PDF) . СИГГРАФ. Том. Фракталы – от народного искусства к гиперреальности. СИГРАФ ACM . Архивировано из оригинала (PDF) 12 сентября 2017 г. Проверено 30 июня 2017 г.
8. Дитмар Саупе, Рауф Хамзауи. «Обзор литературы по фрактальному сжатию изображений».
9. Джон Коминек. «Алгоритм быстрого фрактального сжатия изображений». дои : 10.1117/12.206368.
10. Майкл Барнсли и др. , «Фракталы и суперфракталы с V-переменной» (PDF) . (2,22 МБ)

Рекомендации

• Дравс, Скотт ; Эрик Рекейс (июль 2007 г.). «Алгоритм фрактального пламени» (PDF) . Архивировано из оригинала (PDF) 9 мая 2008 г. Проверено 17 июля 2008 г.
• Фальконер, Кеннет (1990). Фрактальная геометрия: Математические основы и приложения . Джон Уайли и сыновья. стр. 113–117, 136. ISBN. 0-471-92287-0.
• Барнсли, Майкл ; Эндрю Винс (2011). «Игра в хаос в общей итеративной функциональной системе». Эргодическая теория Динам. Системы . 31 (4): 1073–1079. arXiv : 1005.0322 . Бибкод : 2010arXiv1005.0322B. дои : 10.1017/S0143385710000428. S2CID  122674315.
• Исторический обзор и обобщение: Дэвид, Клэр (2019). «фрактальные свойства функций типа Вейерштрасса». Труды Международного геометрического центра . 12 (2): 43–61. дои : 10.15673/tmgc.v12i2.1485 . S2CID  209964068.

Внешние ссылки

• Букварь по элементарной теории бесконечных композиций комплексных функций