Iterowany system funkcji

Trójkąt Sierpińskiego utworzony przy użyciu IFS (pokolorowany w celu zilustrowania struktury samopodobnej)

Kolorowy IFS zaprojektowany przy użyciu oprogramowania Apophysis i renderowany przez Electric Sheep .

W matematyce iterowane systemy funkcyjne ( IFS ) są metodą konstruowania fraktali ; powstałe fraktale są często samopodobne . Fraktale IFS są bardziej związane z teorią mnogości niż z geometrią fraktalną. Zostały wprowadzone w 1981 roku.

IFS , jak się je zwykle nazywa, mogą mieć dowolną liczbę wymiarów, ale zwykle są obliczane i rysowane w 2D. Fraktal składa się z połączenia kilku swoich kopii, przy czym każda kopia jest przekształcana przez funkcję (stąd „system funkcji”). Kanonicznym przykładem jest trójkąt Sierpińskiego . Funkcje są zwykle kontrakcyjne , co oznacza, że ​​zbliżają do siebie punkty i zmniejszają kształty. Stąd kształt fraktala IFS składa się z kilku prawdopodobnie nakładających się mniejszych kopii samego siebie, z których każda składa się również z własnych kopii, ad infinitum . To jest źródłem jego samopodobnej natury fraktalnej.

Definicja

Formalnie, iterowany system funkcji jest skończonym zbiorem odwzorowań skurczów w kompletnej przestrzeni metrycznej . Symbolicznie,

${\ Displaystyle \ {f_ {i}: X \ do X \ mid i = 1,2, \ kropki, N \} ,\ N\w \mathbb {N}}$

jest iterowanym systemem funkcji, jeśli każdy $ja$ skróceniem całej przestrzeni metrycznej. ${\ displaystyle X$ .

Nieruchomości

Budowa IFS przez grę chaosu (animowana)

IFS tworzony z dwiema funkcjami.

₀ Hutchinson wykazał, że dla przestrzeni metrycznej lub bardziej ogólnie dla pełnej przestrzeni metrycznej taki układ funkcji ma unikalną niepustą zwartość $} ^ {n}}$$displaystyle \ mathbb {$ (domknięty i ograniczony) zbiór stały S . _Jednym ze sposobów konstruowania stałego zbioru jest rozpoczęcie od początkowego niepustego, zamkniętego i ograniczonego zbioru S i powtórzenie działań fi , przyjmując, że S _{n + 1} jest sumą obrazów S _n pod f _ja ; następnie przyjmując S jako zamknięcie granicy ${\ Displaystyle \ lim _ {n \ rightarrow \ infty} S_ {n}}$ . Symbolicznie, unikalny stały (niepusty zwarty) zbiór ma właściwość ${\ Displaystyle S \ subseteq X}$

${\ Displaystyle S = {\ overline {\ bigcup _ {i = 1} ^ {N} f_ {i} (S)}}.}$

Zbiór S jest zatem ustalonym zbiorem operatora Hutchinsona zdefiniowanym dla $Displaystyle A \ subseteq X }$${\ Displaystyle F: 2 ^ {X} \ do 2 ^ {X}}$ przez

${\ Displaystyle F (A) = {\ overline {\ bigcup _ {i = 1} ^ {N} f_ {i} (A)}}.}$

Istnienie i niepowtarzalność S jest konsekwencją zasady odwzorowania kontrakcji , podobnie jak fakt, że

${\ Displaystyle \ lim _ {n \ do \ infty} F ^ {n} (A) = S}$

dla dowolnego niepustego zestawu kompaktowego ${\ displaystyle A}$ w ${\ displaystyle X}$ . (Dla kurczliwego IFS ta zbieżność ma miejsce nawet dla dowolnego niepustego zbioru domkniętego i ${\ displaystyle A}$ ). Losowe elementy dowolnie bliskie S można uzyskać za pomocą opisanej poniżej „gry w chaos”.

Niedawno wykazano, że IFS typu niekontraktywnego (tj. złożonego z odwzorowań, które nie są kontrakcjami względem żadnej topologicznie równoważnej metryki w X ) mogą dawać atraktory. Powstają one naturalnie w przestrzeniach rzutowych, chociaż można również dostosować klasyczny irracjonalny obrót na okręgu.

Zbiór $_$ monoid w kompozycji . _ _ Jeśli są tylko dwie takie funkcje, monoid można zobrazować jako drzewo binarne , gdzie w każdym węźle drzewa można komponować z jedną lub drugą funkcją ( tzn . wziąć lewą lub prawą gałąź). Ogólnie rzecz biorąc, jeśli istnieje k funkcji, monoid można zwizualizować jako pełne drzewo k -ary , znane również jako drzewo Cayleya .

Konstrukcje

Paproć Barnsleya , wczesny IFS

Gąbka Mengera , trójwymiarowy IFS.

„Drzewo” IFS zbudowane z nieliniowej funkcji Julia

Czasami każda funkcja $liniową$ być transformacją lub bardziej ogólnie transformacją afiniczną , zatem reprezentowaną przez macierz . Jednak IFS można również budować z funkcji nieliniowych, w tym transformacji rzutowych i transformacji Möbiusa . Płomień fraktalny jest przykładem IFS z funkcjami nieliniowymi.

Najpopularniejszy algorytm do obliczania fraktali IFS nazywa się „ grą chaosu ”. Polega na wybraniu losowego punktu na płaszczyźnie, a następnie iteracyjnym zastosowaniu jednej z losowo wybranych funkcji z układu funkcyjnego w celu przekształcenia tego punktu w celu uzyskania następnego punktu. Alternatywnym algorytmem jest wygenerowanie każdej możliwej sekwencji funkcji do określonej maksymalnej długości, a następnie wykreślenie wyników zastosowania każdej z tych sekwencji funkcji do początkowego punktu lub kształtu.

Każdy z tych algorytmów zapewnia globalną konstrukcję, która generuje punkty rozmieszczone na całym fraktalu. Jeśli rysowany jest mały obszar fraktala, wiele z tych punktów wypadnie poza granice ekranu. To sprawia, że ​​powiększanie konstrukcji IFS narysowanej w ten sposób jest niepraktyczne.

Chociaż teoria IFS wymaga, aby każda funkcja była kontrakcyjna, w praktyce oprogramowanie implementujące IFS wymaga jedynie, aby cały system był średnio kontraktywny.

Partycjonowane iterowane systemy funkcyjne

PIFS (partycjonowane iterowane systemy funkcyjne), zwane także lokalnymi iterowanymi systemami funkcyjnymi, zapewniają zaskakująco dobrą kompresję obrazu, nawet w przypadku zdjęć, które nie wydają się mieć tego rodzaju samopodobnej struktury, jak zwykłe fraktale IFS.

Problem odwrotny

Główny artykuł: Kompresja fraktalna

Istnieją bardzo szybkie algorytmy do generowania obrazu z zestawu parametrów IFS lub PIFS. Przechowywanie opisu sposobu jego utworzenia, przesyłanie tego opisu do urządzenia docelowego i ponowne generowanie tego obrazu na urządzeniu docelowym jest szybsze i wymaga znacznie mniej miejsca niż przechowywanie i przesyłanie koloru każdego piksela obrazu .

Odwrotny problem jest trudniejszy: biorąc pod uwagę jakiś oryginalny dowolny obraz cyfrowy, taki jak fotografia cyfrowa, spróbuj znaleźć zestaw parametrów IFS, który po ocenie przez iterację daje inny obraz wizualnie podobny do oryginału. W 1989 roku Arnaud Jacquin przedstawił rozwiązanie ograniczonej postaci problemu odwrotnego, używając tylko PIFS; ogólna postać problemu odwrotnego pozostaje nierozwiązana.

Od 1995 roku całe oprogramowanie do kompresji fraktali opiera się na podejściu Jacquina.

Przykłady

Diagram przedstawia konstrukcję IFS z dwóch funkcji afinicznych. Funkcje są reprezentowane przez ich wpływ na dwujednostkowy kwadrat (funkcja przekształca obrysowany kwadrat w zacieniony kwadrat). Połączenie tych dwóch funkcji tworzy operator Hutchinsona . Pokazane są trzy iteracje operatora, a następnie końcowy obraz przedstawia stały punkt, końcowy fraktal.

Wczesne przykłady fraktali, które mogą być generowane przez IFS, obejmują zbiór Cantora , po raz pierwszy opisany w 1884 roku; i krzywe de Rhama , rodzaj krzywej samopodobnej opisanej przez Georgesa de Rhama w 1957 roku.

Historia

IFS zostały wymyślone w obecnej postaci przez Johna E. Hutchinsona w 1981 roku i spopularyzowane przez książkę Michaela Barnsleya Fractals Everywhere .

IFS zapewniają modele dla niektórych roślin, liści i paproci dzięki samopodobieństwu, które często występuje w rozgałęzionych strukturach w przyrodzie.

— Michael Barnsley i in.

Zobacz też

• System o złożonej podstawie
• Twierdzenie o kolażu
• Nieskończone kompozycje funkcji analitycznych
• Układ L
• Kompresja fraktalna

Notatki

• Draves, Scott ; Erik Reckase (lipiec 2007). „Algorytm fraktalnego płomienia” (PDF) . Zarchiwizowane od oryginału (pdf) w dniu 2008-05-09 . Źródło 2008-07-17 .
•   Sokolnik, Kenneth (1990). Geometria fraktalna: podstawy matematyczne i zastosowania . John Wiley i synowie. s. 113–117, 136 . ISBN 0-471-92287-0 .
• Barnsley, Michael ; Andrew Vince (2011). „Gra w chaos w ogólnym iterowanym systemie funkcji”. Dynam Teorii Ergodycznej. Systemy . 31 (4): 1073–1079. ar Xiv : 1005.0322 . Bibcode : 2010arXiv1005.0322B .
• Przegląd historyczny i uogólnienie: David, Claire (2019). „Właściwości fraktalne funkcji typu Weierstrassa” . Obrady Międzynarodowego Centrum Geometrii . 12 (2): 43–61.

Linki zewnętrzne

• Elementarz na elementarnej teorii nieskończonych kompozycji złożonych funkcji