Matematyczne góry

Podstawy matematyczne na których bazuje algorytm generowania "matematycznych gór" przedstawione będą w sposób ogólny niewymagający znajomości matematyki na poziomie akademickim.
Pierwszym twierdzeniem, które gra podstawową rolę w mojej pracy jest twierdzenie polskiego matematyka Stefana Banacha. Twierdzenie nosi nazwę "Twierdzenia o punkcie stałym". Na początek należałoby wyjaśnić pojęcie przekształcenia zwężającego. Zapis

d (x, y)

oznaczał będzie odległość punktów

x

oraz

y

. Jeśli istnieje liczba

a \in (0, 1)

taka, że

d (f (x), f (y)) \leq a f (x, y)

to przekształcenie f nazywamy zwężającym. Liczbę

a

nazywamy współczynnikiem zwężania.
Przykład Dla liczb rzeczywistych ich odległość mierzymy używając wartości bezwzględnej tzn. dla

x, y \in R

d (x, y) = | x - y |

. Rozpatrzmy dla

x \in [0, 1]

przekształcenie

f (x) = \frac{1}{4} x^{2}

. Ponieważ dla

x, y \in R

prawdziwa jest nierówność

d (f (x), f (y)) = | \frac{1}{4} x^{2} - \frac{1}{4} y^{2} | = \frac{1}{4} | (x - y) (x + y) | \leq \frac{1}{4} 2 | x - y | = \frac{1}{2} | x - y |

Zatem przekształcenie

f

jest przekształceniem zwężającym. Współczynnik zwężania wynosi

\frac{1}{2}

. Twierdzenie Banacha mówi, że przy odpowiednich założeniach (które zakładam, że na potrzeby mojej pracy są spełnione), jeśli przekształcenie

f

jest zwężające, to istnieje dokładnie jeden punkt stały

x

tego przekształcenia, (tzn. w zależności od dziedziny funkcji liczba, punkt, zbiór) taki, że

f (x) = x

.
Aby obliczyć punkty stałe funkcji rozpatrywanej powyżej tj.

f (x) = \frac{1}{4} x^{2}

powinniśmy rozwiązać równanie

\frac{1}{4} x^{2} = x

. Rozwiązaniami równania są liczby

x = 0

oraz

x = 4

. Ze względu na dziedzinę punktem stałym jest liczba 0.

Dowód twierdzenia Banacha podaje iteracyjną metodę znalezienia punktu stałego przekształcenia

f

. Przebiega ona następująco: weżmy dowonly punkt

x_{0}

należący do dziedziny funkcji. Następnie obliczamy

x_{1} = f (x_{0})

. Dalej

x_{2} = f (x_{1})

itd. Ogólnie

x_{n} = f (x_{n - 1})

. Okazuje się, że ciąg

x_{n}

jest zbieżny do punktu stałego przekształcenia

f

.
Bazując na moim przykładzie, weźmy np.

x_{0} = \frac{1}{3}

. Następnie

x_{1} = f (\frac{1}{3}) = \frac{1}{4} \cdot \frac{1}{9} = \frac{1}{36}

x_{2} = f (\frac{1}{36}) = \frac{1}{4} \cdot \frac{1}{1296} = \frac{1}{5184}

itd. Widać dokładnie, że ciąg

x_{n}

będzie zbiegał do punktu stałego przekształcenia, czyli do 0.
Dowód twierdzenia Banacha pokazuje jeszcze jedno oszacowanie, które wykorzystam w dalszym opisie. Zachodzi nierówność

d (x_{0}, x) \leq \frac{1}{1 - a} d (x_{0}, f (x_{0}))

Przekształcenia

w

, które wykorzystuję do generowania matematycznych gór to tzw. przekształcenia afiniczne, które punktom płaszczyzny przyporządkowują inne punkty płaszczyzny. Jeśli

P (x, y)

jest dowolnym punktem płaszczyzny, to

w (P) = (u, v) = (a x + b y + e, c x + d y + f)

. Dla przykładu rozpatrzmy przekształcenie

w (P) = (3 x + y - 1, 2 x - 4 y)

. Dla

P (- 1, 3)

dostaniemy

w (P) = (3 \cdot (- 1) + 3 - 1, 2 \cdot (- 1) - 4 \cdot 3) = (- 1, - 14)

. Mówiąc precyzyjniej, obrazem punktu

P (- 1, 3)

jest punkt

P' (- 1, - 14)

.

Okazuje się, że mając dane na płaszyźnie dwa trójkąty pierwszy o wierzchołkach

P_{1} (x_{1}, y_{1}), P_{2} (x_{2}, y_{2}), P_{3} (x_{3}, y_{3})

drugi o wierzchołkach

Q_{1} (u_{1}, v_{1}), Q_{2} (u_{2}, v_{2}), Q_{3} (u_{3}, v_{3})

(punkty nie mogą być współliniowe) to zawsze możemy znaleźć odwzorowanie afiniczne odwzorowujące jeden z nich na drugi. Wystarczy rozwiązać układ sześciu równań z sześcioma niewiadomymi:

\{\begin{cases} a x_{1} + b y_{1} + e = u_{1} \\ c x_{1} + d y_{1} + f = v_{1} \\ a x_{2} + b y_{2} + e = u_{2} \\ c x_{2} + d y_{2} + f = v_{2} \\ a x_{3} + b y_{3} + e = u_{3} \\ c x_{3} + d y_{3} + f = v_{3} \end{cases}

Jeśli boki trójkąta przekształcanego będą krósze od odpowiednich boków jego obrazu, to możemy twierdzić, że przekształcenie

w

jest zwężające. Dla przykładu obliczę współczynniki przekształcenia afinicznego

w

, które odwzorowuje trójkąt o wierzchołkach

P

na trójkąt o wierzchołkach

Q

. Trójkąty przedstawiłem na obrazie obok.

Należy w tym celu rozwiązać następujący układ równań:

\{\begin{cases} - 4 a + 3 b + e = 1 \\ - 4 c + 3 d + f = 2 \\ 3 a - 2 b + e = 3 \\ 3 c - 2 d + f = 4 \\ - 2 a - b + e = 4 \\ - 2 c - d + f = 3 \end{cases}

Rozwiązaniami układu są liczby:

a = - 0, 39 b = - 0, 94 c = 0, 17 d = - 0, 17 e = 2, 28 f = 3,17

Odwzorowanie wygląda zatem następująco:

w (P) = (- 0, 39 x - 0, 94 y + 2, 28, 0, 12 x - 0, 17 y + 3, 17)

Okazuje się, że jeśli mamy n odwzorowań zwężających, np. takich które były rozważane powyżej to odwzorowanie

w (P) = w_{1} (P) \cup w_{2} (P) \cup . . . \cup w_{n} (P)

jest również przekształceniem zwężającym. Odwzorowanie to nosi nazwę odwzorowania Hutchinsona.

Aby wyjaśnić powstawanie "matematycznych gór" podam jeszcze pojęcie "odległości obrazów" na płaszczyźnie zaporponowane przez niemieckiego matematyka Felixa Hausdorffa. Odległość w języku metematycznym nazywamy metryką.
Trzeba w tym celu zdefiniować pojęcie "otoczenia epsilonowego" zbioru na płaszczyźnie.
Otoczeniem epsilonowym zbioru

A

nazywamy zbiór

A_{ε}

zdefiniowany następująco:

A_{ε} = {y \in R^{2} : \exists_{x \in A} | x - y | \leq ε}

Przykłady Otoczeń epsilonowych zbiorów

Weźmy dwa zbiory

A

B

leżące na płaszczyźnie. Dobierzmy dwie liczby (otoczenia epsilonowe zbiorów

A

oraz

B

)

ε_{A}

oraz

ε_{B}

tak aby zachodziły inkluzje

A \subset B ε_{B}

oraz

B \subset A ε_{A}

. Większą z tych liczb nazywamy odległością Hausdorffa zbiorów

A

B

i oznaczamy literką

h

. Mówiąc prościej, aby odległość Hausdorffa dwóch zbiorów

A

B

była "mała", każdy element zbioru

A

musi leżeć "blisko" jakiegoś elementu zbioru

B

Zapiszę jeszcze raz nierówność wynikającą z dowodu twierdzenia Banacha dla zbiorów

A

B

używając odległości Hausdorffa.

h (A_{0}, A) \leq \frac{1}{1 - a} h (A_{0}, w (A_{0}))

, gdzie

A_{0}

oznacza tutaj obraz początkowy,

A

natomiast jest obrazem generowanych przez ciąg

A_{n + 1} = w (A_{n})

. Jeśli teraz postawimy sobie zadanie znalezienia takiego odwzorowania

w

aby wygenerowany przez niego obraz

A

był jak najbardziej bliski (w sensie metryki Hausdorffa) ustalonemu z góry obrazowi początkowemu

A_{0}

(temu, który chcemy zakodować) to z powyższej nierówności widać, że odległość ta będzie niejako "kontrolowana" przez jednokrotne zastosowanie operatora Hutchinsona. Rozumieć to można w ten sposób, że jeśli

w_{1} (A_{0}) \cup w_{2} (A_{0}) \cup . . . \cup w_{n} (A_{0})

okaże się bliska

A_{0}

(prawa strona nierówności) to tym bardziej

A

będzie bliski

A_{0}

Rozpatrzę przykład z papotką przedstawioną na poniższym rysunku.

Paproć posiada wyraźne cechy "samopodobieństwa" tzn. część paprotki ograniczona trójkątem

T_{1}

jest pomniejszoną i obróconą kopią całości, podobnie jak część ograniczona trójkątem

T_{2}

T_{3}

. Aby ustalić odwzorowania składowe

w_{i}

odwzorowania

w

ustalmy tzw. trójkąt bazowy (zawierający obraz całej paprotki). Następnie zaznaczając współrzędne kolejnych trójkątów

T_{1}, T_{2}, T_{3}

dostaniemy współczynniki kolejnych odwzorowań

w_{i}

(tak jak było to opisane w sekcji drugiej).
Poniżej obraz paprotki wygenerowany za pomocą mojego programu:

Patrząc na obraz góry, na jej nieregularne kształty, możemy dopatrzyć się podobieństwa całej góry do jej małych fragmentów. Zaznaczając trójkąt bazowy jako "obrys" góry, a następnie trójkąty na które ta góra ma być przekształcana, spodziewamy się odtworzenia początkowego obrazu poprzez wielokrotne (w mojej pracy 300000 razy) zastosowanie operatora

w

Do wygenerowania paprotki w powyższej sekcji użyto czterech funkcji

w_{i}

o współczynnikach przedstawionych w tabeli poniżej (przekształcenie

w_{1}

generuje łodygę paprotki).

	a	b	c	d	f
w₁	0	0	0	0,17	0
w₂	0,849	0,025	-0,025	0,849	3
w₃	0,155	0,235	0,195	0,186	1,2
w₄	0,155	-0,235	0,195	0,186	3

Iterowanie zaczynamy od punktu (0,0), ponieważ obraz końcowy nie zależy od wyboru punktu startowego. Łatwo policzyć, że po pierwszym kroku iteracji otrzymujemy 4 punkty, po drugim

4^{2}

, po k-tym

4^{k}

. I tu sprawa się komplikuje gdyż przy wzroście

k

ilości punktów robią się ogromne. Z pomocą przychodzi tzw. probabilistyczny sposób generowania obrazów.
Jeśli mamy

n

odwzorowań

w_{i}

to przyporządkowujemy każdemu z nich liczbę

p_{i}

, która będzie równa prawdopodobieństwu wylosowania odwzorowania

w_{i}

. Musi być przy tym zachowana równość

p_{1} + p_{2} + . . . p_{n} = 1

. Wybieramy następnie dowolny punkt płaszczyzny (u mnie punkt (0,0)), losujemy jedno z odwzorowań

w_{i}

n

odwzorowań

w_{i}

to przyporządkowujemy każdemu z nich liczbę

p_{i}

, która będzie równa prawdopodobieństwu wylosowania odwzorowania

w_{i}

. Musi być przy tym zachowana równość

p_{1} + p_{2} + . . . p_{n} = 1

. Wybieramy następnie dowolny punkt płaszczyzny (u mnie punkt (0,0)), losujemy jedno z odwzorowań

w_{i}

a następnie przekształcamy ten punkt tym odwzorowaniem. Mówiąc ogólnie, każdy następny punkt jest obrazem punktu poprzedniego przekształconego przez jedno z wylosowanych odwzorowań.
W pracy dodatkowo generuję dolne partie obrazu na zielono (symulacja trawy), a górne na szaro (symulacja mgły).