Система ітераційних функцій

Формально система ітераційних функцій є скінченою множиною стискального відображення на повний метричний простір[2]. Символічно, ${\displaystyle \{f_{i}:X\to X\mid i=1,2,\dots ,N\},\ N\in \mathbb {N} }$ є системою ітераційних функцій, якщо кожна ${\displaystyle f_{i}}$ є стискальним відображенням на повний метричний простір ${\displaystyle X}$.

Створення СІФ з допомогою гри хаосу (анімація)

Побудова СІФ з допомогою двох функцій

1981 року Хатчінсон^[хто?] показав, що для метричного простору ${\displaystyle \mathbb {R} ^{n}}$, така система функцій має унікальну непорожню компактну (замкнуту та обмежену) фіксовану множину S. Одним зі способів побудови фіксованого набору є, почати з першої точки множини ${\displaystyle S_{0}}$ й ітерувати дії ${\displaystyle f_{i}}$, приймаючи ${\displaystyle S_{n+1}}$ за сукупність образів ${\displaystyle S_{n}}$ на ${\displaystyle f_{i}}$; і наприкінці взяти S як замикання сукупності ${\displaystyle S_{n}}$. Символічно, унікальна фіксована (непорожня компактна) множина ${\displaystyle S\subseteq X}$ має властивість ${\displaystyle S=\bigcup _{i=1}^{N}f_{i}(S)}$.

Таким чином, множина S є фіксованою множиною оператора Хатчінсона ${\displaystyle H(A)=\bigcup _{i=1}^{N}f_{i}(A)}$.

Існування та єдиність S є наслідком принципу стискальних відображень, як і факт того, що ${\displaystyle \lim _{n\to \infty }H^{\circ n}(A)=S}$ для будь-якої непорожньої компактної множини A в X (для стискальної СІФ ця конвергенція має місце навіть для будь-якої непорожньої замкнутої обмеженої множини A). Випадкові елементи довільно близькі до S, можуть бути отримані за допомогою «гри хаосу», описаної далі.

Нещодавно^[коли?] було показано, що СІФ нестискального типу (тобто ті, що складаються з карт, які не є скороченнями відносно будь-якої топологічно-еквівалентної метрики в X) можуть віддавати атрактори.

Вони природно виникають у проективних просторах, хоча класичне ірраціональне обертання на колі теж може бути адаптовано[3].

Колекція функцій ${\displaystyle f_{i}}$ генерує моноїд на композиції функцій. Якщо є тільки дві такі функції, моноїд може бути візуалізований бінарним деревом, де, на кожній вершині дерева, можна взяти композицію двох функцій (тобто взяти ліве або праве піддерево). Загалом, якщо є k функцій, тоді моноїд можна візуалізувати як повне K-арне дерево, також відоме як дерево Келі.

Папороть Барнслі, рання СІФ

Губка Менгера, тривимірна СІФ

Іноді кожна функція ${\displaystyle f_{i}}$ повинна бути лінійною або, більш загально, афінним перетворенням, а отже, представленою матрицею. Втім, СІФ також можуть бути побудовані з нелінійної функцій, в тому числі з проективного перетворення і перетворення Мебіуса. Фрактальне полум'я є прикладом СІФ з нелінійними функціями.

Найпоширенішим алгоритмом обчислення СІФ-фракталів є гра хаосу. Вона складається з вибору довільної точки на площині, подальшого ітеративного застосування однієї з функцій, обраної навмання з функцій системи, для перетворення точки й отримання наступної точки. Існує альтернативний алгоритм: генерація всіх можливої послідовностей функцій довжиною не більше даної, з подальшим відображенням результатів застосування кожної з них до початкової точки або фігури.

Кожен з цих алгоритмів забезпечує глобальну побудову, яка генерує точки, розподілені по всьому фракталу. Якщо малюється фрактал малої площі, багато таких точок опиняться поза межами екрана. Це робить масштабування побудови СІФ, намальованої в такий спосіб, непрактичним.

Хоча теорія СІФ вимагає стискальності кожної функції, на практиці програмне забезпечення, що реалізує СІФ, вимагає лише середньої стискальності всієї системи[4].

Діаграма показує побудову СІФ із двох афінних функцій. Функції представлено їх впливом на бі-одиничний квадрат (функція перетворює контурний квадрат у затінений). Поєднання двох функцій утворює оператор Хатчінсона. Показано три ітерації оператора та кінцеве зображення з фіксованої точки — остаточний фрактал.

Ранніми прикладами фракталів, які можна створити з IСФ є множина Кантора, вперше описана 1884 року, та криві де Рама — тип самоподібних кривих, описаний Жордем Де Рамом 1957 року.

СІФ були задумані в їхньому нинішньому вигляді Джоном Е. Хатчінсоном 1981 року[5] і популяризовані за допомогою книги Майкла Барнслі «Фрактали скрізь».

	СІФ надають моделі для деяких рослин, листя та папоротей завдяки самоподібності, яка часто трапляється в розгалужених структурах у природі. Оригінальний текст (англ.) IFSs provide models for certain plants, leaves, and ferns, by virtue of the self-similarity which often occurs in branching structures in nature.
— Майкл Барнслі та інші, V-variable fractals and superfractals (pdf)., 2,22 МБ

• L-система
• Алгоритм фрактального стиснення

• Дрейвс, Скотт; Рекас, Ерік (липень 2007). The Fractal Flame Algorithm (pdf). Архів оригіналу за 9 травня 2008. Процитовано 17 липня 2008.
• Фалконер, Кеннет (1990). Fractal geometry: Mathematical foundations and applications. John Wiley and Sons. с. 113—117, 136. ISBN 0-471-92287-0.
• Барнслі, Майкл; Вінс, Ендрю (2011). The Chaos Game on a General Iterated Function System. Ergodic Theory Dynam. Systems 31 (4): 1073—1079. arXiv:1005.0322.