MB202 - Diferenciální a integrální počet B Aproximace polynomy a splajny MB202/01 1 / 29 Obsah přednášky Q Literatura 01 Jak moc potřebujeme funkcí? Q Interpolace 01 Derivace 01 Splajny Literatura Kde je dobré číst? • J. Slovák, M. Panák, M. Bulant a kolektiv Matematika drsně a svižně, Masarykova univerzita, Brno, 2013, Dostupné z http://goo.gl/KUbMCD. • I. Horová, J. Zelinka Numerické metody, MU Brno, 2. rozšířené vydání, 2004, 294 s., ISBN 80-210-3317-7. • Z. Došlá, J. Kuben Diferenciální počet funkcí jedné proměnné, MU Brno, 2003, 215 s., ISBN 80-210-3121-2. a K.F. Riley, M.P. Hobson, S.J. Bence Mathematical Methods for Physics and Engineering, second edition, Cambridge University Press, Cambridge 2004, 1232 s., ISBN 0521890675. MB202/01 4/29 Jak moc potřebujeme funkcí? jaké funkce potřebujeme pro naše modely? - pořádný zvěřinec... MB202/01 6/29 Jak moc potřebujeme funkcí? 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é. MB202/01 7/29 Interpolace Polynomy Polynomem nad okruhem skalárů K rozumíme zobrazení f : K —> K dané pro každé x G K výrazem x >->• f (x) = anxn + an_ix"_1 H-----h a\x + a0, kde a,-, / = 0,..., n, jsou pevně zadané skaláry, násobení je znázorněno prostým zřetězením symbolu 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 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ů ao,ai,... s konečně mnoha nenulovými prvky. MB202/01 9/29 Interpolace 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. MB202/01 10 / 29 Interpolace 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 jer = 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. □ MB202/01 11 / 29 Interpolace 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ů. MB202/01 12 / 29 Interpolace Theorem Necht 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,..., yn G K existuje právě jeden polynom f stupně nejvýše n (případně nulový polynom), pro který platí Důkaz. Protož 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 f{xi) = Yi, ' = 0,... n. £i(x) nMi(x-xj) Hledaný polynom je f(x) = yoA)(x) +yi^i(x) H-----hyAM- □ MB202/01 13 / 29 Interpolace 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)nan = 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,... ,x„) = det /l xo (x0)2 ... (x0)"\ 1 X! (Xi)2 ... (Xi)n \1 xn (x„)2 ... (x„)7 n-1 II {x;-Xk). i>k=0 Interpolace 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é. MB202/01 15 / 29 Interpolace 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. MB202/01 16 / 29 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-' + ■■■ + (Ax)*, umíme i spočíst ten podíl pro f(x) = anx" + • • • + 3q. MB202/01 18 / 29 f {x + Ax) - f {x) nx"-1 Ax + • • • + (Ax)" Ax -Äx--Äx-+ "-- + 3lÄx" = nanx"_1 + (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 f {x) = nanx"-1 + (n - l)a„_ixn-2 + • • • + au který nazýváme derivace polynomu f (x) podle proměnné x. MB202/01 19 / 29 Z definice je jasné, že f'(xo) dává dobré přiblížení pro chování f(x) v okolí bodu xq. 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 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. Hermiteův interpolační problém Uvažme m + 1 po dvou různých xq, ... ,xm a předepišme hodnoty a derivace y>k^ pro k = 0 a k = 1. Hledáme f(x) = a„x" + ... 3o s těmito hodnotami a derivacemi. Opět obdržíme pro neznámé koeficienty a-, systém rovnic a0 + x0ai H-----h (x0)"a„ = y^0) a0 + xmai H-----h (xm)"an = yi0) ai + 2x0a2 H-----h n(x0)"_1an = y^ ai + 2xma2 H-----h n(xm)n~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 itpíiw intprnnlařní nnlunnm MB202/01 21 / Ú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ě xq. 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. Ukažme si jej v zjednodušeném provedení, kdy xo systému a její inverze budou 0, xi = 1. Pak matice /O 0 0 1\ 1111 0 0 10 \3 2 1 Oj /2 -3 0 3 0 0 1 0 1 \ -1 0 o/ Přímým vynásobením A 1 • (yo,yi,Yq,yí)T pak vyjde vektor (33, 32, ai, 3o)T koeficientů polynomu f, tj. f(x) = (2y0 - 2yi + + y{)x3 + (-3y0 + 3yi - 2y^ - y{)x2 + y^x + y0. 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. 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í. MB202/01 25 / 29 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 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 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ě! MB202/01 26 / 29 Splajny Kubický interpolační splajn 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 (neboť 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ě, i = l,...,n • S/(x,-_i) = y,-_i a S/(x,-) = y pro všechny / = 1,... n, • Sj(xj) = S/+1(x,-) pro všechny / = 1,..., n — 1, • S(-'(x/) = S"+1(xí) pro všechny / = 1,..., n — 1. MB202/01 27 / 29 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, 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. MB202/01 28 / 29 Splajny Pro srovnání se podívejme na interpolaci stejných dat jako v případě Lagrangeova polynomu, nyní pomocí splajnů: MB202/01 29 / 29