Analiza Matematyczna - laboratorium. Maxima.
11. Ciągi  przy okazji odkrywamy, że w Maximie można pro-
gramować.
W rozdziale poświęconym indukcji matematycznej zajmowaliśmy się między innymi
konstruowaniem list wyrazów ciągów zadanych odpowiednimi wzorami. Widzieliśmy jak
można generować dowolnie długie (ale skończone) ciągi  jeżeli znamy wzór na wyraz
ogólny ciągu. Wiele jest jednak sytuacji, w których wzoru ogólnego nie znamy, lub nie
umiemy go zapisać przy pomocy znanego nam zestawu operacji (czy symboli). Spróbuj-
my zapisać na przykład coś takiego:
Å„Å‚
1
òÅ‚
dla n parzystych
n
an =
1
ół
dla n nieparzystych
n2
Albo ciÄ…g zadany rekurencyjnie wzorem
Å„Å‚
"
òÅ‚
3 dla n = 1
bn = "
ół
3 + bn-1 dla n > 1.
Taka wariantowość wymaga pewnej instrukcji warunkowej  i Maxima takową ofe-
ruje. Popatrzmy jak przykłady te można zrealizować:
(%i) a(n) := if remainder(n,2) = 0 then 1/n else 1/n^2
(%i) b(n):= if n = 1 then sqrt(3) else sqrt(3+b(n-1));
Ogólna składnia instrukcji warunkowej wygląda tak:
if cond1 then expr1 elseif cond2 then expr2 elseif ... else expr0
Działa to tak, że jeżeli spełniony jest warunek logicznycond1, to wykonywane jest
polecenieexpr1; w przeciwnym razie sprawdzany jest warunekcond2i jeżeli ten wa-
runek jest spełniony to wykonywane jest polecenieexpr2, w przeciwnym razie... itd.
Jeżeli jednak żaden z warunkówcond1,cond2,... nie jest spełniony, to wykonywane jest
polecenieexpr0.
Przy okazji zauważmy, że w definicji ciągu b(n) posłużyliśmy się rekurencją. Defi-
nicja ciągu b(n) wygląda bardzo zgrabnie i czytelnie ma jednak bardzo ważną wadę.
Popatrzmy na wynik operacji:
(%i) b(1.4);
Czym wytłumaczymy zaobserwowany błąd? W sumie to proste  dla niecałkowitego
argumentu rekurencja nigdy się nie kończy...
Zadanie 11.1 Zmodyfikować definicję ciągu b(n) tak by dla niecałkowitych argumentów
wartość funkcji b wynosiła -1.
1
Zadanie 11.2 A jak zmodyfikować definicję ciągu b(n) by mieć gwarancję, że rekurencja
zawsze się zakończy?
W takiej modyfikacji przydać się mogą funkcjefloororazceilingzwracające od-
powiednio najmiększą (lub najmniejszą) liczbę całkowitę nieprzekraczającą (niemniejszą
niż) argument tej funkcji.
Oczywiście taka modyfikacji nie jest konieczna jeżeli możemy zagwarantować, że
argumenty funkcjib()będą liczbami naturalnymi.
Przy okazji możemy poćwiczyć wykorzystanie instrukcji warunkowej na poniższych
zadaniach:
Zadanie 11.3 Przy pomocy funkcjifloororazceilingzdefiniować funkcje
round funkcja powinna zaokrągłać do najbliższej liczby całkowitej. Zakładamy, że
round(0.5)=1;
truncate(x) funkcja powinna zwracać tą z sąsiednich liczb całkowitych, która jest
bliższa zeru.
Zadanie 11.4 Napisać funkcję, która zwraca true jeśli dwie liczby są odległe od siebie
o mniej niz eps; false w przeciwnym razie. Funkcja ma 3 argumenty  liczby x i y oraz
eps.
Wydaje się, że to dobry moment by przyjrzeć się trochę dokładniej rekurencji. Trochę
bardziej skomplikowaną od podanej wyżej definicją rekurencyjną jest ciąg Fibonacciego
zadany wzorem
Å„Å‚
ôÅ‚
0 dla n = 0
ôÅ‚
òÅ‚
fn = 1 dla n = 1
ôÅ‚
ôÅ‚
ół
fn-1 + fn-2 dla n > 1.
Popatrzmy na definicjÄ™ w Maximie:
(%i) fib(n):= if n < 2 then n else fib(n - 1) + fib(n - 2)
i spróbujmy obliczyć (przy pomocy definiowanej właśnie funkcji) 5, 10, 15, 20, 25, 30
oraz 35 wyraz ciągu Fibonacciego. Zwróćmy uwagę na czasy wykonywania odpowied-
nich poleceń. Ha, na 35-ty wyraz pewnie się w ogóle nie doczekamy. Czym można to
wytłumaczyć? Jeżeli zastanowimy się ile razy wywołana zostanie procedurafib()dla
policzenia tych wartości złapiemy się zapewne za głowę. W każdym kroku ilość wywo-
łań wzrasta niemal dwukrotnie! Możemy spodziewać się, że czas oczekiwania na wynik
wzrastać będzie niemal tak szybko jak ciąg geometryczny o ilorazie 2. Czyli szybko, że
ho-ho!
Zauważmy, że w przypadku ciągu bn zdefiniowanego powyżej problemy z tak szybko
wzrastającymi czasami wykonania funkcji nie występują. Tam jednak każde wywołanie
funkcjib()powoduje tylko jedno dodatkowe wywołanie funkcjib().
2
Zauważmy też, że rekurencja w procedurzefib()jest w zasadzie zbędna. Owszem 
taki sposób obliczania wyrazów ciągu Fibonacciego pochodzi wprost od definicji; jest też
bardzo czytelny i prosty w implementacji  co więcej pozwala na obliczenie dowolnego
wyrazu ciągu (przy dostępie do odpowiednich mocy obliczeniowych i zasobów pamięci).
Jednak ten czas oczekiwania... a gdyby tak powalczyć o skrócenie czasu potrzebnego do
wyliczeniafib(n)? Podstawowa przyczyna opóz
nień to rekurencja  czy da się odpo-
wiednią procedurę zdefiniować bez niej? Pomysłem, który wydaje się iść w dobrą stronę
jest zapmiętywanie wyliczonych już wartości. Przecież w rozwiązaniu rekurencyjnym do
policzeniafib(5)potrzebne jest aż 3 krotne wyliczeniefib(2). A przecież wystarczy
policzyć to raz i zapamiętać. Jak możemy to rozwiązać? Na początek może niezbyt
elegancko  ale w miarÄ™ skutecznie.
(%i) fib(n):=if n < 2 then f[n]:n else f[n]:f[n - 1] + f[n - 2];
Cóż się dzieje? Budujemy listęf[n]kolejnych wyrazów ciągu Fibonacciego, przy
czym do obliczenia wykorzystujemy poprzednie wyniki obliczeń  ale już zapamiętane.
Rekurencji tu nie ma  jak to może zadziałać?
(%i) fib(10);
Ha! To nie zadziała  bez rekurencji niby skąd procedura ma wiedzieć ile to jest f[8]
czy f[9]? Ale spróbujmy teraz po kolei
(%i) makelist(fib(n),n,0,100);
Działa  i to jak szybko! Rozwiązanie to ma jednak zasadniczą wadę  nie da się po
prostu policzyćfib(100). Trzeba policzyć (i zapamiętać) wszystkie poprzednie wyrazy.
Dużo fajniej byłoby mieć możliwość zdefiniowania funkcji w taki sposób byśmy nie mu-
sieli myśleć o tym, że trzeba generować tablicę złożoną z odpowiednio wielu wyrazów
ciągu. Z pomocą przyjdzie nam instrukcja pętli. Wypróbujmy polecenia
(%i) for n:1 thru 5 do display(1/n)
(%i) for n:1 step(1) while 1/n > 0.03 do display(1/n)
Powyższe przykłady mówią nam sporo o sposobie działania tej instrukcji  mamy
pewną zmienną sterującą, która zmienia się przy każdym wywołaniu pętli (w obu powyż-
szych przykładach ton), wartość kroku, o który zmienia się wartość zmiennej sterującej
może być podana jako parametrstep. Kiedy pętla się kończy? Kiedy wykonanych zo-
stanie odpowiednio wiele powtórzeń (to pierwszy przykład), albo kiedy podany warunek
nie jest już spełniony (to drugi przykład). Funkcjadisplaypo prostu wyświetla swój
argument.
Dokumentacja podpowiada nam następujące warianty składni:
for variable: initialvalue step increment thru limit do body
for variable: initialvalue step increment while condition do body
for variable: initialvalue step increment unless condition do body
3
W powyższych przuykładachbodymoże być reprezentowane przez kilka instrukcji 
w formie(aaa, bbb, ccc).
Wypróbujmy taką oto funkcję wyliczającą n-ty wyraz ciągu Fibonacciego.
(%i) fib(n):= block([f,i],f[1]:1,f[2]:1,
for i:2 thru n do f[i] : f[i-1] + f[i-2], f[n] )
Bardziej wrażliwym czytelnikom proponujemy dołożenie jeszcze odpowiedniego za-
chowania dla n = 0 oraz innych n nie będących liczbami naturalnymi.
Pewnej wzmianki wymaga tu na pewno procedurablock(). Czasami jest tak, że
Maxima oczekuje pojedynczej instrukcji  a my chcemy wykonać ich kilka  jedną po
drugiej. W takiej właśnie sytuacji przychodzi nam z pomocą polecenieblock(). Jego ar-
gumentem jest seria poleceń Maximy (poprzedzona opcjonalnie listą zmiennych, których
wartość ustalona jest lokalnie  jedynie wewnątrz definiowanego bloku). Wartość pole-
ceniablock()to wartość ostatniego polecenia na liście (stądf[n]na końcu podanego
przykładu).
Podefiniowaliśmy trochę różnych ciągów, popatrzyliśmy na definicje rekurencyjne 
pora przyjrzeć się liczeniu granic. Tak  Maxima umie liczyć granice. Tyle, że nie są to
granice ciągów  a granice funkcji. Popatrzmy na przykłady:
(%i) limit(1/n,n,inf);
(%i) limit((n-2)/(3*n+1),n,inf);
(%i) limit(sqrt(n^2 +1) - sqrt(n^2 + 3*n) ,n,inf);
(%i) limit(sin(n),n,inf);
Wszystko liczy się zgodnie z oczekiwaniami (czyli pięknie). Ale tutaj już nie...
(%i) limit(sin(%pi*n),n,inf);
Dlaczego? Otóż polecenielimitsłuży do liczenia granic funkcji. Jeżeli granica funk-
cji (w tym wypadku w nieskończoności) istnieje, to jest jednocześnie realizowana jako
granica ciągu wyrażonego tym samym wzorem  i to są przykłady z pierwszej serii. Je-
żeli jednak granica funkcji nie istnieje, to nie mamy podstaw by cokolwiek wnioskować
o granicy ciągu... I to jest drugi przykład. W końcu dla n naturalnych sin(nĄ) = 0, zaś
jeżeli dopuścimy, że n może być dowolną liczbą rzeczywistą to sin(nĄ) przyjmować może
dowolne wartości z przedziału [-1, 1]. Pamiętajmy o tym istotnym ograniczeniu!
4