Vizualizare sursă pentru „Polinomul de interpolare Lagrange”

[[Image:Lagrange polynomial.svg|thumb|Polinomul de interpolare Lagrange pentru 4 puncte:  <font color=#b30000>((&minus;9,&nbsp;5)</font>, <font color=#0000b3>(&minus;4,&nbsp;2)</font>, <font color=#00b300>(&minus;1,&nbsp;&minus;2)</font>, <font color=#b3b300>(7,&nbsp;9)</font>), ''L''(''x''), care este suma polinoamelor de bază ''scalate'' <font color=#b30000>y<sub>0</sub>''l''<sub>0</sub>(''x'')</font>, <font color=#0000b3>y<sub>1</sub>''l''<sub>1</sub>(''x'')</font>, <font color=#00b300>y<sub>2</sub>''l''<sub>2</sub>(''x'')</font> and <font color=#b3b300>y<sub>3</sub>''l''<sub>3</sub>(''x'')</font>.  
Polinomul de interpolare trece prin toate cele 4 puncte, iar fiecare polinom scalat de bază trece prin punctul său de control respectiv, în cazul în care este 0, unde ''x'' corespunde celorlalte 3 puncte. Codul Matlab pentru acest exemplu este disponibil în  <ref>{{Citation |publisher=Stack Overflow |language=en |title=matlab - Lagrange interpolation method |url=http://www.stackoverflow.com/questions/11029615/lagrange-interpolation-method/11552763}}</ref>.]]

==Definiție==
Fie un set de ''k''&nbsp;+&nbsp;1 puncte de date, diferite între ele:
:<math>(x_0, y_0),\ldots,(x_j, y_j),\ldots,(x_k, y_k)</math>

'''Polinomul de interpolare Lagrange''' este combinația liniară
:<math>L(x) := \sum_{j=0}^{k} y_j \ell_j(x)</math>
de polinoame Lagrange de bază
:<math>\ell_j(x) := \prod_{\begin{smallmatrix}0\le m\le k\\ m\neq j\end{smallmatrix}} \frac{x-x_m}{x_j-x_m} = \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)}.</math>

Deși numit după [[Joseph Louis Lagrange]] în 1795, a fost descoperit pentru prima data în 1779 de către [[Edward Waring]] și a fost publicat în 1783 de [[Leonhard Euler]].

Având în vedere ipoteza inițială că <math> x_i </math> sunt diferite între ele, această expresie este întotdeauna [[expresie bine definită|bine definită]].

Se verifică imediat că polinomul interpolează corect funcția, adică: 
<math> P(x_i) </math>=<math> y_i \qquad i=0,\ldots,k</math>, pentru orice i=1..n.

==Exemple==
===1===
[[Image:lagrangeInterp.png|thumb|300px|Polinomul de interpolare al funcției tangentă]]
Să găsim o formulă de interpolare pentru funcția ''f''(''x'')&nbsp;=&nbsp;tan(''x'') dată de următoarele seturi de valori:

: <math>
\begin{align}
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{align}
</math>

Polinoamele de bază sunt:
:<math>\ell_0(x)={x - x_1 \over x_0 - x_1}\cdot{x - x_2 \over 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)</math>

:<math>\ell_1(x) = {x - x_0 \over x_1 - x_0}\cdot{x - x_2 \over x_1 - x_2}\cdot{x - x_3 \over x_1 - x_3}\cdot{x - x_4 \over x_1 - x_4}
             = {} -{8\over 243} x (2x-3)(2x+3)(4x-3)</math>

:<math>\ell_2(x)={x - x_0 \over x_2 - x_0}\cdot{x - x_1 \over 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) </math>

:<math>\ell_3(x)={x - x_0 \over x_3 - x_0}\cdot{x - x_1 \over 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)</math>

:<math>\ell_4(x)={x - x_0 \over x_4 - x_0}\cdot{x - x_1 \over 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).</math>

Deci polinomul de interpolare este:

:<math> \begin{align}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{align} </math>

===2===
Să interpolăm funcția ''f''(''x'')&nbsp;=&nbsp;''x''<sup>2</sup> pe domeniul 1&nbsp;?&nbsp;''x''&nbsp;?&nbsp;3, prin următoarele 3 puncte:

: <math>
\begin{align}
x_0 & = 1 & & & f(x_0) & = 1 \\
x_1 & = 2 & & & f(x_1) & = 4 \\
x_2 & = 3 & & & f(x_2) & =9.
\end{align}
</math>

Polinomul este:
:<math> \begin{align}
L(x) &= {1}\cdot{x - 2 \over 1 - 2}\cdot{x - 3 \over 1 - 3}+{4}\cdot{x - 1 \over 2 - 1}\cdot{x - 3 \over 2 - 3}+{9}\cdot{x - 1 \over 3 - 1}\cdot{x - 2 \over 3 - 2} \\[10pt]
&= x^2.
\end{align} </math>

===3===
Să interpolăm funcția ''f''(''x'')&nbsp;=&nbsp;''x''<sup>3</sup> pe domeniul 1&nbsp;<&nbsp;''x''&nbsp;<&nbsp;3, prin punctele:
{| cellpadding=10px
|-
| <math>x_0=1\,</math>  || <math>f(x_0)=1\,</math>
|-
| <math>x_1=2\,</math> || <math>f(x_1)=8\,</math>
|-
| <math>x_2=3\,</math>     || <math>f(x_2)=27\,</math>
|}

Polinomul este:
:<math> \begin{align}
L(x) &= {1}\cdot{x - 2 \over 1 - 2}\cdot{x - 3 \over 1 - 3}+{8}\cdot{x - 1 \over 2 - 1}\cdot{x - 3 \over 2 - 3}+{27}\cdot{x - 1 \over 3 - 1}\cdot{x - 2 \over 3 - 2} \\[8pt]
&=  6x^2 - 11x + 6.
\end{align} </math>

== Interpolarea baricentrică ==

[[File:Runge's phenomenon in Lagrange polynomials.svg|thumb|upright=2|Exemplu de divergență  al polinomului de interpolare Lagrange]]
Forma Lagrange de interpolare polinomului arată caracterul liniar al polinomului de interpolare și unicitatea acestui polinom. De aceea, este de preferat în probe și argumente teoretice. 
Dar, după cum se poate observa din construcții, de fiecare dată când un nod ''x''<sub>''k''</sub> se modifică, toate polinoame Lagrange de bază trebuie să fie recalculate. O formă mai bună a polinomului de interpolare în practică este forma baricentrică de interpolare Lagrange formula Newton a polinomului.

Utilizând

:<math>\ell(x) = (x - x_0)(x - x_1) \cdots (x - x_k)</math>

putem rescrie polinoamele de bază Lagrange ca

:<math>\ell_j(x) = \frac{\ell(x)}{x-x_j} \frac{1}{\prod_{i=0,i \neq j}^k(x_j-x_i)}</math>

sau, prin definirea '''ponderilor baricentrice''' <ref>Jean-Paul Berrut, [[Lloyd Nicholas Trefethen|Lloyd N. Trefethen]], ''Barycentric Lagrange Interpolation'', vol. 46,  p.501-517</ref>

:<math>w_j = \frac{1}{\prod_{i=0,i \neq j}^k(x_j-x_i)}</math>

putem scrie pur și simplu

:<math>\ell_j(x) = \ell(x)\frac{w_j}{x-x_j}</math>

care este denumit în mod obișnuit ca '''prima formă''' a  formulei de interpolare baricentrică.

Avantajul este că această reprezentare polinomul de interpolare poate fi acum evaluat ca
:<math>L(x) = \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j}y_j</math>

care, în cazul în care ponderile <math> w_j </math> au fost pre-calculate, are nevoie doar de <math> \ mathcal O (n) </math> (operații de evaluare <math> \ell (x) </math> și ponderile <math> w_j / (x-x_j) </math>), spre deosebire de <math>\mathcal O(n^2)</math> pentru evaluarea polinoamelor Lagrange de bază <math> \ ell_j (x) </math> individual.

Formula de interpolare baricentrică poate fi, de asemenea, ușor de actualizat pentru a include un nod nou <math>x_{k+1}</math> prin împărțirea nodurilor <math>w_j</math>, <math>j=0 \dots k</math> la<math>(x_j - x_{k+1})</math> și construirea noului <math>w_{k+1}</math> ca mai sus.

Putem simplifica și mai mult prima formă prin luarea în considerare prima interpolare baricentrică a funcției constante <math>g(x)\equiv 1</math>:

:<math>g(x) = \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j}.</math>

Împărțirea <math>L(x)</math> la <math>g(x)</math> nu modifică interpolarea, dar conduce la rezultatul

:<math>L(x) = \frac{\sum_{j=0}^k \frac{w_j}{x-x_j}y_j}{\sum_{j=0}^k \frac{w_j}{x-x_j}}</math>

care este menționat ca '''forma a doua'''  sau''' adevarata forma a formulei de interpolare baricentrică'''. Această formă are avantajul că <math>\ell(x)</math> nu trebuie să fie evaluate pentru fiecare evaluare a <math> L(x) </math>.

==Referințe==
<references/>
===Bibliografie===
*Constantin Ilioi, ''Probleme de optimizare și algoritmi de aproximare a soluțiilor'', Editura Academiei Republicii Socialiste România, București, 1980. 
== Legături externe ==
* www.utgjiu.ro/math/mbuneci/book/mn2009.pdf
* http://cs.upm.ro/~bela.finta/.files/carti/Numerika.pdf {{Webarchive|url=https://web.archive.org/web/20120907085840/http://cs.upm.ro/~bela.finta/.files/carti/Numerika.pdf |date=2012-09-07 }}

[[Categorie:Analiză numerică]]