{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Klassikalised fraktalid ja sarnasusdimensioon"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Viimastes loengutes oleme näinud, et atraktoritel võib olla ka \"kummaline\" struktuur. Kaootiliste süsteemide atraktorid on tihti *fraktaalsed*. Käesolev tööleht selgitab fraktaalide põhimõisteid ja omadusi."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Hulgad eukleidilises ruumis ja sarnasusdimensioon"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Fraktaalide mõõtmiseks oluline omadus on fraktaali *dimensioon*, mida saab erivatel viisidel defineerida. Üks kõige lihtsamatest definitsioonitest on *sarnasusdimensioon*. Selle mõiste kirjeldamiseks on kõige lihtsam vaadata kuupi $K^d = [0, 1]^d \\subset \\mathbb{R}^d$ üldises $d$-mõõtmelises eukleidilises ruumis. Kui me võtame kordajaga $\\frac{1}{n}$ skaleeritud kuupi\n",
"\n",
"$$\\left\\{\\frac{(x_1, x_2, \\ldots, x_d)}{n}, (x_1, x_2, \\ldots, x_d) \\in K^d\\right\\},$$\n",
"\n",
"siis võib $N = n^d$ koopiast kuupi $K^d$ taas ehitada,\n",
"\n",
"$$K^d = \\bigcup_{a_1 = 0}^{n - 1}\\cdots\\bigcup_{a_d = 0}^{n - 1}\\left\\{\\frac{(x_1 + a_1, x_2 + a_2, \\ldots, x_d + a_d)}{n}, (x_1, x_2, \\ldots, x_d) \\in K^d\\right\\}.$$\n",
"\n",
"Kuubi dimensiooni leiame kui $d = \\frac{\\ln N}{\\ln n}$. Seega defineerime: Kui fraktaalset hulka saab jagada $N$ osaks nii, et iga osa on $n$ korda väiksem kui esialgne hulk, siis tema sarnasusdimensioon on $\\frac{\\ln N}{\\ln n}$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Klassikalised fraktaalid ja nende sarnasusdimensioonid"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Järgmisena uurime erinevaid fraktaale. Nende joonistamiseks kasutame SVG graafikaformaati."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from IPython.display import SVG, display\n",
"from math import sqrt"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Kuna meie joonised on suuremad kui tavaliselt, suurendame ka tulemusalasid."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%html\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Cantori hulk"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Cantori hulk](http://en.wikipedia.org/wiki/Cantor_set) $C_{\\infty}$ on tüüpiline fraktaali näide, mida võib defineerida sellisel viisil:\n",
"\n",
"* $C_0 = [0, 1]$.\n",
"* $C_{n + 1} = \\left\\{\\frac{x}{3}, x \\in C_n\\right\\} \\cup \\left\\{\\frac{x + 2}{3}, x \\in C_n\\right\\}$.\n",
"* $$C_{\\infty} = \\bigcap_{n = 0}^{\\infty}C_n.$$\n",
"\n",
"Hulki $C_n$ võime ka joonistada SVG graafikuna Pythoni abil. Selleks defineerime:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"def cantor(n):\n",
" display(SVG(data=cantorsvg(cantorit(n, 0.0, 1.0))))\n",
"\n",
"def cantorsvg(s):\n",
" return ''\n",
" \n",
"def cantorit(n, x1, x2):\n",
" s = \"\"\n",
" if n > 0:\n",
" s = s + cantorit(n - 1, x1, (2 * x1 + x2) / 3)\n",
" s = s + cantorit(n - 1, (2 * x2 + x1) / 3, x2)\n",
" else:\n",
" s = s + '\\n' % (x1, x2)\n",
" return s"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Funktsioon `cantorit` joonistab vahemikke, millest koosneb hulk $C_n$. `cantorsvg` lisab SVG graafiku jaoks vajalikke andmeid, ja `cantor` näitab joonist. Tulemus on siis selline:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"for n in range(7):\n",
" cantor(n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Nagu me näeme, on esimesed hulgad sellised:\n",
"\n",
"\\begin{align}\n",
"C_0 &= [0, 1],\\\\\n",
"C_1 &= \\left[0, \\frac{1}{3}\\right] \\cup \\left[\\frac{2}{3}, 1\\right],\\\\\n",
"C_2 &= \\left[0, \\frac{1}{9}\\right] \\cup \\left[\\frac{2}{9}, \\frac{1}{3}\\right] \\cup \\left[\\frac{2}{3}, \\frac{7}{9}\\right] \\cup \\left[\\frac{8}{9}, 1\\right].\n",
"\\end{align}\n",
"\n",
"Lisaks näeme, et Cantori hulk $C_{\\infty}$ kindlasti ei ole tühi, sest vahemikute piirid kuuluvad Cantori hulka. Aga nad ei ole ainsad Cantori hulga elemendid - tegelikult on Cantori hulk mitteloenduv. Selleks et seda näidata võime defineerida punkti $x \\in C_{\\infty}$ *aadressi* järgneva protseduuri abil:\n",
"\n",
"* Kuna $x \\in C_{\\infty}$, kehtib ka $x \\in C_1$. Hulk $C_1$ koosneb kahest osast, vahemikutest $C_1^- = \\left[0, \\frac{1}{3}\\right]$ ja $C_1^+ = \\left[\\frac{2}{3}, 1\\right]$. Kui $x \\in C_1^-$, defineerime $x_1 = 0$. Kui $x \\in C_1^+$, defineerime $x_1 = 1$.\n",
"* Kuna $x \\in C_{\\infty}$, kehtib ka $x \\in C_2$. Hulk $C_2$ võime samuti kahesse ossa jagada. Selleks defineerime:\n",
"$$C_2^{\\pm} = \\left\\{\\frac{x}{3}, x \\in C_1^{\\pm}\\right\\} \\cup \\left\\{\\frac{x + 2}{3}, x \\in C_1^{\\pm}\\right\\}$$\n",
"Kui $x \\in C_2^-$, defineerime $x_2 = 0$. Kui $x \\in C_2^+$, defineerime $x_2 = 1$.\n",
"* Edasi defineerime\n",
"$$C_{n + 1}^{\\pm} = \\left\\{\\frac{x}{3}, x \\in C_n^{\\pm}\\right\\} \\cup \\left\\{\\frac{x + 2}{3}, x \\in C_n^{\\pm}\\right\\},$$\n",
"ja seega kui $x \\in C_n^-$, defineerime $x_n = 0$. Kui $x \\in C_n^+$, defineerime $x_n = 1$.\n",
"\n",
"Hulgad $C_n^{\\pm}$ on järgnevalt joonistatud, kus $C_n^-$ on sinine ja $C_n^+$ on punane."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"def cantorc(n):\n",
" display(SVG(data=cantorcsvg(cantorcit(n - 1, 0.0, 1.0 / 3.0, 'blue') + cantorcit(n - 1, 2.0 / 3.0, 1.0, 'red'))))\n",
"\n",
"def cantorcsvg(s):\n",
" return ''\n",
" \n",
"def cantorcit(n, x1, x2, c):\n",
" s = \"\"\n",
" if n > 0:\n",
" s = s + cantorcit(n - 1, x1, (2 * x1 + x2) / 3, 'blue')\n",
" s = s + cantorcit(n - 1, (2 * x2 + x1) / 3, x2, 'red')\n",
" else:\n",
" s = s + '\\n' % (x1, x2, c)\n",
" return s"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"for n in range(1, 7):\n",
" cantorc(n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Kuna $C_n^- \\cap C_n^+ = \\emptyset$, on igal punktil $x \\in C_{\\infty}$ unikaalne aadress $(x_1, x_2, \\ldots)$. Samuti võib näidata, et igale aadressile vastab ka unikaalne punkt $x \\in C_{\\infty}$, mida annab meile võrrand\n",
"\n",
"$$x = \\frac{1}{2} + \\sum_{n = 1}^{\\infty}\\frac{2x_n - 1}{3^n}.$$\n",
"\n",
"Aadressite hulk on mitteloenduv, seega kehtib sama ka Cantori hulga kohta.\n",
"\n",
"Cantori hulgal on lisaks ka omadus, et kehtib\n",
"\n",
"$$C_{\\infty} = \\left\\{\\frac{x}{3}, x \\in C_{\\infty}\\right\\} \\cup \\left\\{\\frac{x + 2}{3}, x \\in C_{\\infty}\\right\\}.$$\n",
"\n",
"See tähendab, et kui me skaleerime Cantori hulka kordajaga $\\frac{1}{3}$ ja võtame sellest väiksemast hulgast kaks koopiat, saame jälle Cantori hulka. Sellest järeldub, et Cantori hulga sarnasusdimensioon on $\\frac{\\ln 2}{\\ln 3} \\approx 0.63092975357145743710$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Sierpinski vaip"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Sierpinski vaip](http://en.wikipedia.org/wiki/Sierpinski_carpet) on konstrueeritud sarnase printsiibiga kui Cantori hulk. Seekord alustatakse hulgast $S_0 = [0, 1] \\times [0, 1]$. Seejärel kasutatakse rekursiooni\n",
"\n",
"$$\\begin{split}\n",
"S_{n + 1} &= \\left\\{\\left(\\frac{x}{3}, \\frac{y}{3}\\right), (x, y) \\in S_n\\right\\}\\\\\n",
"&\\cup \\left\\{\\left(\\frac{x}{3}, \\frac{y + 1}{3}\\right), (x, y) \\in S_n\\right\\}\\\\\n",
"&\\cup \\left\\{\\left(\\frac{x}{3}, \\frac{y + 2}{3}\\right), (x, y) \\in S_n\\right\\}\\\\\n",
"&\\cup \\left\\{\\left(\\frac{x + 1}{3}, \\frac{y}{3}\\right), (x, y) \\in S_n\\right\\}\\\\\n",
"&\\cup \\left\\{\\left(\\frac{x + 1}{3}, \\frac{y + 2}{3}\\right), (x, y) \\in S_n\\right\\}\\\\\n",
"&\\cup \\left\\{\\left(\\frac{x + 2}{3}, \\frac{y}{3}\\right), (x, y) \\in S_n\\right\\}\\\\\n",
"&\\cup \\left\\{\\left(\\frac{x + 2}{3}, \\frac{y + 1}{3}\\right), (x, y) \\in S_n\\right\\}\\\\\n",
"&\\cup \\left\\{\\left(\\frac{x + 2}{3}, \\frac{y + 2}{3}\\right), (x, y) \\in S_n\\right\\}.\n",
"\\end{split}$$\n",
"\n",
"Lõpuks defineerime, nagu ka Cantori hulga puhul:\n",
"\n",
"$$S_{\\infty} = \\bigcap_{n = 0}^{\\infty}S_n.$$\n",
"\n",
"Joonis on siis järgnevalt."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def sierp4(n):\n",
" display(SVG(data=sierp4svg(sierp4it(n, 0.0, 0.0, 1.0, 1.0))))\n",
"\n",
"def sierp4svg(s):\n",
" return ''\n",
" \n",
"def sierp4it(n, x1, y1, x2, y2):\n",
" s = \"\"\n",
" if n > 0:\n",
" s = s + sierp4it(n - 1, x1, y1, (2 * x1 + x2) / 3, (2 * y1 + y2) / 3)\n",
" s = s + sierp4it(n - 1, x1, (2 * y1 + y2) / 3, (2 * x1 + x2) / 3, (2 * y2 + y1) / 3)\n",
" s = s + sierp4it(n - 1, x1, (2 * y2 + y1) / 3, (2 * x1 + x2) / 3, y2)\n",
" s = s + sierp4it(n - 1, (2 * x1 + x2) / 3, y1, (2 * x2 + x1) / 3, (2 * y1 + y2) / 3)\n",
" s = s + sierp4it(n - 1, (2 * x1 + x2) / 3, (2 * y2 + y1) / 3, (2 * x2 + x1) / 3, y2)\n",
" s = s + sierp4it(n - 1, (2 * x2 + x1) / 3, y1, x2, (2 * y1 + y2) / 3)\n",
" s = s + sierp4it(n - 1, (2 * x2 + x1) / 3, (2 * y1 + y2) / 3, x2, (2 * y2 + y1) / 3)\n",
" s = s + sierp4it(n - 1, (2 * x2 + x1) / 3, (2 * y2 + y1) / 3, x2, y2)\n",
" else:\n",
" s = s + '\\n' % (x1, y1, x2 - x1, y2 - y1)\n",
" return s"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"image/svg+xml": [
"