Lagrangeův polynom - Lagrange polynomial - Wikipedia
Tento obrázek ukazuje pro čtyři body ((−9, 5), (−4, 2), (−1, −2), (7, 9)), (kubický) interpolační polynom L(X) (přerušovaná, černá), což je součet zmenšen základní polynomy y0ℓ0(X), y1ℓ1(X), y2ℓ2(X) a y3ℓ3(X). Interpolační polynom prochází všemi čtyřmi kontrolními body a každým zmenšen základní polynom prochází příslušným řídicím bodem a je 0 kde X odpovídá dalším třem kontrolním bodům.
v numerická analýza, Lagrangeovy polynomy se používají pro polynomiální interpolace. Pro danou sadu bodů bez dvou stejné hodnoty, Lagrangeův polynom je polynomem nejnižší stupeň která předpokládá u každé hodnoty odpovídající hodnotu , takže funkce se shodují v každém bodě.
Ačkoli pojmenoval podle Joseph-Louis Lagrange, který ji publikoval v roce 1795, byla metoda poprvé objevena v roce 1779 autorem Edward Waring[1] Je to také snadný důsledek vzorce publikovaného v roce 1783 autorem Leonhard Euler.[2]
Lagrangeova interpolace je náchylná k Rungeův fenomén velké oscilace. Jako změna bodů vyžaduje přepočet celého interpolantu, jeho použití je často snazší Newtonovy polynomy namísto.
Zde vykreslíme Lagrangeovy základní funkce 1., 2. a 3. řádu na doméně bi-unit. Lineární kombinace Lagrangeových základních funkcí se používají ke konstrukci Lagrangeových interpolačních polynomů. Lagrangeovy základní funkce se běžně používají v analýza konečných prvků jako základy pro tvarové funkce prvku. Dále je běžné používat doménu dvou jednotek jako přirozený prostor pro definici konečných prvků.
Vzhledem k souboru k + 1 datové body
kde žádné dva jsou stejné, interpolační polynom ve Lagrangeově formě je lineární kombinace
Lagrangeových polynomů
kde . Všimněte si, jak vzhledem k původnímu předpokladu, že žádné dva jsou tedy stejné (když ) , takže tento výraz je vždy dobře definovaný. Dvojice důvodů s nejsou povoleny je, že žádná interpolační funkce takhle bude existovat; funkce může získat pouze jednu hodnotu pro každý argument . Na druhou stranu, pokud také , pak by tyto dva body byly ve skutečnosti jeden jediný bod.
Pro všechny , zahrnuje termín v čitateli, takže celý produkt bude nulový v :
Na druhou stranu,
Jinými slovy, všechny základní polynomy jsou nulové , až na , pro které to platí , protože mu chybí období.
Z toho vyplývá, že , takže v každém bodě , , což ukazuje interpoluje funkci přesně.
Důkaz
Funkce L(X) hledaný je polynom v X nejmenšího stupně, který interpoluje danou sadu dat; to znamená, že předpokládá hodnotu yj na odpovídající Xj pro všechny datové body j:
Všimněte si, že:
v existují k faktory v produktu a každý faktor obsahuje jeden X, tak L(X) (což je součet těchto k-degree polynomials) musí být nanejvýš polynomem stupně k.
Rozbalte tento produkt. Protože produkt vynechává výraz kde m = j, pokud i = j pak jsou všechny výrazy, které se objeví . Také pokud i ≠ j pak jeden výraz v produktu vůle být pro m = i), , vynulování celého produktu. Tak,
Tedy funkce L(X) je polynom s maximálním stupněm k a kde L(Xi) = yi.
Kromě toho je interpolační polynom jedinečný, jak ukazuje věta o disolvenci na polynomiální interpolace článek.
Je také pravda, že:
protože to musí být nanejvýš polynom stupně, k a prochází všemi těmito k + 1 datové body:
což má za následek vodorovnou čáru, protože přímka je jediný polynom stupně menšího než k + 1, které prochází k +1 zarovnané body.
Perspektiva z lineární algebry
Řešení problém interpolace vede k problému v lineární algebra ve výši inverze matice. Pomocí standardu monomiální základ pro náš interpolační polynom , musíme obrátit Vandermondeova matice vyřešit pro koeficienty z . Výběrem lepšího základu, Lagrangeova základu, , pouze dostaneme matice identity, , což je jeho vlastní inverzní: Lagrangeův základ automaticky inverze analog Vandermondeovy matice.
Tato konstrukce je obdobou Čínská věta o zbytku. Místo toho, abychom zkontrolovali zbytky celých čísel modulo prvočísel, kontrolujeme zbytky polynomů, když jsou vyděleny liniemi.
Navíc, když je objednávka velká, Rychlá Fourierova transformace lze použít k řešení koeficientů interpolovaného polynomu.
Příklady
Příklad 1
Chtěli bychom interpolovat ƒ(X) = X2 v rozsahu 1 ≤X ≤ 3, vzhledem k těmto třem bodům:
Interpolační polynom je:
Příklad 2
Chtěli bychom interpolovat ƒ(X) = X3 v rozsahu 1 ≤X ≤ 4, vzhledem k těmto čtyřem bodům:
Interpolační polynom je:
Poznámky
Příklad interpolační divergence pro sadu Lagrangeových polynomů.
Lagrangeova forma interpolačního polynomu ukazuje lineární charakter polynomiální interpolace a jedinečnost interpolačního polynomu. Proto je upřednostňován v důkazech a teoretických argumentech. Jedinečnost je patrná také z invertibility Vandermondeovy matice v důsledku nezmizení Vandermonde determinant.
Ale jak je vidět z konstrukce, pokaždé uzel Xk změny, je nutné přepočítat všechny polynomy Lagrangeovy báze. Lepší formou interpolačního polynomu pro praktické (nebo výpočetní) účely je barycentrická forma Lagrangeovy interpolace (viz níže) nebo Newtonovy polynomy.
Lagrangeova a jiná interpolace ve stejně rozmístěných bodech, jako ve výše uvedeném příkladu, poskytuje polynom oscilační nad a pod skutečnou funkcí. Toto chování má tendenci růst s počtem bodů, což vede k divergenci známé jako Rungeův fenomén; problém lze odstranit výběrem interpolačních bodů v Čebyševovy uzly.[3]
který se běžně označuje jako první forma barycentrické interpolační formule.
Výhodou této reprezentace je, že interpolační polynom lze nyní vyhodnotit jako
který, pokud váhy byly předem vypočítány, vyžaduje pouze operace (hodnocení a váhy ) naproti tomu pro vyhodnocení Lagrangeových polynomů jednotlivě.
Barycentrický interpolační vzorec lze také snadno aktualizovat, aby zahrnoval nový uzel dělením každého z , podle a konstrukci nového jak je uvedeno výše.
První formu můžeme dále zjednodušit tak, že nejprve vezmeme v úvahu barycentrickou interpolaci konstantní funkce :
Dělení podle nemění interpolaci, přesto poskytuje výnosy
který se označuje jako druhá forma nebo pravdivá forma barycentrické interpolační formule. Tato druhá forma má tu výhodu, že nemusí být hodnoceno pro každé hodnocení .
Zbytek v Lagrangeově interpolačním vzorci
Při interpolaci dané funkce F o polynom stupně k v uzlech dostaneme zbytek které lze vyjádřit jako[5]
kde je zápis pro rozdělené rozdíly. Alternativně může být zbytek vyjádřen jako obrysový integrál v komplexní doméně jako
Jasně, je nula v uzlech. Najít v určitém okamžiku . Definujte novou funkci a vybrat (Tím je zajištěno v uzlech) kde je konstanta, kterou jsme povinni určit pro danou . Nyní má nuly (na všech uzlech a ) mezi a (včetně koncových bodů). Za předpokladu, že je -krát rozlišitelné, a jsou polynomy, a proto jsou nekonečně diferencovatelné. Podle Rolleova věta, má nuly, má nuly ... má 1 nulu, řekněme . Výslovně psaní :
(Protože nejvyšší síla v je )
Rovnici lze přeskupit jako
Deriváty
The th deriváty Lagrangeova polynomu lze zapsat jako
.
U první derivace jsou koeficienty dány vztahem
a pro druhou derivaci
.
Pomocí rekurze lze vypočítat vzorce pro vyšší deriváty.