Система ітераційних функцій
Ця стаття потребує уваги й турботи фахівця у своїй галузі. |
У математиці система ітераційних функцій (скор. СІФ, англ. Iterated function system, IFS) — метод побудови фракталів; отримані фрактали часто є самоподібними. Фрактали СІФ більше стосуються теорії множин, ніж фрактальної геометрії[1]. Їх було введено 1981 року.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sierpinski1.png/250px-Sierpinski1.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Chris_Ursitti_fractal_0000.png/200px-Chris_Ursitti_fractal_0000.png)
Фрактали СІФ, як їх зазвичай називають, можуть бути будь-якої розмірності, але найчастіше обчислюються та малюються у 2D. Фрактал складається з об'єднання декількох власних копій, кожна з яких перетворюється функцією (звідси «система функцій»). Канонічним прикладом є трикутник Серпінського. Функції, як правило, стискальні, що означає, що вони об'єднують точки ближче та зменшують розміри фігури. Як наслідок, форма фракталу СІФ складається з декількох менших власних копій, які можуть накладатися одна на одну і кожна з яких також складається зі власних копій, до нескінченності[en]. Це є джерелом природи самоподібності фракталів.
Визначення
ред.Формально система ітераційних функцій є скінченою множиною стискального відображення на повний метричний простір[2]. Символічно, є системою ітераційних функцій, якщо кожна є стискальним відображенням на повний метричний простір .
Властивості
ред.1981 року Хатчінсон[хто?] показав, що для метричного простору , така система функцій має унікальну непорожню компактну (замкнуту та обмежену) фіксовану множину S. Одним зі способів побудови фіксованого набору є, почати з першої точки множини й ітерувати дії , приймаючи за сукупність образів на ; і наприкінці взяти S як замикання сукупності . Символічно, унікальна фіксована (непорожня компактна) множина має властивість .
Таким чином, множина S є фіксованою множиною оператора Хатчінсона[en] .
Існування та єдиність S є наслідком принципу стискальних відображень, як і факт того, що для будь-якої непорожньої компактної множини A в X (для стискальної СІФ ця конвергенція має місце навіть для будь-якої непорожньої замкнутої обмеженої множини A). Випадкові елементи довільно близькі до S, можуть бути отримані за допомогою «гри хаосу», описаної далі.
Нещодавно[коли?] було показано, що СІФ нестискального типу (тобто ті, що складаються з карт, які не є скороченнями відносно будь-якої топологічно-еквівалентної метрики в X) можуть віддавати атрактори.
Вони природно виникають у проективних просторах, хоча класичне ірраціональне обертання на колі теж може бути адаптовано[3].
Колекція функцій генерує[en] моноїд на композиції функцій. Якщо є тільки дві такі функції, моноїд може бути візуалізований бінарним деревом, де, на кожній вершині дерева, можна взяти композицію двох функцій (тобто взяти ліве або праве піддерево). Загалом, якщо є k функцій, тоді моноїд можна візуалізувати як повне K-арне дерево[en], також відоме як дерево Келі.
Побудова
ред.Іноді кожна функція повинна бути лінійною або, більш загально, афінним перетворенням, а отже, представленою матрицею. Втім, СІФ також можуть бути побудовані з нелінійної функцій, в тому числі з проективного перетворення і перетворення Мебіуса. Фрактальне полум'я[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 МБ |
Див. також
ред.Примітки
ред.- ↑ Зобріст, Джордж Вінстон; Сабгарвал, Шаман (1992). Progress in Computer Graphics: Volume 1. Intellect Books. с. 135. ISBN 9780893916510. Процитовано 7 травня 2017.
- ↑ Барнслі, Майкл (1988). Фрактали скрізь. Academic Press, Inc.
- ↑ The Chaos Game on a General Iterated Function System.
- ↑ Дрейвс, Скотт; Рекас, Ерік (липень 2007). The Fractal Flame Algorithm (PDF). Архів оригіналу (pdf) за 9 травня 2008. Процитовано 17 липня 2008.
- ↑ Хатчінсон, Джон Е. (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). Архів оригіналу (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.