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

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

Кольорова СІФ, розроблена Apophysis і випущена Шаблон:Не перекладено

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

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

Визначення

Формально система ітераційних функцій є скінченою множиною стискального відображення на повний метричний простір. Символічно, $\{f_i:X\to X\mid i=1,2,\dots ,N\},N\in \mathbb{N}$ є системою ітераційних функцій, якщо кожна $f_i$ є стискальним відображенням на повний метричний простір $X$.

Властивості

Створення СІФ з допомогою Шаблон:Не перекладено (анімація)

Побудова СІФ з допомогою двох функцій

1981 року ХатчінсонШаблон:Хто? показав, що для метричного простору ${ℝ}^n$, така система функцій має унікальну непорожню компактну (замкнуту та обмежену) фіксовану множину S. Одним зі способів побудови фіксованого набору є, почати з першої точки множини $S_0$ й ітерувати дії $f_i$, приймаючи $S_{n+1}$ за сукупність образів $S_n$ на $f_i$; і наприкінці взяти S як замикання сукупності $S_n$. Символічно, унікальна фіксована (непорожня компактна) множина $S\subseteq X$ має властивість $S=\bigcup _{i=1}^N{f}_i(S)$.

Таким чином, множина S є фіксованою множиною Шаблон:Не перекладено $H(A)=\bigcup _{i=1}^N{f}_i(A)$.

Існування та єдиність S є наслідком принципу стискальних відображень, як і факт того, що $\underset{n\to \mathrm{\infty }}{\lim }{H}^{\circ n}(A)=S$ для будь-якої непорожньої компактної множини A в X (для стискальної СІФ ця конвергенція має місце навіть для будь-якої непорожньої замкнутої обмеженої множини A). Випадкові елементи довільно близькі до S, можуть бути отримані за допомогою «гри хаосу», описаної далі.

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

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

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

Побудова

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

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

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

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

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

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

Приклади

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

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

Історія

СІФ були задумані в їхньому нинішньому вигляді Джоном Е. Хатчінсоном 1981 року і популяризовані за допомогою книги Шаблон:Не перекладено «Фрактали скрізь».

Див. також

• Шаблон:Не перекладено
• Алгоритм фрактального стиснення

Посилання

• Шаблон:Cite web
• Шаблон:Cite book
• Шаблон:Cite journal