Fraktaalsed atraktorid ja Minkowski-Bouligandi dimensioon¶
Varasemas loengus uurisime, kuidas saab fraktaali dimensiooni defineerida, ja jõudsime sarnasusdimensiooni definitsioonini. See tööleht räägib alternatiivsest mõistest, mida nimetatakse Minkowski-Bouligandi dimensiooniks, ja näitab kuidas definitsiooni saab rakendada atraktoritele. Sarnane mõiste, mis tihti langeb kokku Minkowski-Bouligandi dimensiooniga, on Hausdorff-Besikovitši dimensioon.
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
import numpy.random as rnd
Minkowski-Bouligandi dimensioon¶
Minkowski-Bouligandi dimensioon, või kastilugemise dimensioon, on veel üks võimalus, kuidas saab fraktaali dimensiooni defineerida. Selleks jagatakse faasiruumi $Q = \mathbb{R}^m$ ühtlaselt kastideks
$$Q^{\epsilon}_{i_1 \cdots i_m} = \left[\epsilon\left(i_1 - \frac{1}{2}\right), \epsilon\left(i_1 + \frac{1}{2}\right)\right) \times \ldots \times \left[\epsilon\left(i_m - \frac{1}{2}\right), \epsilon\left(i_m + \frac{1}{2}\right)\right).$$Me nüüd uurime hulka $S \subset Q$. Olgu $N(\epsilon)$ nende suurusega $\epsilon$ kastide $Q^{\epsilon}_{i_1 \cdots i_m}$ arv, mille puhul kehtib $S \cap Q^{\epsilon}_{i_1 \cdots i_m} \neq \emptyset$, ehk hulga maht
$$N(\epsilon) = \#\left\{(i_1, \ldots, i_m) \in \mathbb{Z}^m, S \cap Q^{\epsilon}_{i_1 \cdots i_m} \neq \emptyset\right\}.$$Piiril $\epsilon \to 0$ leiame, et kastide arv käitub kui $N(\epsilon) \approx C\epsilon^{-d}$, kus $C$ on konstantne $d$ on Minkowski-Bouligandi dimensioon. Logaritimi abil leiame
$$\ln N(\epsilon) \approx \ln C - d\ln\epsilon.$$Sellest järeldub
$$d = -\lim_{\epsilon \to 0}\frac{\ln N(\epsilon) - \ln C}{\ln\epsilon} = -\lim_{\epsilon \to 0}\frac{\ln N(\epsilon)}{\ln\epsilon}.$$Praktikas on tihti kasulikum, Minkowski-Bouligandi dimensioon teisel viisil arvutada. Tavaliselt teame, et hulk $S$ on risttahuka $R$ alamhulk, $S \subset R \subset Q$. Seega piisab sellest, et me jagame hulka $R$ kastideks, niiet kastide koguarv on lõplik. Kastide suuruseks kasutame $\epsilon = 2^{-p}$, millest järeldub $\ln\epsilon = -p\ln 2$. Seega kehtib
$$\ln N(2^{-p}) \approx \ln C + dp\ln 2.$$Funktsioon
$$p \mapsto \frac{\ln N(2^{-p})}{\ln 2} = \log_2N(2^{-p})$$seega käitub asümptootiliselt nagu lineaarne funktsioon, mille kasv on $d$, ja me võime defineerida
$$d = \lim_{p \to \infty}\frac{d}{dp}\log_2N(2^{-p}).$$Piiril $p \to \infty$ ilmub aga praktiline probleem, et tihti teame ainult lõpliku arvu punkte $x_n \in S$, näiteks kui $S$ on diskreetse dünaamika atraktor, ja $(x_n)$ on trajektoor, mis koondub atraktorile, ja millest meil on lõplik osa $x_0, \ldots, x_{n_0 - 1}$ arvutatud. Kui me aga eeldame, et $S \approx S_{n_0} = \{x_n, n < n_0\}$, siis kehtib
$$N_{n_0}(\epsilon) = \#\left\{(i_1, \ldots, i_m) \in \mathbb{Z}^m, S \cap Q^{\epsilon}_{i_1 \cdots i_m} \neq \emptyset\right\} = \#\left\{(i_1, \ldots, i_m) \in \mathbb{Z}^m, \exists n < n_0: x_n \in Q^{\epsilon}_{i_1 \cdots i_m} \neq \emptyset\right\} \leq n_0,$$kuna kastide arv, milles asub vähemalt üks punkt $x_n$, ei saa olla suurem kui punktide arv $n_0$. Seega $N_{n_0}(\epsilon)$ ei saa kasvata üle selle piiri. Praktiliselt peame seega sellega leppima, et on mõistlik ülempiir $p$, mis on seda suurem, mida suurem on punktide arv $n_0$.
Alljärgnev algoritm aitab hinnata Minkowski-Bouligandi dimensiooni, kui hulk asub kahemõõtmelises faasiruumis. pts on punktide loetelu, xmin ja xmax on ristküliku alumine-vasakpoolne ja ülemine-parempoolne nurk ning pmax on parameetri $p$ maksimaalne väärtus. Algoritm joonistab $\frac{d}{dp}\log_2N(2^{-p})$ sõltuvalt parameetrist $p$. Kui joon on horitsontaalne, võrdub $\frac{d}{dp}\log_2N(2^{-p})$ umbes Minkowski-Bouligandi dimensiooniga.
def hbdim(pts, xmin, xmax, pmax):
sets = [np.zeros((2 ** p, 2 ** p), dtype=np.int8) for p in range(pmax + 1)]
Xmin = np.array(xmin)
Xdiff = np.array(xmax) - Xmin
for x in pts:
y = (x - Xmin) / Xdiff
for p in range(pmax + 1):
sets[p][int(2 ** p * y[0]), int(2 ** p * y[1])] = 1
visited = [s.sum() for s in sets]
logs = np.log2(visited)
ldiff = np.diff(logs)
print(visited)
print(logs)
print(ldiff)
plt.plot(logs)
plt.show()
plt.plot(ldiff)
plt.show()
Henon atraktor¶
Esimene fraktaal, millele me Minkowski-Bouligandi algoritmi rakendame, on Henoni atraktor. See on diskreetse dünaamika atraktor faasiruumis $Q = \mathbb{R}^2$, mis on definieeritud kui
\begin{align} x_{n + 1} &= y_n - ax_n^2 + 1,\\ y_{n + 1} &= bx_n. \end{align}Seega defineerime:
def henon(x, a, b):
return [x[1] + 1 - a * x[0] ** 2, b * x[0]]
Konstantsed parameetrid on tavaliselt valitud $a = 1.4$ ja $b = 0.3$:
a = 1.4
b = 0.3
Atraktori joonistamiseks on lisaks ka algtingimust vaja. Algtingimuseks valime $(x_0, y_0) = (0, 0)$.
x = [0, 0]
Atraktori jooonistamiseks arvutame trajektoori. Trajektoori algust $(x_0, y_0), \ldots, (x_{n_1}, y_{n_1})$ me ei joonista, kuna siis trajektoor alles läheneb atraktorile, vaid joonistame ainult osa $(x_{n_1 + 1}, y_{n_1 + 1}), \ldots, (x_{n_2}, y_{n_2})$. Selleks valime $n_1$ ja $n_2$ järgnevalt:
npre = 100
nmax = 1000000
Lõpuks joonistame:
res = []
for _ in range(npre):
x = henon(x, a, b)
for _ in range(nmax):
x = henon(x, a, b)
res.append(x)
val = np.array(res)
fig = plt.figure(figsize=(8, 6), dpi=96)
ax = fig.add_subplot(111)
ax.scatter(val[:, 0], val[:, 1], marker=".", s=1, lw=0)
plt.show()
Lisaks arvutame ka Minkowski-Bouligandi dimensiooni eelnevalt defineeritud algoritmi abil. Kõik punktid trajektoori peal asuvad hulgas $(-1.5, 1.5) \times (-0.5, 0.5) \subset \mathbb{R}^2$. Seega valime:
hbdim(val, [-1.5, -0.5], [1.5, 0.5], 16)
Joonis näitab, et logaritmide kasv on enam-vähem tasane vahemikus $1.2 \ldots 1.3$. Sellest järeldub, et Minkowski-Bouligandi dimensioon asub selles vahemikus. Kirjanduses leidub väärtus $1.261 \pm 0.003$.
Itereeritud funktsioonisüsteemid¶
Järgmisena uurime fraktaalide klassi, mis ei ole determineeritud dünaamika, vaid juhusliku dünaamika atraktorid. Faasiruumis $Q$ on antud $m$ funktsiooni $f_1, \ldots, f_m: Q \to Q$. Igal sammul $x_n \to x_{n + 1}$ valitakse juhuslikult ühe. Seega tekib juhuslik trajektoor. Sellist süsteemi nimetatakse itereeritud funktsioonisüsteemiks.
Alljärgnev kood joonistab sellist süsteemi.
def ifsplot(ifs, x0, npre, nmax):
ni = len(ifs)
wgh = []
for fkt in ifs:
wgh.append(fkt[2])
wgh = np.array(wgh) / sum(wgh)
rnd.seed()
x = x0
res = []
for _ in range(npre):
r = rnd.choice(ni, p=wgh)
x = np.dot(ifs[r][0], x) + ifs[r][1]
for _ in range(nmax):
r = rnd.choice(ni, p=wgh)
x = np.dot(ifs[r][0], x) + ifs[r][1]
res.append(x)
val = np.array(res)
fig = plt.figure(figsize=(6, 6), dpi=96)
ax = fig.add_subplot(111)
ax.set_aspect('equal')
ax.scatter(val[:, 0], val[:, 1], marker=".", s=1, lw=0)
plt.show()
return val
Nagu ka eelmise näite puhul valime joonistamiseks ainult trajektoori osa, mis asub atraktori lähedal.
npre = 100
nmax = 1000000
Lisaks valime ka algtingimust. Kuna trajektoor jälgib atraktori kuju, ei sõltu trajektoori kvalitatiivne kuju algtingimuse valikust.
x0 = np.array([0.3, 0.7])
Süsteemides, mida me uurime, on funktsioonid $f_i$ affiinsed teisendused kahemõõtmelises ruumis,
$$f_i(\underline{x}) = \underline{\underline{M}} \cdot \underline{x} + \underline{v}.$$Sierpinski kolmnurk¶
Esimene näide on Sierpinski kolmnurk, mida me juba varasemas loengus joonistasime. Nüüd konstrueerime seda intereeritud funktsioonisüsteemina. Selleks valime:
sierp3 = [
(np.array([[1/2, 0], [0, 1/2]]), np.array([0, 1]), 1),
(np.array([[1/2, 0], [0, 1/2]]), np.array([np.sqrt(3)/2, -1/2]), 1),
(np.array([[1/2, 0], [0, 1/2]]), np.array([-np.sqrt(3)/2, -1/2]), 1)
]
Tulemus on tuttav kuju:
val = ifsplot(sierp3, x0, npre, nmax)
Lisaks arvutame ka Minkowski-Bouligandi dimensiooni:
hbdim(val, [-2.0, -1.0], [2.0, 2.1], 16)
Joonis näitab, et Minkowski-Bouligandi dimensioon on umbes $1.55 \ldots 1.6$. Tuletame meelde, et sarnasusdimensioon on $\frac{\ln 3}{\ln 2}$:
np.log(3) / np.log(2)
Sierpinski vaip / nelinurk¶
Samuti tuttav näide on Sierpinski vaip, mida me konstrueerime järgnevalt:
sierp4 = [
(np.array([[1/3, 0], [0, 1/3]]), np.array([1, 1]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([1, -1]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([-1, 1]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([-1, -1]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([1, 0]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([0, 1]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([-1, 0]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([0, -1]), 1)
]
Ka selle süsteemi kuju on juba tuttav:
val = ifsplot(sierp4, x0, npre, nmax)
Järgmisena arvutame Minkowski-Bouligandi dimensiooni:
hbdim(val, [-1.6, -1.6], [1.6, 1.6], 16)
Tulemus näitab, et ta on umbes $1.85 \ldots 1.9$. Sarnasusdimensioon on $\frac{\ln 8}{\ln 3}$:
np.log(8) / np.log(3)
Sierpinski kuusnurk - variant 1¶
Lisaks eelnevalt näidatud kujudele võib näiteks ka kuusnurka konstrueerida. Üks võimalus on selline:
sierp6a = [
(np.array([[1/3, 0], [0, 1/3]]), np.array([1, 0]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([-1, 0]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([0.5, np.sqrt(3)/2]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([0.5, -np.sqrt(3)/2]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([-0.5, np.sqrt(3)/2]), 1),
(np.array([[1/3, 0], [0, 1/3]]), np.array([-0.5, -np.sqrt(3)/2]), 1)
]
Joonisel on tõepoolest kuusnurga sümmeetria:
val = ifsplot(sierp6a, x0, npre, nmax)
Arvutame Minkowski-Bouligandi dimensiooni:
hbdim(val, [-1.6, -1.5], [1.6, 1.5], 16)
Väärtus on seega umbes $1.6 \ldots 1.65$. Analüütiliselt leiame sarnasusdimensiooni $\frac{\ln 6}{\ln 3}$.
np.log(6) / np.log(3)
Sierpinski kuusnurk - variant 2¶
Teine võimalus kuidas kuusnurka konstrueerida on selline:
sierp6b = [
(np.array([[0, np.sqrt(3/25)], [-np.sqrt(3/25), 0]]), np.array([1, 0]), 1),
(np.array([[0, np.sqrt(3/25)], [-np.sqrt(3/25), 0]]), np.array([-1, 0]), 1),
(np.array([[0, np.sqrt(3/25)], [-np.sqrt(3/25), 0]]), np.array([0.5, np.sqrt(3)/2]), 1),
(np.array([[0, np.sqrt(3/25)], [-np.sqrt(3/25), 0]]), np.array([0.5, -np.sqrt(3)/2]), 1),
(np.array([[0, np.sqrt(3/25)], [-np.sqrt(3/25), 0]]), np.array([-0.5, np.sqrt(3)/2]), 1),
(np.array([[0, np.sqrt(3/25)], [-np.sqrt(3/25), 0]]), np.array([-0.5, -np.sqrt(3)/2]), 1)
]
Ka seekord leiame kuusnurga sümmeetriat:
val = ifsplot(sierp6b, x0, npre, nmax)
Arvutame Minkowski-Bouligandi dimensiooni:
hbdim(val, [-1.6, -1.5], [1.6, 1.5], 16)
Tulemus on umbes $1.65 \ldots 1.7$ ja seega natuke suurem kui eelmisel korral. Analüütiliselt leiame sarnasusdimensiooni $\frac{\ln 6}{\ln\frac{5}{\sqrt{3}}} = \frac{2\ln 6}{2\ln 5 - \ln 3}$.
2 * np.log(6) / (2 * np.log(5) - np.log(3))
Sõnajalg¶
Teistsugune näide väiksema sümmeetriaga on sõnajalg, mida me defineerime järgnevalt:
fern = [
(np.array([[0, 0], [0, 0.16]]), np.array([0, 0]), 1),
(np.array([[0.85, 0.04], [-0.04, 0.85]]), np.array([0, 1.6]), 85),
(np.array([[0.2, -0.26], [0.23, 0.22]]), np.array([0, 1.6]), 7),
(np.array([[-0.15, 0.28], [0.26, 0.24]]), np.array([0, 0.44]), 7)
]
Tulemus selgitab selle kuju nime:
val = ifsplot(fern, x0, npre, nmax)
Arvutame Minkowski-Bouligandi dimensiooni:
hbdim(val, [-3.0, -0.1], [3.0, 11.0], 16)
Binaarne puu¶
Veel üks lihtne võimalus on binaarne puu, mida me järgmisena uurime.
tree = [
(np.array([[0, 0], [0, 0.5]]), np.array([0, 0]), 1),
(np.array([[0.42, -0.42], [0.42, 0.42]]), np.array([0, 0.2]), 8),
(np.array([[0.42, 0.42], [-0.42, 0.42]]), np.array([0, 0.2]), 8),
(np.array([[0.1, 0], [0, 0.1]]), np.array([0, 0.2]), 3)
]
Tulemus on selline:
val = ifsplot(tree, x0, npre, nmax)
Arvutame Minkowski-Bouligandi dimensiooni:
hbdim(val, [-0.25, 0], [0.25, 0.45], 16)
Test¶
def sierpn(s, n):
return [(np.array([[s, 0], [0, s]]), np.array([np.cos(2 * i * np.pi / n), np.sin(2 * i * np.pi / n)]), 1) for i in range(n)]
nmax = 100000
vals = [ifsplot(sierpn(1 / (np.sqrt(0.25 + 2 * n) - 0.5), n), x0, npre, nmax) for n in range(2,11)]
