У математиці система ітераційних функцій (скор. СІФ, , IFS) — метод побудови фракталів; отримані фрактали часто є самоподібними. Фрактали СІФ більше стосуються теорії множин, ніж фрактальної геометрії. Їх було введено 1981 року.
Фрактали СІФ, як їх зазвичай називають, можуть бути будь-якої розмірності, але найчастіше обчислюються та малюються у 2D. Фрактал складається з об'єднання декількох власних копій, кожна з яких перетворюється функцією (звідси «система функцій»). Канонічним прикладом є трикутник Серпінського. Функції, як правило, стискальні, що означає, що вони об'єднують точки ближче та зменшують розміри фігури. Як наслідок, форма фракталу СІФ складається з декількох менших власних копій, які можуть накладатися одна на одну і кожна з яких також складається зі власних копій, . Це є джерелом природи самоподібності фракталів.
Визначення Формально система ітераційних функцій є скінченою множиною стискального відображення на повний метричний простір. Символічно, є системою ітераційних функцій, якщо кожна є стискальним відображенням на повний метричний простір .
Властивості
1981 року Хатчінсон показав, що для метричного простору , така система функцій має унікальну непорожню компактну (замкнуту та обмежену) фіксовану множину S. Одним зі способів побудови фіксованого набору є, почати з першої точки множини й ітерувати дії , приймаючи за сукупність образів на ; і наприкінці взяти S як замикання сукупності . Символічно, унікальна фіксована (непорожня компактна) множина має властивість .
Таким чином, множина S є фіксованою множиною .
Існування та єдиність S є наслідком принципу стискальних відображень, як і факт того, що для будь-якої непорожньої компактної множини A в X (для стискальної СІФ ця конвергенція має місце навіть для будь-якої непорожньої замкнутої обмеженої множини A). Випадкові елементи довільно близькі до S, можуть бути отримані за допомогою «гри хаосу», описаної далі.
Нещодавно було показано, що СІФ нестискального типу (тобто ті, що складаються з карт, які не є скороченнями відносно будь-якої топологічно-еквівалентної метрики в X) можуть віддавати атрактори.
Вони природно виникають у проективних просторах, хоча класичне ірраціональне обертання на колі теж може бути адаптовано.
Колекція функцій моноїд на композиції функцій. Якщо є тільки дві такі функції, моноїд може бути візуалізований бінарним деревом, де, на кожній вершині дерева, можна взяти композицію двох функцій (тобто взяти ліве або праве піддерево). Загалом, якщо є k функцій, тоді моноїд можна візуалізувати як повне , також відоме як дерево Келі.
Побудова
Іноді кожна функція повинна бути лінійною або, більш загально, афінним перетворенням, а отже, представленою матрицею. Втім, СІФ також можуть бути побудовані з нелінійної функцій, в тому числі з проективного перетворення і перетворення Мебіуса. є прикладом СІФ з нелінійними функціями.
Найпоширенішим алгоритмом обчислення СІФ-фракталів є . Вона складається з вибору довільної точки на площині, подальшого ітеративного застосування однієї з функцій, обраної навмання з функцій системи, для перетворення точки й отримання наступної точки. Існує альтернативний алгоритм: генерація всіх можливої послідовностей функцій довжиною не більше даної, з подальшим відображенням результатів застосування кожної з них до початкової точки або фігури.
Кожен з цих алгоритмів забезпечує глобальну побудову, яка генерує точки, розподілені по всьому фракталу. Якщо малюється фрактал малої площі, багато таких точок опиняться поза межами екрана. Це робить масштабування побудови СІФ, намальованої в такий спосіб, непрактичним.
Хоча теорія СІФ вимагає стискальності кожної функції, на практиці програмне забезпечення, що реалізує СІФ, вимагає лише середньої стискальності всієї системи .
Приклади Діаграма показує побудову СІФ із двох афінних функцій. Функції представлено їх впливом на бі-одиничний квадрат (функція перетворює контурний квадрат у затінений). Поєднання двох функцій утворює . Показано три ітерації оператора та кінцеве зображення з фіксованої точки — остаточний фрактал.
Ранніми прикладами фракталів, які можна створити з ІСФ є множина Кантора, вперше описана 1884 року, та — тип самоподібних кривих, описаний 1957 року.
Історія СІФ були задумані в їхньому нинішньому вигляді Джоном Е. Хатчінсоном 1981 року і популяризовані за допомогою книги «Фрактали скрізь».
Див. також
Алгоритм фрактального стиснення
Примітки
Посилання