Interpolace - Interpolation

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Říjen 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

V matematický pole numerická analýza, interpolace je typ odhad, metoda konstrukce nového datové body v rozsahu a diskrétní sada známých datových bodů.^[1]

v inženýrství a Věda, jeden často má řadu datových bodů získaných pomocí vzorkování nebo experimentování, které představují hodnoty funkce pro omezený počet hodnot parametru nezávislé proměnné. Často se to vyžaduje interpolovat, tj. odhadnout hodnotu této funkce pro střední hodnotu nezávislé proměnné.

Úzce souvisejícím problémem je přiblížení komplikované funkce jednoduchou funkcí. Předpokládejme, že vzorec pro danou funkci je známý, ale příliš komplikovaný na efektivní vyhodnocení. Několik datových bodů z původní funkce lze interpolovat, aby se vytvořila jednodušší funkce, která je stále poměrně blízká původnímu. Výsledný zisk v jednoduchosti může převážit ztrátu z chyby interpolace.

Interpolace konečné množiny bodů na epitrochoid. Body v červené barvě jsou spojeny modrou interpolací křivky spline odvodit pouze z červených bodů. Interpolované křivky mají polynomiální vzorce mnohem jednodušší než u původní epitrochoidní křivky.

Příklad

Tato tabulka uvádí některé hodnoty neznámé funkce ${displaystyle f (x)}$.

Graf datových bodů, jak je uvedeno v tabulce.

	${displaystyle x}$		${displaystyle f (x)}$
	0		0
	1		0	.	8415
	2		0	.	9093
	3		0	.	1411
	4		−0	.	7568
	5		−0	.	9589
	6		−0	.	2794

Interpolace poskytuje prostředky pro odhad funkce v mezilehlých bodech, jako např ${displaystyle x = 2,5}$.

Popíšeme některé metody interpolace, která se liší vlastnostmi jako: přesnost, cena, počet potřebných datových bodů a hladkost výsledného interpolant funkce.

Po částech konstantní interpolace

Po částech konstantní interpolace, nebo interpolace nejbližšího souseda.

Nejjednodušší interpolační metodou je najít nejbližší hodnotu dat a přiřadit stejnou hodnotu. U jednoduchých problémů se tato metoda pravděpodobně nepoužije, protože lineární interpolace (viz níže) je téměř stejně snadná, ale ve vícerozměrných vícerozměrná interpolace, to může být příznivá volba pro jeho rychlost a jednoduchost.

Lineární interpolace

Plot dat s lineární interpolací superponovanou

Jedna z nejjednodušších metod je lineární interpolace (někdy známá jako lerp). Zvažte výše uvedený příklad odhadu F(2.5). Vzhledem k tomu, že 2,5 je uprostřed mezi 2 a 3, je rozumné to vzít F(2.5) uprostřed mezi F(2) = 0,9093 a F(3) = 0,1411, čímž se získá 0,5252.

Obecně platí, že lineární interpolace trvá dva datové body, řekněme (X_A,y_A) a (X_b,y_b) a interpolant je dán vztahem:

${displaystyle y = y_ {a} + left (y_ {b} -y_ {a} ight) {frac {x-x_ {a}} {x_ {b} -x_ {a}}} {ext {v bodě }} vlevo (x, yight)}$

${displaystyle {frac {y-y_ {a}} {y_ {b} -y_ {a}}} = {frac {x-x_ {a}} {x_ {b} -x_ {a}}}}$

${displaystyle {frac {y-y_ {a}} {x-x_ {a}}} = {frac {y_ {b} -y_ {a}} {x_ {b} -x_ {a}}}}$

Tato předchozí rovnice uvádí, že sklon nové přímky mezi ${displaystyle (x_ {a}, y_ {a})}$ a ${displaystyle (x, y)}$ je stejný jako sklon přímky mezi ${displaystyle (x_ {a}, y_ {a})}$ a ${displaystyle (x_ {b}, y_ {b})}$

Lineární interpolace je rychlá a snadná, ale není příliš přesná. Další nevýhodou je, že interpolant není rozlišitelný na místě X_k.

Následující odhad chyby ukazuje, že lineární interpolace není příliš přesná. Označme funkci, kterou chceme interpolovat Ga předpokládejme to X leží mezi X_A a X_b a to G je dvakrát spojitě diferencovatelné. Pak je chyba lineární interpolace

${displaystyle | f (x) -g (x) | leq C (x_ {b} -x_ {a}) ^ {2} quad {ext {where}} quad C = {frac {1} {8}} max _ {rin [x_ {a}, x_ {b}]} | g '' (r) |.}$

Slovy, chyba je úměrná druhé mocnině vzdálenosti mezi datovými body. Chyba v některých dalších metodách, včetně polynomiální interpolace a spline interpolace (popsaná níže), je úměrná vyšším mocnostem vzdálenosti mezi datovými body. Tyto metody také produkují hladší interpolanty.

Polynomiální interpolace

Graf dat s aplikovanou polynomiální interpolací

Polynomiální interpolace je zobecněním lineární interpolace. Všimněte si, že lineární interpolant je a lineární funkce. Nyní tento interpolant nahradíme a polynomiální vyšších stupeň.

Zvažte znovu problém uvedený výše. Následující polynom šestého stupně prochází všemi sedmi body:

${displaystyle f (x) = - 0,0001521x ^ {6} -0,003130x ^ {5} + 0,07321x ^ {4} -0,3577x ^ {3} + 0,2255x ^ {2} + 0,9038x.}$

Střídání X = 2,5, zjistíme, že F(2.5) = 0.5965.

Obecně, pokud ano n datových bodů, existuje přesně jeden polynom stupně n-1 prochází všemi datovými body. Chyba interpolace je úměrná vzdálenosti mezi datovými body a výkonem n. Kromě toho je interpolant polynomem a je tak nekonečně diferencovatelný. Vidíme tedy, že polynomiální interpolace překonává většinu problémů lineární interpolace.

Polynomiální interpolace má však také některé nevýhody. Výpočet interpolačního polynomu je výpočetně nákladný (viz výpočetní složitost ) ve srovnání s lineární interpolací. Kromě toho může polynomiální interpolace vykazovat oscilační artefakty, zejména v koncových bodech (viz Rungeův fenomén ).

Polynomiální interpolace může odhadnout lokální maxima a minima, která jsou mimo rozsah vzorků, na rozdíl od lineární interpolace. Například interpolant výše má lokální maximum na X ≈ 1.566, F(X) ≈ 1,003 a místní minimum na X ≈ 4.708, F(X) ≈ -1,003. Tato maxima a minima však mohou přesahovat teoretický rozsah funkce - například funkce, která je vždy pozitivní, může mít interpolant se zápornými hodnotami a jejíž inverzní funkce proto obsahuje falešné hodnoty vertikální asymptoty.

Obecněji může být tvar výsledné křivky, zejména pro velmi vysoké nebo nízké hodnoty nezávislé proměnné, v rozporu s rozumem, tj. S tím, co je známo o experimentálním systému, který generoval datové body. Tyto nevýhody lze snížit pomocí spline interpolace nebo omezením pozornosti na Čebyševovy polynomy.

Spline interpolace

Spiknutí dat s aplikovanou spline interpolací

Pamatujte, že lineární interpolace používá lineární funkci pro každý z intervalů [X_k,X_{k + 1}]. Interpolace spline používá v každém z intervalů polynomy nízkého stupně a vybírá polynomiální části tak, aby do sebe hladce zapadaly. Výsledná funkce se nazývá a spline.

Například přírodní kubický spline je po částech kubický a dvakrát spojitě diferencovatelný. Kromě toho je jeho druhá derivace v koncových bodech nulová. Přirozený kubický spline interpolací bodů v tabulce výše je dán vztahem

${displaystyle f (x) = {egin {cases} -0.1522x ^ {3} + 0,9937x, & {ext {if}} xin [0,1], - 0,01258x ^ {3} -0,4189x ^ { 2} + 1,4126x-0,1396, & {ext {if}} xin [1,2], 0,1403x ^ {3} -1,3359x ^ {2} + 3,2467x-1,3623, & {ext {if}} xin [2,3], 0,1579x ^ {3} -1,4945x ^ {2} + 3,7225x-1,8381, & {ext {if}} xin [3,4], 0,05375x ^ {3} -0,2450x ^ {2} -1,2756x + 4,8259, & {ext {if}} xin [4,5], - 0,1871x ^ {3} + 3,3673x ^ {2} -19,3370x + 34,9282, & {ext {pokud }} xin [5,6] .end {cases}}}$

V tomto případě dostaneme F(2.5) = 0.5972.

Stejně jako polynomiální interpolace, spline interpolace přináší menší chybu než lineární interpolace, zatímco interpolant je hladší a snáze vyhodnotitelný než polynomy vysokého stupně používané v polynomiální interpolaci. Globální povaha základních funkcí však vede ke špatnému podmínění. To je zcela zmírněno pomocí spline kompaktní podpory, jako jsou implementovány v Boost.Math a diskutovány v Kress.^[2]

Aproximace funkce

Interpolace je běžný způsob aproximace funkcí. Vzhledem k funkci ${displaystyle f: [a, b] o mathbb {R}}$ se sadou bodů ${displaystyle x_ {1}, x_ {2}, tečky, x_ {n} v [a, b]}$ jeden může tvořit funkci ${displaystyle s: [a, b] o mathbb {R}}$ takhle ${displaystyle f (x_ {i}) = s (x_ {i})}$ pro ${displaystyle i = 1,2, tečky, n}$ (to je to ${displaystyle s}$ interpoluje ${displaystyle f}$ v těchto bodech). Obecně platí, že interpolant nemusí být dobrou aproximací, ale existují dobře známé a často přiměřené podmínky. Například pokud ${displaystyle fin C ^ {4} ([a, b])}$ (čtyřikrát nepřetržitě diferencovatelné) kubická spline interpolace má chybu vázanou danou ${displaystyle | f-s | _ {infty} leq C | f ^ {(4)} | _ {infty} h ^ {4}}$ kde ${displaystyle hmax _ {i = 1,2, tečky, n-1} | x_ {i + 1} -x_ {i} |}$ a ${displaystyle C}$ je konstanta.^[3]

Prostřednictvím Gaussových procesů

Gaussův proces je mocný nelineární interpolační nástroj. Mnoho populárních interpolačních nástrojů je ve skutečnosti ekvivalentních konkrétním gaussovským procesům. Gaussovy procesy lze použít nejen pro přizpůsobení interpolantu, který prochází přesně danými datovými body, ale také pro regresi, tj. Pro přizpůsobení křivky hlučnými daty. V geostatistické komunitě je Gaussova procesní regrese také známá jako Kriging.

Jiné formy

Jiné formy interpolace lze sestavit výběrem jiné třídy interpolantů. Například racionální interpolace je interpolace podle racionální funkce použitím Padé přibližný, a trigonometrická interpolace je interpolace pomocí trigonometrické polynomy použitím Fourierova řada. Další možností je použít vlnky.

The Whittaker-Shannonův interpolační vzorec lze použít, pokud je počet datových bodů nekonečný nebo pokud má funkce, která má být interpolována, kompaktní podporu.

Někdy známe nejen hodnotu funkce, kterou chceme v některých bodech interpolovat, ale také její derivaci. Tohle vede k Hermitova interpolace problémy.

Když je každý datový bod sám funkcí, může být užitečné vidět problém s interpolací jako částečný advekce problém mezi každým datovým bodem. Tato myšlenka vede k interpolace posunutí problém použitý v teorie dopravy.

Ve vyšších dimenzích

Srovnání některých 1- a 2-dimenzionálních interpolací. Černé a červené / žluté / zelené / modré tečky odpovídají interpolovanému bodu a sousedním vzorkům. Jejich výšky nad zemí odpovídají jejich hodnotám.

Vícerozměrná interpolace je interpolace funkcí více než jedné proměnné. Metody zahrnují bilineární interpolace a bikubická interpolace ve dvou rozměrech a trilineární interpolace ve třech rozměrech. Lze je použít na mřížková nebo rozptýlená data.

• 

  Nejbližší soused

• 

  Bilineární

• 

  Bikubický

Při digitálním zpracování signálu

V oblasti digitálního zpracování signálu se termín interpolace týká procesu převodu vzorkovaného digitálního signálu (například vzorkovaného zvukového signálu) na proces vyšší vzorkovací frekvence (Převzorkování ) pomocí různých digitálních filtračních technik (např. konvoluce s frekvenčně omezeným impulzním signálem). V této aplikaci existuje specifický požadavek, aby byl zachován harmonický obsah původního signálu, aniž by byl vytvořen aliasovaný harmonický obsah původního signálu nad původní Nyquistův limit signálu (tj. Nad fs / 2 původní vzorkovací frekvence signálu). Časnou a poměrně základní diskusi na toto téma lze najít v knize Rabinera a Crochiere Mnohonásobné digitální zpracování signálu.^[4]

Související pojmy

Termín extrapolace se používá k vyhledání datových bodů mimo rozsah známých datových bodů.

v přizpůsobení křivky problémy, omezení, které musí interpolant procházet přesně datovými body, je uvolněné. Je nutné pouze přiblížit se k datovým bodům co nejblíže (v rámci některých dalších omezení). To vyžaduje parametrizaci potenciálních interpolantů a nějaký způsob měření chyby. V nejjednodušším případě to vede k nejmenší čtverce přiblížení.

Teorie aproximace studuje, jak najít nejlepší aproximaci dané funkce jinou funkcí z nějaké předem určené třídy a jak dobrá je tato aproximace. Tím se jasně získá ohraničení toho, jak dobře může interpolant aproximovat neznámou funkci.

Zobecnění

Pokud vezmeme v úvahu ${displaystyle x}$ jako proměnná v a topologický prostor a funkce ${displaystyle f (x)}$ mapování na a Banachův prostor, pak je problém považován za „interpolaci operátorů“.^[5] Klasické výsledky o interpolaci operátorů jsou Riesz – Thorinova věta a Marcinkiewiczova věta. Existuje také mnoho dalších následných výsledků.

Viz také

Reference

externí odkazy

• Online nástroje pro lineární, kvadratický, kubický spline, a polynomiální interpolace s vizualizací a JavaScript zdrojový kód.
• Sol Tutorials - Interpolační triky
• Kompaktně podporovaná kubická interpolace B-Spline v Boost.Math
• Barycentrická racionální interpolace v Boost.Math
• Interpolace pomocí Čebyševovy transformace v Boost.Math