Wymiar fraktalny

O scenariuszu

Scenariusz ten jest materiałem do przeprowadzenia jednej godziny zajęć lekcyjnych i jest uzupełnieniem do scenariusza Od punktu do punktu.

Został on opracowany w ramach projektu iCSE4school na podstawie lekcji prowadzonych w latach 2015-2017 w III Liceum Ogólnokształcącym im. Stefana Batorego w Chorzowie przez Krzysztofa Olesia.

Uwaga!

W każdym z okien programu można zmieniać liczby, tekst, zmienne lub cały kod. Nie trzeba się martwić, jeśli program przestanie działać, bo po odświeżeniu strony powróci do ustawień początkowych. W tym przypadku komórki korzystają w poprzednich definicji, więc należy ćwiczenia (algorytmy) wykonywać według kolejności występowania.

Wstęp - generacja samopodobnych objektów

W dalszej analizie potrzebujemy algorytmów do generacji samopodobnych obiektów geometrycznych. Rozważymy trzy obiekty, chociaż przedstawione rozwiązania mogą służyć badaniu dowolnych danych, zarówno pomiarowych jak i sztucznie wygenerowanych. Ponieważ analiza poniższych algorytmów nie jest dla nas celem, to poprzestaniemy na wypróbowaniu ich działania.

Wypróbujmy działanie tych funkcji. Na początek możemy narysować krzywą Kocha. Algorytm jej tworzenia jest dwuetapowy. Najpierw należy odcinek podzielić na trzy równe części. Następnie środkową zastąpić dwoma bokami trójkąta równobocznego. Powtarzając wiele razy wspomnianą operację, otrzymujemy nieskończenie długą linię mieszczącą się w obszarze o skończonym polu. Narysujmy pierwszą, drugą i szóstą iterację.

Widzimy, że każde kolejne zwiększenie liczby iteracji (argumentu) powoduje skomplikowanie wykresu.

Należy pamiętać, że ilość danych rośnie potęgowo z liczbą pokoleń, więc badzo łatwo przekroczyć zasoby komputera, na którym wykonujemy powyższy algorytm. Warto sprawdzić ile czasu zajmuje wyenerowanie danej krzywej.

Podobnie z krzywą Hilberta - narysujmy pierwszą, drugą i szóstą iterację.

Na samym końcu wygenerujemy dane będące punktami na okręgu - czyli obiekcie wymiarze równym jeden.

Wymiar pudełkowy (Mińkowskiego)

Wymiar Minkowskiego można określić rozważając to, jak długość zależy od skali, tzn. „linijki”, którą przeprowadzamy pomiar:

\[l(\epsilon) \sim e^{ (1-d)},\]

gdzie \(d\) jest wymiarem obiektu.

Ponieważ znamy procedurę tworzenia niektórych obiektów, to możemy dla nich otrzymać dokładne wyniki. I tak dla:

• Krzywej Kocha:

  \[d = \frac{\log(4)}{\log(3)}\simeq 1.2618\]

• okręgu:

  \[d=1\]

• Krzywej Hilberta:

  \[d=2.\]

Spróbujmy obliczyć wymiar obiektu, zapominając skąd mamy dane: weźmy je (np. 1 milion punktów leżących na krzywej Kocha) i zmierzmy długość łamanej. Następnie wyrzućmy co drugi punkt i powtórzmy pomiar. Taką procedurę możemy zastosować dla dowolnego obiektu będącego łamaną.

Operacje na tablicach:

Pozornie skomplikowana linijka w Python/Sage np.mean(np.sqrt(np.sum(np.diff(l,axis=0)**2,axis=1))) jest równoznaczna z matematycznym zapisem:

\[\frac{1}{N} \sum_{i=0}^{N-1} \sqrt{ \sum_{j=1}^{2} (l_{i,j}- l_{i-1,j})^2},\]

a np.sum(np.sqrt(np.sum(np.diff(l,axis=0)**2,axis=1)))

oznacza:

\[\sum_{i=0}^{N-1} \sqrt{ \sum_{j=1}^{2} (l_{i,j}- l_{i-1,j})^2}.\]

Informacja

W poniższej komórce można „odkomentować” inne przypadki, powtórzyć obliczenia i przeanalizować wyniki.

Wystarczy dopasować tak otrzymane dane do modelu \(l(\epsilon) \sim e^{ (1-d)}\) i powinniśmy otrzymać przybliżenie wymiaru.

Narysujmy dopasowanie.

Otrzymujemy liczbę zbliżoną do wyniku dokładnego. Zaletą tego postępowania jest jego niezależność od źródła danych.

Box counting

Wyobraźmy sobie, ze robimy zdjęcie naszego obiektu aparatem cyfrowym o pewnej rozdzielczości i zliczamy tylko te piksele, na których widać obiekt. Jak zmienia się liczba pikseli, na których znajduje się nasz obiekt z rozmiarem piksela aparatu? Taka procedura nazywa się box-counting.

Wykorzystujemy histogram wbudowany w numpy: np.histogramdd

Piksel - lub voxel (3d) - może być n-wymiarowym pudełkiem, jednak takim, by mógł on pokrywać cały obiekt: np. dla krzywej Kocha musimy rozważyć co najmniej piksele 2d.

Zaletą box-countingu jest to, że wystarczy dysponować punktami należącymi do obiektu w dowolnej kolejności, np. takimi jak te generowane w grze w chaos.

Podsumowanie

Powyższe przykłady zachęcają do przeprowadzania eksperymetnów z własnymi danymi. Można na przykład wykorzystać dane geodezyjne linii brzegowej rzek i zbadać ich wymiar fraktalny. Szczególnie prostą i uniwersalną wydaje się metoda box-counting, która w języku Python - wykorzystującym biblioteki zawarte w SageMath - zawiera się w kilku liniach kodu.