Перегляд вихідного коду сторінки Система ітераційних функцій

{{Експерт}}
[[Файл:Sierpinski1.png|міні|праворуч|250px|[[Трикутник Серпінського]] створений з СІФ]]
[[Файл:Chris Ursitti fractal 0000.png|міні|200px|Кольорова СІФ, розроблена [[Apophysis]] і випущена {{не перекладено|Electric Sheep}}]]
У [[Математика|математиці]] '''система ітераційних функцій''' ([[Абревіатура|скор.]] ''СІФ'', {{lang-en|Iterated function system}}, ''IFS'')&nbsp;— метод побудови [[фрактал]]ів; отримані фрактали часто є [[Самоподібність|самоподібними]]. Фрактали СІФ більше стосуються [[Теорія множин|теорії множин]], ніж фрактальної геометрії<ref name="picg">{{Cite book|назва=Progress in Computer Graphics: Volume 1|прізвище1=Зобріст|ім'я1=Джордж Вінстон|прізвище2=Сабгарвал|ім'я2=Шаман|рік=1992|видавець=Intellect Books|isbn=9780893916510|сторінка=135|url=https://play.google.com/store/books/details?id=Ai6Qo0qoE9EC|дата-доступу=7 травня 2017}}</ref>. Їх було введено 1981 року.

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

== Визначення ==
Формально система [[Ітераційна функція|ітераційних функцій]] є скінченою множиною стискального відображення на [[Повний метричний простір|повний метричний простір]]<ref>{{Cite book|прізвище=Барнслі|ім'я=Майкл|назва=Фрактали скрізь|видавництво=Academic Press, Inc.|рік=1988}}</ref>. Символічно, <math>\{f_i:X\to X\mid i=1,2,\dots,N\},\ N\in\mathbb{N}</math> є системою ітераційних функцій, якщо кожна <math>f_i</math> є стискальним відображенням на повний метричний простір <math>X</math>.

== Властивості ==
[[Файл:Chaosgame.gif|міні|праворуч|250px|Створення СІФ з допомогою {{не перекладено|Гра хаосу|гри хаосу|en|Chaos game}} (анімація)]]
[[Файл:Ifs-construction.png|міні|Побудова СІФ з допомогою двох функцій]]
1981 року Хатчінсон{{хто?}} показав, що для метричного простору <math>\mathbb{R}^n</math>, така система функцій має унікальну непорожню [[Компактний простір|компактну]] (замкнуту та обмежену) фіксовану множину ''S''. Одним зі способів побудови фіксованого набору є, почати з першої точки множини <math>S_0</math> й ітерувати дії <math>f_i</math>, приймаючи <math>S_{n+1}</math> за сукупність образів <math>S_n</math> на <math>f_i</math>; і наприкінці взяти ''S'' як [[Замикання (топологія)|замикання]] сукупності <math>S_n</math>. Символічно, унікальна фіксована (непорожня компактна) множина <math>S\subseteq X</math> має властивість <math>S = \bigcup_{i=1}^N f_i(S)</math>.

Таким чином, множина ''S'' є фіксованою множиною {{не перекладено|Оператор Хатчінсона|оператора Хатчінсона|en|Hutchinson operator}} <math>H(A)=\bigcup_{i=1}^N f_i(A)</math>.

Існування та єдиність ''S'' є наслідком [[Теорема Банаха про нерухому точку|принципу стискальних відображень]], як і факт того, що <math>\lim_{n\to\infty}H^{\circ n}(A)=S</math> для будь-якої непорожньої компактної множини ''A'' в ''X'' (для стискальної СІФ ця конвергенція має місце навіть для будь-якої непорожньої замкнутої обмеженої множини ''A''). Випадкові елементи довільно близькі до ''S'', можуть бути отримані за допомогою «гри хаосу», описаної далі.

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

Вони природно виникають у проективних просторах, хоча класичне ірраціональне обертання на колі теж може бути адаптовано<ref>{{Стаття|прізвище1=Барнслі|ім'я1=М.|прізвище2=Вінс|ім'я2=А.|назва=The Chaos Game on a General Iterated Function System}}</ref>.

Колекція функцій <math>f_i</math> {{не перекладено|Генератор (математика)|генерує|en|Generator (mathematics)}} [[моноїд]] на [[Композиція функцій|композиції функцій]]. Якщо є тільки дві такі функції, моноїд може бути візуалізований [[Двійкове дерево|бінарним деревом]], де, на кожній вершині дерева, можна взяти композицію двох функцій (тобто взяти ліве або праве піддерево). Загалом, якщо є ''k'' функцій, тоді моноїд можна візуалізувати як повне {{не перекладено|K-арне дерево|||K-ary tree}}, також відоме як [[Ґратка Бете|дерево Келі]].

== Побудова ==
[[Файл:Fractal fern explained.png|міні|upright|[[Папороть Барнслі]], рання СІФ]]
[[Файл:Menger sponge (IFS).jpg|міні|200px|[[Губка Менгера]], тривимірна СІФ]]
Іноді кожна функція <math>f_i</math> повинна бути [[Лінійне відображення|лінійною]] або, більш загально, [[Афінне перетворення|афінним перетворенням]], а отже, представленою [[Матриця (математика)|матрицею]]. Втім, СІФ також можуть бути побудовані з нелінійної функцій, в тому числі з [[Проективне перетворення|проективного перетворення]] і [[перетворення Мебіуса]]. {{не перекладено|Фрактальне полум'я|||Fractal flame}} є прикладом СІФ з нелінійними функціями.

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

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

Хоча теорія СІФ вимагає стискальності кожної функції, на практиці програмне забезпечення, що реалізує СІФ, вимагає лише середньої стискальності всієї системи<ref>{{Cite web|прізвище1=Дрейвс|ім'я1=Скотт|прізвище2=Рекас|ім'я2=Ерік|місяць=липень|рік=2007|url=http://flam3.com/flame.pdf|назва=The Fractal Flame Algorithm|формат=pdf|дата-доступу=17 липня 2008|archiveurl=https://web.archive.org/web/20080509073421/http://flam3.com/flame.pdf|archivedate=9 травня 2008|deadurl=yes}} {{Webarchive|url=https://web.archive.org/web/20080509073421/http://flam3.com/flame.pdf |date=2008-05-09 }}</ref>.

== Приклади ==
Діаграма показує побудову СІФ із двох афінних функцій. Функції представлено їх впливом на бі-одиничний квадрат (функція перетворює контурний квадрат у затінений). Поєднання двох функцій утворює {{не перекладено|оператор Хатчінсона|||Hutchinson operator}}. Показано три ітерації оператора та кінцеве зображення з фіксованої точки&nbsp;— остаточний фрактал.

Ранніми прикладами фракталів, які можна створити з ІСФ є [[множина Кантора]], вперше описана 1884 року, та {{не перекладено|Крива Де Рама|криві де Рама|en|De Rham curve}}&nbsp;— тип самоподібних кривих, описаний {{не перекладено|Жорж Де Рам|Жордем Де Рамом|ru|Де Рам, Жорж}} 1957 року.

== Історія ==
СІФ були задумані в їхньому нинішньому вигляді Джоном Е. Хатчінсоном 1981 року<ref>{{Cite journal|прізвище=Хатчінсон|ім'я=Джон Е.|назва=Fractals and self similarity|журнал=Indiana Univ. Math. J.|том=30|рік=1981|сторінки=713—747|doi=10.1512/iumj.1981.30.30055 |url=http://wwwmaths.anu.edu.au/~john/Assets/Research%20Papers/fractals_self-similarity.pdf|номер=5|формат=pdf}}</ref> і популяризовані за допомогою книги {{не перекладено|Майкла Барнслі|||Michael Barnsley}} «Фрактали скрізь». <!-- In 1992 [[Scott Draves]] developed the [[Fractal flame]] algorithm.-->

{{Цитата|СІФ надають моделі для деяких рослин, листя та папоротей завдяки самоподібності, яка часто трапляється в розгалужених структурах у природі.
{{oq|en|IFSs provide models for certain plants, leaves, and ferns, by virtue of the self-similarity which often occurs in branching structures in nature.}}
|40|Майкл Барнслі ''та інші''|{{Cite web|url=http://www.maths.anu.edu.au/~barnsley/pdfs/V-var_super_fractals.pdf|назва=V-variable fractals and superfractals|формат=pdf}}, 2,22&nbsp;МБ}}

== Див. також ==
* {{не перекладено|L-система||ru}}
* [[Алгоритм фрактального стиснення]]

== Примітки ==
{{reflist}}

== Посилання ==
* {{Cite web|прізвище1=Дрейвс|ім'я1=Скотт|прізвище2=Рекас|ім'я2=Ерік|місяць=липень|рік=2007|url=http://flam3.com/flame.pdf|назва=The Fractal Flame Algorithm|формат=pdf|дата-доступу=17 липня 2008|archiveurl=https://web.archive.org/web/20080509073421/http://flam3.com/flame.pdf|archivedate=9 травня 2008|deadurl=yes}}
* {{Cite book|прізвище=Фалконер|ім'я=Кеннет|назва=Fractal geometry: Mathematical foundations and applications|видавець=John Wiley and Sons|рік=1990|isbn=0-471-92287-0|сторінки=[https://archive.org/details/fractalgeometrym0000falc/page/113 113—117, 136]|url=https://archive.org/details/fractalgeometrym0000falc/page/113}}
* {{Cite journal|прізвище1=Барнслі|ім'я1=Майкл|прізвище2=Вінс|ім'я2=Ендрю|arxiv=1005.0322|назва=The Chaos Game on a General Iterated Function System|журнал=Ergodic Theory Dynam. Systems|том=31|рік=2011|номер=4|сторінки=1073—1079}}

{{Портал|Математика}}
[[Категорія:Ітераційні методи]]
[[Категорія:Фрактали]]