Matematika II - 1. přednáška Polynomiální interpolace Michal Bulant Masarykova univerzita Fakulta informatiky 21. 9. 2011 Funkce jedné promě :nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO OOOO Qf Funkce jedné proměnné • Polynomy a interpolace Q| Derivace (zatím jen polynomů) Q Splajny 0 Aproximace 0 Reálná čísla Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo oooo oooo Doporučené zdroje • Martin Panák, Jan Slovák - Drsná matematika, e-text. • Roman Hilscher - MB102, e-text. Funkce jedné promě :nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO OOOO Doporuč* zd roje • 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 Kuběn - 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/download/skript.pdf). Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo oooo oooo Plán přednášky Q| Funkce jedné proměnné • Polynomy a interpolace Q Derivace (zatím jen polynomů) O Splajny Q Aproximace Q Reálná čísla Funkce jedné promě !nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla •ooooooo OOOOOOO oooo OOOO OOOO Touto kapitolou započneme budování nástrojů umožňujících modelování závislostí, které nejsou ani lineární ani diskrétní. S takovou potřebou se např. setkáme, kdykoliv popisujeme systém vyvíjející se v čase a to nejen v několika vybraných okamžicích ale „souvisle", tj. pro všechny možné okamžiky. Někdy je to přímo záměr či potřeba (třeba ve fyzikálních procesech), 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é Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla o»oooooo ooooooo oooo oooo oooo Polynomy Polynomem nad okruhem M rozumíme zobrazení f : M —> M dané pro každé x G M výrazem x >->• f (x) = anxn + an_ix"_1 H-----h a^x + a0, kde a,- G M, / = 0,..., n, jsou pevně zadaná čísla, tzv. koeficienty. Pokud je 3„ 0, říkáme, že polynom f je stupně n. Stupeň nulového polynomu není definován (někdy se klade roven —oo). Funkce jedné promě !nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oo»ooooo ooooooo oooo OOOO OOOO 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 M hodnota f (b) = 0, pak to znamená, že v podílu f (x) = q(x)(x — b) + r(x) 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 M 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é Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla ooo#oooo ooooooo oooo OOOO OOOO Lemma Dva polynomy f a g nad M jsou si rovny jako zobrazení, právě když mají shodné koeficienty. Funkce jedné promě nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla ooo#oooo ooooooo oooo OOOO OOOO Lemma Dva polynomy f a g nad M jsou si rovny jako zobrazení, právě když mají shodné koeficienty. Uvědomme si, že pro (obecněji definované) polynomy nad konečnými okruhy samozřejmě takové tvrzení neplatí. Uvažte např. polynom x2 +x nad Z2. Funkce jedné promě nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla ooo#oooo ooooooo OOOO OOOO OOOO Lemma Dva polynomy f a g nad M jsou si rovny jako zobrazení, právě když mají shodné koeficienty. Uvědomme si, že pro (obecněji definované) polynomy nad konečnými okruhy samozřejmě takové tvrzení neplatí. Uvažte např. polynom x2 +x nad Z2. Důkaz. 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é Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla 000*000 ooooooo oooo oooo oooo 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 xq, ... ,x„. Funkce jedné proměnné oooo»ooo Derivace (zatím jen polynomů) ooooooo Splajny OOOO Aproximace OOOO Reálná čísla OOOO 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 xq, ... ,xn. 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. Funkce jedné proměnné oooo»ooo Derivace (zatím jen polynomů) ooooooo Splajny OOOO Aproximace OOOO Reálná čísla OOOO 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 xq,. .. ,xn. 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, jak jsme dokázali před chvílí, nenulový polynom stupně n, nemá nikdy více než n nulových bodů. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla ooooo»oo OOOOOOO OOOO OOOO OOOO Lagrangeův interpolační polynom Věta Pro každou množinu různých bodů xq ,..., xn G M a předepsané hodnoty yo,..., y„ G M 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é Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla ooooo»oo ooooooo oooo oooo oooo Lagrangeův interpolační polynom Pro každou množinu různých bodů xq ,..., x„ G M a předepsané hodnoty yo,..., y„ G M 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 y 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) = yoA)(x) + yi^i(x) H-----h yn4(x)- □ Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooo^o ooooooo OOOO OOOO OOOO 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, a0 + x03i H-----h (xo)nan = y0 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í, tj. pokud je nenulový. V MB101 jsme dokázali, že pro tento tzv. Vandermondův determinant platí /l x0 (x0)2 1 X! (Xi)2 V(x0,... ,x„) = det . . \1 Xn {Xnf a je tedy skutečně nenulový. (*o)"\ {XnY) n (xi-xj)> ij=0,...,n 1 -O^O Funkce jedné proměnr OOOOOOO* ié Derivace (zatím jen polynomů) OOOOOOO Splajny OOOO Aproximace OOOO Reálná čísla OOOO Problémy interpolace 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 x/, protože se zde těmito rozdíly dělí. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla OOOOOOO* ooooooo oooo oooo oooo Problémy interpolace 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 x,-, protože se zde těmito rozdíly dělí. Přímé řešení soustav soustavy rovnic by vyžadovalo čas úměrný n3, což je často neefektivní. Funkce jedné proměnn OOOOOOO* é Derivace (zatím jen polynomů) OOOOOOO Splajny OOOO Aproximace OOOO Reálná čísla OOOO Problémy interpolace 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 x,-, protože se zde těmito rozdíly dělí. Přímé řešení soustav soustavy rovnic by vyžadovalo čas úměrný n3, což je často neefektivní. Ještě horším problémem je velice špatná stabilita hodnot reálných nebo racionálních polynomů při zvětšující se hodnotě proměnné x. Brzy budeme mít nástroje na přesný popis kvalitativního chování funkcí, nicméně i bez nich je zřejmé, že podle znaménka koeficientu u nejvyšší mocniny polynomu se hodnoty velice rychle při rostoucím x vydají bud' do plus nebo do mínus nekonečna (jde tedy o dost nevhodný nástroj pro extrapolaci). Ani toto znaménko koeficientu u nejvyššího stupně se ale u interpolačního polynomu při malých změnách prokládaných hodnot nechová stabilně. Funkce jedné promě :nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo OOOO OOOO OOOO 0 Funkce jedné proměnné • Polynomy a interpolace Q| Derivace (zatím jen polynomů) O Splajny Q Aproximace 0 Reálná čísla Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo •oooooo oooo OOOO OOOO 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 {xo,... ,x„} mohou chovat dosti divoce . 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 polynomy. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo •oooooo oooo OOOO OOOO 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 {xo,... ,x„} mohou chovat dosti divoce . 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 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 (dokonce nad libovolným okruhem) (x + Ax)k = xk + kx^Ax + ■■■+ ^x'{Ax)k-' + ■■■ + (Ax)*, umíme i spočíst zmiňovaný podíl pro f(x) = anxn + • • • + 3q. Funkce jedné promě :nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo o»ooooo OOOO OOOO OOOO f{x + Ax) - f(x) nx^Ax + ■■■ + (Ax)" Ax -= an--h • • • + 3i- Ax Ax Ax = nanx"_1 + (n - l)an_ix"-2 + • • • + a1 + Ax(...), kde výraz v závorce je polynomiálně závislý na Ax. Funkce jedné promě :nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo o»ooooo OOOO OOOO OOOO f(x + Ax) - f(x) nx^Ax + • • • + (Ax)" Ax -= an--h • • • + 3i- Ax Ax Ax = 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 ?{x) = nanx"-1 + (n - l)a„_ixn-2 + • • • + au který nazýváme derivace polynomu f(x) podle proměnné x. Funkce jedné promě :nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo oo»oooo OOOO OOOO OOOO Z definice je jasné, že f'(xo) dává dobré přiblížení pro chování f(x) v okolí bodu xo. 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. Funkce jedné promě ;nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo oo»oooo oooo OOOO OOOO 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 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. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooo»ooo oooo oooo oooo Hermiteův interpolační problém Uvažme opět m + 1 po dvou různých xq, ... ,xm a předepišme (k) hodnoty a derivace y- ' pro k = 0 a k = 1. Hledáme f(x) = anx" + ... 3q s těmito hodnotami a derivacemi. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooo»ooo OOOO OOOO OOOO Hermiteův interpolační problém Uvažme opět m + 1 po dvou různých xq, ... ,xm a předepišme (k) hodnoty a derivace y- ' pro k = 0 a k = 1. Hledáme f(x) = anx" + ... 3o s těmito hodnotami a derivacemi. Opět obdržíme pro neznámé koeficienty a-, systém rovnic a0 + x03i H-----h (xo)nan = y0 a0 + xmai H-----h (xm)"an = ym ai + 2x0a2 H-----h n(x0)n~1an = y'Q 3i + 2xm32 H-----h n(xm)"_13n = y'm. Při volbě n = 2m + 1 bude determinant tohoto systému rovnic nenulový. Opět lze také zkonstruovat takový polynom f přímo (viz skripta). Nazýváme jej Hermiteův interpolační polynom.< s > s Funkce jedné promě nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo oooo»oo OOOO OOOO OOOO Příklad Nalezněte polynom P splňující následující podmínky: P(1)=0, P'(l) = l, P(2) = 3, P'(2) Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo oooo»oo OOOO OOOO OOOO Příklad Nalezněte polynom P splňující následující podmínky: P(1)=0, P'(l) = l, P(2) = 3, P'(2) = 3. Máme m = 1 a hledáme polynom stupně n = 2m + 1 = 3, tj. P(x) = 33 x3 + 32 x2 + 3i x + 3(). Dosazením za x = 1 a x = 2 do výrazu pro P(x) a P'(x) dostaneme systém P(l) = 33 + 32 + 31 + 30 = 0, P(2) = 8s3 + 4s2 + 231 + a0 = 3, P'(l) = 333 + 232 + 31 = 1, P'(2) = 1233 + 432 + 31 = 3. Vyřešením tohoto systému dostaneme P(x) = -2x3 + 10x2 - 13x + 5. Funkce jedné promě ;nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooo»o OOOO OOOO OOOO Ú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. Funkce jedné promě ;nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooo»o OOOO OOOO OOOO Ú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 = f'(xo), yi = ^(xi), y[ = f'{x{) pro dva různé body x,-, dostaneme ještě pořád poměrně snadno řešitelný problém. Funkce jedné proměnné oooooooo Derivace (zatím oooooo* en polynomů) Splajny OOOO Aproximace OOOO Reálná čísla OOOO Ukažme si jej v zjednodušeném provedení, kdy xq = 0, xi = = 1. Pak matice systému a její inverze budou /o 0 0 1^ / 2 -2 1 1 ^ 1111 a-1 — -3 3 - -2 -1 m — 0 0 10 , a — 0 0 1 0 \3 2 1 O/1 0 0 ) Přímým vynásobením A ■ (yo,yi, j/q,y'i)T pak vyje e vektor (33, 32, 3i, ao)7" koeficientů polynomu ŕ, tj. f (x) = (2y0 - 2yi +y'Q +y[ )x3 + (-3y0 + 3yi - 2y^ - -y[)x2+yóx+yo- Funkce jedné proměnné oooooooo Derivace (zatím oooooo* en polynomů) Splajny OOOO Aproximace OOOO Reálná čísla OOOO Ukažme si jej v zjednodušeném provedení, kdy xq = 0, xi = = 1. Pak matice systému a její inverze budou /o 0 0 1^ / 2 -2 1 1 ^ 1111 a-1 — -3 3 - -2 -1 m — 0 0 10 , a — 0 0 1 0 \3 2 1 O/1 0 0 ) Přímým vynásobením A ■ (yo,yi, j/q,y'i)T pak vyje e vektor (33, 32, 3i, ao)7" koeficientů polynomu ŕ, tj. f (x) = (2y0 - 2yi +y'Q +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. Funkce jedné proměnné oooooooo Derivace (zatím 000000» en polynomů) Splajny OOOO Aproximace OOOO Reálná čísla OOOO Ukažme si jej v zjednodušeném provedení, kdy xq = 0, xi = = 1. Pak matice systému a její inverze budou /o 0 0 1^ / 2 -2 1 1 ^ 1111 a-1 — -3 3 - -2 -1 m — 0 0 10 , a — 0 0 1 0 \3 2 1 0^ 0 0 J Přímým vynásobením A ■ (yo,yi, j/q,y'i)T pak vyje e vektor (33, 32, 3i, ao)7" koeficientů polynomu ŕ, tj. f (x) = (2y0 - 2yi +y'Q +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. Funkce jedné promě ;nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo OOOO OOOO OOOO 0 Funkce jedné proměnné • Polynomy a interpolace Q Derivace (zatím jen polynomů) Q Splajny Q Aproximace 0 Reálná čísla Funkce jedné promě ;nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo •ooo oooo OOOO 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é Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo •ooo oooo OOOO 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é Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo •ooo oooo OOOO 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é Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo o»oo oooo OOOO 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. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo o»oo oooo OOOO 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ě! Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oo»o oooo oooo 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 (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. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo ooo« oooo OOOO 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) nebojsou druhé derivace zadány jako nula (tzv. přirozený splajn). Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo ooo« oooo OOOO 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) nebojsou 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íhnou k počítačové grafice, se s tímto pojmem určitě ještě setkají (viz též B-spline, Bézierova křivka). Funkce jedné proměnné Derivace (zatím jen polynomů) Spk-ijny Aproximace Reálná čísla oooooooo ooooooo OOOO OOOO OOOO Plán přednášky Ql Funkce jedné proměnné • Polynomy a interpolace Q Derivace (zatím jen polynomů) 0 Splajny Q Aproximace Q Reálná čísla Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla OOOOOOOO OOOOOOO OOOO »000 OOOO 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é Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla ooooooo oooo o»oo oooo nší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 xi,... ,x„ mají nejmenší součet druhých mocnin vzdáleností od zadaných hodnot yi,..., y„. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla ooooooo oooo o»oo oooo nší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 xi,... ,x„ mají nejmenší součet druhých mocnin vzdáleností od zadaných hodnot yi,..., y„. 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ů ([xi,yi],..., [x„,yn\) a hledáme přímku, která nejlépe vystihuje rozložení těchto bodů. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo OOOO oo»o OOOO Hledáme tedy funkci tvaru f(x) = a ■ x + b s neznámými a, b G M tak, aby hodnota n byla minimální. 4Ľ3k4l3*4 = k4 = * -š -O^O Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo oo»o OOOO Hledáme tedy funkci tvaru f(x) = a ■ x + b s neznámými a, b G M tak, aby hodnota n byla minimální. S pomocí odhadu 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 x\,..., xn od hodnot y, funkce splňující aJ2xi + bJ2Xi = Hx''^ a ^ x; + b ■ n = ^ y; 00.O Funkce jedné promě nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo OOOO ooo» OOOO Příklad Metodou nejmenších čtverců určete regresní přímku odpovídající naměřeným datům: x i 2 3 4 y 1.5 1.6 2.1 3.0 Funkce jedné promě nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo ooo» OOOO Příklad Metodou nejmenších čtverců určete regresní přímku odpovídající naměřeným datům: X i 2 3 4 y 1.5 1.6 2.1 3.0 Řešení Data je vhodné seřadit v tabulce podle schématu: X y xy x2 1 1.5 1.5 1 2 1.6 3.2 4 3 2.1 6.3 9 4 3 12 16 10 8.2 23 30 Funkce jedné promě nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo ooo» OOOO Příklad Metodou nejmenších čtverců určete regresní přímku odpovídající naměřeným datům: X i 2 3 4 y 1.5 1.6 2.1 3.0 Řešení Data je vhodné seřadit v tabulce podle schématu: X y xy x2 1 1.5 1.5 1 2 1.6 3.2 4 3 2.1 6.3 9 4 3 12 16 10 8.2 23 30 Dostáváme rovnice 30a + 10b = 23,10a + 4b = 8,2, odkud a = 0,5, b = 0,8. Funkce jedné promě ;nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo OOOO OOOO OOOO 0 Funkce jedné proměnné • Polynomy a interpolace Ql Derivace (zatím jen polynomů) O Splajny Q Aproximace 0 Reálná čísla Funkce jedné promě ;nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo OOOO OOOO •ooo Reálná čísla zavedeme v podstatě intuitivně jako obrazy bodů na přímce, kde vyznačíme bod 0 označující počátek a rozhodneme o kladném směru (doprava). Značíme M. Matematicky lze reálná čísla zavést pomocí axiomů. Funkce jedné promě :nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO •OOO Reálná čísla zavedeme v podstatě intuitivně jako obrazy bodů na přímce, kde vyznačíme bod 0 označující počátek a rozhodneme o kladném směru (doprava). Značíme M. Matematicky lze reálná čísla zavést pomocí axiomů. Připomeňme si nyní vlastnosti (axiomy) reálných čísel včetně souvislostí uspořádání a ostatních relací. Dělící čáry v tabulce naznačují, jak axiomy postupně zaručují, že jsou reálná čísla komutativní grupou vůči sčítání, že M \ {0} je komutativní grupa vůči násobení, M je pole, množina M spolu s operacemi +, • a s relací uspořádání je tzv. uspořádané těleso (pole) a konečně poslednímu axiomu můžeme rozumět tak, že M je dostatečně husté, tj. nechybí nám tam body, jako např. druhá odmocnina ze dvou v číslech racionálních. Funkce jedné promě nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO o»oo (Rl) (a + b) + c = a + (b + c), pro všechny a, b, c G R (R2) a + fa = b + a, pro všechny a, b eR (R3) existuje 0 G M takový, že pro všechny a G M platí a + 0 = a (R4) pro všechny a G M existuje opačný prvek (—a) G R takový, že platí a + (—a) = 0 (R5) (a • b) ■ c = a ■ (b • c), pro všechny a, b, c G M (R6) a ■ b = b ■ a pro všechny a, Ď G R (R7) existuje 1 G M takový, že pro všechny a G M platí 1 • a = a (R8) pro každý a G R, a ^ 0 existuje inverzní prvek a-1 G R takový, že platí a • a-1 = 1 (R9) a • (b + c) = a • b + a • c, pro všechny a, b, c G M (RIO) relace < je úplné uspořádání, tj. reflexivní, antisymetrická, tranzitivní a úplná relace na R (Rll) pro a, b, c G R platí, že z a < b vyplývá a + c < b + c (R12) pro všechny a, Ď G R, a > 0, b > 0, platí také a • Ď > 0 (R13) každá neprázdná ohraničená množina A c M má supremum. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná oooooooo ooooooo OOOO OOOO oo»o Pojem suprema má smysl pro každou uspořádanou množinu, my se zde omezíme na reálná čísla. Funkce jedné promě :nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO oo»o BgBBEfflmílaimll^^^^M Pojem suprema má smysl pro každou uspořádanou množinu, my se zde omezíme na reálná čísla. Nechť je dána neprázdná množina ACK. Prvek b G M nazveme horní závorou množiny A, pokud Vx G A : x < b, tj. pokud je prvek b větší (nebo roven) než všechny prvky v množině A. Obdobně se definuje dolní závora množiny A, tj. je to prvek a G M s vlastností, že a < x pro všechny x £ A Funkce jedné promě ;nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO oo»o Pojem suprema má smysl pro každou uspořádanou množinu, my se zde omezíme na reálná čísla. Nechť je dána neprázdná množina ACK. Prvek b G M nazveme horní závorou množiny A, pokud Vx G A : x < b, tj. pokud je prvek b větší (nebo roven) než všechny prvky v množině A. Obdobně se definuje dolní závora množiny A, tj. je to prvek a G M s vlastností, že a < x pro všechny x G A Řekneme, že množina A je shora ohraničená (shora omezená), pokud má A alespoň jednu horní závoru. Podobně se definuje zdola ohraničená (zdola omezená) množina A. Množina A je ohraničená (omezená), pokud je A současně zdola i shora ohraničená. Viz příklady reálných intervalů. Funkce jedné promě ;nné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO oo»o Pojem suprema má smysl pro každou uspořádanou množinu, my se zde omezíme na reálná čísla. Nechť je dána neprázdná množina ACK. Prvek b G M nazveme horní závorou množiny A, pokud Vx G A : x < b, tj. pokud je prvek b větší (nebo roven) než všechny prvky v množině A. Obdobně se definuje dolní závora množiny A, tj. je to prvek a G M s vlastností, že a < x pro všechny x G A Řekneme, že množina A je shora ohraničená (shora omezená), pokud má A alespoň jednu horní závoru. Podobně se definuje zdola ohraničená (zdola omezená) množina A. Množina A je ohraničená (omezená), pokud je A současně zdola i shora ohraničená. Viz příklady reálných intervalů. Nej menší horní závora množiny A se nazývá supremum množiny A. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO 0009 Tj. prvek b £ M. je supremum množiny A, pokud jsou splněny následující dvě podmínky: • V x G A : x < b (tj. b je horní závora množiny A), • je-li y G M horní závora množiny A, potom je b < y (tj. b je nejmenší horní závora). Supremum množiny A značíme jako b = sup A. Obdobně se definuje infimum množiny A, neboli je to největší dolní závora množiny A, značíme a = inf A. Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO 0009 Tj. prvek b £ M. je supremum množiny A, pokud jsou splněny následující dvě podmínky: • V x G A : x < b (tj. b je horní závora množiny A), • je-li y G M horní závora množiny A, potom je b < y (tj. b je nejmenší horní závora). Supremum množiny A značíme jako b = sup A. Obdobně se definuje infimum množiny A, neboli je to největší dolní závora množiny A, značíme a = inf A. Příklad Je-li A libovolný z intervalů (0,1), [0,1], [0,1) nebo (0,1], potom je vždy sup^ = l a inf/A = 0. Má-li množina A největší (resp. nejmenší) prvek b, potom je b = sup/4 (resp. b = inf A). Funkce jedné proměnné Derivace (zatím jen polynomů) Splajny Aproximace Reálná čísla oooooooo ooooooo oooo OOOO 0009 Tj. prvek b £ M. je supremum množiny A, pokud jsou splněny následující dvě podmínky: • V x G A : x < b (tj. b je horní závora množiny A), • je-li y G M horní závora množiny A, potom je b < y (tj. b je nejmenší horní závora). Supremum množiny A značíme jako b = sup A. Obdobně se definuje infimum množiny A, neboli je to největší dolní závora množiny A, značíme a = inf A. Příklad Je-li A libovolný z intervalů (0,1), [0,1], [0,1) nebo (0,1], potom je vždy sup^ = l a inf/A = 0. Má-li množina A největší (resp. nejmenší) prvek b, potom je b = sup A (resp. b = inf A). Zatímco největší či nejmenší prvek nemusí v A existovat, i když je množina A ohraničená, supremum a infimum existují (v ohraničeném případě) vždy (jak je vidět z výše uvedeného axiomu R13).