Rungeho jev

Ukázka Rungeho jevu při aproximaci Rungeho funkce, která je vykreslena Šablona:Barva.
Šablona:Barva je interpolační polynom 5. řádu (používá šest stejně vzdálených interpolačních bodů).
Šablona:Barva je interpolační polynom 9. řádu (používá deset stejně vzdálených interpolačních bodů).
V interpolačních bodech je rozdíl mezi hodnotou funkce a hodnotou interpolačního polynomu (z definice) nulový. Mezi interpolačních body (zvláště v blízkosti koncových bodů 1 a −1) je rozdíl mezi hodnotou funkce a hodnotou interpolačního polynomu větší pro polynomy vyššího řádu.

Rungeho jev je problém v numerické matematice, který objevil v roce 1901 německý matematik Carl Runge, když zkoumal chování chyb při aproximaci funkcí pomocí interpolačních polynomů na množině ekvidistantních interpolačních bodů. Runge zjistil, že použití polynomu vyššího stupně vždy nezlepšuje přesnost; naopak, na okrajích intervalu se objevují oscilace. Jev je podobný Gibbsově jevu při aproximaci Fourierovou řadou.

Úvod

Weierstrassova věta o aproximaci říká, že ke každé spojité funkci f(x) definované na uzavřeném intervalu $⟨a,b⟩$ existuje posloupnost polynomiálních funkcí P_n(x) pro n=0, 1, 2, …, stupně nejvýše n, které aproximují funkci f(x), a na intervalu $⟨a,b⟩$ k ní konvergují stejnoměrně, tj.

$\underset{n\to \mathrm{\infty }}{\lim }\left(\underset{a\le x\le b}{\max }|f(x)-P_n(x)|\right)=0.$

Chceme funkci f(x) interpolovat v n+1 ekvidistantních bodech polynomem P_n(x) n-tého stupně, který těmito body prochází, můžeme na základě Weierstrassovy věty očekávat, že při použití více bodů bude rekonstrukce funkce f(x) přesnější. Ale tato určitá množina polynomiálních funkcí P_n(x) nezaručuje stejnoměrnou konvergenci; věta pouze tvrdí, že taková sada polynomiálních funkcí existuje. Věta sama neříká, jak najít takovou posloupnost polynomů; k tomu je možné použít Bernsteinovy polynomy.

Řada funkcí P_n(x) vytvořená tímto způsobem může pro rostoucí n divergovat od f(x); typicky se to projeví výskytem oscilací, které se v blízkosti koncových interpolačních bodů zvětšují. Objev tohoto jevu je připisován Rungemu.

Problém

Uvažujme Rungeho funkci

$f(x)=\frac{1}{1+25x^2}$

(zvětšená verze Agnesiny křivky). Runge zjistil, že při interpolaci této funkce v ekvidistantních bodech x_i na intervalu −1 a 1 tak, že:

$x_i=\frac{2i}{n}-1,i\in \{0,1,\dots ,n\}$

polynomy P_n(x) stupně nejvýše n, výsledná interpolační funkce kmitá na konci intervalu, tj. blízko k −1 a 1. Dokonce lze dokázat, že interpolační chyba se při zvyšování stupně polynomu zvětšuje (bez omezení):

$\underset{n\to \mathrm{\infty }}{\lim }(\underset{-1\le x\le 1}{\max }|f(x)-P_n(x)|)=+\mathrm{\infty }.$

To ukazuje, že interpolace polynomem vysokého stupně v ekvidistantních bodech může být problematická.

Příčina

Rungeho jev je důsledkem dvou vlastností tohoto problému:

• Hodnota derivací n-tého řádu této funkce rychle roste se zvětšujícím se n.
• Ekvidistance mezi body vede k Lebesgueově konstantě, která rychle roste se zvětšujícím se n.

Jev je graficky dobře viditelný, protože obě vlastnosti se kombinují a zvyšují řád oscilace.

Chyba mezi vytvořující funkcí a interpolačním polynomem řádu n je

$f(x)-P_n(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}\prod _{i=0}^n(x-x_i)$

pro nějaké $\xi$ z intervalu (−1, 1). Tedy

$\underset{-1\le x\le 1}{\max }|f(x)-P_n(x)|\le \underset{-1\le x\le 1}{\max }\frac{|f^{(n+1)}(x)|}{(n+1)!}\underset{-1\le x\le 1}{\max }\prod _{i=0}^n|x-x_i|$.

Označíme-li symbolem $w_n(x)$ nodální funkci

$w_n(x)=(x-x_0)(x-x_1)\cdots (x-x_n)$

a nechť $W_n$ je maximální řád funkce $w_n$:

$W_n=\underset{-1\le x\le 1}{\max }|w_n(x)|$.

Je jednoduché dokázat, že pro ekvidistantní uzly

$W_n\le n!h^{n+1}$

kde $h=2/n$ je velikost kroku.

Pokud navíc předpokládáme, že (n+1)-tá derivace funkce $f$ je omezená:

$\underset{-1\le x\le 1}{\max }|f^{(n+1)}(x)|\le M_{n+1}$.

Proto

$\underset{-1\le x\le 1}{\max }|f(x)-P_n(x)|\le M_{n+1}\frac{h^{n+1}}{(n+1)}$.

Ale řád (n+1)-té derivace Rungeho funkce se zvyšuje s rostoucím n, protože $M_{n+1}\le (n+1)!5^{n+1}$. Důsledkem je, že výsledná horní mez $(10/n{)}^{n+1}n!$ se blíží k nekonečnu, když n se blíží k nekonečnu.

Fakt, že horní mez chyby jde k nekonečnu, i když je často používán pro vysvětlení Rungeho jevu, samozřejmě neznamená, že samotná chyba také diverguje s rostoucím n.

Zmírňování problému

Změna interpolačních bodů

Oscilaci lze zmírnit použitím zahušťováním uzlů na okrajích intervalu. Například na intervalu ⟨−1,1⟩ lze použít body s asymptotickou hustotou danou vzorcem $1/\sqrt{1-x^2}$. Standardním příkladem takové sady uzlů jsou Čebyševovy uzly, u nichž maximální chyba v aproximaci Rungeho funkce zaručeně klesá s rostoucím řádem polynomu. Jev ukazuje, že polynomy vysokého stupně jsou pro interpolaci s ekvidistantními uzly obecně nevhodné.

S-Rungeho algoritmus bez převzorkování

Když převzorkováníŠablona:Ujasnit na rozumné množině uzlů není proveditelné, je možné vyzkoušet S-Rungeho algoritmus. Při tomto přístupu je původní množina uzlů mapovaná na množinu Čebyševových uzlů, poskytujících stabilní polynomiální rekonstrukci. Zvláštností této metody je, že není potřeba převzorkování na mapovaných uzlech, které se také nazývají umělé uzly. Na github je implementace tohoto postupu v jazyce Python.

Aproximace polynomiální po částech

Popsanému problému se lze vyhnout použitím spline křivek, které jsou po částech polynomiální. Pro zmenšení interpolační chyby můžeme místo zvyšování stupně použitého polynomu zvyšovat počet polynomiálních částí, které se používají pro konstrukci spline křivky.

Omezená minimalizace

Můžeme také proložit polynom vyššího stupně (například pro $n$ bodů použít polynom řádu $N=n^2$ místo $n+1$) a použít takový interpolační polynom, jehož první (nebo druhá) derivace má minimální $L^2$ normu.

Podobným přístupem je minimalizace omezené verze vzdálenosti $L^p$ mezi m-tou derivací polynomu a střední hodnotou jeho m-té derivace. Explicitně pro minimalizaci

$V_p=\underset{a}{\overset{b}{\int }}{|\frac{{\mathrm{d}}^m{P}_N(x)}{\mathrm{d}{x}^m}-\frac{1}{b-a}\underset{a}{\overset{b}{\int }}\frac{{\mathrm{d}}^m{P}_N(z)}{\mathrm{d}{z}^m}\mathrm{d}z|}^p\mathrm{d}x-\sum _{i=1}^n{\lambda }_i(P_N(x_i)-f(x_i)),$

kde $N\ge n-1$ a $m<N$, vzhledem ke koeficientům polynomu a Lagrangeovým multiplikátorům ${\lambda }_i$. Pro $N=n-1$ omezující rovnice generované Lagrangeovými multiplikátory omezují $P_N(x)$ na minimální polynom, který prochází všemi $n$ body. Na opačném konci $\underset{N\to \mathrm{\infty }}{\lim }{P}_N(x)$ se bude blížit tvaru velmi podobnému po částech polynomiální aproximaci. Speciálně pro $m=1$ se $\underset{N\to \mathrm{\infty }}{\lim }{P}_N(x)$ blíží po částech lineárním polynomům, tj. propojuje interpolační body úsečkami.

Při procesu minimalizace $V_p$ má $p$ za úkol omezovat velikost odchylek od střední hodnoty. Čím je $p$ větší, tím více jsou penalizovány větší odchylky v porovnání s malými. Hlavní výhodou Eukleidovské normy $p=2$ je, že umožňuje analytické řešení a zaručuje, že $V_p$ bude mít pouze jediné minimum. Pro $p\ne 2$ může ve $V_p$ existovat více minim, kvůli čemuž je obtížné zjistit, zda nalezené minimum je globálním minimem.

Použití metody nejmenších čtverců

Další metodou je proložení polynomu nižšího stupně použitím metody nejmenších čtverců. Obecně při použití $m$ ekvidistantních bodů, kde $N<2\sqrt{m}$ pak aproximace metodou nejmenších čtverců $P_N(x)$ je dobře podmíněná.

Bernsteinův polynom

Bernsteinovy polynomy umožňují stejnoměrně aproximovat každou spojitou funkci na uzavřeném intervalu. Tato metoda je však poněkud výpočetně náročná.Šablona:Doplňte zdroj

Příbuzná tvrzení z teorie aproximace

Pro každou předdefinovanou tabulku interpolačních uzlů existuje spojitá funkce, pro kterou posloupnost interpolační polynomů na těchto uzlech diverguje. Pro každou spojitou funkci existuje tabulka uzlů, na kterých interpolační proces konverguje.Šablona:Doplňte zdroj Čebyševova interpolace (na Čebyševových uzlech) konverguje stejnoměrně pro každou absolutně spojitou funkci.

Odkazy

Související články

• Srovnejte s Gibbsovým jevem pro sinusové bázové funkce
• Taylorova řada
• Čebyševovy uzly
• Stoneova–Weierstrassova věta