Polinomio di Newton

Interpolazione e regressione

Isaac Newton, Philosophiae Naturalis Principia Mathematica, 1687

La funzione polinomiale di grado n passante per n+1 punti.
Le ascisse dei punti devono essere tutte diverse.

Grado = 1

$y = ax+b$

$P_0 = (x_0, y_0)$
$P_1 = (x_1, y_1)$

Grado = 2

$y = ax^2+bx+c$

$P_0 = (x_0, y_0)$
$P_1 = (x_1, y_1)$
$P_2 = (x_2, y_2)$

Grado = 3

$y = ax^3+bx^2+cx+d$

$P_0 = (x_0, y_0)$
$P_1 = (x_1, y_1)$
$P_2 = (x_2, y_2)$
$P_3 = (x_3, y_3)$

Grado = n

$y = ax^n+bx^{n-1}+\cdots$

$P_0 = (x_0, y_0)$
$P_1 = (x_1, y_1)$
…
$P_n = (x_n, y_n)$

Grado = 1

$\begin{cases}y_0 = a x_0 +b\\y_1 = a x_1 +b\end{cases}$

…

$\begin{cases}a = \displaystyle\frac{y_1-y_0}{x_1-x_0}\\\\b = \displaystyle\frac{y_0 x_1-y_1 x_0}{x_1-x_0}\end{cases}$

Versione 1

$y = \displaystyle\frac{y_1-y_0}{x_1-x_0} \cdot x + \displaystyle\frac{y_0 x_1-y_1 x_0}{x_1-x_0}$

Versione 2

$\displaystyle \frac{y-y_0}{y_1-y_0} = \displaystyle \frac{x-x_0}{x_1-x_0}$

oppure

$\displaystyle \frac{y-y_0}{x-x_0} = \displaystyle \frac{y_1-y_0}{x_1-x_0}$

Versione 3

$\displaystyle y = y_0 +\frac{y_1-y_0}{x_1-x_0}\cdot (x-x_0)$

oppure

$\displaystyle y = b_0 +b_1\cdot (x-x_0)$

oppure

$\displaystyle y = f_0 +f_1[x_0, x_1]\cdot (x-x_0)$

Grado = 2

Ripetendo tutti i passaggi si ripropone il problema di avere una formulazione di semplice memorizzazione…

$\displaystyle y = b_0 + b_1\cdot (x-x_0) + b_2\cdot (x-x_0)(x-x_1)$

$\displaystyle y = f_0 + f_1[x_0, x_1]\cdot (x-x_0) + f_2[x_0, x_1, x_2]\cdot (x-x_0)(x-x_1)$

Osserva

$f_0 = y_0$

$f_1[x_0, x_1]$ = $\displaystyle \frac{y_1-y_0}{x_1-x_0}$

$\displaystyle f_2[x_0, x_1, x_2]$ = $\displaystyle \frac{f[x_1, x_2]-f[x_0, x_1]}{x_2-x_0}$ = $\displaystyle \frac{\displaystyle\frac{y_2-y_1}{x_2-x_1} - \displaystyle\frac{y_1-y_0}{x_1-x_0}}{x_2-x_0}$

Dimostrazione

Deve essere $y(x_2) = y_2$ , quindi…

$y_2 = b_0 + b_1 (x_2-x_0) + b_2 (x_2-x_0)(x_2-x_1)$

$y_2 = y_0 + \displaystyle\frac{y_1-y_0}{x_1-x_0}(x_2-x_0) + b_2(x_2-x_0)(x_2-x_1)$

$y_2-y_0 = \displaystyle\frac{y_1-y_0}{x_1-x_0}(x_2-x_0) + b_2(x_2-x_0)(x_2-x_1)$

$\displaystyle\frac{(y_2-y_0)(x_1-x_0)}{(x_1-x_0)}$ = $\displaystyle\frac{(y_1-y_0)(x_2-x_0)}{(x_1-x_0)} + b_2 (x_2-x_0)(x_2-x_1)$

$b_2$ = $\displaystyle\frac{(y_2-y_0)(x_1-x_0) - (y_1-y_0)(x_2-x_0)}{(x_2-x_1)(x_1-x_0)} \cdot \displaystyle \frac{1}{(x_2-x_0)}$

$b_2$ = $\displaystyle\frac{(y_2-y_1)(x_1-x_0)+(y_1-y_0)(x_1-x_0) - (y_1-y_0)(x_2-x_1)- (y_1-y_0)(x_1-x_0)}{(x_2-x_1)(x_1-x_0)}$ $\cdot$ $\displaystyle \frac{1}{(x_2-x_0)}$

$b_2$ = $\displaystyle \frac{\displaystyle\frac{y_2-y_1}{x_2-x_1} - \displaystyle\frac{y_1-y_0}{x_1-x_0}}{x_2-x_0}$ = $\displaystyle \frac{f[x_1, x_2]-f[x_0, x_1]}{x_2-x_0}$ = $\displaystyle f_2[x_0, x_1, x_2]$

Grado = n

Lo schema generale è il polinomio di Newton

$\displaystyle y = b_0 + b_1 (x-x_0) + b_2 (x-x_0)(x-x_1)+ \dots + b_n (x-x_0)(x-x_1)\dots (x-x_n)$

$\displaystyle y = f_0 + f_1[x_0, x_1] (x-x_0) + f_2[x_0, x_1, x_2] (x-x_0)(x-x_1)$ + $\dots$ + $f_n[x_0, x_1, x_2, \dots , x_n]$ $(x-x_0)(x-x_1)\dots (x-x_n)$

Con

$f_0 = y_0$

$f_1[x_0, x_1]$ = $\displaystyle \frac{y_1-y_0}{x_1-x_0}$

$\displaystyle f_2[x_0, x_1, x_2]$ = $\displaystyle \frac{f[x_1, x_2]-f[x_0, x_1]}{x_2-x_0}$

…

$\displaystyle f_n[x_0, x_1, \dots , x_n]$ = $\displaystyle \frac{f[x_1, x_2, \dots , x_n]-f[x_0, x_1, \dots, , x_{n-1}]}{x_n-x_0}$