fg Ivan Zelinka, Frantiek Vèelaø, Marek Èandík
FRAKTÁLNÍ GEOMETRIE principy a praxe Praha 2006
NÁZORY RECENZENTÙ Monografie Fraktální geometrie, principy a praxe vhodným zpùsobem vyplòuje citelnou mezeru v èesky psané odborné literatuøe. Jde o dílo interdisciplinární, které najde uplatnìní u øady specialistù v pøírodních a technických vìdách, matematice, ale i u specialistù v oblasti IT. Kniha je napsána bez nadbyteèného matematického balastu a pøístup k výkladu by se dal oznaèit jako algoritmický. Proto se bude dobøe èíst i posluchaèùm univerzit; výklad je tak názorný, e mu porozumí absolventi ji prvního roèníku naich vysokých kol. Formálnì je práce rozdìlena do dvou èástí, teoretické a praktické. Obì dvì jsou doplnìny algoritmy v programu Mathematica a zejména øadou nádherných obrázkù. Dílo úspìnì snese srovnání s podobnými publikacemi zahranièními. Mám za to, e kniha má ambice stát se bestsellerem na poli èeské odborné literatury. RNDr. Ale Raidl, Ph.D. MFF UK, Praha Pøedkládaná publikace se zabývá popularizaèní formou svìtem fraktálù. Je nutno zdùraznit, za co se kníka nevydává: nejedná se o uèebnici s pøesnou hierarchií vìtadùkaz, ani o vevyèerpávající katalog fraktálù; a není to ani základní pøíruèka, zabývající se teorií samoorganizace èi chaosu. Kdo hledá pouèení v tìchto oblastech, musí hledat jinde. Kdo se ale zaète do této kníky, dá mi urèitì za pravdu, e potìil své oko i svého ducha. A to není zase tak málo
Prof. RNDr. Pavel Demo, CSc. Fyzikální ústav, AVÈR, Praha Kadý autor odborné knihy urèené iroké veøejnosti se musí vypoøádat s problémem jak vyváit její obsah, aby zùstal pøístupný a ètivý a pøitom si zachoval svoji odbornou úroveò. Po prostudování knihy Fraktální geometrie principy a praxe mohu s potìením konstatovat, e se autorùm podaøilo vytvoøit text, který ètenáøe zaujme a odborníka neurazí, i kdy se v nìkterých èástech museli autoøi Ivan Zelinka, Frantiek Vèelaø a Marek Èandík uchýlit k nutným zjednoduením a zkratkám. I kdy je obor fraktální geometrie relativnì mladý, vysvìtluje nìkteré, do té doby nevysvìtlitelné problémy, obecnì známý je napøíklad problém rozdílného mìøítka pøi mìøení hranic státù. Aplikace fraktální geometrie nachází také vyuití na rùzných místech technické praxe, pøièem je oblast fraktální komprese nejznámìjí, ale ne jedinou. Na øadu dalích moností uplatnìní autoøi ve své knize upozoròují a otevírají tak prostor pro dalí úvahy a experimenty ètenáøù. Významným poèinem autorù je také vytvoøení velkého mnoství aplikaèních úloh v prostøedí programového systému Mathematica, kterými jednak doplnili text knihy a zejména je zpøístupnili v elektronické podobì veøejnosti, aby tak dále podnítili zájem o problematiku fraktální geometrie. Knihu Fraktální geometrie principy a praxe mohu s radostí doporuèit vem zájemcùm o informatiku a její aplikace. Doc. Ing. Radim Farana, CSc. Fakulta strojní, VB-TU, Ostrava
Ivan Zelinka: Vìnuji památce mých prarodièù, Marii a Ondøeji Muchovým. Frantiek Vèelaø: Rád bych tuto kníku vìnoval památce svého otce Ladislava Vèelaøe a jeho nejlepího pøítele Antonína Gajdùka. Byli grafiky, výtvarníky a malíøi. Patøili k malé skupinì lidí, kteøí i za hluboké totality pøináeli Evropu do mìsta Zlína. V dobì, kdy svìt neumìl fraktály ani pojmenovat, tvoøili díla s obrazy, které by dnes byly jednoznaènì povaovány za nejkvalitnìjí výtvory fraktální grafiky. Co na tom, e jeden tak èinil experimentálními fotografickými nebo grafickými a druhý pøedevím malíøskými technikami. Obìma to bylo jasné, nepotøebovali ádnou matematickou berlièku, jejich výtvarné vidìní bylo jednodue prostoupeno pøirozenou fraktální vizí. Marek Èandík: Vìnuji památce Jozefa Èandíka, mého laskavého otce a uèitele.
Publikace se zabývá problematikou fraktální geometrie ve dvou úrovních a to teoretické a aplikaèní. V teoretické èásti se ètenáø dozví co provázelo vznik fraktální geometrie a jací lidé ji pøímo èi nepøímo doprovázeli pøi jejím vzniku. Po té budou vysvìtleny nìkteré algoritmy pomocí kterých se generují fraktální obrazce a to jak èernobílé tak barevné. Témata fraktální dimenze a interpolace jsou zde rovnì diskutovány. V aplikaèní èásti je pozornost vìnována digitální kompresi obrazù pomocí fraktální geometrie s podrobným vysvìtlením metody. Text dále pokraèuje popisem výskytu fraktálù v èasových øadách s vysvìtlením, jak je jich pouíváno burzovními makléøi k burzovním spekulacím. Knihu uzavírá kapitola o moném vyuití fraktální geometrie v ifrování. Knihu provází mnoství programových pøíkladù konstrukce fraktálù v prostøedí Mathematica.
Tato publikace vznikla za podpory grantù: è. MSM 7088352101, GAÈR 102/06/1132 a GAÈR 102/05/0271.
Ivan Zelinka, Frantiek Vèelaø, Marek Èandík
Fraktální geometrie principy a praxe Bez pøedchozího písemného svolení nakladatelství nesmí být kterákoli èást kopírována nebo rozmnoována jakoukoli formou (tisk, fotokopie, mikrofilm nebo jiný postup), zadána do informaèního systému nebo pøenáena v jiné formì èi jinými prostøedky. Autoøi a nakladatelství nepøejímají záruku za správnost titìných materiálù. Pøedkládané informace jsou zveøejnìny bez ohledu na pøípadné patenty tøetích osob. Nároky na odkodnìní na základì zmìn, chyb nebo vynechání jsou zásadnì vylouèeny. Vechny registrované nebo jiné obchodní známky pouité v této knize jsou majetkem jejich vlastníkù. Uvedením nejsou zpochybnìna z toho vyplývající vlastnická práva. Vekerá práva vyhrazena © Ivan Zelinka, Frantiek Vèelaø, Marek Èandík, Zlín 2006 © Nakladatelství BEN technická literatura, Vìínova 5, Praha 10 Ivan Zelinka, Frantiek Vèelaø, Marek Èandík: Fraktální geometrie principy a praxe BEN technická literatura, Praha 2006 1. vydání
ISBN 80-7300-193-4
OBSAH Názory recenzentù Struèná historie fraktální geometrie Pøedmluva
2 8 10
1
11
1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10
2 2.1 2.2 2.3 2.4
3 3.1 3.2 3.3
A
Historický pohled na vznik fraktální geometrie
Georg Ferdinand Ludwig Philipp Cantor ............................................ 15 Wac³aw Franciszek Sierpiñski ............................................................ 16 Niels Fabian Helge von Koch ............................................................. 18 Gaston Maurice Julia ......................................................................... 20 Felix Hausdorff ................................................................................... 22 Alexander Michajloviè Ljapunov ......................................................... 22 Aristid Lindenmayer ........................................................................... 23 Benoit B. Mandelbrot ......................................................................... 24 Edward Norton Lorenz ....................................................................... 26 Otto E. Rössler ................................................................................... 27
Fraktály a jejich principy
29
Konstrukce fraktálù, algoritmus IFS ................................................... 30 Stochastický IFS a jiné algoritmy ....................................................... 47 Juliovy mnoiny a algoritmus TEA ..................................................... 52 Fraktály a pøíbuzné geometrické vzory .............................................. 69
Fraktály a fraktální geometrie
83
Geometricky hladký útvar .................................................................. 84 Nekoneènì èlenitý útvar ..................................................................... 84 Hausdorffova-Besicovicova dimenze ................................................. 85
3.3.1 3.3.1.1 3.3.1.2 3.3.1.3
Výpoèet fraktální dimenze ................................................................... 85 Úseèka ................................................................................................. 86 Ètverec ................................................................................................. 87 Krychle ................................................................................................. 87
Obsah
5
3.3.1.4 3.3.1.5 3.3.1.6 3.3.1.7 3.3.1.8
3.4
4 4.1 4.2 4.3 4.4 4.5 4.6
5 5.1 5.2 5.3
6 6.1
6.2
7 7.1
6
Zobecnìní výpoètu fraktální dimenze .................................................. 87 Cantorovo diskontinuum ...................................................................... 89 Kochova køivka .................................................................................... 89 Sierpinského trojúhelník ...................................................................... 89 Hausdorffova-Besicovicova dimenze vybraných pøírodních útvarù .... 90
Sobìpodobnost .................................................................................. 91
Nìkteré matematické pojmy fraktální geometrie 93 Metrika a metrický prostor .................................................................. 94 Kontraktivní zobrazení ....................................................................... 94 Pevný bod .......................................................................................... 95 Banachova vìta o pevném bodu ....................................................... 95 Iterující funkèní systémy IFS vìta ................................................... 95 Koláová vìta ..................................................................................... 96
Fraktální interpolace
97
Interpolace a fraktální interpolace ...................................................... 98 Jednoduchá fraktální interpolace ....................................................... 99 Fraktální interpolace se skrytými promìnnými ................................ 103
Fraktály a jejich principy
105
Fraktálové kódování digitálních obrazù ........................................... 106
6.1.1 6.1.2 6.1.3 6.1.4 6.1.5 6.1.6 6.1.7 6.1.8 6.1.9
Význam koláové vìty ....................................................................... 106 Dekompozice obrazù ......................................................................... 106 Transformace pøíbuznosti .................................................................. 108 Podobnosti blokù ............................................................................... 110 Jacquinùv kódovací algoritmus ......................................................... 110 Zpìtná rekostrukce obrazù ................................................................ 113 Rychlé kódovací algoritmy ................................................................. 115 Zvyování komprese .......................................................................... 116 Zobecnìní kódovacího algoritmu pro barevné obrazy ...................... 117
Omezení fraktálového kódování obrazù ...........................................119
Fraktály v èasových øadách Elliottovy vlny
121
Elliottova vlna ................................................................................... 122
Zelinka, Vèelaø, Èandík: Fraktální geometrie principy a praxe
A
7.2
7.3
7.4
8 8.1
8.2
8.3 8.4
9 9.1
Impulzní vlny .................................................................................... 123
7.2.1 7.2.2 7.2.3
Rozíøená ........................................................................................... 124 Diagonální pátá .................................................................................. 125 Neúspìná pátá ................................................................................. 125
Korekèní vlny .................................................................................... 126
7.3.1 7.3.2 7.3.3
Cikcak ................................................................................................ 126 Hladká ................................................................................................ 127 Trojúhelník ......................................................................................... 127
Analýza ............................................................................................ 128
Neurofraktální ifrování
Základy kryptologie .......................................................................... 131
8.1.1 8.1.2 8.1.3 8.1.4
Transpozièní systémy ........................................................................ 132 Transkripèní systémy ......................................................................... 132 Polyalfabetické ifry ........................................................................... 132 Systémy s veøejným klíèem ............................................................... 132
Vyuití fraktální geometrie k ifrování .............................................. 133
8.2.1 8.2.2
ifrování obrazù ................................................................................. 133 ifrování textu .................................................................................... 133
Neuronové sítì ................................................................................. 134 Vyuití neuronových sítí k ifrování ................................................. 136
8.4.1 8.4.2
Fraktální ifrování textu ..................................................................... 137 Neurofraktální ifrování textu ............................................................. 138
Inverzní fraktální problém
143
Experiment 1 uèení ....................................................................... 145 Experiment 2 rozeznávání ............................................................ 145
Závìr Literatura a vybrané internetové odkazy Rejstøík A
139
Inverzní fraktální problém a jeho øeení .......................................... 140
10 Pøíklad vyuití neuronové sítì a fraktální geometrie fraktální vidìní 10.1 10.2
129
Obsah
149 151 155 7
STRUÈNÁ HISTORIE FRAKTÁLNÍ GEOMETRIE Období matematických monster (komplexní, neregulární objekty) 1872: Cantorova mnoina diskontinuum 1875: Weierstrassova spojitá køivka bez derivace 1906: Brownùv pohyb, Kochova køivka
Hierarchické, stupòovité chování 1919: 1951: 1956: 1961:
Hausdorffova dimenze komplexních (sloitých) geometrických objektù Hurstùv zákon pro chování toku Nilu Gutenbergùv-Richterùv zákon o distribuci amplitud zemìtøesení Richardsonùv zákon o mìøení komplexních (sloitých) pøírodních útvarù, jako napø. pobøeí 1963: Stommelùv diagram, popisující prostorové a èasové mìøítko pro dynamiku oceánu v èase a prostoru 1969: Rozíøení Hurstovy práce v hydrologii (Mandelbrot, Van Ness, Wallis)
Oficiální vznik fraktální geometrie 1975: Mandelbrot pouil slovo fraktál 1977: Mandelbrotovy fraktály: formy, dimenze 1980: Weierstrassova-Mandelbrotova fraktální funkce geometrie Weierstrassových monster (z r. 1875) 1982: Fraktální modely aplikované na ekologii (Hastings), vzory tvoøené mraky (Lovejoy) 1986: Vznik IFS algoritmu (Barnsley)
Fraktály a dynamika 1981: 1983: 1984: 1987: 1991:
Witten a Sander pøedstavují DLA (Diffusion-Limited Aggregation) Hentschel a Procaccia dávají do souvislosti fraktály a podivné atraktory Zveøejnìna Wolframova dynamika bunìèných automatù Samoorganizace (Bak, Tang, Weisendelf) Kniha Fraktály a multifraktály v geofyzice (Schertzer, Lovejoy)
90. léta 1991: Cca 400 publikací na téma fraktály 1992: Pouívání fraktálù k vysvìtlení nejrùznìjích otázek od struktury vesmíru a po distribuci zemìtøesení 2006: Vznik této publikace :-)
8
Zelinka, Vèelaø, Èandík: Fraktální geometrie principy a praxe
A
Georg Cantor: Umìní klást ty správné otázky je dùleitìjí, ne umìní je øeit.
PØEDMLUVA Pøedkládaná kniha je publikací, která se zabývá tzv. fraktální geometrií. Snahou a snad i cílem autorù bylo vytvoøit publikaci, která by zaplnila jisté vakuum v oblasti fraktální geometrie na kniním trhu a zároveò, aby byla èitelná, pokud mono, pro nejirí okruh ètenáøù. Celá kniha je koncipována tak, e k pochopení základù fraktální geometrie by mìla postaèit sama bez studia dalích materiálù, nicménì studium dalích materiálù je vhodné, zvlátì pro ty ètenáøe, kteøí chtìjí postoupit dále. V takovém pøípadì lze doporuèit literaturu, jako napø. [1] a [2]. Snahou autorù bylo doloit ke vem tvrzením a vztahùm programy, které je realizují, vèetnì obrázkù generovaných tìmito programy. Vekerý poèítaèový kód v této publikaci je napsán v prostøedí Mathematica (www.wolfram.com, www.elkan.cz) a je volnì pøístupný na stránkách www.fai.utb.cz/people/zelinka/fraktaly.zip. Ti ètenáøi, kteøí Mathematicu nevlastní, si mohou zdarma stáhnout tzv. Mathreader (prohlíeè), umoòující pasivní prohlíení kódù a obrázkù. Celá publikace je napsána tak, e je vhodné ji èíst postupnì od zaèátku. V první èásti jsou probrány základy fraktální geometrie, Juliovy mnoiny a tzv. IFS a TEA algoritmy. Dále následuje speciální kapitola, která demonstruje existenci fraktálních a pseudofraktálních mnoin ve vybrané tøídì matematických funkcí, rovnic, fyzikálních a poèítaèových systémù. Tato kapitola byla pøidána hlavnì z dùvodu ukázat ètenáøi, e nádherné fraktální struktury se mohou skrývat za mnohdy na první pohled nudnými, nepøehlednými a sloitými rovnicemi. Poté následuje aplikaèní èást, v ní se ètenáø seznámí, èasto jen rámcovì, s fraktálovým kódováním obrazu, Elliotovými vlnami, neurofraktálním ifrováním atd. Rádi bychom podìkovali naim recenzentùm, a to prof. RNDr. Pavlu Demovi, CSc. (FU AVÈR), doc. Ing. Radimu Faranovi, CSc. (VB-TU Ostrava) a RNDr. Alei Raidlovi, Ph.D (MFF UK) za velmi peèlivé pøeètení rukopisu a cenné pøipomínky, které rozhodnì pøispìly ke zvýení jeho kvality. To, zda se kniha povedla nebo ne, je na názoru ètenáøe. I navzdory faktu, e publikace byla nìkolikrát peèlivì ètena a opravována, nelze vylouèit pøípadné pøeklepy i zásadnìjí chyby, za co se pøedem omlouváme a za dodateèné pøipomínky dìkujeme. Autoøi knihy
