Rungeův fenomén

V matematickém poli z numerické analýzy , Runge fenomén se projevuje v souvislosti s polynomiální interpolace , zejména Lagrange interpolace . U určitých funkcí (i analytických ) nemusí zvyšování počtu n interpolačních bodů nutně představovat dobrou strategii přiblížení.

Studiem této otázky německý matematik Carl Runge objevil v roce 1901 výsledek, který je v rozporu s intuicí: existují konfigurace, kde maximální rozdíl mezi funkcí a její interpolací narůstá na neurčito s n .

Příklad, kde se vyskytuje Rungeův jev

Zvažte následující funkci:

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

Body $( n + 1)$ považujeme za rovnoměrně rozložené v segmentu $[-1, 1]$ :

{\ displaystyle x_ {0} = - 1, \; x_ {1} = x_ {0} + h, \; \ cdots, \; x_ {k + 1} = x_ {k} + h = x_ {0} + (k + 1) h, \; \ cdots, \; x_ {n} = 1 \ {\ text {with}} \ h = {\ frac {2} {n}}.}

Nakonec uvažujeme interpolační polynom $f$ v bodech $( x i )$ , tj. Jedinečný polynom $P$ stupně menšího nebo rovného $n$ tak, že $P ( x i ) = f ( x i )$ pro všechna $i$ . Označíme $P n$ tento polynom.

Runge ukázal, že chyba interpolace mezi $P n$ a $f$ má sklon k nekonečnu, jak se n zvyšuje. Jinými slovy, čím více bodů opravíme, kde má polynom stejnou hodnotu jako $f$ , tím méně se přiblížíme funkci. Formálně:

{\ displaystyle \ lim _ {n \ rightarrow \ infty} \ left (\ max _ {- 1 \ leq x \ leq 1} | f (x) -P_ {n} (x) | \ right) = \ infty. }

Ve skutečnosti při zvyšování počtu bodů vidíme, že polynom začne silně oscilovat mezi body $x i$ se zvyšující se amplitudou, jak je znázorněno na obrázku.

Vysvětlení

Rungeův fenomén je důsledkem dvou vlastností problému.

Amplituda derivací funkce Runge se zvyšuje velmi rychle, jak se zvyšuje n .
Rovnoměrné rozdělení interpolačních bodů vede k Lebesgueově konstantě, která se velmi rychle zvyšuje, když se zvyšuje n .

Opakovanými aplikacemi Rollovy věty můžeme ukázat, že pro případ interpolace s n + 1 ekvidistribuovanými body existuje bod takový, že ${\ displaystyle \ xi \ in] -1,1 [}$

{\ displaystyle f (x) -P_ {n} (x) = {\ frac {f ^ {(n + 1)} (\ xi)} {(n + 1)!}} \ prod _ {i = 0 } ^ {n} (x-x_ {i}).}

Ve zvoleném příkladu se hodnoty postupných derivací funkce zvyšují s počtem bodů, takže oscilace mezi každým interpolačním bodem jsou zesíleny.

Navíc, když jsou interpolační uzly rovnoměrně rozloženy, zhoršuje to tuto situaci, jak je vysvětleno níže. Ve všeobecnějším rámci není Lagrangeova interpolace na ekvidistantních uzlech nejlepší. Poznamenáním ( $l i$ ) základny Lagrangeových polynomů spojených s body ( $x i$ ) máme:

{\ displaystyle P_ {n} (x) = \ součet _ {i = 0} ^ {n} f (x_ {i}) l_ {i} (x),}

z čehož odvozujeme následující odhad:

{\ displaystyle \ left | P_ {n} (x) \ right | \ leqslant \ left (\ sum _ {i = 0} ^ {n} \ left | l_ {i} (x) \ right | \ right) \ | f \ | _ {\ infty} \ leqslant \ sup _ {x \ in [a, b]} \ left (\ sum _ {i = 0} ^ {n} \ left | l_ {i} (x) \ vpravo | \ right) \ | f \ | _ {\ infty}.}

Konstanta se nazývá Lebesgueova konstanta spojená s body ( $x$ $i$ ) . Všimli jsme si, že Lebesgueova konstanta závisí pouze na interpolačních uzlech (je nezávislá na interpolované funkci). V případě bodů ve stejné vzdálenosti lze tuto konstantu odhadnout pomocí: ${\ displaystyle \ Lambda _ {n} = \ sup _ {x \ in [a, b]} \ left (\ sum _ {i = 0} ^ {n} \ left | l_ {i} (x) \ right | \ vpravo)}$

{\ displaystyle \ Lambda _ {n} \ sim {\ frac {2 ^ {n + 1}} {{\ rm {e}} \, n \ ln (n)}},}

s $e$ , počet Euler či konstanty neper , být v hodnotě 2,7183 ... Je tedy zřejmé, že v tomto případě je konstanta Lebesgueův tendenci rychle směrem k velké hodnoty.

Řešení problému, který představuje Rungeův fenomén

Rungeův fenomén zdůrazňuje skutečnost, že polynomiální interpolace není vždy vhodná pro aproximaci funkcí.

Výběr bodů

Můžeme minimalizovat oscilaci interpolačních polynomů pomocí Čebyševových úseček namísto rovnoměrně rozložených bodů k interpolaci. V tomto případě můžeme ukázat, že chyba interpolace (tj. ) Klesá s nárůstem n (můžeme to vidět studiem Lebesgueovy konstanty Čebyševových bodů při logaritmickém růstu). ${\ displaystyle \ max _ {- 1 \ leq x \ leq 1} | f (x) -P_ {n} (x) |}$

Segmentace

Abychom se přiblížili funkci s polynomy, můžeme raději použít například splajny (jsou to po částech polynomy). V tomto případě, abychom zlepšili aproximaci, zvýšíme počet kusů a ne stupeň polynomů.

Minimalizace za určitých podmínek

Dobré výsledky je možné získat hledáním polynomu vyššího stupně (například 2 n ), ale formulováním problému z hlediska optimalizace za určitých podmínek (aby se reabsorbovaly přebytečné stupně volnosti). Mezi všemi polynomy, které procházejí funkcí v interpolačních bodech, hledáme ten, který minimalizuje

integrál čtverce jeho první derivace (penalizace „strmých svahů“).
integrál čtverce jeho druhé derivace (penalizace slabých poloměrů zakřivení , „roztažený“ polynom).
kombinace dvou předchozích termínů.

Jde o minimalizaci kvadratické formy pod lineárními omezeními, což se nakonec rovná řešení soustavy lineárních rovnic .

Odkaz

Jean-Pierre Demailly , Numerická analýza a diferenciální rovnice , EDP Sciences , kol. "Grenoble Sciences",2006, 344 s. ( ISBN 978-2-7598-0112-1 , číst online ) , s. ? .
Abgrall Rémi, Aplikovaná matematika L3: Kompletní kurz s 500 opravenými testy a cvičeními , Pearson ,2009( ISBN 978-2-7440-7352-6 ) , „Kapitola 2, část 2“.

Dodatky

Bibliografie

Jean Dieudonné , Calculus infinitesimal [ detail vydání ] , kap. IX, příloha, str. 319-320

Podívejte se také

Můžeme srovnávat fenomén Runge s fenoménem Gibbs, ke kterému dochází, když interpolujeme funkce trigonometrickými polynomy.