Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Matematika II ­ 1. přednáška Polynomiální interpolace, splajny Michal Bulant Masarykova univerzita Fakulta informatiky 17. 9. 2008 Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Obsah přednášky 1 Funkce jedné proměnné 2 Interpolace 3 Derivace (zatím jen polynomů) 4 Splajny 5 Aproximace Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Doporučené zdroje Martin Panák, Jan Slovák ­ Drsná matematika, e-text. Roman Hilscher ­ MB102, e-text. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Doporučené zdroje Martin Panák, Jan Slovák ­ Drsná matematika, e-text. Roman Hilscher ­ MB102, e-text. 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 (rovněž na http://www.math.muni.cz/~dosla/skript.pdf). Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Plán přednášky 1 Funkce jedné proměnné 2 Interpolace 3 Derivace (zatím jen polynomů) 4 Splajny 5 Aproximace Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace V tomto semestru budeme budovat nástroje pro modelování závislostí, které nejsou ani lineární ani diskrétní. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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 vzhledem k faktickému stavu zkoumaného problému (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ů). Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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é. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Plán přednášky 1 Funkce jedné proměnné 2 Interpolace 3 Derivace (zatím jen polynomů) 4 Splajny 5 Aproximace Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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 symbol + označuje sčítání. Pokud je an = 0, říkáme, že polynom f je stupně n. Stupeň nulového polynomu není definován (někdy se klade roven - = ). Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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 symbol + označuje sčítání. Pokud je an = 0, říkáme, že polynom f je stupně n. Stupeň nulového polynomu není definován (někdy se klade roven - = ). 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í? Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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! Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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 . Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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í: Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Interpolační polynom Častá praktická úloha zní zadejte formuli pro funkci, pro kterou máme zadány hodnoty v předem daných daných bodech x0, . . . , xn. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Interpolační polynom Častá praktická úloha zní zadejte formuli pro funkci, pro kterou máme zadány hodnoty v předem daných 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Interpolační polynom Častá praktická úloha zní zadejte formuli pro funkci, pro kterou máme zadány hodnoty v předem daných 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ů. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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). Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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). Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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 citlivé 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é. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Plán přednášky 1 Funkce jedné proměnné 2 Interpolace 3 Derivace (zatím jen polynomů) 4 Splajny 5 Aproximace Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Hodnoty polynomů s rostoucí proměnnou rychle míří k nekonečným hodnotám a navíc se uvnitř intervalu daného největší a nejmenší hodnotu z množiny {x0, . . . , xn} mohou chovat dosti divoce . 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Hodnoty polynomů s rostoucí proměnnou rychle míří k nekonečným hodnotám a navíc se uvnitř intervalu daného největší a nejmenší hodnotu z množiny {x0, . . . , xn} mohou chovat dosti divoce . 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 zmiňovaný podíl pro f (x) = anxn + + a0. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace f (x + x) - f (x) x = an nxn-1x + + (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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace f (x + x) - f (x) x = an nxn-1x + + (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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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 = y0 ... a0 + xma1 + + (xm)n an = ym a1 + 2x0a2 + + n(x0)n-1 an = y0 ... a1 + 2xma2 + + n(xm)n-1 an = ym. 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Ú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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Ú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 poměrně snadno řešitelný problém. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Plán přednášky 1 Funkce jedné proměnné 2 Interpolace 3 Derivace (zatím jen polynomů) 4 Splajny 5 Aproximace Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace I u polynomiálních 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace I u polynomiálních 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. Nabízí se tedy využití malých polynomiálních kousků, které ale musíme umět rozumně navazovat. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace I u polynomiálních 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. 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í. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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ě! Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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 první derivace v krajních bodech (tzv. úplný splajn) nebo jsou druhé derivace zadány jako nula (tzv. přirozený splajn). Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace 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 první derivace v krajních bodech (tzv. úplný splajn) nebo jsou druhé derivace 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. Výpočty splajnů jsou však základem takřka všech grafických balíčků pracujících s křivkami, proto je pochopení principu jejich fungování velmi důležité. Ti z vás, kteří tíhnout k počítačové grafice, se s tímto pojmem určitě ještě setkají. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Plán přednášky 1 Funkce jedné proměnné 2 Interpolace 3 Derivace (zatím jen polynomů) 4 Splajny 5 Aproximace Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Aproximace je narozdíl od interpolace postup, který bere ohled na to, že pracujeme s potenciálně nepřesnými vstupními daty, a nesnaží se proto trefit přesně do zadaných bodů, ale výstupem je funkce, která má ze zadané třídy funkcí (ve vhodném smyslu) nejmenší vzdálenost od zadaných bodů. Častým případem je rovněž situace, kdy řešíme tzv. přeurčenou soustavu rovnic, tj. máme více rovnic než neznámých (např. z výše uvedených důvodů nechceme aproximovat n + 1 daných bodů hodnotami polynomu stupně n ale stupně nižšího). Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Metoda nejmenších čtverců Metoda nejmenších čtverců je založena na tom, že hledáme funkci z dané množiny (např. lineární polynomy, kvadratické polynomy, polynomy stupně nejvýše n, ale i mnohé jiné funkce v závislosti na zvoleném modelu), jejíž hodnoty v daných bodech x1, . . . , xn mají nejmenší součet druhých mocnin vzdáleností od zadaných hodnot y1, . . . , yn. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Metoda nejmenších čtverců Metoda nejmenších čtverců je založena na tom, že hledáme funkci z dané množiny (např. lineární polynomy, kvadratické polynomy, polynomy stupně nejvýše n, ale i mnohé jiné funkce v závislosti na zvoleném modelu), jejíž hodnoty v daných bodech x1, . . . , xn mají nejmenší součet druhých mocnin vzdáleností od zadaných hodnot y1, . . . , yn. Tato metoda se velmi často objevuje ve zejména ve statistice (regresní analýza). Ukažme si použití této metody v nejjednodušším případě, kdy máme dáno n bodů ([x1, y1], . . . , [xn, yn]) a hledáme přímku, která nejlépe vystihuje rozložení těchto bodů. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Hledáme tedy funkci tvaru f (x) = a x + b s neznámými a, b R tak, aby hodnota n i=1 (f (xi ) - yi )2 byla minimální. Funkce jedné proměnné Interpolace Derivace (zatím jen polynomů) Splajny Aproximace Hledáme tedy funkci tvaru f (x) = a x + b s neznámými a, b R tak, aby hodnota n i=1 (f (xi ) - yi )2 byla minimální. S pomocí odhadů nebo základních metod diferenciálního počtu (toho budeme schopni za několik týdnů) lze snadno odvodit následující tvrzení. Věta Mezi přímkami tvaru f (x) = a x + b má nejmenší součet čtverců vzdáleností funkčních hodnot v bodech x1, . . . , xn od hodnot yi funkce splňující a x2 i + b xi = xi yi a xi + b n = yi