Formula interpolante di Lagrange

Il polinomio interpolante di Lagrange che si ottiene scegliendo come funzione base $\varphi_j(x),j=0,...,n$ le seguenti funzioni:
$L_j(x)=\frac{(x-x_0)(x-x_1)...(x-x_{i-1})(x-x_{i+1})...(x-x_n)}{(x_j-x_0)(x_j-x_1)...(x_j-x_{i-1})(x_j-x_{i+1})...(x_j-x_n)}=\prod\limits_{i=0,i \neq j}^n\frac{x-x_i}{x_j-x_i}$ per $j=0,1,...,n$ tali che $L_j(x_i)=\delta_{ji}=\begin{cases}1, & \mbox{if } i=j\\0, & \mbox{if } i\neq j\end{cases}$
Allora $p_n(x)=\sum\limits_{j=0}^n y_jL_j(x)$ dove $y_j=f(x_j)$ per $j=0,...,n$ e soddisfa le condizioni di interpolazione $p_n(x_i)=\sum\limits_{j=0}^n y_jL_j(x_i)=y_i, i=0,...,n$

Osservazioni.

1. Ciascun $L_j(x)$ coinvolto nella forma $p_n(x)=\sum\limits_{j=0}^n y_jL_j(x)$ è un polinomio di grano $n$.
2. al variare di $j$, gli $L_j(x)$ sono funzioni linearmente indipendenti
3. Le funzioni vanno scelte sempre diverse l'una dall'altra e su uno stesso intervallo $[a,b]$

Costo computazionale del polinomio di Lagrange.

Consideriamo il caso di 4 nodi $x_0, x_1, x_2, x_3$
$p_3(x)=\sum\limits_{j=0}^3y_jL_j(x)=y_0L_0(x)+y_1L_1(x)+y_2L_2(x)+y_3L_3(x)$
$4 = n+1$ moltiplicazioni

Stimiamo il costo del calcolo di un $L_j(x)$

$L_0(x)=\frac{(x-x_1)(x-x_2)(x-x_3)}{(x_0-x_1)(x_0-x_2)(x_0-x_3)}$

Sia al numeratore che al denominatore, contiamo $n-1=2$ moltiplicazioni. A queste $2n-2$ moltiplicazioni, sommiamo anche la divisione del numeratore per il denominatore.

Allora il costo di un polinomio $L_j(x)$ è di $2n-1$.

Dovendo valutare $4=n+1$ polinomi $L_j(x), j=0,1,2,3 \Rightarrow$ il costo totale di tutti gli $L_j(x)$ è:
$(n+1)(2n-1)=2n^2+n-1$

A queste $2n^2+n-1$ operazioni sommiamo gli $(n+1)$ prodotti tra ogni polinomio $L_j(x)$ e il suo relativo $y_j$, ottenendo quindi:
$2n^2+n-1+n+1 = 2n^2+2n \Rightarrow$ il costo computazionale del polinomio interpolante di Lagrange è dell'$O(2n^2)$