Lagrange-interpolationspolynom

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 25 november 2021; kontroller kräver 2 redigeringar .

Lagrange-interpolationspolynomet är ett polynom av minsta grad som antar givna värden vid en given uppsättning punkter, det vill säga löser interpolationsproblemet .

Definition

Låt ett par siffror ges där alla är olika. Det krävs att man konstruerar ett polynom av högst grad , för vilket . $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))$

Allmänt fall

J. L. Lagrange föreslog följande metod för att beräkna sådana polynom:

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

där de grundläggande polynomen bestäms av formeln $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}}}

För varje polynom har grad och $i=0,\ldots ,n$ $l_{i}$ $n$

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

Detta innebär att , som är en linjär kombination av polynom , har grad som mest och . $L(x)$ $l_{i}(x)$ $n$ $L(x_{i})=y_{i}$

Fallet med ekvidistanta interpolationsnoder

Låt interpolationsnoderna vara ekvidistanta, det vill säga de uttrycks i termer av startpunkten och något fast positivt värde enligt följande: $x_{j}$ $x_{0}$ $h$

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

Därav följer det

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

Genom att ersätta dessa uttryck i formeln för det grundläggande polynomet och ta ut produktens tecken i täljaren och nämnaren 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) \över h^{n}\prod \limits _ {i=0,\,i\neq j}^{n}(ji)}

Nu kan vi införa en förändring av variabel

y={{x-x_{0}} \över h}

och få ett uttryck för grundläggande polynom i termer av , som är byggt med enbart heltalsaritmetik : $y$

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

Dessa kvantiteter kallas Lagrange-koefficienter. De är inte beroende av eller på och kan därför beräknas i förväg och skrivas i form av tabeller. Nackdelen med detta tillvägagångssätt är den faktoriella komplexiteten hos täljaren och nämnaren, vilket kräver användning av lång aritmetik . $y_{0},\ldots ,y_{n}$ $h$

Resten

Om vi betraktar siffrorna som värdena för någon funktion vid noderna , är felet att interpolera funktionen med ett polynom lika 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}),

där är någon mittpunkt mellan det minsta och största av talen . Förutsatt att man kan skriva $\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})|.

Unikhet

Det finns ett enda polynom av grad som inte överstiger som tar de givna värdena vid en given punkt. $n$ $n+1$

Bevis

Antag att det finns två olika polynom av grad som mest , för vilket det är sant att för par av nummer där alla är olika, Betrakta polynomet . Genom att ersätta ( ) i det får vi det . Således har polynomet rötter och de är alla olika. Därför eftersom ett polynom som inte är noll av grad som mest har högst rötter. Därför, . ■ ■ $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)$

Detta påstående är en generalisering av det faktum att det bara finns en linje genom två punkter.

Ur linjär algebrasynpunkt

Det unika med interpolationspolynomet kan också ses från SLAE :s synvinkel . Betrakta ett ekvationssystem . Det är uttryckligen skrivet 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 skrivas om som ett ekvationssystem med en okänd 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}}

Matrisen i ett sådant system är Vandermonde-matrisen och dess determinant är . Följaktligen, om alla punkter är olika, är matrisen icke degenererad och systemet har en unik lösning. $X$ $\prod \limits _{i<j}(x_{i}-x_{j})$ ${\displaystyle x_{0},x_{1},\dots ,x_{n))$

När det gäller den kinesiska restsatsen

Enligt Bezouts teorem är resten av divisionen med . Således kan hela systemet uppfattas som ett system av jämförelser: $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}}

Enligt den kinesiska restsatsen har ett sådant system en unik lösning modulo , det vill säga ett givet system bestämmer unikt ett gradpolynom som mest . En sådan representation av ett polynom i form av uppsättningar av rester över moduler av monomials liknar representationen av ett tal i form av rester från uppdelning i enkla moduler i systemet av restklasser . I det här fallet kan en explicit formel för Lagrangepolynomet också erhållas i enlighet med formlerna för det kinesiska teoremet : , där och . $(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}$

Exempel

Låt oss hitta interpolationsformeln för att ha följande värden: $f(x)=\mathop {\mathrm {tg} } \nolimits (x)$

{\begin{aligned}x_{0}&=-1.5&&&&&f(x_{0})&=-14.1014\\x_{1}&=-0.75&&&&&f(x_{1})&=- 0.931596\ \x_{2}&=0&&&&&f(x_{2})&=0\\x_{3}&=0.75&&&&&f(x_{3})&=0.931596\\x_{4}&= 1.5&&&&&f(x_{4} })&=14,1014.\end{aligned}}

l_{0}(x)={x-x_{1} \över x_{0}-x_{1}}\cdot {x-x_{2} \över x_{0}-x_{2} }\cdot {x-x_{3} \over x_{0}-x_{3}}\cdot {x-x_{4} \over x_{0}-x_{4}}={1 \over 243} x(2x-3)(4x-3)(4x+3)

l_{1}(x)={x-x_{0} \över x_{1}-x_{0}}\cdot {x-x_{2} \över x_{1}-x_{2} }\cdot {x-x_{3} \över x_{1}-x_{3}}\cdot {x-x_{4} \över x_{1}-x_{4}}={}-{8 \ över 243}x(2x-3)(2x+3)(4x-3)

l_{2}(x)={x-x_{0} \över x_{2}-x_{0}}\cdot {x-x_{1} \över x_{2}-x_{1} }\cdot {x-x_{3} \over x_{2}-x_{3}}\cdot {x-x_{4} \over x_{2}-x_{4}}={3 \over 243} (2x+3)(4x+3)(4x-3)(2x-3)

l_{3}(x)={x-x_{0} \över x_{3}-x_{0}}\cdot {x-x_{1} \över x_{3}-x_{1} }\cdot {x-x_{2} \over x_{3}-x_{2}}\cdot {x-x_{4} \over x_{3}-x_{4}}=-{8 \over 243 }x(2x-3)(2x+3)(4x+3)

l_{4}(x)={x-x_{0} \över x_{4}-x_{0}}\cdot {x-x_{1} \över x_{4}-x_{1} }\cdot {x-x_{2} \over x_{4}-x_{2}}\cdot {x-x_{3} \over x_{4}-x_{3}}={1 \over 243} x(2x+3)(4x-3)(4x+3).

Skaffa sig

{\begin{aligned}L(x)&={1 \over 243}{\Big (}f(x_{0})x(2x-3)(4x-3)(4x+3)\ \&{}\qquad {}-8f(x_{1})x(2x-3)(2x+3)(4x-3)\\&{}\qquad {}+3f(x_{2})( 2x+3)(4x+3)(4x-3)(2x-3)\\&{}\qquad {}-8f(x_{3})x(2x-3)(2x+3)(4x+ 3) )\\&{}\qquad {}+f(x_{4})x(2x+3)(4x-3)(4x+3){\Big )}\\&=4.834848x^{3}- 1,477474x.\end{aligned}}

Applikationer

Numerisk integration

Låt funktionens värden vara kända vid vissa punkter. Sedan kan vi interpolera denna funktion med Lagrange-metoden: $f(x)$ $y_{i}=f(x_{i})$

f(x)\approx \sum _{i=0}^{n}f(x_{i})l_{i}(x).

Det resulterande uttrycket kan användas för att approximera beräkningen av den definitiva integralen av funktionen : $f$

\int \limits _{a}^{b}f(x)dx\approx \sum _{{i=0}}^{n}f(x_{i})\int \limits _{a}^{ b}l_{i}(x)dx

Värdena på integralerna av beror inte på och de kan beräknas i förväg med hjälp av sekvensen . $l_{i}$ $f(x)$ $x_{j}$

Litteratur

Berezin, I. S. , Zhidkov N. P. Beräkningsmetoder. Volym I. - 2:a uppl., stereotypisk - M .: Fizmatlit . 1962.

Länkar

M. A. Tynkevitj. Kapitel 7.6.1. Lagrange-interpolationspolynom // Numeriska analysmetoder . - Kemerovo, 2002. - ISBN 5-89070-042-1 . (inte tillgänglig länk)
A. G. Khovansky. Lagrangepolynom och deras tillämpningar . Videoföreläsning. VI Sommarskola "Modern Mathematics ", Dubna, 2006.