Interpolazione newtoniana

In analisi numerica , l' interpolazione newtoniana , dal nome di Isaac Newton , è un metodo di interpolazione polinomiale che consente di ottenere il polinomio di Lagrange come combinazione lineare di polinomi della " base newtoniana".

A differenza dell'interpolazione Hermite, ad esempio, questo metodo differisce dall'interpolazione lagrangiana solo per il modo in cui viene calcolato il polinomio, il polinomio di interpolazione risultante è lo stesso. Per questo motivo parliamo piuttosto anche della forma di Newton del polinomio di Lagrange.

Definizione

dato punti $k + 1$

(x_ {0}, y_ {0}), \ ldots, (x_ {k}, y_ {k})

(gli x j tutti distinti da 2 a 2), l'interpolazione polinomiale in una base di Newton è una combinazione lineare di polinomi appartenenti a questa base

{\ displaystyle N (x) = \ sum _ {j = 0} ^ {k} a_ {j} n_ {j} (x)}

con i polinomi di Newton definiti come segue

{\ displaystyle n_ {j} (x) = \ prod _ {0 \ leq i <j} (x-x_ {i}) \ qquad j = 0, \ ldots, k}

(in particolare , il prodotto vuoto ) ${\ displaystyle n_ {0} = 1}$

e i coefficienti uguali alle differenze divise :

{\ displaystyle a_ {j} = [y_ {0}, \ ldots, y_ {j}].}

In sintesi :

Il polinomio di interpolazione di Newton associato ai punti è definito da: $N (x)$ $k + 1$ $(x_ {0}, y_ {0}), \ ldots, (x_ {k}, y_ {k})$

{\ displaystyle N (x) = [y_ {0}] + [y_ {0}, y_ {1}] (x-x_ {0}) + \ ldots + [y_ {0}, \ ldots, y_ {k }] (x-x_ {0}) \ ldots (x-x_ {k-1}).}

Teorema di interpolazione di Newton

Il seguente teorema giustifica il nome di "polinomio di interpolazione" per : $NON$

Questo polinomio è uguale al polinomio di interpolazione di Lagrange associato ai punti, cioè all'unico polinomio di grado minore o uguale a soddisfare: $NON$ $k + 1$ $L$ $K$ ${\ displaystyle \ forall i \ in \ {0, \ dots, k \} \ quad L (x_ {i}) = y_ {i}.}$

Dimostrazione

Mostriamo prima, per induzione su , che il coefficiente di grado di è uguale a . Per il punto, questa uguaglianza è immediata. Supponiamo che sia vero per i punti e denotiamo il polinomio di interpolazione associato ai primi punti (con indici to ) e quello associato all'ultimo (con indici to ). Allora, $K$ $K$ $L$ ${\ displaystyle [y_ {0}, \ dots, y_ {k}]}$ $1$ $K$ $P$ $K$ ${\ displaystyle 0}$ $k-1$ $Q$ $K$ $1$ $K$

{\ displaystyle L (x) = {\ frac {(x-x_ {0}) Q (x) - (x-x_ {k}) P (x)} {x_ {k} -x_ {0}}} }

quindi (per ipotesi di induzione) il coefficiente di grado di è effettivamente uguale a . $K$ $L$ ${\ displaystyle {\ frac {[y_ {1}, \ dots, y_ {k}] - [y_ {0}, \ dots, y_ {k-1}]} {x_ {k} -x_ {0}} } = [y_ {0}, \ dots, y_ {k}]}$

Con le stesse annotazioni, mostriamo ora, ancora una volta per induzione , questo . Per il punto, questa uguaglianza è immediata. Supponiamo che sia vero per i punti. è di grado minore o uguale ae zero in e il suo coefficiente di grado è uguale a quello di quindi, secondo quanto sopra, a . Pertanto, è uguale a , cioè (per ipotesi di induzione) a . $K$ ${\ displaystyle L = N}$ $1$ $K$ ${\ displaystyle LP}$ $K$ ${\ displaystyle x_ {0}, \ dots, x_ {k-1}}$ $K$ $L$ ${\ displaystyle [y_ {0}, \ dots, y_ {k}]}$ $L (x)$ ${\ displaystyle P (x) + [y_ {0}, \ ldots, y_ {k}] (x-x_ {0}) \ ldots (x-x_ {k-1})}$ $N (x)$

Nota

Il polinomio di interpolazione di Lagrange appartiene allo spazio vettoriale dei polinomi di grado minore o uguale a , di cui la "base di Newton" sopra definita è una base. Secondo il teorema di interpolazione di Newton, le coordinate di in sono , dove sono le differenze divise. Un metodo ingenuo per calcolare direttamente le coordinate di in sarebbe risolvere il sistema di equazioni lineari $L$ $K$ ${\ displaystyle n: = (n_ {0}, \ dots, n_ {k})}$ $L$ $non$ ${\ displaystyle (a_ {0}, \ dots, a_ {k})}$ $avere}$ $L$ $non$

{\ displaystyle \ sum _ {j = 0} ^ {i} a_ {j} n_ {j} (x_ {i}) = y_ {i} \ qquad i = 0, \ dots, k}

che si riscrive

{\ displaystyle {\ begin {pmatrix} 1 &&&& 0 \\ 1 & x_ {1} -x_ {0} &&& \\ 1 & x_ {2} -x_ {0} & (x_ {2} -x_ {0} ) (x_ {2} -x_ {1}) && \\\ vdots & \ vdots && \ ddots & \\ 1 & x_ {k} -x_ {0} & \ ldots & \ ldots & \ prod _ {j = 0} ^ {k-1} (x_ {k} -x_ {j}) \ end {pmatrix}} {\ begin {pmatrix} a_ {0} \\\ vdots \\ a_ {k} \ end {pmatrix} } = {\ begin {pmatrix} y_ {0} \\\ vdots \\ y_ {k} \ end {pmatrix}}.}

Dato che questo sistema è sfalsato e triangolare ancora più basso , potremmo risolverlo passo dopo passo, partendo dalla retta che ci darebbe poi per , il calcolo di ci permetterebbe di dedurre , e così via fino a . ${\ displaystyle i = 0}$ $a_0$ $io = 1$ $a_0$ $a_1$ ${\ displaystyle i = k}$

Applicazioni

Come mostra la definizione delle differenze divise , è possibile aggiungere ulteriori punti per creare un nuovo polinomio di interpolazione senza ricalcolare i coefficienti. Inoltre, se si modifica un punto, è inutile ricalcolare tutti i coefficienti. Un altro vantaggio è che se x i sono distribuiti uniformemente, il calcolo delle differenze divise diventa molto più veloce. Pertanto, la forma di Newton per il polinomio di interpolazione è preferita a quella di Lagrange o anche al metodo ingenuo sopra, per ragioni pratiche.

Il teorema di interpolazione di Newton ci permette di dimostrare che qualsiasi funzione polinomiale è uguale alla sua serie di Newton .

Vedi anche

Link esterno

Interpolazione polinomiale di tipo Newton (sic) e differenze divise su math-linux.com

Credito dell'autore

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Polinomio di Newton " ( vedere l'elenco degli autori ) . <img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">