Система повторяющихся функций

редактировать

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

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

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

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

СОДЕРЖАНИЕ

1 Определение
2 свойства
3 конструкции
4 Системы многораздельных итерированных функций
5 Обратная задача
6 Примеры
7 История
8 См. Также
9 Примечания
10 Ссылки

Определение

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

{\ displaystyle \ {f_ {i}: от X \ до X \ mid i = 1,2, \ dots, N \}, \ N \ in \ mathbb {N}}

{\ displaystyle \ {f_ {i}: от X \ до X \ mid i = 1,2, \ dots, N \}, \ N \ in \ mathbb {N}}

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

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

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

IFS выполняется с двумя функциями.

Hutchinson (1981) показали, что для метрического пространства, или в более общем случае, для полного метрического пространства, такая система функций имеет единственное непустое компактное (замкнуто и ограничено) фиксированный набор S. Один из способов построения фиксированного множества - начать с начального непустого замкнутого и ограниченного множества S 0 и повторить действия f i, принимая S n +1 за объединение образов S n под f i ; затем взяв S за замыкание объединения S n. Символически уникальное фиксированное (непустое компактное) множество обладает свойством ${\ Displaystyle \ mathbb {R} ^ {п}}$ $\ mathbb {R} ^ {n}$ ${\ displaystyle X}$ $Икс$ ${\ Displaystyle S \ substeq X}$ $S \ substeq X$

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

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

Множество S, таким образом, фиксированный набор из оператора Hutchinson определяется для помощью ${\ displaystyle F: 2 ^ {X} \ to 2 ^ {X}}$ ${\ displaystyle F: 2 ^ {X} \ to 2 ^ {X}}$ ${\ displaystyle A \ substeq X}$ $A \ substeq X$

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

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

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

{\ Displaystyle \ lim _ {п \ к \ infty} F ^ {\ circ n} (A) = S}

{\ Displaystyle \ lim _ {п \ к \ infty} F ^ {\ circ n} (A) = S}

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

Недавно было показано, что IFS несжимающего типа (т. Е. Составленные из отображений, которые не являются сжатиями по отношению к любой топологически эквивалентной метрике в X) могут давать аттракторы. Они естественным образом возникают в проективных пространствах, хотя классическое иррациональное вращение на окружности тоже может быть адаптировано.

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

Конструкции

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

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

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

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

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

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

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

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

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

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

Основная статья: Фрактальное сжатие

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

Обратная задача сложнее: учитывая некоторые оригинальные произвольные цифровые изображения, такие как цифровая фотография, попытаться найти набор параметров КСФА, которые, при оценке с помощью итераций, производит другое изображение визуально похожее на оригинал. В 1989 году Арно Жакен представил решение ограниченной формы обратной задачи, используя только PIFS; общий вид обратной задачи остается нерешенным.

С 1995 года все программное обеспечение фрактального сжатия основано на подходе Жакена.

Примеры

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

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

История

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

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

- Майкл Барнсли и др.

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

Примечания

использованная литература

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