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

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

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

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

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

Визначення

Формально система ^[en] є скінченою множиною стискального відображення на повний метричний простір. Символічно, ${\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) можуть віддавати атрактори.

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

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

Побудова

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

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

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

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

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

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

Приклади

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

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

Історія

СІФ були задумані в їхньому нинішньому вигляді Джоном Е. Хатчінсоном 1981 року і популяризовані за допомогою книги ^[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 МБ

Див. також

• ^[ru]
• Алгоритм фрактального стиснення

Примітки

1. Зобріст, Джордж Вінстон; Сабгарвал, Шаман (1992). Progress in Computer Graphics: Volume 1. Intellect Books. с. 135. ISBN . Процитовано 7 травня 2017.
2. Барнслі, Майкл (1988). Фрактали скрізь. Academic Press, Inc.
3. The Chaos Game on a General Iterated Function System.
4. Дрейвс, Скотт; Рекас, Ерік (липень 2007). (PDF). Архів оригіналу (pdf) за 9 травня 2008. Процитовано 17 липня 2008.
5. Хатчінсон, Джон Е. (1981). Fractals and self similarity (pdf). Indiana Univ. Math. J. 30 (5): 713—747. doi:10.1512/iumj.1981.30.30055.

Посилання

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