Polinom i Lagranzhit

Ky imazh tregon, për katër pika ( ( − 9, 5), ( − 4, 2), ( − 1, − 2), (7, 9) ), polinomi i interpolimit (kubik) $L(x)$ (i ndërprerë, i zi), i cili është shuma e polinomeve të bazës të shkallëzuara y ₀ ℓ ₀ ( x ), y ₁ ℓ ₁ ( x ), y ₂ ℓ ₂ ( x ) dhe y ₃ ℓ ₃ ( x ) . Polinomi i interpolimit kalon nëpër të katër pikat e kontrollit, dhe çdo polinom i bazës i shkallëzuar kalon nëpër pikën e tij përkatëse të kontrollit dhe është 0 ku x përkon me tre pikat e tjera të kontrollit.

Në analizën numerike, polinomi interpolues i Lagranzhit është polinomi unik i shkallës më të ulët që interpolon një bashkësi të caktuar të dhënash.

Jepet një bashkësi të dhënash në formën e çifteve koordinative $(x_j,y_j)$ me $0\le j\le k,$ të $x_j$ quhen nyje dhe $y_j$ quhen vlera . Polinomi i Lagranzhit $L(x)$ ka shkallë $\le k$ dhe merr çdo vlerë në nyjen përkatëse, $L(x_j)=y_j.$

Edhe pse i emërtuar sipas Jozef-Luis Lagranzhit, i cili e botoi atë në 1795, metoda u zbulua për herë të parë në 1779 nga Edward Waring . Është gjithashtu një pasojë e lehtë e një formule të botuar në 1783 nga Leonhard Euleri .

Përdorimet e polinomeve të Lagranzhit përfshijnë metodën Newton-Cotes të integrimit numerik, skemën e ndarjes së fshehtë të Shamirit në kriptografi dhe korrigjimin e gabimit Reed-Solomon në teorinë e kodimit .

Për nyjet e barazlarguara, interpolimi i Lagranzhit është i ndjeshëm ndaj dukurisë së luhatjes së madhe të Runges .

Përkufizimi

Duke pasur parasysh një bashkësi prej $k+1$ nyjesh $\{x_0,x_1,\dots ,x_k\}$, të cilat duhet të jenë të gjitha të veçanta, $x_j\ne x_m$ për indekset $j\ne m$, baza e Lagranzhit për polinomet e shkallës $\le k$ për këto nyje është bashkësia e polinomeve $\{{\ell }_0(x),{\ell }_1(x),\dots ,{\ell }_k(x)\}$ secila e shkallës $k$ të cilat marrin vlera ${\ell }_j(x_m)=0$ nëse $m\ne j$ dhe ${\ell }_j(x_j)=1$ . Duke përdorur deltën e Kronecker, kjo mund të shkruhet ${\ell }_j(x_m)={\delta }_{jm}.$ Çdo polinom bazë mund të përshkruhet në mënyrë të shkoqur nga produkti:$$\begin{array}{cc}{\ell }_j(x)& =\frac{(x-x_0)}{(x_j-x_0)}\cdots \frac{(x-x_{j-1})}{(x_j-x_{j-1})}\frac{(x-x_{j+1})}{(x_j-x_{j+1})}\cdots \frac{(x-x_k)}{(x_j-x_k)}\\ & =\prod _{\begin{array}{c}0\le m\le k\\ m\ne j\end{array}}\frac{x-x_m}{x_j-x_m}.\end{array}$$Vini re se numëruesi $\prod _{m\ne j}(x-x_m)$ ka $k$ rrënjë në nyjet $\{x_m{\}}_{m\ne j}$ ndërsa emëruesi $\prod _{m\ne j}(x_j-x_m)$ shkallëzon polinomin që rezulton në mënyrë që ${\ell }_j(x_j)=1.$

Polinomi interpolues i Lagranzhit për ato nyje përmes vlerave përkatëse $\{y_0,y_1,\dots ,y_k\}$ është kombinimi linear:$$L(x)=\sum _{j=0}^k{y}_j{\ell }_j(x).$$Çdo polinom i bazës ka shkallë $k$, pra shuma $L(x)$ ka shkallë $\le k$, dhe interpolon të dhënat sepse $L(x_m)={\sum }_{j=0}^k{y}_j{\ell }_j(x_m)={\sum }_{j=0}^k{y}_j{\delta }_{mj}=y_m.$

Polinomi interpolues është unik.

Një këndvështrim nga algjebra lineare

Zgjidhja e një problemi interpolimi çon në një problem të algjebrës lineare që arrin në të anasjelltën e një matrice. Duke përdorur një bazë monomiale standarde për polinomin tonë të interpolimit $L(x)={\sum }_{j=0}^k{x}^j{m}_j$, duhet të marrim të anasjelltën e matricëns Vandermonde $(x_i{)}^j$ te zgjidhesh $L(x_i)=y_i$ për koeficientët $m_j$ të $L(x)$ . Duke zgjedhur një bazë më të mirë, bazën e Lagranzhit, $L(x)={\sum }_{j=0}^k{l}_j(x)y_j$, ne thjesht marrim matricën identitet, ${\delta }_{ij}$, e cila është e anasjellta e saj: baza e Lagranzhit inverton automatikisht analogun e matricës Vandermonde.

Shembull

Ne dëshirojmë të interpolojmë $f(x)=x^2$ mbi segmentin $1\le x\le 3$ në tre nyjet Stampa:Nowrap

$\begin{array}{cccccc}{x}_0& =1,& & & y_0=f(x_0)& =1,\\ x_1& =2,& & & y_1=f(x_1)& =4,\\ x_2& =3,& & & y_2=f(x_2)& =9.\end{array}$

Polinomi i nyjës, $\ell$ , është

$\ell (x)=(x-1)(x-2)(x-3)=x^3-6x^2+11x-6.$

Peshat baricentrike janë

$\begin{array}{cc}{w}_0& =(1-2{)}^{-1}(1-3{)}^{-1}=\frac{1}{2},\\ w_1& =(2-1{)}^{-1}(2-3{)}^{-1}=-1,\\ w_2& =(3-1{)}^{-1}(3-2{)}^{-1}=\frac{1}{2}.\end{array}$

Polinomet e bazës së Lagranzhit janë

$\begin{array}{cc}{\ell }_0(x)& =\frac{x-2}{1-2}\cdot \frac{x-3}{1-3}=\frac{1}{2}{x}^2-\frac{5}{2}x+3,\\ {\ell }_1(x)& =\frac{x-1}{2-1}\cdot \frac{x-3}{2-3}=-x^2+4x-3,\\ {\ell }_2(x)& =\frac{x-1}{3-1}\cdot \frac{x-2}{3-2}=\frac{1}{2}{x}^2-\frac{3}{2}x+1.\end{array}$

Polinomi interpolues i Lagranzhit është:

$\begin{array}{cc}L(x)& =1\cdot \frac{x-2}{1-2}\cdot \frac{x-3}{1-3}+4\cdot \frac{x-1}{2-1}\cdot \frac{x-3}{2-3}+9\cdot \frac{x-1}{3-1}\cdot \frac{x-2}{3-2}\\ & =x^2.\end{array}$

Në formën (e dytë) baricentrike,

$L(x)=\frac{\sum _{j=0}^2\frac{w_j}{x-x_j}{y}_j}{\sum _{j=0}^2\frac{w_j}{x-x_j}}=\frac{\frac{\frac{1}{2}}{x-1}+\frac{-4}{x-2}+\frac{\frac{9}{2}}{x-3}}{\frac{\frac{1}{2}}{x-1}+\frac{-1}{x-2}+\frac{\frac{1}{2}}{x-3}}.$

Shiko gjithashtu

• Algoritmi i Nevilit
• Forma e Njutonit të polinomit të interpolimit
• Polinomi Bernshtajn
• Teorema e Karlsonit
• Konstantja e Lebegut (interpolimi)
• Sistemi Chebfun
• Tabela e serive Njutoniane
• Kovarianti i Frobeniusit
• Formula e Silvesterit
• Koeficienti i diferencës së fundme
• Interpolimi i Hermitit