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

Трикутник Серпінського створений з СІФ

Кольорова СІФ, розроблена Apophysis і випущена Electric Sheep

У математиці система ітераційних функцій (скор. СІФ, англ. Iterated function system, IFS) — метод побудови фракталів; отримані фрактали часто є самоподібними. Фрактали СІФ більше стосуються теорії множин, ніж фрактальної геометрії. Їх було введено 1981 року.

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

Визначення

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

Властивості

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

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

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

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

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

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

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

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

Побудова

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

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

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

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

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

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

Приклади

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

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

Історія

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

	СІФ надають моделі для деяких рослин, листя та папоротей завдяки самоподібності, яка часто трапляється в розгалужених структурах у природі. Оригінальний текст (англ.) 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). Архів оригіналу (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.