Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Drsná matematika II – 1. přednáška Aproximace polynomy a splajny Jan Slovák Masarykova univerzita Fakulta informatiky 21. 2. 2011 Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Obsah přednášky 1 Literatura 2 Podmínky výuky 3 Jak moc potřebujeme funkcí? 4 Interpolace 5 Derivace 6 Splajny Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Kde je dobré číst? vlastní poznámky, texty současného nebo předcházejícího přednášejícího, GOOGLE, atd. Ivana Horová, Jiří Zelinka, Numerické metody, MU Brno, 2. rozšířené vydání, 2004, 294 s., ISBN 80-210-3317-7. Zuzana Došlá, Jaromír Kuben, Diferenciální počet funkcí jedné proměnné, MU Brno, 2003, 215 s., ISBN 80-210-3121-2. Riley, K.F., Hobson, M.P., Bence, S.J. Mathematical Methods for Physics and Engineering, second edition, Cambridge University Press, Cambridge 2004, ISBN 0 521 89067 5, xxiii + 1232 pp. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Podmínky pro absolvování předmětu Povinnosti před ústní zkouškou: 1 Odevzdat alespoň 10 domácích úloh z celkových 13. 2 Za průběžné tři písemné testy a úlohy získat alespoň 10 bodů z 20 možných — lze: 2 body za domácí úlohy, pokud bude uznáno alespoň deset z nich, 6 bodů za každý jednotlivý test (v poslednim ještě s bonusovými 2 body navíc). Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny jaké funkce potřebujeme pro naše modely? – pořádný zvěřinec... Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny V tomto semestru budeme budovat nástroje pro modelování závislostí, které nejsou ani lineární ani diskrétní. Někdy je to přímo záměr či potřeba (třeba u modelů fyzikálních jevů), jindy je to vhodné přiblížení diskrétního modelu (třeba u ekonomických nebo populačních modelů), v každém případě to bývá jediný nástroj pro studium robustnosti numerických výpočtů a odhad chyb. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Budeme pracovat s funkcemi R → R (reálné funkce reálné proměnné) nebo R → C (komplexní funkce reálné proměnné), případně s funkcemi Q → Q (funkce jedné racionální proměnné s racionálními hodnotami) apod. Většinou půjdou naše závěry snadno rozšířit na případ s vektorovými hodnotami nad stejnými skaláry, ve výkladu se ale zpravidla omezíme jen na případ reálných čísel, případně komplexních čísel. Čím větší třídu funkcí připustíme, tím obtížnější bude vybudovat nástroje pro naši práci. Cílem našich prvních dvou kapitol matematické analýzy bude proto explicitně zavést několik typů elementárních funkcí, implicitně popsat více funkcí a vybudovat standardní nástroje pro práci s nimi. Souhrnně se tomu říká diferenciální a integrální počet jedné proměnné. Zabere nám to více než polovinu semestru. . . Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Polynomy Skaláry umíme sčítat i násobit a tyto operace splňují řadu vlastností, které jsme vyjmenovali hned na začátku minulého semestru. Polynomem nad okruhem skalárů K rozumíme zobrazení f : K → K dané pro každé x ∈ K výrazem x → f (x) = anxn + an−1xn−1 + · · · + a1x + a0, kde ai , i = 0, . . . , n, jsou pevně zadané skaláry, násobení je znázorněno prostým zřetězením symbolů a „+“ označuje sčítání. Pokud je an = 0, říkáme, že polynom f je stupně n. Stupeň nulového polynomu není definován. Skaláry ai označujeme jako koeficienty polynomu f . Polynomy stupně nula jsou konstantní nenulová zobrazení x → a0. Algebraicky jsou polynomy definovány jako formální výrazy f (x), tj. jako posloupnosti koeficientů a0, a1, . . . s konečně mnoha nenulovými prvky. Jsou tyto přístupy ekvivalentní?. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Je snadné ověřit, že polynomy nad okruhem skalárů tvoří opět okruh, kde násobení a sčítání je dáno operacemi v původním okruhu K pomocí hodnot polynomů. Připomeňte si při této příležitosti vlastnosti skalárů a ověřte! Lemma Je-li K pole s nekonečně mnoha prvky, pak dva polynomy f a g jsou si rovny jako zobrazení, právě když mají shodné koeficienty. Uvědomme si, že u konečných polí samozřejmě takové tvrzení neplatí. Uvažte např. polynom x2 + x nad Z2. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Důkaz. Nad každým polem skalárů funguje dělení polynomů se zbytkem, tj. pro polynomy f stupně n a g stupně m, existují jednoznačně určené polynomy q a r takové, že stupeň r je menší než m nebo je r = 0 a f = q · g + r. Je-li pro nějaký prvek b ∈ K hodnota f (b) = 0, pak to znamená, že v podílu f (x) = q(x)(x − b) + r musí být r = 0. Jinak by totiž nebylo možné dosáhnout f (b) = q(b) · 0 + r, kde stupeň r je nulový. Říkáme, že b je kořen polynomu f . Stupeň q je pak právě n − 1. Pokud má q opět kořen, můžeme pokračovat a po nejvýše n krocích dojdeme ke konstatnímu polynomu. Dokázali jsme tedy, že každý nenulový polynom nad polem K má nejvýše tolik kořenů, kolik je jeho stupeň. Odtud již snadno dovodíme i následující pozorování: Předpokládejme f = g, tj. f − g = 0 jako zobrazení. Polynom (f − g)(x) tedy má nekonečně mnoho kořenů, což je možné pouze tehdy, je-li nulovým polynomem. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Interpolační polynom Častá praktická úloha zní „zadejte formuli pro funkci, pro kterou máme zadány hodnoty v předem daných bodech x0, . . . , xn “. Pokud by šlo o nulové hodnoty, umíme přímo zadat polynom f (x) = (x − x0)(x − x1) . . . (x − xn), který bude mít nulové hodnoty právě v těchto bodech a nikde jinde. To ale není jediná odpověď, protože požadovanou vlastnost má i nulový polynom. Ten je přitom jediný s touto vlastností ve vektorovém prostoru polynomů stupně nejvýše n. Ve skutečnosti jsme dokázali před chvílí, že nenulový polynom stupně n, nemá nikdy více než n nulových bodů. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Theorem Nechť K je nekonečné pole skalárů, pak pro každnou množinu po dvou různých bodů x0, . . . , xn ∈ K a předepsaných hodnot y0, . . . , yn ∈ K existuje právě jeden polynom f stupně nejvýše n (případně nulový polynom), pro který platí f (xi ) = yi , i = 0, . . . , n. Důkaz. Protož už víme, že existuje nejvýše jeden polynom stupně n s předepsanými n + 1 hodnotami yi v různých bodech x0, . . . , xn, stačí sestrojit takový polynom. To ale není těžké, stačí pracovat s polynomy i (x) = j=i (x − xj ) j=i (xi − xj ) . Hledaný polynom je f (x) = y0 0(x) + y1 1(x) + · · · + yn n(x). Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Dosazením požadovaných hodnot do polynomu s neznámými koeficienty dostaneme systém n + 1 rovnic pro stejný počet neznámých koeficientů ai a0 + x0a1 + · · · + (x0)n an = y0 ... a0 + xna1 + · · · + (xn)n an = yn. Jak je dobře známo z lineární algebry, tento systém lineárních rovnic má právě jedno řešení pokud je determinant jeho matice invertibilní skalár, tj. pokud je nenulový. Dokázali jsme proto nenulovost tzv. Vandermondova determinantu V (x0, . . . , xn) = det      1 x0 (x0)2 . . . (x0)n 1 x1 (x1)2 . . . (x1)n ... ... ... ... ... 1 xn (xn)2 . . . (xn)n      = n−1 i>k=0 (xi −xk). Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Problémy interpolace Uvažujme reálné nebo případně racionální polynomy, tj. polynomiálně zadané funkce R → R nebo Q → Q. Vypadají jako hezká třída funkcí jedné proměnné, kterou můžeme snadno použít na proložení jakékoliv sady předem zadaných hodnot. Bohužel: Vyjádření tzv. Lagrangeova interpolačního polynomu je velmi citlivosté na nepřesnosti výpočtu při malých rozdílech zadaných hodnot xi , protože se v ní těmito rozdíly dělí. Přímé řešení soustav rovnic by vyžadovalo čas úměrný n3. Interpolační polynomy mají velice špatnou stabilitu hodnot reálných nebo racionálních polynomů při zvětšující se hodnotě proměnné. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Nestabilitu vidíme na obrázcích, kde je proložena funkce sin(x) jedenácti body. -4 x 2 4 1 2 0 -1 0 -2 -2 -4 x 2 4 1 2 0 -1 0 -2 -2 Zelená je aproximovaná funkce, kolečka jsou malinko posunuté hodnoty a červený je interpolační polynom. Kolem interpolačních polynomů existuje bohatá teorie viz text Horová-Zelinka. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Hodnoty polynomů s rostoucí proměnnou rychle míří k nekonečným hodnotám. Mohlo by se ale zdát, že podstatně lepší výsledky budeme alespoň mezi body xi dosahovat, když si budeme kromě hodnot funkce hlídat, jak rychle naše funkce v daných bodech rostou. Zavedeme proto (prozatím spíše intuitivně) pojem derivace pro reálné, komplexní nebo racionální polynomy. Rychlost růstu v bodě x ∈ R pro reálný polynom f (x) dobře vyjadřují podíly f (x + ∆x) − f (x) ∆x a protože umíme spočíst (nad libovolným okruhem) (x + ∆x)k = xk + kxk−1 ∆x + · · · + k l xl (∆x)k−l + · · · + (∆x)k , umíme i spočíst ten podíl pro f (x) = anxn + · · · + a0. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny f (x + ∆x) − f (x) ∆x = an nxn−1∆x + · · · + (∆x)n ∆x + · · · + a1 ∆x ∆x = nanxn−1 + (n − 1)an−1xn−2 + · · · + a1 + ∆x(. . . ), kde výraz v závorce je polynomiálně závislý na ∆x. Evidentně pro hodnoty ∆x velice blízké nule dostaneme hodnotu libovolně blízkou výrazu f (x) = nanxn−1 + (n − 1)an−1xn−2 + · · · + a1, který nazýváme derivace polynomu f (x) podle proměnné x. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Z definice je jasné, že f (x0) dává dobré přiblížení pro chování f (x) v okolí bodu x0. Přesněji řečeno, přímka y = f (x0)(x − x0) + f (x0) velice dobře aproximuje přímky procházející body [x0, f (x0)] a [x0 + ∆x, f (x0 + ∆x)] pro malé hodnoty ∆x. Hovoříme o lineárním přiblížení polynomu f jeho tečnou. Derivace polynomů je lineární zobrazení, které přiřazuje polynomům stupně nejvýše n polynomy stupně nejvýše n − 1. Iterací této operace dostáváme druhé derivace f , třetí derivace f (3) a obecně po k–násobném opakování polynom f (k) stupně nejvýše n − k. Po n + 1 derivacích je výsledkem nulový polynom. S tímto lineárním zobrazením jsme se již potkali v odstavci o nilpotentních zobrazeních. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Hermiteův interpolační problém Uvažme m + 1 po dvou různých x0, . . . , xm a předepišme hodnoty a derivace y (k) i pro k = 0 a k = 1. Hledáme f (x) = anxn + . . . a0 s těmito hodnotami a derivacemi. Opět obdržíme pro neznámé koeficienty ai systém rovnic a0 + x0a1 + · · · + (x0)n an = y (0) 0 ... a0 + xma1 + · · · + (xm)n an = y (0) m a1 + 2x0a2 + · · · + n(x0)n−1 an = y (1) 0 ... a1 + 2xma2 + · · · + n(xm)n−1 an = y (1) m . Při volbě n = 2m + 1 bude determinant tohoto systému rovnic nenulový. Opět lze také zkonstruovat takový polynom f přímo. Nazýváme jej Hermiteův interpolační polynom. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Úplně nejjednodušší případ je zadání hodnoty a derivace v jediném bodě. Tím určíme beze zbytku polynom stupně 1 f (x) = f (x0) + f (x0)(x − x0) tj. právě rovnici přímky zadané hodnotou a směrnicí v bodě x0. Když zadáme hodnotu a derivaci ve dvou bodech, tj. y0 = f (x0), y0 = f (x0), y1 = f (x1), y1 = f (x1) pro dva různé body xi , dostaneme ještě pořád snadno počítatelný problém. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Ukažme si jej v zjednodušeném provedení, kdy x0 = 0, x1 = 1. Pak matice systému a její inverze budou A =     0 0 0 1 1 1 1 1 0 0 1 0 3 2 1 0     , A−1 =     2 −2 1 1 −3 3 −2 −1 0 0 1 0 1 0 0 0     . Přímým vynásobením A · (y0, y1, y0, y1)T pak vyjde vektor (a3, a2, a1, a0)T koeficientů polynomu f , tj. f (x) = (2y0 −2y1 +y0 +y1)x3 +(−3y0 +3y1 −2y0 −y1)x2 +y0x +y0. Formuli lze snadno upravit pro libovolné body x0, x1 a lze tak počítat aproximace funkcí „po kouskách“. Obdobně lze předepisovat libovolný konečný počet derivací v jednotlivých bodech a vhodnou volbou stupně polynomu obdržíme vždy jednoznačné interpolace. Nebudeme zde uvádět podrobnosti, viz opět text Horová-Zelinka. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny I u interpolací s derivacemi pořád zůstávají problémy zmíněné už v případě jednoduchých interpolací hodnot – složitost výpočtů a nestabilita. Navíc přibývá problém spojený s odhadem derivací pokud je zadána pouze množina hodnot. Použití derivací však podbízí jednoduché vylepšení metodiky – splajny. (Ošklivé české slovo „splajn“ vzniklo fonetickým přepisem anglického ekvivalentu „spline“, který znamenal tvárné pravítko užívané inženýry pro kreslení křivek.) Nabízí se tedy využití malých polynomiálních kousků, které ale musíme umět rozumně navazovat. Nejjednodušší je propojení vždy dvou sousedních bodů lineárním polynomem. Tak se nejčastěji zobrazují data. Z pohledu derivací to znamená, že budou na jednotlivých úsecích konstantní a pak se skokem změní. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny O něco sofistikovanější možností je předepsat v každém bodě hodnotu a derivaci, tj. pro dva body budeme mít 4 hodnoty a jednoznačně tím určíme Hermiteův polynom 3. stupně, viz výše. Tento polynom pak můžeme použít pro všechny hodnoty nezávislé proměnné mezi krajními hodnotami x0 < x1. Hovoříme o intervalu [x0, x1]. Takové polynomiální příblížení po kouskách už bude mít tu vlastnost, že derivace na sebe budou navazovat. V praxi ale není pouhé navazování první derivace dostatečné (viz třeba koleje tramvají) a navíc při naměřených datech nemíváme hodnoty derivací k dispozici. Přímo se proto vnucuje pokus využívat pouze zadané hodnoty ve dvou sousedních bodech, ale požadovat zároveň rovnost prvních i druhých derivací u sousedních kousků polynomů třetího stupně! Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Kubický interpolační splajn Definition Nechť x0 < x1 < · · · < xn jsou reálné (nebo racionální) hodnoty, ve kterých jsou zadány požadované hodnoty y0, . . . , yn. Kubickým interpolačním splajnem pro toto zadání je funkce S : R → R (nebot S : Q → Q), která splňuje následující podmínky: zúžení S na interval [xi−1, xi ] je polynom Si třetího stupně, i = 1, . . . , n Si (xi−1) = yi−1 a Si (xi ) = yi pro všechny i = 1, . . . n, Si (xi ) = Si+1(xi ) pro všechny i = 1, . . . , n − 1, Si (xi ) = Si+1(xi ) pro všechny i = 1, . . . , n − 1. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Kubický splajn pro n + 1 bodů sestává z n kubických polynomů, tj. máme k dispozici 4n volných parametrů (první definiční podmínka). Další podmínky přitom zadávají 2n + (n − 1) + (n − 1) rovností, tj. dva parametry zůstávají volné. Při praktickém použití se dodávají předpisy pro derivace v krajních bodech, tzv. úplný splajn, nebo jsou tyto zadány jako nula, tzv. přirozený splajn. Výpočet celého splajnu už není bohužel tak jednoduchý jako u nezávislých výpočtů Hermiteových polynomů třetího stupně, protože data se prolínají vždy mezi sousedními intervaly. Při vhodném uspořádání se však dosáhne matice systému, která má nenulové prvky prakticky jen ve třech diagonálách, a pro takové existují vhodné numerické postupy, které umožní splajn počítat také v čase úměrném počtu bodů. Podrobnosti vynecháme, lze je dohledat např. v textu Horová-Zelinka. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny Pro srovnání se podívejme na interpolaci stejných dat jako v případě Lagrangeova polynomu, nyní pomocí splajnů: 0 -4 0 -0,5 2 -1 1 -2 4 x 0,5 0 -4 -0,5 x 2 -1 1 0 0,5 4-2