Lagrangeova interpolace

V numerické analýze , jsou Lagrangeovy polynomy , pojmenoval Joseph-Louis Lagrange , aby bylo možné interpolovat řadu bodů polynomu, který prochází přesně skrz tyto body rovněž nazývaných uzly. Tuto polynomiální interpolační techniku objevil Edward Waring v roce 1779 a později ji znovu objevil Leonhard Euler v roce 1783. Jde o speciální případ čínské věty o zbytku .

Definice

Dali jsme $si n + 1$ bodů (s $x$ $i$ odlišnými dvěma po dvou). Navrhujeme sestrojit polynom minimálního stupně, který na úsečce $x$ $i$ přebírá hodnoty $y$ $i$ , čehož je možné dosáhnout pomocí následující metody. $(x_ {0}, y_ {0}), \ tečky, (x_ {n}, y_ {n})$

Následující studie navrhuje ukázat, že polynom je jediným polynomem stupně, který n uspokojí tuto vlastnost. ${\ displaystyle L (X) = \ součet _ {j = 0} ^ {n} y_ {j} \ vlevo (\ prod _ {i = 0, i \ neq j} ^ {n} {\ frac {X- x_ {i}} {x_ {j} -x_ {i}}} \ vpravo)}$

Lagrangeovy polynomy

Lagrangeovy polynomy spojené s těmito body jsou polynomy definované:

{\ displaystyle l_ {i} (X) = \ prod _ {j = 0, j \ neq i} ^ {n} {\ frac {X-x_ {j}} {x_ {i} -x_ {j}} } = {\ frac {X-x_ {0}} {x_ {i} -x_ {0}}} \ cdots {\ frac {X-x_ {i-1}} {x_ {i} -x_ {i- 1}}} ~ {\ frac {X-x_ {i + 1}} {x_ {i} -x_ {i + 1}}} \ cdots {\ frac {X-x_ {n}} {x_ {i} -x_ {n}}}.}

Máme zejména dvě vlastnosti:

$l i$ je stupně $n$ pro všechna $i$ ;
$l_ {i} (x_ {j}) = \ delta _ {{i, j}}, 0 \ leq i, j \ leq n$ to znamená a pro $l_ {i} (x_ {i}) = 1$ $l_ {i} (x_ {j}) = 0$ $j \ neq i$

Interpolační polynom

Polynom definovaný jako je jedinečný polynom stupně, který nanejvýš $n$ vyhovuje všem $i$ . ${\ displaystyle L (X) = \ součet _ {j = 0} ^ {n} y_ {j} l_ {j} (X)}$ $L (x_ {i}) = y_ {i}$

Vskutku :

na jedné straně ; ${\ displaystyle L (x_ {i}) = \ součet _ {j = 0} ^ {n} y_ {j} l_ {j} (x_ {i}) = y_ {i}}$
na druhé straně je lineární kombinací polynomů stupně $n$ , $L$ je stupně $n$ maximálně $n$ ; pokud jiný polynom $Q$ splňuje tyto vlastnosti, pak $L - Q$ má stupeň $n$ a mizí v $n + 1$ různých bodech ( $x k$ ): $L - Q$ je tedy nula, což dokazuje jedinečnost.

Příklad

Pro body nejprve vypočítáme Lagrangeovy polynomy: ${\ displaystyle (x_ {0} = 1, y_ {0} = 3), (x_ {1} = - 1, y_ {1} = 2), (x_ {2} = 2, y_ {2} = - 1)}$

${\ displaystyle l_ {0} (X) = {\ frac {(X + 1) (X-2)} {(1 + 1) (1-2)}} = - {\ frac {1} {2} } (X ^ {2} -X-2)}$ ;
${\ displaystyle l_ {1} (X) = {\ frac {(X-1) (X-2)} {(- 1-1) (- 1-2)}} = {\ frac {1} {6 }} (X ^ {2} -3X + 2)}$ ;
${\ displaystyle l_ {2} (X) = {\ frac {(X-1) (X + 1)} {(2-1) (2 + 1)}} = {\ frac {1} {3}} (X ^ {2} -1)}$ .

Potom vypočítáme polynomiální funkci procházející těmito body:

${\ displaystyle L (X) = P (X) = 3l_ {0} (X) + 2l_ {1} (X) -l_ {2} (X)}$ ;
${\ displaystyle L (X) = P (X) = - {\ frac {3} {2}} X ^ {2} + {\ frac {1} {2}} X + 4}$ .

Jiné psaní

Nastavme polynom . Okamžitě vidíme, že splňuje $N$ $($ $x$ $i$ $) = 0$ a pomocí Leibnizova vzorce je jeho derivát: ${\ displaystyle N (X) = \ prod _ {j = 0} ^ {n} (X-x_ {j})}$

{\ displaystyle N '(X) = \ součet _ {j = 0} ^ {n} \ prod _ {i = 0, i \ neq j} ^ {n} (X-x_ {i})}

Zejména v každém uzlu $x k$ se všechny produkty navzájem ruší, kromě jednoho, což dává zjednodušení:

{\ displaystyle N '(x_ {k}) = \ prod _ {i = 0, i \ neq k} ^ {n} (x_ {k} -x_ {i})}

Lagrangeovy polynomy lze tedy definovat z N :

{\ displaystyle l_ {i} (X) = {N (X) \ nad N '(x_ {i}) (X-x_ {i})}}

Můžete použít $N$ přeložit jedinečnost: Je-li $Q$ šeky pro všechny $i$ poté $Q - L$ zmizí v místech $x$ $i$ je tedy násobkem $N$ . Je tedy ve formě, kde $P$ je libovolný polynom. Máme tedy sadu interpolačních polynomů spojených s body $($ $x$ $i$ $,$ $y$ $i$ $)$ a $L$ je minimální stupeň. $Q (x_ {i}) = y_ {i}$ $Q (X) = L (X) + N (X) \ cdot P (X)$

Efektivní algoritmus

Alternativní psaní je základem rychlého algoritmu pro výpočet Lagrangeova interpolačního polynomu. Se stejnými notacemi jako dříve spočívá algoritmus ve výpočtu přístupem rozděl a panuj , poté jeho derivaci, která se poté vyhodnotí pomocí vícebodového vyhodnocení . Od toho odvozujeme ${\ displaystyle N (X)}$ ${\ displaystyle N '(X)}$ $x_ {i}$ ${\ displaystyle L (X) = \ součet _ {j = 0} ^ {n} y_ {j} l_ {j} (X)}$

L(X)NE(X)=∑j=1myjNE′(Xj)(X-Xj).{\ displaystyle {\ frac {L (X)} {N (X)}} = \ součet _ {j = 1} ^ {m} {\ frac {y_ {j}} {N '(x_ {j}) (X-x_ {j})}}.}

{\ displaystyle {\ frac {L (X)} {N (X)}} = \ součet _ {j = 1} ^ {m} {\ frac {y_ {j}} {N '(x_ {j}) (X-x_ {j})}}.}

Vzhledem ke všem hodnotám lze vypočítat čitatele a jmenovatele racionálního zlomku, opět pomocí přístupu rozděl a panuj. Pomocí algoritmů rychlého násobení (in) lze Lagrangeovu interpolační polynom vypočítat pomocí řady kvazilineárních algebraických operací.

{\ displaystyle N '(x_ {j})}

Základ polynomů

Dáme $si n + 1$ odlišných skalárů . Pro jakýkoli polynom

P

patřící do , pokud nastavíme ,

P

je interpolační polynom odpovídající bodům: je roven polynomu

L

definovanému výše.

x_ {0}, \ ldots, x_ {n}

K_ {n} [X]

y_ {i} = P (x_ {i})

Tak jsme tedy jako rodina generátoru . Protože jeho mohutnost (rovná se

n

+ 1

) se rovná dimenzi prostoru, je jeho základem.

{\ displaystyle P (X) = \ součet _ {j = 0} ^ {n} P (x_ {j}) l_ {j} (X)}

(l_ {0}, l_ {1}, \ dots, l_ {n})

K_ {n} [X]

Příklady: výběrem $P = 1$ nebo $P = X$ máme:

${\ displaystyle 1 = \ součet _ {j = 0} ^ {n} l_ {j} (X)}$ ;
${\ displaystyle X = \ součet _ {j = 0} ^ {n} x_ {j} l_ {j} (X)}$ .

Ve skutečnosti to je báze, jejíž dvojí základ je rodina $n + 1$ lineární formy z

Dirac definován

u_i

{\ displaystyle \ forall i \ in \ {0, \ ldots, n \}, \, u_ {i} (P) = P (x_ {i})}

Pokud vezmeme v úvahu bodový produkt:

{\ displaystyle \ forall P, Q, \, \ součet _ {i = 0} ^ {n} P (x_ {i}) Q (x_ {i})}

rodina tvoří

ortonormální báze a .

{\ displaystyle (l_ {1}, \ tečky, l_ {n})}

\ mathbb {R} _ {n} [X]

Aplikace

Lagrangeovou interpolaci lze použít k výpočtu inverzní matice Vandermondeovy matice .
Používá se v kryptografii ke sdílení Shamirových tajných klíčů .
Může být použit pro numerický výpočet integrálu (pomocí Newton-Cotesových vzorců ) nebo obecněji pro aproximaci funkce .
Lze jej použít k aproximaci derivace funkce. Derivace Lagrangeova polynomu je ${\ displaystyle L '(x): = \ součet _ {j = 0} ^ {k} y_ {j} \ ell _ {j}' (x)}$ kde . ${\ displaystyle \ ell _ {j} '(x) = \ ell _ {j} (x) \ cdot \ sum _ {m = 0, \ m \ neq j} ^ {n} {\ frac {1} { x-x_ {m}}}}$

Hlavní myšlenka

Řešení problému s interpolací vede k převrácení pevné matice typu Vandermondeovy matice . Jedná se o těžký výpočet počtu operací. Lagrangeovy polynomy definují nový základ polynomů, který umožňuje, aby již neměla úplnou matici, ale diagonální matici . Nicméně, invertující diagonální matice je triviální operace .

Lagrangeův -

Sylvesterův interpolační polynom

Pro každý multiset o scalars a jakéhokoliv prvku z , existuje jedinečná polynom na stupeň tak, že ${\ displaystyle (X, m)}$ ${\ displaystyle Y = (y_ {x, k}) _ {x \ v X, 0 \ leq k <m (x)}}$ ${\ displaystyle \ prod _ {x \ v X} K ^ {m (x)}}$ $L$ ${\ displaystyle <\ součet _ {x \ v X} m (x)}$

{\ displaystyle \ forall x \ in X \ quad \ forall k <m (x) \ quad L ^ {(k)} (x) = y_ {x, k}}

Tento polynom je tedy zapsán , kde je jedinečný polynom stupně , který a všechny ostatní jsou nulové. Tím se zevšeobecňuje interpolace Lagrangeovy a

Hermitovy .

{\ displaystyle L = \ součet _ {x \ v X, 0 \ leq k <m (x)} y_ {x, k} \ ell _ {x, k}}

{\ displaystyle \ ell _ {x, k}}

{\ displaystyle <\ součet _ {z \ v X} m (z)}

{\ displaystyle \ ell _ {x, k} ^ {(k)} (x) = 1}

{\ displaystyle \ ell _ {x, k} ^ {(j)} (z)}

Podívejte se také

Související články

externí odkazy

Polynomiální interpolace Lagrangeova typu (sic) na math-linux.com
Výpočet Lagrangeova polynomu zadáním souřadnic bodů na homeomath2.imingo.net

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku Wikipedie v angličtině s názvem „ Lagrangeův polynom “ ( viz seznam autorů ) .

Scientific Computing: Kurzy, opravená cvičení a ilustrace v Matlabu v Knihách Google .
Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf, Bruno Salvy a Éric Schost, efektivní algoritmy ve formálním počtu ,2017( ISBN 979-10-699-0947-2 , číst online )
Mathematics L3 - Applied Mathematics on Google Books .
(en) EN Gantmacher (in) , Theory of Matrices , sv. 1, vydavatelství Chelsea,1959( číst online ) , s. 101-102.