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

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

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

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

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

Визначення

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

Властивості

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

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

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 є фіксованою множиною оператора Хатчінсона^[en] ${\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}}$ генерує^[en] моноїд на композиції функцій. Якщо є тільки дві такі функції, моноїд може бути візуалізований бінарним деревом, де, на кожній вершині дерева, можна взяти композицію двох функцій (тобто взяти ліве або праве піддерево). Загалом, якщо є k функцій, тоді моноїд можна візуалізувати як повне K-арне дерево^[en], також відоме як дерево Келі.

Побудова

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

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

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

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

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

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

Приклади

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

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

Історія

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

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