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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Трикутник Серпінського створений з СІФ
Кольорова СІФ, розроблена Apophysis[ru] і випущена Electric Sheep[en]

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

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

Визначення[ред. | ред. код]

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

Властивості[ред. | ред. код]

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

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

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

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

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

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

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

Побудова[ред. | ред. код]

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

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

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

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

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

Приклади[ред. | ред. код]

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

Ранніми прикладами фракталів, які можна створити з IСФ є множина Кантора, вперше описана 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 МБ

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  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). Процитовано 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). The Fractal Flame Algorithm (pdf). Процитовано 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.