Lagrange interpolationspolynomium

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. november 2021; checks kræver 2 redigeringer .

Lagrange-interpolationspolynomiet er et polynomium af minimumsgrad, der antager givne værdier ved et givet sæt af punkter, det vil sige løser interpolationsproblemet .

Definition

Lad et par tal gives, hvor alle er forskellige. Det er påkrævet at konstruere et polynomium af grad højst , for hvilket . $n+1$ $(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n}),$ $x_{j}$ $L(x)$ $n$ ${\displaystyle L(x_{j})=y_{j))$

Generel sag

J. L. Lagrange foreslog følgende metode til beregning af sådanne polynomier:

L(x)=\sum _{i=0}^{n}y_{i}l_{i}(x),

hvor de grundlæggende polynomier er bestemt af formlen $l_{i}$

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}}}\cdot {\frac {x-x_{i+1}}{x_{i}-x_{i+1}}}\cdots {\frac {x-x_{n}}{x_{i }-x_{n}}}

For ethvert polynomium har grad og $i=0,\ldots ,n$ $l_{i}$ $n$

l_{i}(x_{j})=\venstre\{{\begin{array}{rl}0,&j\neq i,\\1,&j=i.\end{array}}\right .

Dette indebærer, at , som er en lineær kombination af polynomier , har højst grad og . $L(x)$ $l_{i}(x)$ $n$ $L(x_{i})=y_{i}$

Tilfældet med ækvidistante interpolationsnoder

Lad interpolationsknudepunkterne være ækvidistante, det vil sige, at de udtrykkes i form af udgangspunktet og en fast positiv værdi som følger: $x_{j}$ $x_{0}$ $h$

x_{j}=x_{0}+jh.

Derfor følger det

x_{j}-x_{i}=(ji)h.

Ved at indsætte disse udtryk i formlen for det grundlæggende polynomium og tage produktets tegn ud i tæller og nævner, får vi $h$

l_{j}(x)={\prod _{i=0,\,i\neq j}^{n}{(x-x_{i}) \over (x_{j}-x_{ i})}}={\prod \limits _{i=0,\,i\neq j}^{n}(x-x_{0}-ih) \over h^{n}\prod \limits _ {i=0,\,i\neq j}^{n}(ji)}

Nu kan vi indføre en ændring af variabel

y={{x-x_{0}} \over h}

og få et udtryk for basale polynomier i form af , som er bygget ved kun at bruge heltals aritmetik : $y$

l_{j}(x)=l_{j}(x_{0}+yh)=(-1)^{nj}C_{n}^{j}{\dfrac {y(y-1) \ldots (yn)}{(yi)n!}}.

Disse mængder kaldes Lagrange-koefficienter. De er ikke afhængige af eller af og kan derfor beregnes på forhånd og skrives i form af tabeller. Ulempen ved denne tilgang er den faktorielle kompleksitet af tælleren og nævneren, som kræver brug af lang aritmetik . $y_{0},\ldots ,y_{n}$ $h$

Resten

Hvis vi betragter tallene som værdierne af en funktion ved noderne , så er fejlen ved at interpolere funktionen med et polynomium lig med $y_{0},\ldots ,y_{n}$ $f$ ${\displaystyle x_{0},\ldots ,x_{n))$ $f$ $L$

f(x)-L(x)={\dfrac {f^{(n+1)}(\xi )}{(n+1)!}}(x-x_{0})\ldots (x-x_{n}),

hvor er et eller andet midtpunkt mellem det mindste og det største af tallene . Forudsat at man kan skrive $\xi$ ${\displaystyle x_{0},\ldots ,x_{n))$ $M_{n+1}=\sup _{x\in [x_{0},x_{n}]}|f^{(n+1)}(x)|$

|f(x)-L(x)|\leqslant {\dfrac {M_{n+1}}{(n+1)!}}|(x-x_{0})\ldots (x- x_{n})|.

Unikhed

Der er et enkelt polynomium af grad, der ikke overstiger , der tager de givne værdier på et givet punkt. $n$ $n+1$

Bevis

Antag, at der er to forskellige polynomier af grad på de fleste , for hvilket det er rigtigt, at for par af tal, hvor alle er forskellige, Overvej polynomiet . Hvis vi erstatter ( ) i det, får vi det . Således har polynomiet rødder, og de er alle forskellige. Derfor , da et polynomium ikke-nul af grad højst har rødder. Derfor ,. ■ ■ $P(x)$ $Q(x)$ $n$ $n+1$ $(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n}),$ $x_{j}$ $P(x_{j})=Q(x_{j})=y_{j}.$ $L(x)=P(x)-Q(x)$ $x_{j}$ $0\leq j\leq n$ $L(x_{j})=P(x_{j})-Q(x_{j})=y_{j}-y_{j}=0$ $L(x)$ $n+1$ $L(x)\equiv 0$ $n$ $n$ $P(x)=Q(x)$

Dette udsagn er en generalisering af det faktum, at der kun er én linje gennem to punkter.

Fra et lineært algebra synspunkt

Det unikke ved interpolationspolynomiet kan også ses fra SLAE 's synspunkt . Overvej et ligningssystem . Det er udtrykkeligt skrevet som ${\displaystyle P(x_{0})=y_{0},P(x_{1})=y_{1},\dots ,P(x_{n})=y_{n))$

{\begin{cases}a_{0}+a_{1}x_{0}+a_{2}x_{0}^{2}+\dots +a_{n}x_{0}^{n }=y_{0},\\a_{0}+a_{1}x_{1}+a_{2}x_{1}^{2}+\dots +a_{n}x_{1}^{n }=y_{1},\\\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots ,\\a_{0}+a_{1}x_{n}+ a_{2}x_{n}^{2}+\dots +a_{n}x_{n}^{n}=y_{n}\\\end{cases}}

Det kan omskrives som et ligningssystem med en ukendt vektor : $Xa=y$ $a=(a_{0},a_{1},\dots,a_{n})$

{\begin{bmatrix}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_ {1}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n}\\ \end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\\vdots \\a_{n}\end{bmatrix}}={\begin{bmatrix}y_{0}\ \y_{1}\\\vdots \\y_{n}\end{bmatrix}}

Matrixen i et sådant system er Vandermonde-matricen, og dens determinant er . Følgelig, hvis alle punkter er forskellige, så er matrixen ikke degenereret, og systemet har en unik løsning. $x$ $\prod \limits _{i<j}(x_{i}-x_{j})$ ${\displaystyle x_{0},x_{1},\dots ,x_{n))$

Med hensyn til den kinesiske restsætning

Ifølge Bezouts sætning er resten af divisionen med . Hele systemet kan således opfattes som et sammenligningssystem: $P(x)$ $(xa)$ $P(a)$

{\begin{cases}P(x)\equiv y_{0}{\pmod {x-x_{0}}},\\P(x)\equiv y_{1}{\pmod {x- x_{1}}},\\\dots ,\\P(x)\equiv y_{n}{\pmod {x-x_{n}}},\\\end{cases}}

Ifølge den kinesiske restsætning har et sådant system en unik løsning modulo , det vil sige, at et givet system højst entydigt bestemmer et gradspolynomium . En sådan repræsentation af et polynomium i form af sæt af rester over moduler af monomialer svarer til repræsentationen af et tal i form af rester fra opdeling i simple moduler i systemet af restklasser . I dette tilfælde kan en eksplicit formel for Lagrange-polynomiet også opnås i overensstemmelse med formlerne for den kinesiske sætning : , hvor og . $(x-x_{0})(x-x_{1})\dots (x-x_{n})$ $n$ ${\textstyle P(x)=\sum \limits _{i=0}^{n}y_{i}M_{i}M_{i}^{-1))$ $M_{i}=\prod \limits _{j\neq i}(x-x_{j})$ $M_{i}^{-1}=\prod \limits _{j\neq i}(x-x_{j})^{-1}{\pmod {x-x_{i))}= \prod \limits _{j\neq i}(x_{i}-x_{j})^{-1}$