Eida.cz - Rekurentní opravy

Rekurentní opravy

29. května 2016, 06:53 Eida

Kdo ovládá minulost, ovládá přítulnost. Kdo ovládá přítulnost, ovládá všechno ostatní. To ví každý. Čas je konstanta, možná se mění jenom doba a éry, které už nelze změnit. Ale skákat v dobách a snažit se napravovat chyby, i když to třeba leckdy úplně nejde, je nesmírně lákavé. Byla neděle, pětadvacátého listopadu 2007. Bylo Kateří. Všechno hodně, hodně dávno před tím vším. Každý byl ještě mladý a naivní. Za oknem si s osudem bezelstně hrála rodina plná vší a pavouků, bohužel, snad v nesmyslné touze všechno změnit a přetavit svoji pitomou dceru ve špičkovou odbornici. Leda tak ve snu. Spíš ale ani to ne.

Za tento náhlý a zdánlivě nelogický skok bude nejspíš zodpovědný opatrný návrat k maturitám díky mým vystrašeným čumáčkům a díky včerejší R, která se třásla snad ještě mohutněji jak čumáčci. Ale asi ještě víc tu odpovědnost nese neuvěřitelně depresivní prostředí, které na našem velitelství teď od podzimu nastolili přivandrovalí krocani z FITu. Naprosto dementní “inženýři”, kteří nerozumí životu a neumí si navíc vůbec ničeho vážit, natož respektovat zavedené řády a autority. Stojím si otevřeně za tím, že FIT zcela neumí vychovávat lidi s plnohodnotně rozvinutou integritou osobnosti, natož se schopností pokory.

No ale k tématu. Onehdáž, ještě za časů minjiho a jeho magických koulí, byly (a dost možná, asi, třeba i za dnešních časů stále jsou) tématem druhého céčkového projektu rekurentní vztahy. Smyslem bylo účelně přeměnit rekurzí definovaný předpis v aktuálním zadání v iterační výpočet. Na tom by celkově asi nebylo nic úplně špatného, kdyby… kdyby bokem existovala nějaká rozumná podpora v matematické teorii analytických a numerických metod. Je totiž hrozivě nepravděpodobné, že by se drtivá většina vyjukaných středoškoláků kdy předtím setkala s hlubším diferenciálním počtem, aby byla jakkoliv s to odvodit, nebo alespoň dostatečně ocenit odvozování Taylorovy řady pro zadané funkce, nebo ještě ke všemu umět u takto získaných mocninných řad určit jejich konvergenční intervaly. Ve většině případů tohle trápení prostě dopadlo tak, že se z ryzí nouze vzal nějaký už odvozený vzorec pro zadanou funkci a bylo. Ono to pak taky vypadá i hloupě v dokumentaci, kde k tomu zkrátka chybí taková ta omáčka, zkrátka vzorečkové trápení. Jo a vizuálně vyblitě, což je další nešvar středních škol. Mistrovství ve Wordu totiž není známka punku, ale pořádný krok vedle. Práce formálně správná, 10/10, ale vizuálně vypadá úplně vyblitě. Do pekel se vším.

V tom konkrétním zadání před téměř deseti lety v kalendáři byly v iteračních výpočtech prováděné odhady pro relativně milé a přívětivé funkce sin(x) a ln(x). U nich celkem nebylo nijak složité odvodit, jak má být správně použitá Oldova epsílonová přesnost, jednotlivé taylorovské zlomky se zkrátka ve všech krocích pořád zmenšovaly, až najednou nemělo pražádný smysl je počítat dál. Ten fatální průšvih byl ovšem někde úplně jinde, a to by si asi konečně zasloužilo dnešní opravu. Jako nepovinná možnost za určitý finanční bonus, nebo možná spíš bonus nefinanční, bylo rozšíření tohoto céčkového projektového programu o numerický výpočet určitého integrálu z oněch dvou zadaných funkcí na nějakém uživatelem zvoleném intervalu. To zní díky tomu vzorečkovému trápení vlastně dost jednoduše, ale ono by to tady trochu chtělo vložit do úvahy poněkud hlubší myšlenku, protože vyhledaný vzoreček může obsahovat nějaké ne úplně příjemné překvapení a jeho přímé a bezhlavé použití by mohlo mít fatální následky.

Geometrickým významem určitého integrálu je pochopitelně celková plocha pod grafem funkce f(x), kterou obyčejně hledáme na nějakém konkrétním ohraničeném intervalu a, b. No a je taky nepochybně pravda, že se dá jeho hodnota díky vzorečkovému trápení numericky vyjádřit použitím kvadraturních formulí, mezi které jako nejznámější patří obdélníková, lichoběžníková a Simpsonova metoda. Ale co to, ke všem čertům, vlastně je nějaká ta kvadraturní formule? A vzniká podobně jako dýně? Jak se tady bude řídit přesnost? A může na to všechno prachobyčejný čiperník v rozumném čase přijít a splnit tento podivný úkol tak, aby byl ve finále spokojený?

Kvadraturní formule jsou konečné vzorečky připravené k použití odvozené z původního jednoduchého Newton-Cotesova vzorce. Ten říká, že při výpočtu integrálu z f(x) na nějakém - jakémkoliv - jejím subintervalu xi-1, xi můžeme celý integrand f(x) nahradit jeho aproximací získanou z Lagrangerova polynomu zvoleného k-tého stupně.

$$\int_{x_{i-1}}^{x_i}f(x)\,d{x}\,\approx\,\int_{x_{i-1}}^{x_i}L_{i,k}(x)\,d{x}$$

Pokud bychom chtěli tímto způsobem spočítat integrál na celém původním intervalu ⟨a, b⟩, bude potřeba sečíst všechny dílčí integrály spočítané jednoduchým Newton-Cotesovým vzorcem. Kvadraturním formulím říkáme ekvidistantní, protože v tomto okamžiku rozdělí celý interval ⟨a, b⟩ na ekvivalentně od sebe vzdálené uzly, jejichž vzdálenost, označovaná jako h, bude udávat velikost spodní základny každého počítaného obrazce, jejichž celkový počet na celém intervalu ⟨a, b⟩ bude nějaké n

$$\int_{a}^{b}f(x)\,d{x}\,=\,\sum_{i=1}^{n}\,\int_{x_{i-1}}^{x_i}f(x)\,d{x}\,\approx\,\sum_{i=1}^{n}\,\int_{x_{i-1}}^{x_i}L_{i,k}(x)\,d{x}$$

Teď přijde na řadu asi ta úvaha. Kterak zvolit ten záhadný počet n. Nuže, nejdřív další teorie a zamyšlení se nad polynomy a jejich stupněm k. Obdélníkové pravidlo vyrábí jednotlivé dílky obdélníkové, jejich horní základna je rovnoběžná s osou x, tedy Lagrangerův polynom pro obdélníkovou metodu tvoří konstantní funkci, což je polynom stupně k=0. Naproti tomu lichoběžníková metoda, která tvoří jako dílky lichoběžníky s vodorovnou spodní základnou a a nějak skloněnou horní základnou, používá právě pro tu horní základnu předpis přímky, což je polynom stupně k=1, tedy s nenulovou, ale konstantní směrnicí. A nakonec Simpsonovo pravidlo, které, jak se dá z různých vzorečkových trápení vyčíst, aproximuje nad každým dílkem paraboly, tedy využívá polynomy stupně k=2. Pokud vynecháme otázky midpointů, můžeme si celou situaci při rozhodování zjednodušeně představit zhruba nějak takhle:

Ilustrace dílčích integrací pro polynomy různých stupňů při n = 4.

Hned na první pohled je sympatická parabolická krása Simpsonova pravidla, protože se pro sinus tak nějak hodí. Na pohled druhý by mělo být jasné, že případná chyba odhadu bude ve všech případech různá pro všechna n. Z logiky věci je vyplývá, že celková chyba bude daná součtem n dílčích chyb na jednotlivých subintervalech a bude se odvíjet od nějakého reálného nenulového zbytku poslední derivace daného polynomu, kde bychom očekávali nulu. Jako chyba se bere nějaké Mk, maximální číslo z absolutní hodnoty této nejvyšší derivace na daném intervalu aplikované na celý interval. Absolutně dopočítat se to dá pro každou z metod, když ale vezmeme opět ze vzorečkového utrpení hotový konkrétní předpis pro chybu Simpsonova pravidla, dozvíme se, že

$$|\bar{R}_2(f)|\,\leq\,\dfrac{n}{90}\cdot\left(\dfrac{b-a}{2n}^{5}\right)\cdot{\bar{M}_4},$$

a tedy, že R2(f)=g(n), pro které budeme chtět taky R2≤ε. Takže je otázka, je vhodné do programu napaštit nějakou tvrdou a nemyslně vysokou konstantu n pro různá uživatelem zadávaná Oldova epsílon? Abychom sestavili nějaký konkrétní programový odhad, tj. n=f(a,b,ε), musíme si nejdřív vzoreček trochu zpracovat. Vyjde zhruba něco jako

$$n\,\geq\,\sqrt[4]{\dfrac{\bar{M}_4\cdot(b-a)^5}{2880\cdot{ε}}},$$

což pořád ještě není úplně žůžo, protože tam ocasí ta kryptická hodnota M4. Čtyřka označuje čtvrtou derivaci počítaného inegrandu f(x). Je to celkem docela štěstí, protože pro zadané funkce sin(x) a ln(x) se to dá vyjádřit celkem slušně, vyjde to

$$\dfrac{d{}^4}{d{x^4}}(\sin{x})\,=\,\sin{x},$$

$$\dfrac{d{}^4}{d{x^4}}(\ln{x})\,=\,-\dfrac{6}{x^4}.$$

Protože bychom to chtěli ale jako absolutní konstantu, jsme tady zase zpátky u konvergenčních intervalů, na které se upravují (upravovat by se měly!) vstupní hodnoty při aproximaci samotných funkcí. Když je sinus, i nečipera musí z jeho grafu bleskově pochopit, že absolutně maximální hodnoty |sin(x)| jsou vždycky nejvýše 1, a to pro vstupy celočíselných násobků π/2. S tím se celkem dá žít, možná si to někdo ještě upravil na konvergenční interval ⟨0, π/4⟩, kde je tedy absolutní maximum právě v π/4, a to přesně 2^(-0,5), nepřesně nějakých 0,7071. M4 by se tu dalo asi bez řečí uvažovat 1. U přirozeného logaritmu je to maličko zábavnější, konvergenční interval se dá upravit různě, celkem zajímavý a rychlý je například ⟨1/(e)^(-0,5), e^(0,5)⟩, kde mají krajní body absolutní hodnotu 0,5. Čtvrtá derivace je definovaná celkem strmým zlomkem, což znamená, že čím menší číslo x mezi nulou a jedničkou bude, tím větší a mohutnější bude i celková hodnota zlomku. V zadaném intervalu je minimem levá krajní hodnota, která je zhruba 44,334.

Takže s takovými konstantami by šel přepsat funkční předpis pro výpočet platných n tak, aby respektoval zadaná Oldova epsílon. Samozřejmě je potřeba nezapomenout, že je to minimální možná hodnota, musí být celočíselná a ještě ke všemu musí být v případě Simpsonova pravidla sudá. To ostatně vyplývá z odvození kvadraturní formule, nebo alespoň by to mělo být vidět ze vzorečkového trápení.  

Nuže, tím by se snad dal uzavřít pokus o rekurentní opravu této deset let staré vraždy. Pořád se máme co učit. Vlastně Zuzaně asi závidím. Všechen svůj primární čas si užila v rozkvětu a ten sekundární, na ten se jí už nikdo ptát nebude. Ale věřím, že to mohla mít úplně stejně těžké, jako my, ti jediní, co zbyli, mezi hejnem rozvrkočených krocanů, neschopných samostatného kritického myšlení a postrádajících v sobě základní pravidla obyčejného slušného chování.

Eida
Tento článek přečetlo již 339 čtenářů (0 dnes).

Komentáře

Nový komentář