Prędkość ucieczki do nieskończoności - czyli zabawy z rekurencją (część 2)

Dziś ciekawostka w nawiązaniu do wpisu z dnia 20 października 2015 roku "Liczba PI ukryta w zbiorze Mandelbrota" - przeanalizujmy równanie rekurencyjne dla liczb rzeczywistych:

x_n=\begin{cases}x_{n-1}^2+\frac{1}{4}+\epsilon,&\text{dla}\quad n>0\\0,&\text{dla}\quad n=0\end{cases}

Zbliżanie się do "ostrza" zbioru Mandelbrota

Powyższe wyrażenie powstaje na bazie równania zbioru Mandelbrota z_n=z_{n-1}^2+c (w liczbach zespolonych), jeśli ograniczymy się do prostej rzeczywistej (dlatego użyłem zapisu x_n) i będzie nas interesowało zbliżanie się elementu x_1=\frac{1}{4}+\epsilon do "ostrza" (ang. "cusp") zbioru o współrzędnych (\frac{1}{4},0).

Mandelbrot - Ostrze

Szybkość ucieczki do nieskończoności

Ustalając odpowiednio małe \epsilon>0 decydujemy jak bardzo chcemy się zbliżyć do "ostrza", teraz zadanie polega na znalezieniu pierwszego n, dla którego x_n>=2. Takie minimalne n jest dobrą miarą prędkości ucieczki x_n do nieskończoności w zależności od wybranego \epsilon. Na marginesie dodam, że zbiór Juli dla równania Mandelbrota jest na powyższym obrazku oznaczony kolorem czarnym, który reprezentuje punkty "nieuciekające" do nieskończoności w trakcie nieskończonej iteracji (ta tematyka jest sama w sobie bardzo ciekawa i zapewne kiedyś coś napiszę o atraktorach).

Rekurencja na rekurencji

Zapiszmy nasze zadanie wykorzystując rekurencję w celu poszukiwania rozwiązania:

f(n,\epsilon)=\begin{cases}f(n+1,\epsilon),&\text{dla}\quad x_n<2\\n,&\text{dla}\quad x_n>=2\end{cases}

Niestety zdefiniowaliśmy rekurencję na rekurencji - to zły znak dla wydajności - cóż - sprawdźmy to używając mXparsera.

/* Definicja funkcji rekurencyjnej */
Function x = new Function("x(n,c) = if( n>0, x(n-1,c)^2+0.25+c, 0 )");
Function f = new Function("f(n,c) = if( x(n,c) >= 2, n, f(n+1, c) )", x);

/* Obliczenia i wyświetlenie wyniku */
mXparser.consolePrintln( "c = 0.01" + ", f(0,c) = " + f.calculate(0, 0.01) + ", czas = " + f.getComputingTime() + " s" );
mXparser.consolePrintln( "c = 0.0001" + ", f(0,c) = " + f.calculate(0, 0.0001) + ", czas = " + f.getComputingTime() + " s" );
mXparser.consolePrintln( "c = 0.000001" + ", f(0,c) = " + f.calculate(0,0.000001) + ", czas = " + f.getComputingTime() + " s" );
mXparser.consolePrintln( "c = 0.00000001" + ", f(0,c) = " + f.calculate(0,0.00000001) + ", czas = " + f.getComputingTime() + " s" );

+ wyczekiwany wynik


c = 0.01, f(0,c) = 30.0, czas = 0.224 s
c = 0.0001, f(0,c) = 312.0, czas = 1.532 s
c = 0.000001, f(0,c) = 3140.0, czas = 37.343 s
c = 0.00000001, f(0,c) = 31414.0, czas = 4068.338 s


Wzorzec prędkości ucieczki

Wow - jaki przedziwny wzorzec liczby iteracji wymaganych, aby przekroczyć 2!! Dostajemy coś, co przypomina \pi, jednak wymaga postawienia przecinka w odpowiednim miejscu! Można również zauważyć, że 100-krotne zmniejszenie \epsilon zwiększa niezbędną liczbę iteracji około 10-krotnie. Zmniejszając \epsilon otrzymamy liczbą coraz bardziej przypominającą \pi 🙂

Czasy wykonania

Tak jak oczekiwaliśmy - czasy wykonania są koszmarne - głównie z dwóch powodów:

  1. wykorzystanie generycznych funkcji rekurencyjnych (możliwe dowolne definicje, jednak kosztem wydajności - konieczność klonowania obiektów, brak możliwości zapamiętywania wartości z poprzednich przebiegów)
  2. definicji rekurencji na rekurencji,

mXparser dostarcza również nieco wydajniejszą wersję rekurencji - tzw. argumenty rekurencyjne z indexem (klasa RecursiveArgument). Wykorzystanie  RecursiveArgument jest ograniczone do jednego indexu, co umożliwia przechowywanie rezultatów z poprzednich iteracji. Zyskujemy na wydajności, tracąc na elastyczności i przejrzystości kodu. Działanie RecursiveArgument zaprezentuję w kolejnej części.

Pozdrowienia,

Mariusz Gromada

BTW: uruchamiając kody mXparsera nie zapomnijcie o dodaniu

import org.mariuszgromada.math.mxparser.*;

Zobacz również:

  1. Polowanie na czarownice - czyli zabawy z rekurencją (część 1)
  2. Naiwny test pierwszości - czyli zabawy z rekurencją (część 3)
  3. Rekurencja pośrednia - czyli zabawy z rekurencją (część 4)
  4. Liczba PI ukryta w zbiorze Mandelbrota

Precyzja liczby Pi a obwód obserwowalnego Wszechświata

Obserwowalny Wszechświat

Znana obecnie (06.11.2015) precyzja liczby Pi

Alexander J. Yee i Shigeru Kondo w grudniu 2013 roku wyznaczyli liczbę Pi z dokładnością do ponad 12 bilionów cyfr - zdumiewająca precyzja! Dalszych obliczeń zaniechano w związku z wyczerpaniem się przestrzeni dyskowej. W poniższym tekście chciałbym przybliżyć co tak wielka dokładność może oznaczać w praktyce.

Obwód obserwowalnego Wszechświata

Rozważmy rozmiar Obserwowalnego Wszechświata zadając pytanie jakiej precyzji liczby Pi potrzeba do wyznaczenia jego obwodu z dokładnością rzędu 1 atomu wodoru? Promień walencyjny wodoru to 37 pm = 3.7×10 ‾¹¹ m. Rozmiar Obserwowalnego Wszechświata to suma odległości jaką światło przebyło od momentu Wielkiego Wybuchu (13.8 miliarda lat świetlnych) oraz dystansu, o jaki oddaliły się (przez ten okres) najodleglejsze galaktyki. Obecnie szacowana średnica Obserwowalnego Wszechświata to 92 miliardy lat świetlnych.

Promień obserwowalnego Wszechświata

Promień rzędu 46 miliardów lat świetlnych zdaje się sugerować, że oddalanie się galaktyk musiało się odbywać z prędkością większą niż prędkość światła. "Oddalanie się galaktyk" to uproszczenie myślowe - faktyczne oddalanie się jest konsekwencją ekspansji Wszechświata, która to jest rozszerzaniem się przestrzeni. Wielki Wybuch jest momentem rozpoczęcia ekspansji, czyli początkiem rozszerzania się przestrzeni. Fotony, które teraz obserwujemy, "leciały" do nas 13.8 miliarda lat, ale w momencie kiedy "startowały" to punkt startu i punkt docelowy były znacznie bliżej siebie. Wraz z podróżą fotonu przestrzeń się rozszerzała sprawiając, że przebyta droga była dłuższa, jak i dłuższa (niż początkowo) jest droga jeszcze "do przebycia". Niezgodność z zasadą niemożliwości przekroczenia prędkości światła jest w tym przypadku pozorna, gdyż to sama przestrzeń (i jej współrzędne) się rozszerzają, co jest wyrażone w odpowiednim zakrzywieniu czaso-przestrzeni opisywanej w Ogólnej Teorii Względności. O samej prędkości światła też jest wygodniej myśleć jako o prędkości "przyczynowo-skutkowości", wtedy łatwiej jest zrozumieć idee stożków świetlnych, etc. A jeszcze lepiej przyjąć c = 1 🙂

No to liczymy 🙂

  • Prędkość światła w próżni w przybliżeniu to c = 3 \times 10^8 \frac{m}{s}
  • Rok świetlny w przybliżeniu to 9.46 \times 10^{15} m
  • 46 miliardów lat świetlnych w przybliżeniu to 4.35 \times 10^{26} m
  • Obwód koła o takim promieniu to około 2.73 \times 10^{27} m
  • Zatem dokładność o rząd mniejszą niż rozmiar atomu wodoru uzyskamy przy wykorzystaniu 27 + 11 + extra 1 = 39 cyfr liczby Pi.

To niesamowite, że jedynie 39 cyfr liczby Pi wystarczy do osiągnięcia tak niezwykłej dokładności obliczeń dla obrzeży Obserwowalnego Wszechświata - 39 (=3.141592653589793238462643383279502884197) z poznanych 12 bilionów!

Na zakończenie filmik od Numberphile przedstawiający wyżej opisany problem.

Pozdrowienia,

Mariusz Gromada

 

Przeciwieństwo nieskończoności, Wielkość nieskończenie mała, Wielkość infinitezymalna, Różniczka, Monada, Infinitesimal, Differential - czyli początki rachunku różniczkowego i całkowego

Wielkość nieskończenie mała - Pole koła

Wielkość nieskończenie - geneza powstania

W 17 wieku Newton i Leibniz skonstruowali podstawy rachunku różniczkowego i całkowego. Ich logika opierała się na wykorzystaniu wielkości nieskończenie małej w celu wyznaczenia powierzchni pod krzywą daną równaniem funkcji. Podejście to zakładało istnienie niezerowego elementu nieskończenie małego. Filozof Leibniz poszedł dalej, gdyż ponadto uważał, że cały świat jest zbudowany z tzw. monad, czyli z substancji, które nie mają żadnej postaci, ponieważ są niepodzielne, nie mogą być ani wytworzone ani unicestwione.

Jeszcze przed naszą erą Grecy z sukcesem stosowali metodę wyczerpywania do wyznaczenia pól powierzchni figur geometrycznych. Metoda ta wykorzystywała granice, nie wykorzystywała natomiast wielkości nieskończenie małej. Jednak z metody wyczerpywania wyrosła zasada Cavalieriego, odkryta przez Archimedesa, służąca do wyznaczania objętości brył, która opierała się na argumentacji wielkości niepodzielnej.

Wielkość nieskończenie mała a skala Plancka

Intuicja podpowiada, że wielkość nieskończenie mała powinna być ekstremalnie mała, ale o niezerowym rozmiarze. W świecie praktycznym byłaby to np. wielkość mniejsza od najmniejszej teoretycznie możliwej wielkości do zmierzenia. Np. skala Plancka w fizyce dostarcza teoretycznej granicy pomiaru - nie ma możliwości skonstruowania przyrządu pomiarowego z błędem mniejszym niż skala Plancka, co nie oznacza, że poniżej skali Plancka nic nie istnieje.

Wielkość nieskończenie mała - cykl filmów od Numberphile

Numberphile logo Zapraszam do ciekawego cyklu filmów przygotowanych przez Numberphile na temat wielkości nieskończenie małych.

I na koniec jeszcze ciekawostka od MinutePhysics - Proof Without Words: The Circle.

Pozdrowienia,

Mariusz Gromada

Liczba PI ukryta w zbiorze Mandelbrota

Zbiór Mandelbrota

Numberphile logoCiekawostka od Numberphile pokazująca w jaki przedziwny sposób liczba PI jest ukryta w "ostrzu" zbioru Mandelbrota. Polecam!

Pozdrowienia,

Mariusz Gromada

Zobacz również:

  1. Prędkość ucieczki do nieskończoności - czyli zabawy z rekurencją (część 2)