Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Drsná matematika II – 10. přednáška Aproximace funkcí, Fourierovy řady Jan Slovák Masarykova univerzita 25. 4. 2012 Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Obsah přednášky 1 Literatura 2 Vzdálenost funkcí 3 Ortogonální systémy 4 Fourierovy řady 5 Wavelety Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Kde je dobré číst? vlastní poznámky, texty současného nebo předcházejícího přednášejícího, GOOGLE, atd. 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 Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Pro pevný interval I = [a, b], konečný nebo nekonečný, definujeme kvadrát vzdálenosti funkcí na I takto: f − g 2 = b a |f (x) − g(x)|2 dx. Samozřejmě je třeba předpokládat, že tento Riemannův integrál existuje. Velikost f funkce f je pak její vzdálenost od funkce nulové, tj. f 2 = b a |f (x)|2 dx. Funguje dobře pro množinu S = S[a, b] omezených a po částech spojitých reálných funkcí na I. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Viděli jsme, že S je vektorový prostor a snadno se ověří, že námi právě uvažovaná velikost je odvozena z dobře definovaného skalárního součinu, tj. symetrického bilineárního zobrazení f , g = b a f (x)g(x) dx, s příslušnými vlastnostmi. V konečněrozměrném případě jsme takto definovali velikost vektorů. Nyní je to naprosto stejné a pokud zúžíme naši definici na vektorový prostor generovaný nad reálnými čísly jen konečně mnoha funkcemi f1, . . . , fk, dostaneme opět dobře definovaný skalární součin na tomto konečněrozměrném vektorovém podprostoru. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Máme-li generátory gi s vlastností gi , gj = 0 pro i = j 1 pro i = j hovoříme o tzv. ortonormální bázi (pracujeme také s ortogonálními). Grammova–Schmidtova ortogonalizace vytvoří z libovolného spočetného systému generátorů fi nové ortogonální generátory gi téhož prostoru, tj. gi , gj = 0 pro všechny i = j. Spočteme je postupně: g1 = f1 a formulemi g +1 = f +1 + a1g1 + · · · + a g , ai = − f +1, gi gi 2 pro > 1. Příkladem jsou např. ortogonální polynomy. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Připomeňme si výhody, které ortonormální báze podprostorů měly pro konečněrozměrné vektorové prostory. Můžeme pokračovat v příkladu Legendreových polynomů h1, h2 a h3, které generují R2[x] a uvažovat třeba V = R∞[x] jakožto funkce na intervalu [0, 1]. Pro libovolný polynom h ∈ V bude funkce H = h, h1 h1 + h, h2 h2 + h, h3 h3 jednoznačně určenou funkcí, která minimalizuje vzdálenost h − H mezi všemi funkcemi v R2[x]. Koeficienty pro nejlepší aproximaci zadané funkce pomocí funkce z vybraného podprostoru je možné tedy získat prostě integrací. Stejně tak ale tato formule zadá nejlepší aproximaci polynomem nejvýše druhého stupně pro libovolnou funkci h ∈ S[a, b] ve smyslu naší vzdálenosti funkcí na tomto prostoru. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Poslední příklad podbízí zobecnění – co se stane, když zvolíme úplně libovolný spočetný systém lineárně nezávislých funkcí v S takový, že každé dvě různé z nich mají nulový skalární součin? Takovému systému funkcí na intervalu I říkáme ortogonální systém funkcí. Jestliže jsou všechny funkce fn v posloupnosti po dvou ortogonální a zároveň je pro všechna n velikost fn = 1 normovaná, hovoříme o ortonormálním systému funkcí. Nechť tedy tvoří posloupnost funcí fn ortogonální systém po částech spojitých funkcí na intervalu I = [a, b] a předpokládejme, že pro konstanty cn konverguje řada F(x) = ∞ n=1 cnfn stejnoměrně na I. Pak snadno vyjádříme skalární součin F, fn po jednotlivých sčítancích: F, fn = ∞ m=1 cm b a fm(x)fn(x) dx = cn fn 2 . Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Máme tedy tušení, v jakou přibližně odpověď je možné doufat, a docela přehledně nám ji skutečně dává následující věta: Theorem Nechť fn, n = 1, 2, . . . , je ortogonální posloupnost funkcí Riemannovsky integrovatelných na I = [a, b] a nechť g je libovolná funkce Riemannovsky integrovatelná v kvadrátu na I. Označme cn = fn −2 b a fn(x)g(x) dx. (1) Pro libovolné pevné n ∈ N má ze všech lineárních kombinací funkcí f1, . . . , fn nejmenší vzdálenost od g výraz hn = n i=1 ci fi (x). Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Theorem (pokračování) (2) Řada čísel ∞ n=1 c2 n fn 2 vždy konverguje a platí ∞ n=1 c2 n fn 2 ≤ g 2 . (3) Vzdálenost g od částečných součtů sk = k n=1 cnfn jde v limitě k nule, tj. lim k→∞ g − sk 2 = 0, tehdy a jen tehdy, když ∞ n=1 c2 n fn 2 = g 2 . Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Ještě než se pustíme do důkazu, zkusíme lépe porozumět významu jednotlivých tvrzení této věty. Náš ortogonální systém funcí je libovolný, nemůžeme očekávat, že lze dobře aproximovat jakoukoliv funkci pomocí lineárních kombinací funkcí fi . Např. když se omezíme u ortogonálních polynomů pouze na sudé stupně, určitě budeme dobře aproximovat pouze sudé funkce. Nicméně hned první tvrzení nám říká, že vždycky budeme dosahovat nejlepší možné aproximace částečnými součty. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Druhé a třetí tvrzení pak můžeme vnímat jako analogii ke kolmým průmětům do podprostorů vyjádřených pomocí souřadnic. Skutečně vidíme, že pokud pro naši funkci g bodově konverguje řada F(x) = ∞ n=1 cnfn(x), pak je funkce F(x) kolmým průmětem g do vektorového podprostoru všech takovýchto řad. Zároveň ale naše věta neříká, že by částečné součty uvažované řady musely bodově konvergovat k nějaké funkci. Tj. řada F(x) nemusí být obecně konvergentní ani v případě, kdy nastane rovnost v (3). Pokud ale např. existuje konečná hodnota ∞ n=1 |ci | a všechny funkce fn jsou stejnoměrně omezené na I, pak zřejmě řada F(x) konverguje v každém x. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Důkaz věty: Zvolme libovolnou lineární kombinaci f = k n=1 anfn a spočtěme její vzdálenost od g. Dostáváme g − k n=1 anfn 2 = g 2 + k n=1 fn 2 ((cn − an)2 − c2 n ). Evidentně lze poslední výraz minimalizovat právě volbou an = cn a tím je první tvrzení dokázáno. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Dosazením minimalizující volby dostáváme tzv. Besselovu identitu g − k n=1 cnfn 2 = g 2 − k n=1 c2 n fn 2 , ze které okamžitě díky nezápornosti levé strany vyplývá tzv. Besselova nerovnost k n=1 c2 n fn 2 ≤ g 2 . Tím je dokázáno druhé tvrzení, protože každá neklesající a shora omezená posloupnost reálných čísel má limitu (a je jí supremum celé množiny hodnot prvků posloupnosti). Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Jestliže v Besselově nerovnosti nastane rovnost, hovoříme o tzv. Parsevalově rovnosti. Přímo z definic vyplývá nyní tvrzení (3): (3) Vzdálenost g od částečných součtů sk = k n=1 cnfn jde v limitě k nule, tj. lim k→∞ g − sk 2 = 0, tehdy a jen tehdy, když ∞ n=1 c2 n fn 2 = g 2 . Ortonogonální systém funkcí nazveme úplný ortogonální systém na intervalu I = [a, b], jetliže platí Parsevalova rovnost pro každou funkci g s konečnou velikostí g na tomto intervalu. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Předchozí věta naznačuje, že umíme se spočetnými ortogonálními systémy fn funkcí pracovat velice podobně jako s konečnými ortogonálními bazemi vektorových prostorů, jsou tu ale zásadní rozdíly: Není snadné říci, jak vypadá celý prostor konvergentních nebo stejnoměrně konvergentních řad F(x) = ∞ n=1 cnfn. Pro danou integrovatelnou funkci umíme najít jen nejlepší možné přiblížení takovou řadou F(x). V případě, že místo ortonogonálního systému fn máme systém ortonormální, jsou formulky ve větě o něco jednodušší, žádné další zlepšení ale nenastane. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Jako pěkný příklad na integrování lze elementárními metodami ověřit, že systém funkcí 1, sin x, cos x, sin 2x, cos 2x, . . . , sin nx, cos nx, . . . je ortogonální systém na intervalu [−π, π] (a také na kterémkoliv jiném intervalu o délce 2π). Řady z předchozí věty odpovídající tomuto systému nazýváme Fourierovy řady. I v obecném případě diskutovaném výše se někdy hovoří o obecných Fourierových řadách vzhledem k ortogonálnímu systému funkcí fn. Koeficienty cn se pak nazývají Fourierovy koeficienty funkce f . Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Na intervalu [−π, π] jsou velikosti všech funkcí kromě první vždy √ π, první má velikost √ 2π. Lze dokázat, že náš systém funkcí je úplným ortogonálním systémem, nebudeme to zde ale dokazovat. Ve smyslu vzdálenosti funkcí definované pomocí našeho skalárního součinu proto budou částečné součty Fourierovy řady F(x) pro libovolnou funkci g(x) s konečným integrálem b a g(x)2 dx, tj. F(x) = a0 2 + ∞ n=1 (an cos(nx) + bn sin(nx)) s koeficienty an = 1 π π −π g(x) cos(nx) dx, bn = 1 π π −π g(x) sin(nx) dx, vždy konvergovat k funkci g(x). Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Z obecnějších úvah lze dovodit, že z konvergence v tomto smyslu vždy vyplývá bodová konvergence částečných součtů ve skoro všech bodech x ∈ I. Nebudeme zde ale ani vysvětlovat, co znamená „skoro všechny“, ani nebudeme takový výsledek dokazovat. Jako příklad uveďme Fourierovu řadu pro periodickou funkci vzniklou zúžením Heavisideovy funkce na jednu periodu. Tj. naše funkce g bude na intervalu [−π, 0] rovna −1 a na intervalu [0, π] bude rovna 1. Protože jde o funkci lichou, jistě budou všechny koeficienty u funkcí cos(nx) nulové, a pro coeficienty u funkcí sin(nx) spočteme bn = 1 π π −π g(x) sin(nx) dx = 2 π π 0 sin(nx) dx = 2 nπ (1 − (−1)n ). Výsledná Fourierova řada je tedy tvaru g(x) = 4 π sin(x) + 1 3 sin(3x) + 1 5 sin(5x) + . . . a součet jejích prvních pěti a prvních padesáti členů je na následujících dvou obrázcích. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Všimněme si, že se zvyšujícím se počtem členů řady se výrazně spřesňuje aproximace s výjimkou stále se zmenšujícího okolí bodu nespojitosti, na němž je ale maximum odchylky stále zhruba stejné. Je to obecná vlastnost Fourierových řad, které se říká Gibbsův jev. -1 0 2 x 0 -2 -0,5 0,5 -4 1 4 t=2. -1 0 2 x 4-2 -0,5 0 -4 1 0,5 t=24. Povšimněme si také, že v samotném bodě nespojitosti je hodnota aproximující funkce právě v polovině mezi limitami zprava a zleva pro Heavisideovu funkci. Nelze očekávat, že by konvergence pro funkce s body nespojitosti mohla být stejnoměrná (to by totiž g musela být coby stejnoměrná limita spojitých funkcí sama spojitá!). Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Bez podrobného důkazu si uvedeme následující větu podávající ucelený obrázek o bodové konvergenci Fourierových řad. Nejde o nutné podmínky konvergence a v literatuře lze najít řadu jiných formulací. Tato je ale jednoduchá a postihuje velké množství užitečných případů. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Theorem Nechť g je po částech spojitá a monotonní na intervalu [−π, π]. Pak její Fourierova řada F(x) konverguje na [−π, π] a součet je roven hodnotě g(x0) v každém bodě x0 ∈ [−π, π], ve kterém je funkce g(x) spojitá, v každém bodě nespojitosti x0 funkce g(x) roven 1 2 lim x→x+ 0 g(x) + lim x→x− 0 g(x) , v krajních bodech intervalu [−π, π] je roven 1 2 lim x→−π+ g(x) + lim x→π− g(x) . Pokud navíc je g(x) spojitá, periodická s periodou 2π a všude existuje její po částech spojitá derivace, pak konverguje její Fourierova řada F(x) stejnoměrně. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Fourierovy řady a další z nich vycházející nástroje jsou využívány ke zpracování různých signálů, obrázků apod. Povaha použitých periodických goniometrických funkcí a jejich prosté škálování pomocí zvětšující se frekvence zároveň omezují jejich použitelnost. V mnoha oborech proto vyvstala přirozená potřeba nalézt šikovnější úplné ortogonální systémy funkcí, které budou vycházet z předpokládané povahy dat a které bude možné efektivněji zpracovávat. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Takový systém se lze například vytvořit volbou vhodné spojité funkce ψ s kompaktním nosičem, ze které sestrojíme spočetně mnoho funkcí ψij , j, k ∈ Z, pomocí dyadických translací a dilatací: ψjk(x) = 2j/2 ψ(2j x − k). Pokud tvar mateřské funkce ψ dobře vystihuje možné chování dat, a zároveň její potomci ψjk tvoří úplný ortogonální systém, pak se zpravidla dobře daří konkrétní zpracovávaný signál aproximovat pomocí jen několika málo funkcí. Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Nebudeme zde zacházet do podrobností, jde o mimořádně živý směr výzkumu i základ komerčních aplikací. Zájemce snadno najde spoustu literatury. Na obrázku je ilustrována tzv. Daubechies mateřská wavelet D4(x) a její dcera D4(2−3x − 1). 1,2 2 0,8 0,4 1 0 0-1 t 3 4 t 252015 0 1,2 0 5 30 0,8 10 0,4 Literatura Vzdálenost funkcí Ortogonální systémy Fourierovy řady Wavelety Wavelety navíc nejsou vůbec definovány jako funkce analyticky. Místo toho jsou pouze tabelovány jejich hodnoty v dostatečném rozlišení.