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

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

Трикутник Серпінського створений з СІФ
Кольорова СІФ, розроблена Apophysis і випущена Electric Sheep

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

Визначення

Формально система ітераційних функцій є скінченою множиною стискального відображення на повний метричний простір[2]. Символічно, є системою ітераційних функцій, якщо кожна є стискальним відображенням на повний метричний простір .

Властивості

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

1981 року Хатчінсон[хто?] показав, що для метричного простору , така система функцій має унікальну непорожню компактну (замкнуту та обмежену) фіксовану множину S. Одним зі способів побудови фіксованого набору є, почати з першої точки множини й ітерувати дії , приймаючи за сукупність образів на ; і наприкінці взяти S як замикання сукупності . Символічно, унікальна фіксована (непорожня компактна) множина має властивість .

Таким чином, множина S є фіксованою множиною оператора Хатчінсона .

Існування та єдиність S є наслідком принципу стискальних відображень, як і факт того, що для будь-якої непорожньої компактної множини A в X (для стискальної СІФ ця конвергенція має місце навіть для будь-якої непорожньої замкнутої обмеженої множини A). Випадкові елементи довільно близькі до S, можуть бути отримані за допомогою «гри хаосу», описаної далі.

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

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

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

Побудова

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

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

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

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

Хоча теорія СІФ вимагає стискальності кожної функції, на практиці програмне забезпечення, що реалізує СІФ, вимагає лише середньої стискальності всієї системи[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 МБ

Див. також

Примітки

  1. Зобріст, Джордж Вінстон; Сабгарвал, Шаман (1992). Progress in Computer Graphics: Volume 1. Intellect Books. с. 135. ISBN 9780893916510. Процитовано 7 травня 2017.
  2. Барнслі, Майкл (1988). Фрактали скрізь. Academic Press, Inc.
  3. The Chaos Game on a General Iterated Function System.
  4. Дрейвс, Скотт; Рекас, Ерік (липень 2007). The Fractal Flame Algorithm (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.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.