Altre scritture dei polinomi interpolanti

Scrittura dei polinomi interpolanti in funzione dei polinomi nodali

Definizione 5.1

Definisco polinomio nodale

$$W_{n+1}(x)=\prod _{i=0}^{n}(x-x_{i}).$$

$$W_{n+1}(x) = \prod_{i=0}^n (x-x_i).$$

 

Cerchiamo una scrittura equivalente dei polinomi interpolanti:

$$\sum _{i=0}^{n}y_{i}l_{i}=$$

$$\sum_{i=0}^n y_i l_i =$$

$$=\sum _{i=0}^{n}y_{i}{\frac {\prod _{i\neq j,j=0}^{n}(x-x_{j})}{\prod _{i\neq j,j=0}^{n}(x_{i}-x_{j})}}$$

$$=\sum_{i=0}^n y_i \frac{\prod_{i \neq j, j=0}^n (x-x_j)}{\prod_{i \neq j, j=0}^n (x_i-x_j)}$$

e tenendo conto dell'espressione di $w_{n+1}(x)$$w_{n+1}(x)$:

$$=\sum _{i=0}^{n}y_{i}{\frac {w_{n+1}(x)}{x-x_{i}}}*{\frac {1}{\prod _{j\neq i,j=1}^{n}(x_{i}-x_{j})}}$$

$$= \sum_{i=0}^n y_i \frac{w_{n+1}(x)}{x-x_i}*\frac{1}{\prod_{j \neq i, j=1}^n (x_i-x_j)}$$

Osservo che:

$$w_{n+1}(x)'=(\prod _{j=0}^{n}(x-x_{j}))'=\sum _{i=0}^{n}\prod _{j\neq i,j=0}^{n}(x-x_{j})$$

$$w_{n+1}(x)' = (\prod_{j=0}^n (x-x_j))' =\sum_{i=0}^n \prod_{j \neq i, j=0}^n (x-x_j)$$

e valutando in $x_{k}$$x_k$:

$$w_{n+1}(x_{k})'=\prod _{j\neq k,j=0}^{n}(x_{k}-x_{j})$$

$$w_{n+1}(x_k)' = \prod_{j \neq k, j=0}^n (x_k-x_j)$$

quindi, tornando all'espressione del polinomio interpolante:

$$\sum _{i}y_{i}l_{i}(x)=$$

$$\sum_i y_i l_i(x) =$$

$$=W_{n+1}(x)*\sum _{i=0}^{n}y_{i}{\frac {1}{x-x_{i}}}*{\frac {1}{w_{n+1}'(x_{i})}}$$

$$= W_{n+1}(x)*\sum_{i=0}^n y_i \frac1{x-x_i}*\frac{1}{w_{n+1}'(x_i)}$$

Considerazioni sui costi computazionali

Poniamo

$$p_{n}(x)=w_{n+1}(x)*\sum _{i=0}^{n}{\frac {z_{i}}{x-x_{i}}}$$

$$p_{n}(x)=w_{n+1}(x)*\sum _{i=0}^{n}{\frac {z_{i}}{x-x_{i}}}$$

dove $z_{i}={\frac {y_{i}}{\prod _{i\neq j,j=0}^{n}(x_{i}-x_{j})}}$$z_{i}={\frac {y_{i}}{\prod _{i\neq j,j=0}^{n}(x_{i}-x_{j})}}$.
Ci si chiede qual è il costo computazionale della valutazione di $p_{n}(x)$$p_n(x)$ in un $x$$x$ assegnato. Sono necessarie:

1. $n$$n$ sottrazioni per calcolare $x-x_{i}$$x-x_{i}$ (al denominatore)
2. $n^{2}/2$$n^{2}/2$ sottrazioni per calcolare gli $x_{i}-x_{j}$$x_{i}-x_{j}$ nella produttoria, e questo equivale a calcolare le entrate della matrice $L=(l_{ij})$$L=(l_{ij})$ con 0sulla diagonale principale, tale che $l_{ij}=-l_{ji}$$l_{ij}=-l_{ji}$.
3. $n^{2}$$n^2$ operazioni per calcolare gli $z_{i}$$z_i$, in particolare per calcolare ogni $z_{i}$$z_i$, una volta che gli $x_{i}-x_{j}$$x_{i}-x_{j}$ sono noti, sono necessari solo $n$$n$ prodotti. Siccome gli $z_{i}$$z_i$ sono $n$$n$ ho in totale $n^{2}$$n^2$ operazioni.
4. $n$$n$ addizioni (defivano dalla sommatoria) e $n$$n$ moltiplicazioni per calcolare ${\frac {z_{i}}{x-x_{i}}}$${\frac {z_{i}}{x-x_{i}}}$, divisione tra due numeri già noti,
5. $n$$n$ operazioni per la valutazione del polinomio nodale di cui già conosco i fattori.
   $$tot=n^{2}/2+n^{2}$$

   $$tot=n^{2}/2+n^{2}$$
   più una quantità trascurabile dell'ordine di $n$$n$ operazioni.

Mi chiedo quanto costa calcolare il polinomio interpolante in un nuovo punto ${\bar {x}}$$\bar x$, dopo aver effettuato il calcolo descritto sopra. Le operazioni riferite ai punti 2 e 3 (calcolo completo degli $z_{i}$$z_i$) sono indipendenti dal punto in cui si valuta il polinomio, e non vanno ripetute a ogni passaggio. Ci hanno quindi solo $2n$$2n$ operazioni additive e $2n$$2n$ moltiplicative. Rispetto alla risoluzione del sistema delle $n+1$$n+1$ equazioni nelle $n+1$$n+1$ incognite (come nella dimostrazione 1), dove la fattorizzazione LU richiede $n^{3}$$n^{3}$ operazioni, si risparmiano operazioni.

Supponiamo di aggiungere un nuovo punto $(x_{n+1},y_{n+1})$$(x_{n+1},y_{n+1})$ ai dati: si vuole calcolare un nuovo polinomio interpolante di grado $n+1$$n+1$.

Gli $z_{i}$$z_i$ sono già stati calcolati, si ha che il nuovo polinomio è:

$$p_{n+1}(x)=w_{n+2}(x)*[\sum _{i=0}^{n}({\frac {z_{i}^{(n+1)}}{x-x_{i}}})+{\frac {z_{n+1}^{(n+1)}}{x-x_{n+1}}}]$$

$$p_{n+1}(x)=w_{n+2}(x)*[\sum _{i=0}^{n}({\frac {z_{i}^{(n+1)}}{x-x_{i}}})+{\frac {z_{n+1}^{(n+1)}}{x-x_{n+1}}}]$$

$z_{i}^{(n+1)}={\frac {y_{i}}{\prod _{j=0}^{n}(x_{i}-x_{j})}}*{\frac {1}{x_{i}-x_{n+1}}}$$z_{i}^{(n+1)}={\frac {y_{i}}{\prod _{j=0}^{n}(x_{i}-x_{j})}}*{\frac {1}{x_{i}-x_{n+1}}}$, quindi

$$z_{i}^{(n+1)}={\frac {z_{i}^{(n)}}{x_{i}-x_{n+1}}}$$

$$z_{i}^{(n+1)}={\frac {z_{i}^{(n)}}{x_{i}-x_{n+1}}}$$

Inoltre

$$w_{n+2}(x)=w_{n+1}(x)*(x-x_{n+1})$$

$$w_{n+2}(x)=w_{n+1}(x)*(x-x_{n+1})$$

e si ricava che

$$p_{n+1}(x)=w_{n+1}(x)*(x-x_{n+1})*[\sum _{i=0}^{n}({\frac {z_{i}^{(n)}}{(x-x_{i})(x_{i}-x_{n+1})}})+{\frac {z_{n+1}^{(n+1)}}{x-x_{n+1}}}]$$

$$p_{n+1}(x)=w_{n+1}(x)*(x-x_{n+1})*[\sum _{i=0}^{n}({\frac {z_{i}^{(n)}}{(x-x_{i})(x_{i}-x_{n+1})}})+{\frac {z_{n+1}^{(n+1)}}{x-x_{n+1}}}]$$

quindi le operazioni totali in più, avendo già calcolato $p_{n}(x)$$p_{n}(x)$, sono una Sottrazione per $x-x_{n+1}$$x-x_{n+1}$, $n$$n$ sottrazioni per $x_{i}-x_{n+1}$$x_{i}-x_{n+1}$, $n$$n$ moltiplicazioni per $z_{i}^{(n+1)}$$z_{i}^{(n+1)}$, $n$$n$ addizioni per la sommatoria, $n$$n$ moltiplicazioni per $z_{i}^{n}/(x-x_{i})$$z_{i}^{n}/(x-x_{i})$, 2 operazioni per l'ultimo termine.

In totale ho $2n$$2n$ addizioni e $2n$$2n$ moltiplicazioni.

Forma di Newton

Il polinomio interpolante è unico ma ci sono diverse riscritture. La forma di Newton permette di calcolare i polinomi interpolanti aumentando le operazioni additive e diminuendo quelle moltiplicative.

Il polinomio interpolante

$$p_{n}(x)=\sum _{k=0}^{n}a_{k}*\phi _{k}(x)$$

$$p_n(x) = \sum_{k=0}^n a_k*\phi_k(x)$$

viene riscritto in funzione della base dei polinomi nodali, ponendo

$$\phi _{k}=\prod _{j=1}^{k}(x-x_{j})$$

$$\phi_k = \prod_{j=1}^k (x-x_j)$$

Gli $a_{k}$$a_k$ vengono posti uguali alla differenza divisa di ordine k.

Definizione 5.2

Si indica con $f[x_{0},\dots ,x_{k}]$$f[x_0,\dots,x_k]$ la differenza divisa di ordine $k$$k$ ($k+1$$k+1$ nodi). La differenza divisa si definisce induttivamente, ponendo:

$$f[x_{0}]=f(x_{0}){\hbox{per definizione}}$$

$$f[x_{0}]=f(x_{0}){\hbox{per definizione}}$$

$$f[x_{0},x_{1}]={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}\quad {\hbox{rapporto incrementale}}$$

$$f[x_{0},x_{1}]={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}\quad {\hbox{rapporto incrementale}}$$

$$f[x_{0},\dots ,x_{k}]={\frac {f[x_{1},\dots ,x_{k}]-f[x_{0},\dots ,x_{k-1}]}{x_{k}-x_{0}}}$$

$$f[x_{0},\dots ,x_{k}]={\frac {f[x_{1},\dots ,x_{k}]-f[x_{0},\dots ,x_{k-1}]}{x_{k}-x_{0}}}$$

 

Vogliamo dimostrare che

$$p_{n}(x)=f[x_{0}]+f[x_{0},x_{1}]*(x-x_{0})+f[x_{0},x_{1},x_{2}]*(x-x_{0})*(x-x_{1})+\dots +f[x_{0},x_{1},\dots ,x_{n})*(x-x_{0})*(x-x_{1})*(x-x_{n-1})$$

$$p_n(x) = f[x_0]+ f[x_0,x_1]*(x-x_0)+ f[x_0,x_1,x_2]*(x-x_0)*(x-x_1)+\dots+ f[x_0,x_1,\dots,x_n)*(x-x_0)*(x-x_1)*(x-x_{n-1})$$

è un polinomio interpolante, dimostriamo prima il lemma di Neville.

Lemma 5.1 (formula di Neville)

Dato $I=\{i_{1},\dots ,i_{k}\}$$I=\{i_1, \dots, i_k \}$ un insieme di indici, e definendo $p(i_{0},\dots ,i_{k})$$p(i_0, \dots, i_k)$ il polinomio valutato nei nodi $(x_{i_{j}},y_{i_{j}})$$(x_{i_j}, y_{i_j})$ per $j=0,\dots ,n$$j=0,\dots,n$, si ha che:

$$p_{k}(x)={\frac {(x-x_{i_{0}})*p_{k-1}(x)(i_{1},\dots ,i_{k})-(x-x_{i_{k}})*P_{k-1}(x)(i_{0},\dots ,i_{k-1})}{x_{i_{k}}-x_{i_{0}}}}$$

$$p_k(x)= \frac{(x-x_{i_0})*p_{k-1}(x)(i_1,\dots,i_k)-(x-x_{i_k})*P_{k-1}(x)(i_0,\dots,i_{k-1})}{x_{i_k}-x_{i_0}}$$

è un polinomio interpolante.

 

Dimostrazione

Il lemma dà una rappresentazione ricorsiva del polinomio interpolante.

1. Per calcolare l'espressione di $p(i_{0})$$p(i_0)$ si tiene conto che il termine $(x-x_{i_{0}})*p_{k-1}(i_{1},\dots ,i_{k})$$(x-x_{i_0})*p_{k-1}(i_1,\dots,i_k)$ è nullo, quindi rimane
   $$p(i_{0})={\frac {-(x-x_{i_{k}})*P_{k-1}(x_{i_{0}})(i_{0},\dots ,i_{k-1})}{x_{i_{k}}-x_{i_{0}}}}=p_{k-1}(x_{i_{0}})(i_{0},\dots ,i_{k-1})=y_{i_{0}}$$

   $$p(i_0) = \frac{-(x-x_{i_k})*P_{k-1}(x_{i_0})(i_0,\dots,i_{k-1})}{x_{i_k}-x_{i_0}} = p_{k-1}(x_{i_0})(i_0,\dots,i_{k-1}) = y_{i_0}$$
2. Valutando invece $p(i_{k})$$p(i_k)$ si annulla il secondo termine, e rimane:
   $$p(i_{k})={\frac {(x_{i_{k}}-x_{i_{0}})*p_{k-1}(i_{1},\dots ,i_{k})(x_{i_{k}})}{x_{i_{k}}-x_{i_{0}}}}=$$

   $$p(i_k) = \frac{(x_{i_k}-x_{i_0})*p_{k-1}(i_1, \dots, i_k)(x_{i_k})}{x_{i_k}-x_{i_0}} =$$
   $$p_{k-1}(i_{1},\dots ,i_{k})(x_{i_{k}})=y_{i_{k}}$$

   $$p_{k-1}(i_1,\dots, i_k)(x_{i_k}) = y_{i_k}$$
3. per un generico $j=1,2,\dots ,k-1$$j=1,2,\dots,k-1$, si ha:
   $$p(i_{j})=p(x_{i_{j}})={\frac {(x_{i_{j}}-x_{i_{0}})*p_{k-1}(i_{1},\dots ,i_{k})(x_{i_{j}})-(x_{i_{j}}-x_{i_{k}})*p_{k-1}(i_{0},\dots ,i_{k-1})(x_{i_{j}})}{x_{i_{k}}-x_{i_{0}}}}$$

   $$p(i_j) = p(x_{i_j}) = \frac{(x_{i_j}-x_{i_0})*p_{k-1}(i_1, \dots, i_k) (x_{i_j}) -(x_{i_j}-x_{i_k}) *p_{k-1}(i_0,\dots,i_{k-1}) (x_{i_j})}{x_{i_k}-x_{i_0}}$$
   $$={\frac {(x_{i_{j}}-x_{i_{0}})*y_{i_{j}}-(x_{i_{j}}-x_{i_{k}})*y_{i_{j}}}{x_{i_{k}}-x_{i_{0}}}}$$

   $$= \frac{(x_{i_j}-x_{i_0})*y_{i_j}-(x_{i_j}-x_{i_k})*y_{i_j}}{x_{i_k}-x_{i_0}}$$
   $$=y_{i_{j}}$$

   $$= y_{i_j}$$

Ho quindi verificato tutte le condizioni di interpolazione.

 

Teorema 5.3 (dimostrazione della forma di Newton)

$$p_{n}(x)=f[x_{0}]+f[x_{0},x_{1}]*(x-x_{0})+f[x_{0},x_{1},x_{2}]*(x-x_{0})*(x-x_{1})+\dots +f[x_{0},x_{1},\dots ,x_{n}]*(x-x_{0})*\dots *(x-x_{n-1})$$

$$p_n(x) = f[x_0]+ f[x_0,x_1]*(x-x_0)+ f[x_0,x_1,x_2]*(x-x_0)*(x-x_1)+\dots+f[x_0,x_1,\dots,x_n]*(x-x_0)*\dots*(x-x_{n-1})$$

è un polinomio interpolante.

 

Dimostrazione

Dimostro l'asserto per induzione.

1. Se $n=0$$n=0$, ottengo che $p_{0}(x)=f[x_{0}]=y_{0}$$p_0(x) = f[x_0]=y_0$, per definizione.
2. Per ipotesi induttiva, assumo che sia vero che il polinomio di Newton è il polinomio interpolante per il grado $n-1$$n-1$ rispetto alla base nodale, e lo dimostroper $n$$n$.
3. Supponiamo che $p_{n}(x)$$p_n(x)$ sia il polinomio interpolante di grado $n$$n$ rispetto alla base delle $\phi _{k}(x)$$\phi_k(x)$ date dai polinomi nodali di indice $k$$k$, allora possiamo scriverlo come:
   $$p_{n}(x)=p_{n-1}(x)+a_{n}*(x-x_{0})(x-x_{1})*\dots *(x-x_{n})$$

   $$p_n(x) = p_{n-1}(x)+a_n*(x-x_0)(x-x_1)*\dots*(x-x_n)$$
   voglio dimostrare che $a_{n}=f[x_{0},\dots ,x_{n}]$$a_n=f[x_0,\dots,x_n]$.Considero la formula di interpolazione di Neville. Allora
   $$p_{n}(x)={\frac {(x-x_{0})*p_{n-1}(1,\dots ,n)-(x-x_{n})*p_{n-1}(x)(0,\dots ,n-1)}{x_{n}-x_{0}}}$$

   $$p_n(x) = \frac{(x-x_0)*p_{n-1}(1,\dots,n)-(x-x_n)*p_{n-1}(x)(0,\dots,n-1)}{x_n-x_0}$$
   Dall'iptesi di induzione segue che:#*$p_{n-1}(1,\dots ,n)$$p_{n-1}(1,\dots,n)$ è il polinomio interpolante di grado $n-1$$n-1$ sui nodi $x_{1},\dots ,x_{n}$$x_1, \dots, x_n$, e per ipotesi di induzione il coefficiente $K_{1}$$K_1$ del termine di grado massimo è $f[x_{1},\dots ,x_{n}]$$f[x_1, \dots, x_n]$.#*$p_{n-1}(0,\dots ,n-1)$$p_{n-1}(0,\dots, n-1)$ è il polinomio interpolante rispetto ai nodi $(x_{0},\dots ,x_{n-1})$$(x_0,\dots,x_{n-1})$e il coefficiente $K_{2}$$K_2$ del suo termine di grado massimo è $f[x_{0},\dots ,x_{n-1}]$$f[x_0,\dots,x_{n-1}]$.Quindi, nel polinomio $p_{n}$$p_n$, in base alla formula di Neville e a quanto osservato, il coefficiente del termine di grado massimo è:
   $$K={\frac {1*K_{1}-1*K_{2}}{x_{k}-x_{0}}}$$

   $$K=\frac{1*K_1-1*K_2}{x_k-x_0}$$
   $$={\frac {1*f[x_{1},\dots ,x_{n}]-1*f[x_{0},\dots ,x_{n-1}]}{x_{n}-x_{0}}}=f[x_{0},\dots ,x_{n}]\quad {\hbox{per definizione}}$$

   $$= \frac{1*f[x_1, \dots, x_n]-1*f[x_0,\dots,x_{n-1}]}{x_n-x_0} = f[x_0,\dots,x_n] \quad \hbox{per definizione}$$

 

Osservazione 5.1

La differenza divisa non dipende dall'ordine dei punti, infatti, confrontando la scrittura del polinomio interpolante in forma di Newton e di Lagrange, per il coefficiente $a_{n}$$a_n$ si ha:

$$a_{n}=f[x_{0},\dots ,x_{n}]=\sum _{i=0}^{n}{\frac {f(x_{i})}{p_{n+1}'(x_{i})}}$$

$$a_n = f[x_0,\dots,x_n] = \sum_{i=0}^n \frac{f(x_i)}{p_{n+1}'(x_i)}$$

siccome nella sommatoria non c'è dipendenza dall'ordine dei punti, anche la differenza divisa non ne dipende in aritmetica esatta.

 

Algoritmo alla Neville

Considero i due vettori colonna $x=(x_{0},x_{1},\dots ,x_{n})$$x=(x_{0},x_{1},\dots ,x_{n})$ e $y=(f_{0},f_{1},\dots ,f_{n})$$y=(f_{0},f_{1},\dots ,f_{n})$ dove $f_{i}=f(x_{i})$$f_{i}=f(x_{i})$. L'algoritmo alla Neville porta alla costruzione di una matrice triangolare inferiore A, dove le entrate sono determinate nel seguente modo:

$${\rm {{for}(i=1:n-1)}}$$

$${\rm {{for}(i=1:n-1)}}$$

$${\rm {{for}(j=n:i)}}$$

$${\rm {{for}(j=n:i)}}$$

$$Y(j)=(y(j)-y(j-1))/(x(j)-x(j-i))\quad {\hbox{differenza divisa}}$$

$$Y(j)=(y(j)-y(j-1))/(x(j)-x(j-i))\quad {\hbox{differenza divisa}}$$

$${\rm {end}}$$

$${\rm {end}}$$

$${\rm {end}}$$

$${\rm {end}}$$

Ad esempio, presi 6 punti $(x_{0},x_{1},x_{2},x_{3},x_{4},x_{5}$$(x_{0},x_{1},x_{2},x_{3},x_{4},x_{5}$ la matrice che risulta dall'algoritmo di Neville è:

$${\begin{array}{ccccccc}x_{0}&f(x_{0})&&&&&\\x_{1}&f(x_{1})&f[x_{1},x_{0}]&0&0&0&0\\x_{2}&f(x_{2})&f[x_{2},x_{1}]&f[x_{2},x_{1},x_{0}]&0&0&0\\x_{3}&f(x_{3})&f[x_{3},x_{2}]&f[x_{3},x_{2},x_{1}]&f[x_{3},\dots ,x_{0}]&0&0\\x_{4}&f(x_{4})&f[x_{4},x_{3}]&f[x_{4},x_{3},x_{2}]&f[x_{4},\dots ,x_{1}]&f[x_{4},\dots ,x_{0}]&0\\x_{5}&f(x_{5})&f[x_{5},x_{4}]&f[x_{5},x_{4},x_{3}]&f[x_{5},\dots ,x_{2}]&f[x_{5},\dots ,x_{1}]&f[x_{5},x_{0}]\end{array}}$$

$${\begin{array}{ccccccc}x_{0}&f(x_{0})&&&&&\\x_{1}&f(x_{1})&f[x_{1},x_{0}]&0&0&0&0\\x_{2}&f(x_{2})&f[x_{2},x_{1}]&f[x_{2},x_{1},x_{0}]&0&0&0\\x_{3}&f(x_{3})&f[x_{3},x_{2}]&f[x_{3},x_{2},x_{1}]&f[x_{3},\dots ,x_{0}]&0&0\\x_{4}&f(x_{4})&f[x_{4},x_{3}]&f[x_{4},x_{3},x_{2}]&f[x_{4},\dots ,x_{1}]&f[x_{4},\dots ,x_{0}]&0\\x_{5}&f(x_{5})&f[x_{5},x_{4}]&f[x_{5},x_{4},x_{3}]&f[x_{5},\dots ,x_{2}]&f[x_{5},\dots ,x_{1}]&f[x_{5},x_{0}]\end{array}}$$

Il ciclo viene fatto a ritroso perché, calcolando la triangolare inferiore con la colonna partendo dal basso, si possono sovrascrivere direttamente i vettori. In questo algoritmo, l'entrata $A_{ij}$$A_{ij}$ diventa la differenza divisa tra gli elementi $A_{i,j-1}$$A_{i,j-1}$ e $A_{i-1,j-1}$$A_{i-1,j-1}$, per ogni j.

Numero di operazioni effettuate: per ogni elemento faccio una divisione e due sottrazioni, e la triangolare inferiore ha $n^{2}/2$$n^{2}/2$ elementi, quindi vengono effettuate $2*n^{2}/2=n^{2}$$2*n^{2}/2=n^{2}$ operazioni additive e $n^{2}/2$$n^{2}/2$ operazioni moltiplicative.

Algoritmo di Hornern

Per la valutazione del polinomio di Newton in un punto $x$$x$ si usa l'algoritmo di Horner: Ad esempio, nel caso di un polinomio di grado 3, il polinomio di Newton si rappresenta come:

$$p_{n}=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+a_{3}(x-x_{0})(x-x_{1})(x-x_{2})$$

$$p_{n}=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+a_{3}(x-x_{0})(x-x_{1})(x-x_{2})$$

Raccolgo $x-x_{0}$$x-x_{0}$ tra gli ultimi tre addendi:

$$p_{n}=a_{0}+(x-x_{0})*[a_{1}+a_{2}(x-x_{1})+a_{3}(x-x_{1})(x-x_{2})]$$

$$p_{n}=a_{0}+(x-x_{0})*[a_{1}+a_{2}(x-x_{1})+a_{3}(x-x_{1})(x-x_{2})]$$

Poi raccolgo $x-x_{1}$$x-x_{1}$ tra gli ultimi due addendi:

$$p_{n}=a_{0}+(x-x_{0})*[a_{1}+(x-x_{1})*[a_{2}+(x-x_{2})*a_{3}]]$$

$$p_{n}=a_{0}+(x-x_{0})*[a_{1}+(x-x_{1})*[a_{2}+(x-x_{2})*a_{3}]]$$

e per eseguire le operazioni parto dall'ultima parentesi. Tuttavia le operazioni necessarie per la valutazione del polinomio in un punto sono di più rispetto a quelle del polinomio di Lagrange.