POČÍTAČOVÉ SČÍTÁNÍ ČÍSELNÝCH ŘAD VE STŘEDOŠKOLSKÉ MATEMATICE Hana Mahnelová Gymnázium Nymburk Abstrakt: Žáci v rámci výuky matematiky na SŠ řeší součty číselných řad klasickými metodami (např. využitím vzorce, aplikací binomické věty, algebraickými úpravami, kombinatoricky, teleskopicky) nebo použijí některý z programů CAS. Počítač sčítá řadu způsobem, který je pro současného středoškoláka zatím tajemstvím. Článek obsahuje zjednodušenou teorii jednoho ze sumačních algoritmů, Gosperova algoritmu, a konkrétní příklady známé z výuky na SŠ řešené počítačovým způsobem. Klíčová slova: sčítání řad, Gosperův algoritmus, počítačová algebra.
COMPUTER SUMMATION OF THE NUMBERS SERIES AT THE HIGH SCHOOL MATHEMATICS Abstract: Pupils solve summation problems in mathematics at high schools with classical methods (for example with a well-known formula for the sum, application the Binomial theorem, algebraic treatments, combinatorial, with a telescoping method) or they use a special software from CAS. The computer sums the series with the method, which is still unknown for them. The author presents a simplified theory of Gosper algorithm and examples known from teaching at the high school solved with this algorithm in this article. Key words: summation of finite sums and series, Gosper`s algorithm, the computer algebra. 1. Úvod Dnešní studenti středních i vysokých škol běžně používají k urychlení výpočtů kalkulátory (např. grafické) nebo specializované počítačové softwary, a mají tak příležitost ověřit, že mnohé příklady vyřeší i programy počítačové algebry. Odpověď na otázku „Jak k výsledku dojde počítač?“ ale pro zvídavé jedince zatím zůstává tajemstvím, nicméně i podnětem k jeho odhalení. Zavedení počítačů vyžaduje zautomatizování postupů řešení problémů, jež vycházejí ze známých matematických teorií. Zaměřme se na způsoby jak nalézt součet číselné řady. Sčítání konečného počtu sčítanců aritmetických číselných řad nebo konečných i nekonečných geometrických číselných řad je poměrně jednoduché. Stačí např. použít správný vzorec. Už ale na střední škole se žáci mohou setkat s příklady řad, které nepatří mezi výše zmíněné typy. Příkladnou ukázkou jsou třeba řady s faktoriály nebo kombinačními čísly. To je příležitost seznámit nadané studenty se základními principy algoritmů počítačových sumací. Jejich objevení se datuje přibližně od 80. let dvacátého století a zatím nejsou
230
vypracovány jednoduché ukázkové příklady obsahující takový postup řešení, jaký používá počítač. Poprvé se podrobněji studenti seznamují s pojmy konečná a nekonečná řada na střední škole, odvozují např. vztah a nutnou podmínku pro součet nekonečné geometrické řady. Své vědomosti o řadách pak rozšiřují na vysoké škole. Při hledání nebo dokazování součtu číselné řady aplikují také např. teleskopickou metodu, binomickou větu, matematickou indukci. Součty některých řad určují kombinatoricky. Ve všech případech řešení úloh vyžaduje znalost a porozumění matematice, schopnost dávat věci do souvislostí a přesné logické myšlení. Aby i počítač mohl příklad správně vyřešit, musí být vytvořen vhodný algoritmus. S rozvojem algoritmů roste význam tzv. počítačové algebry, tedy algebry, která provádí výpočty symbolicky, tudíž přesně. Na význačnosti nabývá teorie polynomů, protože práce s nimi patří mezi nejdůležitější směry tvorby algoritmů. Vývoj sumačních algoritmů během posledních čtyřiceti let představuje obrovský kus práce a přináší očekávaný výsledek. Předpokládá se, že i tyto nové postupy najdou své místo ve výuce počítačové algebry. 2. Gosperův algoritmus První sumační algoritmus byl objeven v roce 1970 americkým matematikem a programátorem Ralphem Williamem Gosperem jr., známým jako Bill Gosper (obr. 1). Důležitou součástí Gosperova algoritmu je řešení rekurenční relace pro hypergeometrické polynomy. Teorie je pro středoškoláky poměrně složitá (najdeme ji např. v [5], je možné ji však zjednodušit a zvolit takové ukázky příkladů, které odpovídají úrovni žáka střední školy. Podstatou Gosperova algoritmu je nalezení {s n }n =0 tak, aby bylo ∞
možné pro m, k ∈ N , m < k vyjádřit
n
∑a
k =m n
∑a k =1
k
= sn
k
= s n − s m −1 , speciálně
(podle hodnoty aditivní konstanty), a následně
s = lim s n , nebo prokázání, že takové vyjádření neexistuje. n→∞
Obr. 1: Bill Gosper.
Pro užití tohoto postupu je třeba vymezit jistou skupinu posloupností. Definice 1: Posloupnost {a n }n =1 se nazývá hypergeometrická, právě tehdy, když ∀n ∈ N lze ∞
podíl po sobě jdoucích členů a n −1 , a n této posloupnosti zapsat ve tvaru
a n −1 u (n ) , kde u(n) = an v (n )
a v(n) jsou polynomy. Stručně řečeno, je-li dána posloupnost {a n }n =1 , jejíž členy máme sečíst, potřebujeme zjistit, zda podíl bezprostředně po sobě následujících členů tvoří racionální funkci. Začněme příkladem. ∞
231
n
Příklad 1
∑ (2k ) = n(n + 1) k =1
Řada vyjadřuje součet prvních n sudých přirozených čísel. Abychom mohli použít Gosperův a n algoritmus, ověříme, že posloupnost {2k }k =1 je hypergeometrická. Zkoumáme podíl n −1 an a 2n . Čitatel i jmenovatel zlomku je tvořen polynomy a platí a n = 2n, a n −1 = 2n − 2, n = a n −1 2n − 2 prvního stupně, posloupnost je tedy hypergeometrická. Dalším krok užití Gosperova algoritmu vychází z následující věty, jejíž důkaz čtenář najde např. v [5]. u (n ) Věta 1: Každou racionální funkci nad tělesem T lze zapsat ve tvaru v (n ) u (n ) p (n ) ⋅ q (n ) = , kde p (n ), q (n ), r (n ) jsou polynomy, které splňují podmínku v (n ) p (n − 1) ⋅ r (n ) D(q (n ), r (n + j )) = 1 ∀j ∈ N 0 . Uvedená věta napovídá, že je možné racionální funkci zapsat v jiném tvaru, užitečném pro další práci s algoritmem. Pro trojici polynomů p (n ), q (n ), r (n ) zavedeme odborný název.
u (n ) je racionální funkce nad tělesem T a polynomy p (n ), q(n ), r (n ) v (n ) mající vlastnosti uvedené ve větě 2. Pak trojici polynomů p (n ), q (n ), r (n ) nazýváme u (n ) regulární reprezentací podílu . v (n ) Definice 2: Nechť
Přitom polynomy p (n ), q(n ), r (n ) lze také nalézt algoritmicky. Ukažme si, jak to funguje: položíme nejprve p(n) = 1, q(n) = u(n), r(n) = v(n). Pokud pro všechna j ∈ N0 jsou polynomy q(n) a r(n + j) nesoudělné, jsme hotovi. Pokud ale pro jisté číslo j∗ ∈ N0 platí D (q(n ), r (n + j * )) ≠ 1 , pak definujeme nový polynom g(n) := D(q(n), r(n + j∗) ) a současně j ∗ −1
p(n ) := p(n )∏ g (n − k ) , k =0
q(n ) :=
q(n ) , g (n )
r (n ) :=
r (n ) . g (n − j ∗ )
232
Algoritmicky tak dospějeme až k nalezení nesoudělných polynomů q(n) a r(n + j) . Vzhledem k tomu, že stupně polynomů q tvoří klesající posloupnost, musí popsaný algoritmus skončit u (n ) nalezením požadované regulární reprezentace podílu . v (n ) Obecná teorie přitom využívá pokročilejší algebraické pojmy a věty (jako např. rezultant polynomů, Sylvesterovo kritérium). Ale jak si ukážeme, v jednodušších příkladech určených středoškolákům vystačíme s výpočtem největšího společného dělitele polynomů. Pokračujme v řešení příkladu 1: Chceme nalézt regulární reprezentaci podílu
2n , položíme-li p (n ) = 2n, q (n ) = 1, r (n ) = 1 , 2n − 2
2n ⋅ 1 2n = a současně D (1, 1 + j ) = 1 ∀j ∈ N 0 a proto uvedená trojice polynomů 2(n − 1) ⋅ 1 2n − 2 a tvoří regulární reprezentací podílu n . an −1 pak
Jsou-li splněny předpoklady, že posloupnost {a n }n =1 je hypergeometrická a máme regulární a reprezentaci podílu n , pak aplikujeme druhou větu teorie Gosperova algoritmu, kterou an −1 uvádíme opět bez důkazu, s odkazem na zdroj [5]. ∞
Věta 2: Nechť
{a n }∞n=1
je hypergeometrická posloupnost nad tělesem T a polynomy
p (n ), q (n ), r (n ) tvoří regulární reprezentaci podílu
an . Jestliže posloupnost částečných a n −1
n
součtů {s n }n =0 , kde s n = ∑ ai , je hypergeometrická, pak lze n-tý částečný součet s n vyjádřit ∞
i =1
q (n + 1) ⋅ a n ⋅ f (n ) p (n ) p (n ) = q (n + 1) ⋅ f (n ) − r (n ) ⋅ f (n − 1) .
ve
tvaru
sn =
pro
jistý
polynom f (n ) splňující
podmínku
Jediným problémem je v tuto chvíli nalezení polynomu f (n ) . Existuje algoritmus, jak určit stupeň k tohoto polynomu. Vycházíme přitom ze známých hodnot stupňů polynomů p, q, r a z koeficientů členů jistých odvozených polynomů. Algoritmus tohoto procesu je následující: lp := stupeň (q(n + 1) + r(n)) lm := stupeň (q(n + 1) − r(n))
if lp ≤ lm then k := stupeň( p(n)) − lm else
[
]
k0 := − l p ⋅ koef (q, l p ) − koef (q, l p − 1) + koef (r , l p − 1) koef (q, l p )
233
if (k0 je celé číslo) then k := max (k0, stupeň(p(n)) − lp + 1) else k := stupeň(p(n)) − lp + 1 fi fi Dodejme, že zápis koef (q, lp) znamená hodnotu koeficientu členu polynomu q(n) odpovídajícího stupni lp , zápis koef (q, lp -1) hodnotu koeficientu členu polynomu q(n) odpovídajícího stupni lp-1. Pro účely Gosperova algoritmu definujeme stupeň nulového polynomu -1. Známe-li stupeň hledaného polynomu f (n ) , pak nic nestojí v cestě využít větu 2 a zkusit konkrétní polynom najít z rovnice p (n ) = q (n + 1) ⋅ f (n ) − r (n ) ⋅ f (n − 1) . (1) Vraťme se k našemu příkladu 1. q(n + 1) + r (n ) = 2 ⇒ l p = 0 ,
q(n + 1) − r (n ) = 0 ⇒ lm = −1 (viz dodatek o stupni nulového polynomu), to ale znamená, že l p > l m , proto podle algoritmu hledáme dále pomocné k 0 = 0 : 1 = 0 ∈ Z ,
potom k = max (0, 1 − 0 + 1) = 2 a polynom f (n ) bude mnohočlenem druhého stupně. Označme f (n ) = c2 n 2 + c1n + c0 . Dosadíme-li do rovnice (1), platí 2 2n = c 2 n 2 + c1 n + c 0 − c 2 (n − 1) + c1 (n − 1) + c0 , po úpravě 2n = 2c 2 n + c1 − c 2 ⇔ 2 = 2c 2, 0 = c1 − c 2 . Řešením soustavy je c 2 = c1 = 1, c0 = t , t ∈ R . Pro
[
]
hodnotu parametru t = 0 je f (n ) = n 2 + n . Nalezením polynomu f (n ) se kruh uzavírá a užitím vzorce q (n + 1) s n/ = ⋅ a n ⋅ f (n ) (2) p (n ) z věty 2 můžeme určit součet řady. V našem případě q(n + 1) = 1, p(n ) = 2n, a n = 2n, f (n ) = n 2 + n a součet 1 s n/ = ⋅ 2n ⋅ (n 2 + n ) = n(n + 1) . Nyní je třeba ještě ošetřit počáteční podmínky, tj. v našem 2n případě zjistit hodnotu s 0/ . Dosadíme-li do posledního vztahu n = 0 , dostaneme s 0/ = 0 a následně s n = s n/ − s0/ = n(n + 1) .
Správnost výsledku si řešitel může ověřit několika známými způsoby. Např. vzorcem pro součet prvních n členů aritmetické posloupnosti s prvním členem a1 = 2 , a diferencí d = 2 , n n pak s n = [2 + 2 + (n − 1) ⋅ 2] = (2n + 2 ) = n(n + 1) . 2 2
234
Nebo elegantní sčítací metodou, kdy zapíšeme součty pod sebe, využijeme komutativnosti sčítání a ekvivalentní úpravy se soustavou rovnic. sn = 2 + 4 + 6 + . . . + 2n s n = 2n + 2(n − 1) + . . . + 4
+ 2
Sečteme-li obě rovnice, dostaneme 2 s n = n (2 + 2n ) a zjednodušením s n = n(n + 1) . Velice názorný je také geometrický model určení součtu této řady. Začněme hrou s kameny. Seřaďme počty černých kamenů odpovídající postupně sudým přirozeným číslům do řádků. Doplníme řádky bílými kameny tak, aby vznikl obrazec se stejným počtem černých a bílých kamenů (viz obr. 2).
n
2n + 2 obr. 2: Geometrický model součtu řady.
Je vidět, že útvarem je obdélník, jehož jedna strana obsahuje právě n kamenů a druhá 2n+2 (nezávisle na jejich barvě). Pak ale počet všech kamenů v obdélníku je určen číslem n(2n + 2 ) . Protože černých a bílých kamenů je stejně, množství jednobarevných určíme jako n(2n + 2) polovinu z celkového počtu, čili = n(n + 1) . 2 Známe-li výsledný součet řady, o správnosti se můžeme přesvědčit také matematickou indukcí. Nejdříve ověříme platnost pro první možné přirozené číslo, pro n = 1 , 2 ⋅ 1 = 1 ⋅ (1 + 1) , tedy platí. Předpokládáme, že existuje k ∈ N , pro které platí
n
∑ (2k ) = n(n + 1) a dokazujeme k =1
vztah pro (k + 1) ∈ N . 2 + 4 + 6 + . . . + 2k + 2(k + 1) = k (k + 1) + 2(k + 1) = (k + 1)(k + 2 ) , cbd. V dnešní době k ověření výsledku dobře poslouží některý z programů CAS, např. komerční Derive 6 (obr. 4), Maple, Matlab, Mathematica apod., nebo volně dostupný prohlížeč Wolphram Alpha, který počítá on-line (obr. 5), případně novější freeware produkt firmy Microsoft, program Microsoft Mathematics (obr. 6).
235
Obr. 4: Výpočet v Derive 6.
Obr. 5: Výpočet užitím WolphramAlpha.
Obr. 6: Výpočet v prostředí Microsoft Mathematics.
236
n
Příklad 2
∑ k ⋅ k! k =1
Při určení součtu uvedené řady počítačovým způsobem postupujeme podle kroků Gosperova an n2 = algoritmu. Nejdříve označme a n = n ⋅ n!, a n −1 = (n − 1) (n − 1)! , potom platí , to a n −1 n − 1 znamená, že posloupnost {a n }n =1 je hypergeometrická. Regulární reprezentace podílu ∞
zřejmě p (n ) = n, q (n ) = n, r (n ) = 1 , neboť D(n, 1) = 1 . Dále q (n + 1) + r (n ) = n + 2 ⇒ l p = 1 ,
n2 je n −1
q(n + 1) − r (n ) = n ⇒ lm = 1 a pro stupeň polynomu f (n ) platí k = 1 − 1 = 0 , proto f (n ) = c0 . Z rovnice (1) pak vyplývá n +1 n = (n + 1)c0 − c0 , odtud c0 = 1 . Dosadíme do rovnice (2) , s n/ = ⋅ n ⋅ n!⋅1 = (n + 1)! n a s 0/ = 1 . Výsledný součet je pak s n = s n/ − s 0/ = (n + 1)!−1 . Z klasických způsobů řešení této řady vybíráme např. sčítací metodu. Platí 1 ⋅1! = 2 ⋅1! − 1 ⋅1! = 2! − 1! 2 ⋅ 2! = 3 ⋅ 2! − 1 ⋅ 2! = 3! − 3 ⋅ 3! = 4 ⋅ 3! − 1 ⋅ 3! = 4! −
2! 3!
..........
n ⋅ n! = (n + 1) ⋅ n! − n! = (n + 1)! − n! Sečteme-li první a poslední sloupec, pak se čísla 2!, 3!, ..., n! vyruší a dostaneme n
∑ k ⋅ k! = −1 + (n + 1)!= (n + 1)! − 1 . k =1
Nakonec ještě pohled do prostředí programu Derive 6 (obr. 7).
Obr. 7: Součet řady v prostředí Derive 6.
237
3. Shrnutí Chceme-li sčítat řadu užitím Gosperova algoritmu postupujeme takto: ∞ 1. Zjistíme, zda posloupnost {a n }n =1 je hypergeometrická. an . a n −1 3. Z polynomů, jež tvoří regulární reprezentaci podílu, algoritmicky odvodíme stupeň hledaného polynomu f (n ) pro rovnici (1). Napíšeme jeho obecné vyjádření. 4. Dosadíme do rovnice (1) a z ní vypočteme hodnoty koeficientů polynomu f (n ) . 5. Nalezený polynom f (n ) dosadíme do vzorce (2).
2. Nalezneme regulární reprezentaci podílu
6. Zjistíme počáteční podmínky a nakonec vyjádříme s n = s n/ − s m/ , případně s = lim s n , n →∞
pokud sčítáme nekonečnou řadu. 4. Závěr Není problém dokázat, že Gosperův algoritmus sečte každou geometrickou řadu, která je nejrozšířenějším typem řad na středních školách. Stačí algoritmicky pracovat s obecným vzorcem pro n-tý člen geometrické posloupnosti. Dokonce takový postup je dalším, tentokrát počítačovým, důkazem vzorce pro součet prvních n členů geometrické posloupnosti. Gosperův algoritmus ale není všemocný. Jak plyne z věty 2, jestliže posloupnost částečných ∞ součtů {s n }n =0 není hypergeometrická, pak se nepodaří nalézt odpovídající polynom f (n ) a říkáme, že řada není gosperovsky sčítatelná (možné situace, kdy nelze pokračovat v algoritmu dále, analyzujeme poměrně snadno). Proto bylo potřeba pokračovat v hledání dalších sumačních algoritmů. Následoval objev Zeilbergerova algoritmu ct („creative telescoping“) – vznik se datuje v rozpětí let 1982 - 1990. Teorie byla spoluprací dvou matematiků Dorona Zeilbergera a Herberta Saul Wilfa podrobněji rozpracována, rozšířena a zobecněna, a dnes je známa jako WZ algoritmus (1992). Objev Hyper algoritmu Marko Petkovšekem, publikovaném v jeho disertační práci v roce 1991, znamenal další velký přínos v systému poznatků o počítačovém sčítaní řad. Chceme-li prezentovat Gosperovu metodu hledání součtu řady středoškolákům, je třeba definovat dva nové pojmy, a to hypergeometrickou posloupnost a regulární reprezentaci podílu. Další aktivita je založena na práci s polynomy: hledání vhodných polynomů, jejichž největší společný dělitel je 1, určení stupně polynomu, obecné vyjádření polynomu daného stupně, stanovení koeficientu jistého členu polynomu a řešení rovnice na základě porovnání polynomů. V takových případech, kdy polynom f (n ) vychází jako mnohočlen vyššího stupně a musíme řešit soustavu rovnic s vícero proměnnými, oceníme pomoc některého z již zmíněných programů CAS. Z výše uvedeného vyplývá možnost zařadit příklady počítačového sčítání číselné řady už na střední školu a tím zdůraznit mezipředmětové vztahy matematiky a informatiky. Je to současně příležitost ukázat nové pokroky těchto oborů a zvýšit tak zájem nadaných studentů.
238
Literatura: HORA, J. O některých otázkách souvisejících s využíváním programů počítačové [1] algebry ve škole - III. díl. 1. Plzeň: Pedagogické centrum Plzeň, 2001. 74 s. ISBN 807020-092-8. LISKA, R.; DRŠKA, L.; LIMPOUCH, J.; ŠIŇOR, M.; WESTER, M.; WINKLER, F. [2] Počítačová Algebra, Algoritmy, Systémy a Aplikace. [online] . 1998. [cit. 2008-07-02] Dostupné z WWW: http://kfe.fjfi.cvut.cz/~liska/poalg/>. MAHNELOVÁ, H.: Sčítání číselných řad pomocí počítačových algoritmů. In Sborník [3] doktorandské sekce konference Informační a komunikační technologie ve vzdělávání. Konferenci uspořádala Pedagogická fakulta Ostravské univerzity ve dnech 13. - 16. 9. 2010. CD ISBN 978-80-7368-925-4. NELSEN R. B.: Proofs Without Words.[online]. 2009 [cit. 2009–12-8]. Dostupný z [4] WWW:
. PETKOVŠEK, M. ; WILF, H. S.; ZEILBERGER, D. A=B [online]. [s.1.] : [s.208], [5] 17.4.1997 [cit. 2008-07-2]. Dostupné z WWW: . WINKLER, F., Polynomial Algorithms in Computer Algebra, Springer Verlag Wien, [6] 1996. < http://www.vintage.org/gallery.php?grouptag=VCF60> [7] < http://www.wolframalpha.com/> [8]
Hana Mahnelová Gymnázium Nymburk Komenského 779 288 40 Nymburk [email protected]
239
