Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny ooo oooooooooo ooooooo ooooo Drsná matematika II - 1. přednáška Aproximace polynomy a splajny Martin Panák Masarykova univerzita Fakulta informatiky 18. 2. 2013 Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny 000 oooooooooo ooooooo ooooo Obsah před náš O Literatura Q Podmínky výuky Q Jak moc potřebujeme funkcí? Q Interpolace O De rivace O Splajny Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace S pl aj ny ooo oooooooooo ooooooo ooooo • 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 Kuběn, 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 S pl aj ny ooo oooooooooo ooooooo ooooo Povinnosti před ústní zkouškou: O Maximálně tři absence na cvičeních O Z pěti jednobodových a dvou desetibodových písemek v průběhu semestru získat alespoň 10 bodů. Q Zisk ze závěrečné 20 bodové v součtu s předchozím ziskem musí být alespoň 20 bodů Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny •oo oooooooooo ooooooo ooooo 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 o#o oooooooooo ooooooo ooooo 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 oo» oooooooooo ooooooo ooooo Budeme pracovat s funkcemi M —> M (reálné funkce reálné proměnné) nebo M —> 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.. . Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny OOO »000000000 ooooooo ooooo 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í zobrazení f : K —> K dané pro každé xěK: x 1-4- f(x) = anxn + an_ix"_1 H-----h a\x + a0, kde a,-, i = O,..., 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 ^ O, říkáme, že polynom f je stupně n. Stupeň nulového polynomu není definován. Skaláry a, označujeme jako koeficienty polynomu f. Polynomy stupně nula jsou konstantní nenulová zobrazení x i-> a^. Algebraicky jsou polynomy definovány jako formální výrazy f(x), tj. jako posloupnosti koeficientů 3q, ai,... 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 ooo o»oooooooo ooooooo ooooo 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 ooo oo»ooooooo ooooooo ooooo 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 neboje r = 0a f = q ■ g + r. Je-li pro nějaký prvek b G 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 ooo ooo»oooooo ooooooo ooooo • (Základní věta algebry) Každý polynom s koeficienty v C má kořen v C. • Ne každý polynom s reálnými koeficienty má kořen v M. • Pomocí Hornerova schématu umíme dělit polynom lineárním mnohočlenem (x — a) a při tom zjistíme hodnotu polynomu v bodě a. • Polynom stupně n je jednoznačně zadán svými hodnotami v (n + 1) bodech. • Máme-li zadáno (n + 1) dvojic (x,-, y), / = 0,..., n, pak pro každé m > n existuje nekonečně mnoho polynomů P stupně m takových, že P(xf) = y,-. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny ooo oooo»ooooo ooooooo ooooo Interpolační polynom Častá praktická úloha zní „zadejte formuli pro funkci, pro kterou máme zadány hodnoty v předem daných bodech xo,... ,x„". Pokud by šlo o nulové hodnoty, umíme přímo zadat polynom f(x) = (x - x0)(x - xi)... (x - x„), 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 ooo ooooo»oooo ooooooo ooooo Theorem Nechť K je nekonečné pole skalárů, pak pro každnou množinu po dvou různých bodů xq, ..., x„ G K a předepsaných hodnot yo > • • • > y n £ 1K 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že už víme, že existuje nejvýše jeden polynom stupně n s předepsanými n + 1 hodnotami yf- v různých bodech xo,..., x„, stačí sestrojit takový polynom. To ale není těžké, stačí pracovat s polynomy n#,-(* - xj) Hledaný polynom je f(x) = yo£o(x) + y\£i(x) + + y„e„{x). □ Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny ooo oooooo»ooo ooooooo ooooo 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ů a, aQ + x03i H-----h (x0)"an = yo 3q +xna1 H-----h (xn)"an = y„. 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,... ,x„) = det /l x0 (x0)2 1 X! (Xi)2 Vl >k=0 Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny ooo ooooooosoo ooooooo ooooo Příklad. Určete polynom í £ C[x] co nejmenšího stupně zadaný následujícími podmínkami: L(l) = 2, L{2) = 2, Z_(3) = 2. Řešení. L(x) = -\x2 + \x - 1. □ Příklad. Určete polynom í £ C[x] co nejmenšího stupně, zadaný následujícími podmínkami: L(i) = 1 + /', Z_(l) = /'. Řešení. L(x) = {-\ - |)x + \ + \i. □ Příklad. Určete polynom í £ C[x] zadaný následujícími podmínkami: L(i) = 1, L(l) = i, L(l + /) = 2. Řešení. -2/x2 + (-3 + 2/)x + / + 3. □ Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny OOO OOOOOOOO0O ooooooo ooooo Problémy interpolace Uvažujme reálné nebo případně racionální polynomy, tj. polynomiálně zadané funkce M. —> M. 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 x,-, 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 OOO OOOOOOOOO* ooooooo ooooo Nestabilitu vidíme na obrázcích, kde je proložena funkce sin(x) jedenácti body. 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 OOO OOOOOOOOOO »000000 ooooo 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 x; 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 G M pro reálný polynom f(x) dobře vyjadřují podíly f{x + Ax) - f(x) a protože umíme spočíst (nad libovolným okruhem) (x + Ax)k =xk + kx^Ax + ■■■ + ^x'{Ax)k-1 + ■■■ + (Ax)*, umíme i spočíst ten podíl pro f(x) = anxn + • • • + 3q. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny ooo oooooooooo o»ooooo ooooo f(x + Ax) - f(x) nx^Ax + • • • + (Ax)" Ax -= an--h • • • + 3i- Ax Ax Ax = nanxn^ + {n- l)an_ix"-2 + • • • + a1 + Ax(...), kde výraz v závorce je polynomiálně závislý na Ax. Evidentně pro hodnoty Ax velice blízké nule dostaneme hodnotu libovolně blízkou výrazu ?{x) = nanx"-1 + (n - l)a„_ixn-2 + • • • + au 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 ooo oooooooooo oo»oooo ooooo Z definice je jasné, že f'(xo) dává dobré přiblížení pro chování f(x) v okolí bodu X(j. Přesněji řečeno, přímka y = f'{xo){x ~ xo) + f{xo) velice dobře aproximuje přímky procházející body [xo, ^(xo)] a [xo + Ax, f(xo + Ax)] pro malé hodnoty Ax. 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 /c-násobném opakování polynom 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 OOO oooooooooo ooo»ooo ooooo Uvažme m + 1 po dvou různých xq, ... ,xm a předepišme hodnoty a derivace y-^ pro k = 0 a k = 1. Hledáme f(x) = anxn + ... 3q s těmito hodnotami a derivacemi. Opět obdržíme pro neznámé koeficienty a-, systém rovnic a0 + x03i H-----h (x0)"an = y^0) a0 +xmai H-----h (xm)"an 3i + 2x0a2 H-----h n(x0)"_1an ai + 2xma2 H-----h n(xm)"_1an = y^. 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. yi0) JÍ" Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny ooo oooooooooo oooo»oo ooooo Ú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'{xQ){x - x0) tj. právě rovnici přímky zadané hodnotou a směrnicí v bodě xo. Když zadáme hodnotu a derivaci ve dvou bodech, tj. yo = ^(xo), j/q = /^(xo), yi = ^(xi), y[ = f'(x{) pro dva různé body x,-, dostaneme ještě pořád snadno počítatelný problém. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny ooo oooooooooo ooooo^o ooooo Ukažme si jej v zjednodušeném provedení, kdy xo = 0, x\ = 1. Pak matice systému a její inverze budou / 2 -2 1 1 \ -3 3 -2 -1 0 0 10" V 1 0 0 OJ Přímým vynásobením A • (yo,yi, j/q,y'i)T pak vyjde vektor (33, 32, ai, ao)7" koeficientů polynomu f, tj. f{x) = (2yo-2yi+y^+yí)x3 + (-3y0 + 3yi-2y^-yí)x2+y^x+yo. Formuli lze snadno upravit pro libovolné body xo, x\ 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. /O 0 0 1\ 1111 0 0 10 \3 2 1 0/ 1-1 Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny OOO OOOOOOOOOO 000000» ooooo Příklad. Určete Hermiteův interpolační polynom H zadaný následujícími podmínkami: H(0) = 2, H(l) = 3, H'(0) = 1, H'(l) = O Řešení. H(x) = -x3 + x2 + x + 2 Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny ooo oooooooooo ooooooo »oooo 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 ooo oooooooooo ooooooo o»ooo 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 xo < x\. Hovoříme o intervalu [xo,xi]. Takové polynomiální přiblíž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 vlakové koleje - přechodnice, vzestupnice) 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 ooo oooooooooo ooooooo oo»oo Definition Nechť xo < xi < • • • < x„ jsou reálné (nebo racionální) hodnoty, ve kterých jsou zadány požadované hodnoty yo, • • • ,yn- Kubickým interpolačním splajnem pro toto zadání je funkce S : M —> M (nebot S : Q —> Q), která splňuje následující podmínky: • zúžení S na interval [x/_i,x,-] je polynom S/ třetího stupně, / = 1,..., n • S/(x,-_i) = y,-_i a S/(x,-) = y pro všechny i = 1,... n, 9 Sj(xj) = S-+1(x/) pro všechny / = 1,..., n — 1, » S(-'(x/) = S"+1(xí) pro všechny / = 1,..., n — 1. Literatura Podmínky výuky Jak moc potřebujeme funkcí? Interpolace Derivace Splajny ooo oooooooooo ooooooo ooo»o 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, nebojsou 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 ooo oooooooooo ooooooo oooo» Pro srovnání se podívejme na interpolaci stejných dat jako v případě Lagrangeova polynomu, nyní pomocí splajnů: