Czym są iteracje? Mamy je w wielu dziedzinach, ale nas będą interesowały iteracje w matematyce, a głównie w geometrii. Zacznijmy zatem od definicji – i to tej najbardziej poglądowej, a niekoniecznie precyzyjnej w sensie matematycznym i opisanej aksjomatami.
Iteracja, w najbardziej ogólnym jej znaczeniu, jest powtarzaniem określonej operacji, poczynając od pewnego elementu początkowego, aż do osiągnięcia pewnego skutku. Mówimy o elemencie początkowym iteracji i o krokach iteracji. Ciąg obiektów otrzymany w wyniku iteracji często nazywamy jej orbitą. W wielu przypadkach poszczególne kroki iteracji polegają na zastosowaniu danej operacji w stosunku do wyniku otrzymanego z poprzedniego kroku. Taki proces najczęściej nosi odrębną nazwę i znany jest jako iteracja rekurencyjna lub po prostu rekursja. Nie znaczy to jednak, że każda iteracja jest rekursją.
Dla przykładu – iteracja polegająca na wyliczaniu wartości n! jako n! = 1 × 2 × 3 … × n będzie iteracją, w której nie używamy rekursji. Natomiast to samo zapisane w postaci iteracji rekurencyjnej może mieć postać:
POLECAMY
0! = 1 oraz (n + 1)! = n! × (n + 1)
Oczywiste jest, że iteracje rekurencyjne są znacznie bardziej interesujące, gdyż są o wiele bardziej efektywne i wymagają mniej obliczeń.
Jak wspomniałem na wstępie, iteracje są znane od bardzo dawna. Od jak dawna? Aby odpowiedzieć na to pytanie, musielibyśmy dokładnie przeszukać historię matematyki. Z pewnością jednak znali je starożytni Grecy.
Iteracje u starożytnych Greków
Jak pamiętamy, starożytni Grecy nie znali ułamków (ani zwykłych, ani dziesiętnych), nie znali nawet zera. Oni używali tylko liczb naturalnych i proporcji jako sposobu na określenie wartości ułamkowych. Dla przykładu do powiedzenia, że jakiś odcinek jest równy połowie innego, używano zwrotu „stosunek a do b jest jak 1 do 2”, przypominającego nasz zapis a : b = 1 : 2. Nawet zapis taki jak ten: a : b = 1 : 2 nie występuje u Euklidesa. Zapis symboliczny i równania wymyślono znacznie później.
Grecki matematyk, Theon ze Smyrny, żyjący około 100 roku naszej ery, rozważa dwa ciągi liczbowe, nazywając je przy tym liczbami boku i przekątnej. Mamy więc tam kolejno liczby pokazane w tabeli. Dodając tam dodatkowo kolumnę p : b i wyliczając z kalkulatorem wartość ułamka p/b, otrzymujemy kolejne przybliżenia liczby niewymiernej √‾2. Jedynkę, od której zaczynają się oba ciągi, nazywa się czasem monadą od słowa greckiego monas. Popatrzmy na ostatni wiersz. Jak dokładne jest to przybliżenie w porównaniu do tego, jakie my otrzymujemy za pomocą kalkulatora dla √‾2?
Wreszcie warto zauważyć, że liczby 17 i 12, a właściwie ułamek 17/12, były już w tekstach babilońskich używane do obliczeń związanych z kwadratem i jego przekątną, podobnie jak proporcja 22 : 7 służy Heronowi w obliczeniach związanych z okręgiem.
Teraz odrobina wyjaśnień związanych z tym tajemniczym ciągiem. Kluczem do niego jest rycina 1.
Dlaczego wspomniane tu dwa ciągi noszą nazwę liczb boku i przekątnej? W tym celu wystarczy popatrzeć na rycinę 1. Mamy tu ciąg kwadratów, w których bok każdego następnego kwadratu powstaje jako suma boku poprzedniego kwadratu i jego przekątnej, b1 = b + p, natomiast każda przekątna nowego kwadratu jest sumą podwojonego boku poprzedniego kwadratu i jego przekątnej, p1 = 2b + p. Te dwa wzory są niczym innym jak rekurencyjną definicją dwóch ciągów Theona, a w konsekwencji rekurencyjną definicją proporcji służącej do określenia długości przekątnej kwadratu. Nikt, oczywiście, nie zamierzał sięgać do nieskończoności, aby otrzymać dokładną wartość długości przekątnej. Wystarczyło wziąć dostatecznie dalekie wartości b i p.
Ważna uwaga: liczby pokazane na rycinie 1 są przybliżone, ale takimi właśnie operowano w tamtych czasach – liczbami naturalnymi i proporcjami liczb naturalnych. Zauważmy również, że w ciągu kwadratów pominięte zostały dwa pierwsze kwadraty. Współczesnemu Czytelnikowi trudno byłoby zaakceptować tak duże niedokładności. Interesujące jest również to, że choć my opisaną tu metodę znamy z matematyki greckiej, to znano ją również wcześniej w Mezopotamii.
My w czasach współczesnych radzimy sobie z długością przekątnej kwadratu na wiele sposobów. Niektóre z nich są równie interesujące jak metoda Theona. Dla przykładu powszechnie używany ułamek łańcuchowy
jest niczym innym jak ciągiem opisanym przez wzór iteracyjny:
Kolejne wartości an są kolejnymi przybliżeniami √‾2.
Tyle o starożytnych Grekach. Wróćmy teraz do naszego głównego tematu, czyli iteracji w geometrii.
Rozważając iteracje, w wielu przypadkach zakładamy, że liczba kroków iteracji jest nieskończona, a nas interesuje obiekt otrzymany po nieskończonej albo bardzo dużej liczbie kroków. W takim przypadku, jeśli iterujemy obiekty geometryczne, przynajmniej punkty, dochodzimy do niezwykle popularnych ostatnio w matematyce obiektów zwanych fraktalami. W tym dokumencie będą pojawiały się również fraktale, ale bardziej będziemy interesować się tym, co powstaje po drodze niż tym, co pojawia się na końcu.
Iteracje można stosować zarówno do funkcji czy operatorów matematycznych, jak i w stosunku do obiektów geometrycznych. Nas będzie interesowała głównie ta ostatnia sytuacja.
No a teraz, skoro już wiemy, o czym będzie ten tekst, zajmijmy się stroną praktyczną tego zagadnienia.
Narzędzia
Skoro mamy mówić o iteracjach obiektów geometrycznych, będzie potrzebny nam program do geometrii. Jest ich bardzo wiele – Cabri, Geometer’s Sketchpad, Cinderella, GeoGebra itd. W każdym z nich można tworzyć iteracje geometryczne, chociaż nie zawsze w identyczny sposób. My będziemy używać programu Geometer’s Sketchpad, w skrócie GSP, głównie z tego powodu, że jest to program mający gotowe narzędzia do tworzenia iteracji i manipulacji nimi, a także dlatego, że można w nim tworzyć swoje narzędzia i wykorzystywać je w konstrukcjach geometrycznych. Dzięki temu nie musimy powtarzać tej samej konstrukcji dziesiątki razy. Raz zrobiona konstrukcja może być powielana wielokrotnie w miarę potrzeby. Drugą istotną cechą tego programu jest estetyka otrzymanych konstrukcji.
Użytkownicy GeoGebry z pewnością znajdą w niej sposób na odpowiednie powtórzenie rozważań przedstawianych w tym artykule. Jeśli ktoś nie ma programu GSP, to zawsze może ściągnąć jego wersję ewaluacyjną, wprawdzie trochę ograniczoną w czasie, ale i tak pozwalającą na powtórzenie naszych konstrukcji. Jeszcze innym rozwiązaniem może być strona internetowa //onlinemathtools.com, gdzie w tzw. L-systemach znajdziemy wiele ciekawych przykładów z iteracjami geometrycznymi.
Chciałbym tu podkreślić – nie jest istotne, jakiego programu użyjemy. Istotna jest koncepcja, którą można wykonać, rysując elementy geometryczne ołówkiem na papierze. Tak zresztą robią nauczyciele w różnych szkołach w Azji Wschodniej.
Co można zrobić z odcinka?
Odcinek, wbrew wszelkim pozorom, może być zupełnie interesującym materiałem – jeśli tylko mamy tych odcinków odpowiednio dużo. Z odcinków właśnie składają się liczne konstrukcje geometryczne, wykorzystywane w różnych tworach artystycznych, takich jak chińskie kraty czy islamskie gwiazdy. W tym artykule przyjrzymy się tylko paru wybranym konstrukcjom, pozostawiając Czytelnikowi pole do nowych odkryć.
Spotkanie ze smokiem
Na początek rysujemy trójkąt ΔABC, gdzie B jest wierzchołkiem kąta prostego i jest położony poniżej punktów A i C, tak jak na rycinie 2. Odcinek AC chowamy. W ten sposób otrzymujemy kształt litery V.
Dla rozrywki możemy zabarwić jeden z boków na niebiesko, a drugi na czerwono. Możemy również zażądać, aby boki trójkąta były rysowane cienką linią. To będzie pomocne, jeśli przypadkiem otrzymana figura będzie gęstą siatką składającą się z dużej liczby odcinków.
Teraz zaznaczmy całą figurę, łącznie z punktami i odcinkami. A następnie w GSP w menu Transform odszukajmy Iterate. Tu będziemy definiować, jak nasza iteracja ma być robiona. Iteracja może składać się z wielu odwzorowań, na razie mamy na ekranie tylko jedno. Potem będzie ich więcej. W okienku mamy pokazane punkty początkowe iteracji – te z lewej, i musimy zdefiniować, na co one przechodzą w trakcie odwzorowania.
A zatem po kolei – kliknięcie na punkt A spowoduje, że A przejdzie na A, czyli na siebie. Teraz kliknięcie na punkt B spowoduje, że drugi punkt początkowy C przejdzie na B. To pokazuje rycina 3.
Teraz dołożymy drugie odwzorowanie. W tym celu w tabelce wybieramy przycisk [Struct…], a następnie Add New Map. Zadając odwzorowanie 2, postąpimy odwrotnie niż poprzednio. Najpierw klikniemy na C, a następnie na B. To sprawi, że punkt A zostanie odwzorowany na C, a punkt C na B. Teraz, naciskając przycisk [Display], zażądajmy, aby program pokazał tylko efekt końcowy, bez wyświetlania tego wszystkiego, co tworzy się po drodze (Final Iteration Only – czyli ostatni element orbity). To, co powinniśmy otrzymać, pokazane jest na rycinie 4.
No i to już prawie wszystko – wciśnijmy przycisk [Iterate] i mamy zrobiony pierwszy przykład iteracji. Teraz spróbujmy wyjaśnić, co tu właściwie się stało. Na początek zaznaczmy całą tak otrzymaną figurę i wciśnijmy klawisz z minusem [−] kilka razy, aż do momentu, gdy na ekranie nic już nie będzie się działo. To, co otrzymamy, będzie tym, co powinniśmy otrzymać przy jednej iteracji.
Odcinek AB został zastąpiony zmniejszoną kopią początkowego trójkąta, odcinek BC również, ale ponieważ zmieniliśmy kolejność punktów przy odwzorowaniu, to nowy trójkąt skierowany jest do środka – to było zamierzone działanie
to jest albo numeryczny [+], albo [Shift][+]. Otrzymana figura jest tym, co otrzymamy po drugim kroku iteracji. Każdy z odcinków otrzymanych w poprzednim kroku został zastąpiony zmniejszoną kopią trójkąta
A co się stanie, gdy będziemy wciskać [+] jeszcze parę razy, tylko nie za dużo? Po kilku dalszych krokach iteracji otrzymamy coś, co przypomina smoka, jest to tzw. smok Hartera-Heighwaya (ryc. 5 i 6)
Gdybyśmy chcieli rysować ręcznie ten cały proces, to powinniśmy zacząć od odwróconego trójkąta bez podstawy, pomalować jedną krawędź na czerwono, drugą na niebiesko i dalej każdą czerwoną krawędź zastępować tym samym, tylko zmniejszonym trójkątem, zawsze zorientowanym w tym samym
kierunku, oraz niebieską również tym samym trójkątem, ale zorientowanym odwrotnie niż dla czerwonej krawędzi.
Pokazana tu figura (ryc. 5) nosi nazwę smoka Hartera-Heighwaya i po raz pierwszy była badana przez fizyków NASA, Johna Heighwaya, Bruce Banksa oraz Williama Hartera. Opisał ją Martin Gardner w swojej rubryce Mathematical Games w „Scientific American” w 1967 roku.
Smok Hartera-Heighwaya ma bardzo interesujące własności i bogatą literaturę. Można go otrzymać na wiele sposobów, tak jak my to zrobiliśmy lub np. składając pasek papieru. Można go użyć do pokrycia płaszczyzny, można policzyć wymiary jego poszczególnych fragmentów, jako ułamki całego wymiaru itp. Tu warto zwrócić uwagę na to, że różne źródła podają różne wersje tego smoka. Najczęściej jest to ta sama figura odwrócona do góry nogami, odbita symetrycznie z lewej na prawą stronę, itd. Pewne z pokazanych tam figur są podobne do smoka Hartera-Heighwaya, ale w rzeczywistości nim nie są. Rycina 5 pokazuje podobiznę naszego smoka (po 11 iteracjach) z zaznaczoną figurą, od której startowaliśmy.
Jeśli przypadkiem zdarzyło nam się pomylić w trakcie definiowania odwzorowań, to mogliśmy otrzymać inną, równie dobrze znaną i ciekawą figurę, tzw. smoka Levy’ego, przypominającą literę C.
Zastanówmy się teraz, jaki możemy mieć pożytek z tak zrobionych konstrukcji w klasie. Oto kilka problemów, jakie można postawić przed uczniami.
Pytania do uczniów
- Z ilu odcinków składa się smok Hartera dla kolejnych iteracji 1, 2, 3, 4, 5?
- Jaki jest wzór na liczbę odcinków kolejnych iteracji smoka Hartera-Heighwaya?
- Jaka jest długość krzywej łamanej, z której zbudowany jest smok Hartera-Heighwaya, jeśli założymy, że odcinek AC miał długość 1 lub powiedzmy a?
- Jaka byłaby powierzchnia obszaru wyznaczonego przez pola trójkątów każdej iteracji smoka Hartera-Heighwaya?
- Jakie znasz sposoby na pokrycie płaszczyzny smokami Hartera-Heighwaya tak, aby nie było przerw pomiędzy nimi i aby nie nakładały się na siebie?
- Z ilu mniejszych smoków składa się smok Hartera-Heighwaya w 12 generacji?
- Dlaczego smok Hartera-Heighwaya jest fraktalem? Na czym polega samopodobieństwo figury i czy smok Hartera-Heighwaya jest podobny do swoich fragmentów?
Figura H
Skoro mamy już za sobą spotkanie ze smokami, to teraz możemy zabrać się za coś trudniejszego. Tym razem zamiast dwu odcinków weźmiemy trzy i zrobimy z nich coś, co będzie wypełniało nam obszar prostokątny – i to dość gęsto.
Na początek narysujmy poziomy odcinek AB, a następnie skonstruujmy jego środek (ryc. 8). Teraz na lewej połowie tego odcinka wybierzmy dowolny punkt, powiedzmy C. Teraz obracamy punkt C wokół punktu A w jedną stronę o 90 stopni i w drugą stronę o −90 stopni. Następnie przesuwamy te dwa nowe punkty wzdłuż odcinka AB o wektor AB na drugą stronę. Dodajemy dwa pionowe odcinki łączące te nowe punkty tak, aby powstała spłaszczona litera H.
Zauważmy, że w tej konstrukcji punkt C spełnia dość szczególną funkcję. Przesuwając go wzdłuż odcinka AB, spłaszczamy lub podwyższamy literę H.
Pora na zrobienie iteracji z tak utworzonej litery H. Zauważmy, że mamy tu znowu tylko dwa punkty początkowe A i B – i to właśnie te punkty będziemy odwzorowywać.
W tym przypadku zażądamy, aby wyświetlała nam się cała orbita, a nie tylko wynik ostatniej iteracji. Teraz możemy już spokojnie zażądać, aby GSP dokończył nam tę iterację. To, co otrzymamy w czwartym kroku iteracji, będzie podobne to tego, co pokazano na rycinie 10. Natomiast rycina 11 pokazuje nam, co zobaczymy po 10 krokach iteracji.
Kształt tego obiektu, a w szczególności to, czy poszczególne fragmenty zachodzą na siebie, czy nie, możemy regulować, przesuwając punkt C (tu duży ciemny punkt) w lewo lub prawo wzdłuż odcinka AB. Zauważmy przy okazji, że manipulowanie tą figurą jest bardzo wolne. Jest to związane z bardzo dużą liczbą odcinków, z jakimi program musi sobie radzić. No właśnie, a ile jest tych odcinków?
Tak jak poprzednio, w procesie iteracyjnym otrzymujemy ciąg obrazów od bardzo prostych do niezmiernie złożonych. Tu już widać wyraźnie dwie rzeczy – jest to obraz fraktalny i mamy widoczne samopodobieństwo całej figury do jej różnych fragmentów, a taka figura kontynuowana do nieskończoności kompletnie pokryje pewien prostokąt płaszczyzny. Jak zawsze, matematyk może zastanawiać się nad wieloma pytaniami. Oto one.
Pytania do uczniów
- Ile odcinków poziomych i pionowych mamy w kolejnych iteracjach 1, 2, 3, 4, 5?
- Jaki jest wzór na liczbę odcinków w każdej iteracji?
- Co się zmieniło w stosunku do poprzedniego przykładu, że manipulacja tą figurą jest znacznie wolniejsza niż manipulowanie smokami?
- Jaka jest łączna długość odcinków figury otrzymanej w 1, 2, 3, 4, 5 kroku iteracji? Zakładamy, że długość odcinka AB jest równa a lub dla uproszczenia 1, natomiast AC ma długość 0 < k < a/2.
- Jaki jest wzór na łączną długość odcinków figury otrzymanej w n-tym kroku iteracji?
- Czy po nieskończonej lub bardzo dużej liczbie kroków iteracji otrzymana figura będzie fraktalem?
Las jodłowy i płatek Kocha
O figurach otrzymanych przez iterację czegoś, co zostało zbudowane z odcinków, można mówić w nieskończoność. My pokażemy jeszcze jeden przykład, nieco bardziej skomplikowany niż te poprzednie. Przykład ten może być punktem wyjścia do wielu interesujących obiektów.
Zaczynamy konstrukcję od poziomego odcinka AB, który dzielimy na połowy. Teraz wyznaczamy zupełnie dowolny punkt w lewej części odcinka i obracamy go względem środka odcinka o 180 stopni. Powstają w ten sposób punkty C i C’. Teraz rysujemy dwa okręgi o środkach w punktach C i C’ i promieniu równym długości odcinka AC. Ich punkt przecięcia zaznaczamy jako D. Teraz chowamy odcinek AB i rysujemy odcinki AC, CD, DC’ oraz C’B. Otrzymana figura jest pokazana na rycinie 12.
Teraz wystarczy schować okręgi, odcinek AB oraz nazwy punktów. Zostanie nam tylko kształt przypominający z grubsza drzewo jodłowe z dużą podstawą.
To już właściwie wszystko, teraz wystarczy zastosować iterację tego kształtu, powielając go na każdym jego odcinku. To, co otrzymamy, pokazujemy na kolejnych rycinach.
Kolekcja figur możliwych do otrzymania z konstrukcji opisanej w tym przykładzie jest niezmiernie bogata. Dlaczego? Ponieważ mamy luźny punkt C i możemy go przesuwać dowolnie wzdłuż odcinka AB. Oto kilka zdecydowanie różnych tworów otrzymanych z tej samej iteracji.
Jeśli zdecydujemy się na to, aby punkt C dzielił odcinek AB na trzy równe części, to możemy stworzyć płatek Kocha. Wystarczy wziąć trójkąt równoboczny i na każdym z jego boków wykonać iterację lasu jodłowego, zakładając, że C i C’ są w 1/3 i 2/3 długości odpowiedniego boku trójkąta. To, co otrzymamy, może wyglądać tak jak na załączonej tu serii obrazków.
W literaturze często spotykamy wersję płatka Kocha przedstawioną na ryc. 14E.
Iteracja las jodłowy może być zastosowana na bokach trójkąta, kwadratu lub innej figury. Może być skierowana na zewnątrz lub do środka figury. Odcinek AB może być podzielony punktami C i C’ na odcinki o różnych lub identycznych długościach. Oto jak może to wyglądać.
iteracji są skierowane do środka
Pytania do ucznia
- Ile mamy odcinków w każdej z kolejnych iteracji 1, 2, 3, 4, 5?
- Jakie jest pole powierzchni ograniczone odcinkiem AB i krzywą otrzymaną z iteracji 1, 2, 3 itd.?
- Jaka jest długość krzywej otrzymanej w iteracjach 1, 2, 3, 4 i 5?
- Jaka jest graniczna wartość pola powierzchni policzonego w punkcie 2 i jaka jest graniczna wartość długości krzywej, jeśli liczba iteracji zmierza do nieskończoności?
- Jakie jest pole powierzchni zawartej wewnątrz płatka Kocha (tu odcinek AB musi być podzielony na trzy równe części)?
- Jakie jest pole powierzchni wewnątrz wywróconego do środka płatka Kocha?
Wyspa Kocha
Kończąc ten iteracyjny tekst, pozwolę sobie pokazać jeszcze jedną figurę (ryc. 15).
Odcinek AB dzielimy na cztery równe części, nad drugą i trzecią rysujemy trzy boki kwadratu. Rysujemy pogrubione odcinki, tak jak to pokazano na rycinie, i usuwamy okręgi oraz wszelkie linie pomocnicze. Zostają tylko pogrubione odcinki. Co nam z tego wyjdzie, jeśli teraz zaczniemy zastępować każdy odcinek tej figury nią samą? To mamy pokazane na rycinie 15A–B.
Ryc. 15A–D. Mamy tu kolejno element wybrzeża wyspy Kocha po pierwszej iteracji oraz wyspę Kocha po zastosowaniu kolejnych iteracji w stosunku do boków kwadratu (iteracje 1, 2 i 3)
Podobnie jak w przypadku poprzednich figur, możemy postawić szereg interesujących pytań dotyczących wyspy Kocha. Jednym z nich może być: Jaka jest jej powierzchnia przy założeniu, że pokazany na rysunkach kwadrat ma bok równy 1?
Do iteracji obiektów geometrycznych wrócimy w następnej części tego artykułu. Przed nami wiele ciekawych rzeczy. Tym Czytelnikom, którzy chcą szybko zobaczyć lub przeczytać coś na ten temat, proponuję poszukać w internecie informacji na temat fraktali lub L-systems. Bardzo pomocna może być strona Wikipedii: //en.wikipedia.org/wiki/L-system
Bibliografia:
- Peitigen H.O., Jürgens H., Saupe D., Granice chaosu, fraktale, Wydawnictwo Naukowe PWN, Warszawa 1995.
- Prusinkiewicz P., Lindenmayer A., The Algorithmic Beauty of Plants, Springer-Verlag, New York, Berlin, Heidelberg 1996.
