12. Rekurencja. Ciągi zadane rekurencyjnie.
Contents
12. Rekurencja. Ciągi zadane rekurencyjnie.#
Treści kształcenia: Ciągi zadane rekurencyjnie w informatyce. Granice ciągów, algorytmy obliczania granic (problem zbieżności). Problem stopu w algorytmach. Interpretacja geometryczna (aplety) (na ćwiczeniach: obliczanie granic, punkty skupienia ciągów).
Efekty kształcenia: Student potrafi operować ciągami rekurencyjnymi, badać ich zbieżność i granice. Potrafi określić podstawowe wady i zalety takich ciągów w zastosowaniach informatycznych.
Wstęp.#
Rekurencja.
Rekurencja - odwoływanie się np. funkcji lub definicji do samej siebie.
Dalej będziemy się jednak zajmować głównie ciągami zdefiniowanymi rekurencyjnie. O rekurencji już mówiliśmy przy okazji wprowadzenia pojęcia ciągu. Teraz poszerzymy i usystematyzujemy materiał. To naturalna metoda definiowania wielu ciągów.
Na początek: znany (być może) ciąg Fibonacciego
ma wzór analityczny (ogólny) - co wykażemy, czyli możemy też nie korzystać z rekurencji:
gdzie \(\varphi\) jest tzw. ,,złotą proporcją’’ (\(\varphi =\frac{\sqrt{5}+1}{2}\)).
Wyprowadzimy ten wzór i posłuży nam do wprowadzenia ogólnej metody badania ciągów rekurencyjnych (tylko podstawowe zasady!). Zastanowimy się, która z metod definiowania ciągu jest lepsza (i kiedy).
A inne znane nam ciągi zadane rekurencyjnie? Wspomnijmy też o ciągu arytmetycznym \(a_n = a_{n-1} + r\) oraz geometrycznym \(b_n = q \cdot b_{n-1}\), których definicje są oczywiście rekurencyjne.
Nie zapominajmy też o rekurencyjnym definiowaniu silni: \((n+1)! = n! \cdot (n+1)\), czyli dla \(a_n = n!\)
mamy \(a_0 = a_1 = 1\) oraz \(a_{n+1} = a_n \cdot (n+1)\).
Tak samo rekurencyjnie definiujemy też potęgi o wykładniku naturalnym…
I podstawowa informacja dla informatyków: jak się okaże rekurencja to jedna z podstawowych metod obliczeniowych (i algorytmicznych), w trakcie zajęć postaramy się podać wiele ich zastosowań. W wielu problemach algorytmy wykorzystujące ciągi rekurencyjne są najprostszym, eleganckim, o krótkim kodzie i najbardziej naturalnym sposobem ich rozwiązywania, ale jednocześnie ma niekiedy wady (np. wzrost złożoności czasowej). Stąd warto poznać możliwości wprowadzania ciągów rekurencyjnych, ale i ich zamiany (o ile to możliwe) na wzory ogólne i procedury iteracyjne.
Rozpoczniemy od najprostszych pytań (zadania maturalne!):
Ćwiczenie 1.
Ciąg \((a_n)\) dla każdego \(n = 0,1,2,...,2016\) spełnia warunek
Wyraz \(a_3\) tego ciągu jest równy:
\(A) - 755,5 \quad B) - 1511 \quad C) - 6044 \quad D) - 1510,5 \)
Rozwiązanie.
Podstawiamy w danym wzorze rekurencyjnym kolejno \(n = 2\) , a potem \(n = 2014\). Czyli
Podstawiamy teraz z drugiego równania do pierwszego:
Odpowiedź: A).
Ćwiczenie 2.
Ciąg \((a_n )\) jest określony wzorem
dla każdej liczby naturalnej \(n \geq 3\) . Wiadomo ponadto, że \(a_2 = 3, a_4 = - 4\) i \(a_6 = 9\). Wyraz \(a_3\) jest równy:
\(A) - 1 \quad B) \ 0 \quad C) \ 5 \quad D) - 2\)
Rozwiązanie.
Podstawiamy w danym wzorze rekurencyjnym \(n = 4\) oraz \(n = 5\):
czyli
Odejmujemy teraz od pierwszego równania drugie i mamy \(2a_3 = - 2\), \(a_3 = - 1\).
Odpowiedź: A).
Ćwiczenie 3.
Ciąg \((a_n )\) jest określony wzorem
dla każdej liczby naturalnej \(n\). Oblicz sumę pięćdziesięciu początkowych wyrazów tego ciągu. Uwaga: \(a_1\) - dowolne!
(samodzielnie)
Ćwiczenie 4.
Pierwszymi wyrazami ciągu są: 2, 8, 14, … Znajdź parametry \(A\) i \(B\) dla których określa go następujący wzór rekurencyjny
Odpowiedź: \(A=2, B=6\).
Informatycy pewnie nie zwrócili na to uwagi - ale istotne jest pytanie: skąd wiemy, że rekurencja poprawnie nam coś definiuje? Na szczęście mamy
Twierdzenie. Niech \(X\) będzie dowolnym zbiorem. Załóżmy, że \(a \in X\) i \(F: X \to X\). Istnieje wtedy dokładnie jedna funkcja \(g: {\mathbb{N}} \to X\) taka, że \(g(0) = a\) oraz \(g(n + 1) = F (g(n)))\) dla \(n \in {\mathbb{N}}\).
Pytanie. Ważną kwestią jest czy ciąg zdefiniowany rekurencyjnie możemy zapisać wzorem ogólnym (a wiemy, że tak jest dla ciągu arytmetycznegi i geometrycznego)? A odwrotnie?
A co więcej: jeśli ciąg wyrazimy w obu postaciach, to która z postaci jest ``korzystniejsza’’ - choćby pod względem symulacji komputerowych?
Odpowiedzi nie są oczywiste, ale pokażemy, że w przypadku rekurencji liniowej znamy algorytm uzyskiwania wzoru ogólnego (choć nie zawsze będzie efektywny - np. dla rekurencji wyższych stopni!). Na drugie pytanie też nie ma łatwej odpowiedzi - to ważny problem w informatyce. Warto prześledzić to na przykładzie problemu wież Hanoi …
A dlaczego warto rozważać obie postacie (rekurencyjną i wzór ogólny)? Prosty
Przykład: Obliczanie żądanego wyrazu w ciągu. Rozpatrzmy dla ciąg arytmetyczny (\(a_1\) i \(r\) są ustalone)
Zadanie polega na obliczeniu wyrazu \(a_{1000}\).
Ze wzoru rekurencyjnego wymaga to obliczenia wszystkich poprzednich. Za to wykorzystanie wzoru ogólnego
Tak dla przypomnienia: powyższy dowód formalnie wymaga zastosowania indukcji matematycznej - polecam to jako samodzielne ćwiczenie. Za to z tego wzoru mamy w jednym prostym kroku
Złożoność obliczeniowa jest znacznie mniejsza (1 krok zamiast 999 kroków obliczeniowych).
Są więc sytuacje, w których warto znać wzór ogólny (choć nie zawsze to będzie możliwe). Pokażemy jak to zrobić w przypadku rekurencji liniowej… Ale rozpoczniemy od rozwiania wątpliwości czy w ogóle potrzebujemy narzędzi matematycznych - może wystarczy komputer?
Rekurencja - pułapki komputera…
Czy komputer może być przydatny? Albo w ogóle zastąpić obliczenia matematyczne? Po kolei odpowiemy na te pytania. Czy może być przydatny - tak, ale…
Przykład (A). Rozpatrzmy najpierw próbę wyznaczenia wartości przybliżonej liczby \(\pi\). Zastosujemy algorytm Archmiedesa: geometryczą metodę opartą o wpisywanie kolejnych wielokątów foremnych w koło.
Liczymy \(a_2\), czyli wpisujemy kwadrat. Promień okręgu wynosi \(\frac{1}{2}\), czyli przekątna kwadratu ma długość \(1\), a więc bok \(a_2 = \frac{\sqrt{2}}{2}\). W tej konstrukcji dokonujemy w kolejnych krokach podwojenia liczby boków, czyli
w trójkącie o 2 bokach równych promieniowi (czyli: \(r = \frac{1}{2} = |OC| = |OD|\)) oraz trzecim boku będącym odcinkiem o końcach na okręgu (bok wielokąta \(CD\)) o długości \(a_n = 2s\) jego wysokość \(h = |ON|\) (z twierdzenia Pitagorasa) wyniesie
W takim razie w trójkącie równoramiennym o bokach \(a_n\) (podstawa) i \(a_{n+1}\) (ramiona) jego wysokość \(H = |NM|\) wyniesie
Ponownie stosując twierdzenie Pitagorasa uzyskamy
Czyli ostatecznie podstawiając i porządkując wyrazy uzyskujemy
Teraz obliczamy obwód tego wielokąta
Jeżeli ten ciąg jest zbieżny (o czym później), to do liczby \(\pi\).
O tym jak badać istnienie granicy - już wkrótce (do tematu wrócimy), a teraz o sile i słabości obliczeń
na komputerze. Czy musimy użyć matematyki, a może wystarczy komputer? Wykonamy symulację w oparciu
o obliczenia na komputerze kolejnych wyrazów ciągu i spójrzmy czy faktycznie dostaniemy poprawną hipotezę.
Obliczmy:
R = RealField(55)
a = sqrt(R(2))/2
m = 4
n = 1
nmax = 34
while n < nmax:
O = m*a
print("O[%s]=%s"%(n,O))
m = m*2
a=sqrt(2-sqrt(4-4*a*a))/2
n = n+1
O[1]=2.828427124746190
O[2]=3.061467458920718
O[3]=3.121445152258052
O[4]=3.136548490545939
O[5]=3.140331156954757
O[6]=3.141277250932793
O[7]=3.141513801144290
O[8]=3.141572940366725
O[9]=3.141587725277645
O[10]=3.141591421513899
O[11]=3.141592345574021
O[12]=3.141592576693229
O[13]=3.141592634056147
O[14]=3.141592647692809
O[15]=3.141592645321216
O[16]=3.141592645321216
O[17]=3.141592607375720
O[18]=3.141592910939673
O[19]=3.141594125195191
O[20]=3.141596553704820
O[21]=3.141596553704820
O[22]=3.141674265021758
O[23]=3.141829681889201
O[24]=3.142451272494134
O[25]=3.142451272494134
O[26]=3.162277660168379
O[27]=3.162277660168379
O[28]=3.464101615137755
O[29]=4.000000000000000
O[30]=0.0000000000000000
O[31]=0.0000000000000000
O[32]=0.0000000000000000
O[33]=0.0000000000000000
I - niestety - efekt jest inny od oczekiwanego! Mogło się wydawać, że niezłe przybliżenie
jest osiągane (dla \(n=14\)), a tu zwiększanie liczby boków sugeruje wynik zero (??). Czy w związku z tym ciąg w ogóle jest zbieżny???
Dlaczego symulacja nie działa? No cóż - to nie jest najlepszy algorytm, obliczamy wartości
niewymierne i nawet wykorzystanie dobrej biblioteki systemowej z funkcją sqrt nie pomogło
(problem: zero maszynowe). Zastanowimy się jeszcze jak obliczane są pierwiastki w typowych bibliotekach,
co pozwoli z nich nie korzystać pisząc jedynie własny algorytm!
Dla chętnych - spróbować poprawić ten program!
Należy zachować ostrożność we wnioskach symulacji na komputerze. Prezentacja: ciąg rekurencyjny w prezentacji CDF - wymaga CDF Player
Ale czy wiemy, że nasze symulacje granic innych ciągów będą poprawne i pewne? Nie możemy być tego pewni, tylko matematyka to rozstrzyga! A dla nas to cenna informacja: niestety (?) - bez matematyki się nie obejdzie…
Problem podzielimy na dwa: po pierwsze wykażemy, że granica istnieje i dopiero w drugim kroku możemy ją wyznaczyć - ale - jak widać - kontrolując ograniczenia komputera. Do tego przykładu wrócimy gdy już będziemy wiedzieli jak sprawdzić zbieżność tego tego ciągu.
Uwaga też na kolejne zjawisko: pozorną zbieżność ciągu. To sytuacja, gdy wykonując symulację i obliczając pewną liczbę elementów wydaje się (!), że mamy kandydata na granicę, a ciąg w ogóle nie jest zbieżny!
Sprawdźmy:
dla ustalonych \(a_1\) i \(a_2\) oraz odpowiednio dobierając \(c\), \(d\) i \(k\).
R = RealField(55)
c = R(14/10)
d = R(3/10)
k = 1
a0 = R(136.462554878752)
a1 = R(5.39650717129623)
nmax = 60
for n in range(1,nmax+1):
a2=d*a0+k-c*a1*a1
print("a[%s] = %s"%(n,a0))
a0,a1 = a1, a2
a[1] = 136.4625548787520
a[2] = 5.396507171296230
a[3] = 1.167560953833307
a[4] = 0.7104741381062694
a[5] = 0.6435853848650074
a[6] = 0.6332592347753053
a[7] = 0.6316514536600149
a[8] = 0.6314007879574576
a[9] = 0.6313616990513867
a[10] = 0.6313556033465619
a[11] = 0.6313546526874743
a[12] = 0.6313545045457987
a[13] = 0.6313544812318629
a[14] = 0.6313544780035630
a[15] = 0.6313544767163468
a[16] = 0.6313544780233880
a[17] = 0.6313544753266455
a[18] = 0.6313544804860390
a[19] = 0.6313544705562790
a[20] = 0.6313544896578526
a[21] = 0.6313544529113052
a[22] = 0.6313545236020490
a[23] = 0.6313543876115133
a[24] = 0.6313546492217822
a[25] = 0.6313541459519106
a[26] = 0.6313551141116017
a[27] = 0.6313532516247501
a[28] = 0.6313568345614775
a[29] = 0.6313499419209406
a[30] = 0.6313632015394381
a[31] = 0.6313376934149013
a[32] = 0.6313867640848043
a[33] = 0.6312923638183979
a[34] = 0.6314739611638526
a[35] = 0.6311246000663658
a[36] = 0.6317966232166535
a[37] = 0.6305036176687572
a[38] = 0.6329902503142495
a[39] = 0.6282037655105725
a[40] = 0.6374011156919475
a[41] = 0.6196688744536965
a[42] = 0.6536350151541888
a[43] = 0.5877664360862457
a[44] = 0.7124333678009192
a[45] = 0.4657441058472500
a[46] = 0.9100454093562396
a[47] = -0.01973247417233714
a[48] = 1.272468504055125
a[49] = -1.272766273588904
a[50] = -0.8861670308430030
a[51] = -0.4812386912510168
a[52] = 0.4099229416073111
a[53] = 0.6203768473463076
a[54] = 0.5841624766695118
a[55] = 0.7083689353957711
a[56] = 0.4727475749136202
a[57] = 0.8996243031973389
a[58] = 0.008770830809469499
a[59] = 1.269779592496878
a[60] = -1.254645049687312
Ale jeśli liczymy dalej (np. \(nmax = 60\)), to teraz nie ma pomysłu co jest granicą (przykład za: [1.])!
Pamiętajmy: najpierw zapewniamy sobie, że badany ciąg jest zbieżny, a dopiero później robimy symulacje! A tu granica nie istnieje, ale dowód tego jest trudny - zamiast tego polecam symulację np. dla \(nmax = 5000\).
A kto nie wierzy w słabości symulacji, to poproszę samodzielnie - w dowolnym programie - obliczyć wyrazy ciągu
i sformułować hipotezę o jego zbieżności lub nie. Proszę o ostrożność…
Uwaga: proszę nie spodziewać się, że ciągi rekurencyjne to łatwe obiekty do badań czy symulacji komputerowych. Są bardzo ważne w zastosowaniach ciągi jak np. równanie logistyczne (rekurencyjne)
Nawet nie wiadomo, czy przy dowolnych \(r, A\) te ciągi są zbieżne! Wszyscy ufający symulacjom komputerowym: proszę eksperymentować, np. dla
i zobaczyć to na rysunku… (w ostatnim przypadku - uważać = to tzw. chaos)
Uwaga: Mówiliśmy o ciągach rekurencyjnych, a wcześniej również o arytmetyce komputerowej. No to teraz przykład gdy błędy obliczeń w arytmetyce … pomagają. Szczegóły wymagają - niestety - więcej informacji zarówno z algebry, jak i informatyki! Krótko wyjaśnimy o co chodzi.
Metoda potęgowa służy do przybliżania unormowanego wektora własnego odpowiadającego największej wartości własnej macierzy \(A\), nieosobliwej i dodatnio określonej. Idea tej metody jest bardzo prosta: dla wektora startowego \(x_0\) mnożymy macierz przez ten wektor
czyli to rekurencja…
Okazuje się, że podczas sukcesywnego wymnażania przez macierz \(A\) najszybciej rośnie składowa w kierunku wektora odpowiadającego największej wartości własnej. Co więcej, jeżeli \(x_n\) zostanie w każdym kroku wydzielone przez swoją długość (znormalizowane), to składowe w pozostałych kierunkach będą wygaszane (coraz mniejsze). Algorytm powinien znajdować największą wartość własną macierzy \(A\) (zastosowanie np. w macierzy wyszukiwań algorytmu ‘’GooglePageRank’’ to odpowiada najbardziej trafnej odpowiedzi na pytanie zadane w wyszukiwaniu).
To gdzie problem? Wektor początkowy \(x_0\) musi mieć niezerowy rzut na prostą wyznaczaną przez poszukiwany wektor własny. W przeciwnym wypadku (teoretycznie) ciąg nie jest zbieżny.
Ale - i tu uwaga błędy zaokrągleń - w praktyce obliczeniowej nawet, jeśli \(x_0\) ma zerową składową w kierunku wektora odpowiadającego największej wartości własnej, to po kilku iteracjach ta składowa będzie niezerowa dzięki błędom zaokrągleń. Powoduje to, że metoda potęgowa jest (praktycznie) zbieżna dla każdego \(x_0\).
Ćwiczenie 5. Korzystamy z rekurencji: bierzemy kwadrat o boku \(a\) i w kolejnych krokach dodajemy kolejne takie same kwadraty z prawej i u góry, ale tak by nadal tworzyło to kwadrat. Czyli w kroku drugim mamy dodatkowo 3 kwadraty (góra, prawo i ‘’narożnik’’ prawo-góra). Procedurę powtarzamy.
… można zrobić rysunek na tablicy …
Pytanie: ile takich kwadratów będzie w \(n\)-tym kroku? Wyprowadzić wzór rekurencyjny.
Odp. : \(x_1 = 1\), \(x_n = x_{n-1} + 2n -1\)
Zadania dodatkowe.
(1) Definiujemy rekurencyjnie ciąg za pomocą wzorów: \(a_0 = a_1 = 1\) oraz \(a_n = a_{n-1} + 2 a_{n-2}\) dla \(n > 2\). Obliczyć \(a_6\) i pokazać, że wszystkie wyrazy ciągu są nieparzyste.
(2) Definiujemy rekurencyjnie ciąg za pomocą wzorów: \(b_0 = b_1 = 1\) oraz \(b_n = 2b_{n-1} + b_{n-2}\) dla \(n > 2\). Obliczyć \(b_6\) i pokazać, że wszystkie wyrazy ciągu są nieparzyste.
(3) Podaj definicję rekurencyjną ciągu \(2 \ , \ 2^2 \ , \ (2^2)^2 \ , ((2^2)^2)^2 , ...\) i wyraz ogólny tego ciągu.
(4) Mamy alfabet złożony z \(0\) i \(1\). Ciąg \(a_n\) oznacza liczbę słów w tym alfabecie o o długości \(n\), ale nie zawierających układu znaków ‘’\(01\)’’ (w takiej ustalonej kolejności). Obliczyć 5 pierwszych wyrazów tego ciągu i znaleźć wzór ogólny Odp.: \(2,3,4,5,6\), \(a_n = n+1\)
(5) Dane jest ciąg rekurencyjny
Obliczyć 5 pierwszych liczb. Dla ambitnych: pokazać, że \((P_n)^2 + (P_{n+1})^2 = P_{2n+2}\). Nieco poźniej poszukamy wzoru ogólnego na ten ciąg (czyli: \(\frac{1}{2\sqrt{2}} ((1+\sqrt{2})^{n+1} - (1-\sqrt{2})^{n+1})\)).
(6) Zbadaj zbieżność ciągu
(7) Wieże Hanoi. Proszę samodzielnie zapoznać się z problemem wież Hanoi i przeanalizować wzór rekurencyjny i wzór jawny (np. M. Sysło ,,Algorytmy’’) Odp.: \(H_0 = 0, H_{n+1} = 2H_n +1\) oraz \(H_n = 2^n - 1\)
(8) Oblicz sumę \(n\) początkowych wyrazów ciągu \((a_n)\) określonego dla \(n \geq 1\), w którym
dla \(n \in {\mathbb{N}}\).
Rozwiązanie:
Najpierw skorzystamy ze wzoru na sumę kolejnych wyrazów ciągu geometrycznego:
Stąd
(9) Kupujemy na raty telewizor. Każda kolejna rata ma być mniejsza od poprzedniej o stałą kwotę. Ile zapłacimy za telewizor, jeślili spłacamy go w 7 ratach, z których czwarta rata była równa 350 zł?
(10) Podobnie jak w ćwiczeniu 5. podać wzór rekurencyjny dla takiej konstrukcji w 3 wymiarach, czyli bierzemy kostkę, a w kolejnych krokach dodajemy kostki w prawo, w głąb i w górę plus uzupełniamy wszystko do kostki sześciennej. Podać wzór rekurencyjny na ilość kostek potrzebnych w \(n\)-tym kroku.
(11) Ułożyć własne zadanie na wzór ćwiczenia 5 i zadania (10): dwu i trójwymiarowe konstrukcje mile widziane…