Interpolazione polinomiale

Polinomio di interpolazione di 7 ° grado

In matematica numerica , l'interpolazione polinomiale è la ricerca di un polinomio che attraversi esattamente punti specificati (ad esempio da una serie di misurazioni). Questo polinomio è chiamato polinomio di interpolazione e si dice che interpoli i punti dati.

Applicazioni

I polinomi possono essere integrati e derivati ​​molto facilmente. Questo è il motivo per cui i polinomi interpolanti compaiono in molti posti nella matematica numerica, ad esempio nell'integrazione numerica e, di conseguenza, nei metodi per la soluzione numerica di equazioni differenziali ordinarie .

Problema

Per determinate coppie di valori con diversi punti di interpolazione a coppie , viene cercato un polinomio del massimo grado che contiene tutte le equazioni ${\ displaystyle n + 1}$${\ displaystyle (x_ {i}, \, f_ {i})}$ ${\ displaystyle x_ {i}}$${\ displaystyle P}$${\ displaystyle n}$

${\ displaystyle P (x_ {i}) = f_ {i}, \ quad i = 0, \ dotsc, n}$

Adempie. Un tale polinomio esiste sempre ed è determinato in modo univoco, come verrà mostrato di seguito.

Nel caso del problema dell'interpolazione , i polinomi con gradi o meno devono essere cercati nello spazio vettoriale , insomma . È una base di , le equazioni producono un sistema di equazioni lineari per i coefficienti della rappresentazione di base . Poiché uno stesso polinomio può essere rappresentato in modo diverso, a seconda di quale base viene scelta per lo spazio vettoriale , si possono ottenere sistemi di equazioni molto diversi. Se si sceglie per la base standard , ovvero per la rappresentazione , si ottiene un sistema di equazioni con matrice Vandermonde : ${\ displaystyle P}$ ${\ displaystyle \ Pi _ {n}}$${\ displaystyle n}$${\ displaystyle P \ in \ Pi _ {n}}$${\ displaystyle \ phi _ {0}, \ dotsc, \ phi _ {n}}$${\ displaystyle \ Pi _ {n}}$${\ displaystyle P (x_ {i}) = f_ {i}}$${\ Displaystyle P = \ sum _ {k = 0} ^ {n} a_ {k} \ phi _ {k}}$${\ displaystyle \ Pi _ {n}}$${\ displaystyle \ Pi _ {n}}$${\ displaystyle \ sinistra \ {x ^ {k} \ mid 0 \ leq k \ leq n \ right \}}$${\ displaystyle P}$${\ displaystyle P (x) = \ sum _ {k = 0} ^ {n} a_ {k} x ^ {k}}$

${\ displaystyle {\ begin {pmatrix} 1 & x_ {0} & \ cdots & x_ {0} ^ {n} \\\ vdots & \ vdots & \ ddots & \ vdots \\ 1 & x_ {n} & \ cdots & x_ {n} ^ {n} \ end {pmatrix}} {\ begin {pmatrix} a_ {0} \\\ vdots \\ a_ {n} \ end {pmatrix}} = {\ begin {pmatrix} f_ {0} \\\ vdots \\ f_ {n} \ end {pmatrix}}}$.

Questo è normale se i punti di supporto sono diversi a coppie, il sistema di equazioni può quindi essere risolto in modo univoco. In questo modo viene sempre garantita l'esistenza e l'unicità del polinomio ricercato . Nonostante la rappresentazione teoricamente semplice, questo sistema di equazioni non viene utilizzato nella pratica per calcolare il polinomio di interpolazione, poiché la sua soluzione è complessa ed è anche generalmente scarsamente condizionata . ${\ displaystyle x_ {i}}$${\ displaystyle P \ in \ Pi _ {n}}$

Metodo di soluzione

Il sistema di equazioni di cui sopra potrebbe essere risolto, ad esempio, con il metodo di eliminazione gaussiana . Tuttavia, con (vedi i simboli di Landau ) lo sforzo richiesto sarebbe relativamente grande. Se viene selezionata una base diversa dalla base standard per la descrizione del polinomio , lo sforzo può essere ridotto. ${\ displaystyle {\ mathcal {O}} \ left (n ^ {3} \ right)}$${\ displaystyle P}$

Formula di interpolazione lagrangiana

Funzioni base lagrangiane esemplificative per x ₀ = 0, x ₁ = 1, x ₂ = 2, x ₃ = 3 (n = 3)

Una rappresentazione nella base di Lagrange è più favorevole per considerazioni teoriche . Le funzioni di base sono i polinomi di Lagrange

${\ Displaystyle \ ell _ {i} (x) = \ prod _ {\ begin {smallmatrix} j = 0 \\ j \ neq i \ end {smallmatrix}} ^ {n} {\ frac {x-x_ {j }} {x_ {i} -x_ {j}}} = {\ frac {x-x_ {0}} {x_ {i} -x_ {0}}} \ cdots {\ frac {x-x_ {i- 1}} {x_ {i} -x_ {i-1}}} \ cdot {\ frac {x-x_ {i + 1}} {x_ {i} -x_ {i + 1}}} \ cdots {\ frac {x-x_ {n}} {x_ {i} -x_ {n}}} \ ,,}$

che sono definiti in modo tale

${\ displaystyle \ ell _ {i} (x_ {k}) = \ delta _ {ik} = \ left \ {{\ begin {matrix} 1 & {\ text {if}} i = k \\ 0 & { \ text {if}} i \ neq k \ end {matrice}} \ right.}$

si applica, dove il delta di Kronecker rappresenta. La matrice quindi corrisponde esattamente alla matrice identità . La soluzione al problema dell'interpolazione può quindi essere semplicemente fornita come ${\ displaystyle \ delta _ {ik}}$${\ Displaystyle \ left (\ ell _ {i} \ left (x_ {j} \ right) \ right) _ {i, j = 0,1, \ dotsc, n}}$

${\ Displaystyle P (x) = \ sum _ {i = 0} ^ {n} f_ {i} \ ell _ {i} \ left (x \ right)}$

con i valori di supporto . Questo è spesso usato per dimostrare l'esistenza della soluzione al problema di interpolazione. Un vantaggio della base di Lagrange è che le funzioni di base sono indipendenti dai valori di supporto . Di conseguenza, diversi set di valori di interpolazione con gli stessi punti di interpolazione possono essere interpolati rapidamente una volta determinate le funzioni di base . Uno svantaggio di questa rappresentazione, tuttavia, è che tutti i vettori di base devono essere completamente ricalcolati quando viene aggiunto un singolo punto di supporto, motivo per cui questo metodo è troppo complesso per la maggior parte degli scopi pratici. Nell'elaborazione del segnale digitale, l'interpolazione Lagrange viene utilizzata con il nome "Farrow Filter" per il ricampionamento adattivo. ${\ displaystyle f_ {i}}$${\ displaystyle \ ell _ {i}}$${\ displaystyle f_ {i}}$${\ displaystyle f_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle \ ell _ {i}}$

Formula di interpolazione baricentrica

La formula di interpolazione lagrangiana può essere trasformata nella formula di interpolazione baricentrica praticamente più rilevante

${\ displaystyle P (x) = {\ frac {\ sum _ {j = 0} ^ {n} {\ frac {\ lambda _ {j} f_ {j}} {x-x_ {j}}}} { \ sum _ {j = 0} ^ {n} {\ frac {\ lambda _ {j}} {x-x_ {j}}}}} \ ,,}$

dove i pesi baricentrici sono definiti come segue

${\ displaystyle \ lambda _ {j}: = \ prod _ {\ begin {smallmatrix} i = 0 \\ i \ neq j \ end {smallmatrix}} ^ {n} {\ frac {1} {x_ {j} -x_ {i}}} \,.}$

I pesi possono essere precalcolati per punti di supporto specificati , in modo che lo sforzo per la valutazione sia solo ora . Quando si aggiunge un nuovo punto di appoggio, i pesi devono essere rideterminati. Ciò ha una spesa rispetto alla rideterminazione dei polinomi lagrangiani di . ${\ displaystyle \ sinistra (x_ {i} \ destra) _ {i}}$${\ displaystyle \ left (\ lambda _ {i} \ right) _ {i}}$${\ displaystyle P (x)}$${\ displaystyle {\ mathcal {O}} (n)}$${\ displaystyle {\ mathcal {O}} (n)}$${\ displaystyle {\ mathcal {O}} \ left (n ^ {2} \ right)}$

Algoritmo di Newton

In questa procedura, il polinomio è rappresentato in base di Newton in modo che i coefficienti possano essere determinati in modo efficiente utilizzando lo schema delle differenze divise . Una valutazione efficiente del polinomio può quindi avvenire con l' aiuto dello schema di Horner . ${\ displaystyle P}$

Approccio: base di Newton

Come approccio per il polinomio di interpolazione che stai cercando, scegli le funzioni base di Newton e con , in modo che sia rappresentato con la formula di interpolazione newtoniana ${\ displaystyle P}$${\ displaystyle N_ {0} (x) = 1}$${\ displaystyle \ textstyle N_ {i} (x) = \ prod _ {j = 0} ^ {i-1} \ left (x-x_ {j} \ right) = \ left (x-x_ {0} \ destra) \ dotsm \ sinistra (x-x_ {i-1} \ destra)}$${\ displaystyle i = 1, \ dotsc, n}$${\ displaystyle P}$

${\ displaystyle P (x) = \ sum _ {i = 0} ^ {n} c_ {i} \ cdot N_ {i} (x) = c_ {0} + c_ {1} \ left (x-x_ { 0} \ right) + c_ {2} \ left (x-x_ {0} \ right) \ left (x-x_ {1} \ right) + \ dotsb + c_ {n} \ left (x-x_ {0 } \ right) \ dotsm \ left (x-x_ {n-1} \ right)}$

Il sistema di equazioni di equazioni ha quindi la forma ${\ displaystyle P (x_ {i}) = f_ {i}}$

${\ 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_ {n} -x_ {0}) & \ cdots && \ prod _ {i = 0} ^ {n-1} (x_ {n} -x_ {i}) \\\ end {pmatrix}} \ cdot {\ begin {pmatrix} c_ {0} \\\ vdots \\ c_ { n} \ end {pmatrix}} = {\ begin {pmatrix} f_ {0} \\\ vdots \\ f_ {n} \ end {pmatrix}}}$

A differenza della matrice Vandermonde quando viene selezionata la base standard , quando viene selezionata la base di Newton, si ottiene una matrice triangolare inferiore strutturata in modo semplice e il sistema di equazioni può essere risolto facilmente. ${\ displaystyle \ sinistra \ {x ^ {k} \ mid 0 \ leq k \ leq n \ right \}}$

Determinazione dei coefficienti: schema delle differenze divise

I coefficienti non sono determinati direttamente dal sistema di equazioni di cui sopra, ma in modo più efficiente con l'aiuto delle differenze divise. Per induzione si dimostra con la formula di ricorsione di Aitken che vale per i coefficienti${\ displaystyle c_ {i}}$${\ displaystyle c_ {i}}$

${\ displaystyle c_ {i} = \ left [x_ {0}, \ dotsc, x_ {i} \ right] f}$.

Qui, per le differenze divise definite ricorsivamente ${\ displaystyle i <j}$${\ displaystyle \ sinistra [x_ {i}, \ dotsc, x_ {j} \ right] f}$

${\ displaystyle \ sinistra [x_ {i} \ destra] f = f_ {i} \ qquad}$

${\ displaystyle \ left [x_ {i}, \ dotsc, x_ {j} \ right] f = {\ frac {\ left [x_ {i + 1}, \ dotsc, x_ {j} \ right] f- \ sinistra [x_ {i}, \ dotsc, x_ {j-1} \ right] f} {x_ {j} -x_ {i}}}}$.

La notazione con l'aggiunta è spiegata dal fatto che spesso si assume una funzione sconosciuta , che deve essere interpolata con valori di funzione noti . ${\ displaystyle f}$${\ displaystyle f}$${\ displaystyle f_ {i} = f \ sinistra (x_ {i} \ destra)}$

Il calcolo ricorsivo delle differenze divise può essere illustrato come segue. I coefficienti che stai cercando sono esattamente la linea diagonale superiore: ${\ displaystyle c_ {i}}$

${\ displaystyle {\ begin {array} {crcrccrcrc} [x_ {0}] f \\ & \ searrow \\ {} [x_ {1}] f & \ rightarrow & [x_ {0}, x_ {1}] f \\ & \ searrow && \ searrow \\ {} [x_ {2}] f & \ rightarrow & [x_ {1}, x_ {2}] f & \ rightarrow & [x_ {0}, x_ {1} , x_ {2}] f \\ {} \ vdots & \ vdots & \ vdots & \ vdots & \ vdots & \ ddots \\ {} & \ searrow && \ searrow &&& \ searrow \\ {} [x_ {n- 1}] f & \ rightarrow & [x_ {n-2}, x_ {n-1}] f & \ rightarrow & [x_ {n-3}, x_ {n-2}, x_ {n-1}] f & \ cdots & \ rightarrow & [x_ {0}, \ ldots, x_ {n-1}] f \\ & \ searrow && \ searrow &&& \ searrow && \ searrow \\ {} [x_ {n}] f & \ rightarrow & [x_ {n-1}, x_ {n}] f & \ rightarrow & [x_ {n-2}, x_ {n-1}, x_ {n}] f & \ cdots & \ rightarrow & [x_ {1}, \ ldots, x_ {n}] f & \ rightarrow & [x_ {0}, \ ldots, x_ {n}] f \ end {array}}}$

Ovviamente, quando si aggiunge un ulteriore punto alle coppie di valori nello schema sopra, è necessario aggiungere solo un'altra linea per calcolare il coefficiente aggiuntivo . I coefficienti precedentemente determinati non devono essere ricalcolati. ${\ displaystyle n + 1}$${\ displaystyle \ sinistra (x_ {i}, f_ {i} \ destra)}$${\ displaystyle \ sinistra (x_ {n + 1}, f_ {n + 1} \ destra)}$${\ displaystyle c_ {n + 1} = \ left [x_ {0}, \ dotsc, x_ {n + 1} \ right] f}$${\ displaystyle c_ {0}, \ dotsc, c_ {n}}$

In alternativa alla definizione ricorsiva di cui sopra, in uno degli articoli di Marsden, per esempio, la differenza divisa di una funzione sufficientemente spesso differenziabile è definita come il coefficiente non ambiguo alla massima potenza di un polinomio -esimo grado che interpola nei punti . Se un valore compare nella sequenza con la molteplicità , le derivate del polinomio dovrebbero interpolare le derivate della funzione a questo punto fino all'ordine . È quindi vero ${\ displaystyle \ sinistra [x_ {0}, \ dotsc, x_ {n} \ right] f}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle n}$${\ displaystyle p (x)}$${\ displaystyle f}$${\ displaystyle x_ {0}, \ dotsc, x_ {n}}$${\ displaystyle x_ {0}, \ dotsc, x_ {n}}$${\ displaystyle \ nu \ geq 1}$${\ displaystyle f}$${\ displaystyle \ nu -1}$

${\ displaystyle \ left [x_ {0}, \ dotsc, x_ {k} \ right] f = {\ frac {f ^ {(k)} (x ^ {*})} {k!}} \ qquad { \ text {if}} \ quad x ^ {*}: = x_ {0} = \ dotsb = x_ {k} \,.}$

Valutazione del polinomio: schema di Horner

Una volta noti i coefficienti del polinomio di interpolazione , è possibile valutarli in modo efficiente utilizzando lo schema di Horner . Per fare ciò, si scrive nella forma (semplice trasformazione della formula di interpolazione di Newton) ${\ displaystyle c_ {i}}$${\ displaystyle P}$${\ displaystyle P}$

${\ Displaystyle P (x) = \ left (\ dotso \ left (c_ {n} \ left (x-x_ {n-1} \ right) + c_ {n-1} \ right) \ left (x-x_ {n-2} \ right) + \ dotsb + c_ {1} \ right) \ left (x-x_ {0} \ right) + c_ {0}}$,

in modo che possa essere calcolato ricorsivamente attraverso ${\ displaystyle P (x)}$

${\ displaystyle {\ begin {align} b_ {n} & = c_ {n} \\ b_ {i} & = b_ {i + 1} \ left (x-x_ {i} \ right) + c_ {i} , \ qquad i = n-1, \ dotsc, 0 \\ P (x) & = b_ {0} \ end {allineato}}}$

Ciò richiede uno sforzo di . ${\ displaystyle {\ mathcal {O}} (n)}$

Algoritmo di Neville-Aitken

Simile all'algoritmo di Newton, l'algoritmo di Neville-Aitken calcola la soluzione in modo ricorsivo. A tal fine, denotare il polinomio di interpolazione determinato in modo univoco -esimo grado per i punti di supporto , dove è. La formula di ricorsione di Aitken si applica quindi: ${\ displaystyle p \ sinistra (f | x_ {i}, \ dotsc, x_ {j} \ right)}$${\ displaystyle k}$${\ displaystyle k + 1}$ ${\ displaystyle \ left (x_ {i}, f_ {i} \ right), \ dotsc, \ left (x_ {j}, f_ {j} \ right)}$${\ displaystyle k = ji}$

${\ displaystyle {\ begin {align} p (f | x_ {i}) (x) & = f_ {i}, \\ p \ left (f | x_ {i}, \ dotsc, x_ {j} \ right ) (x) & = {\ frac {\ sinistra (x-x_ {i} \ destra) p \ sinistra (f | x_ {i + 1}, \ dotsc, x_ {j} \ destra) (x) - \ sinistra (x-x_ {j} \ destra) p \ sinistra (f | x_ {i}, \ dotsc, x_ {j-1} \ destra) (x)} {x_ {j} -x_ {i}}} . \ end {allineato}}}$

Può essere dimostrato mediante sostituzione , che verifica che il lato destro dell'equazione soddisfi la condizione di interpolazione. L'unicità del polinomio di interpolazione fornisce quindi l'asserzione. ${\ displaystyle x_ {i}, \ ldots, x_ {j}}$

Secondo la formula di ricorsione di Aitken, il coefficiente univoco da alla potenza è la differenza tra i coefficienti da e a diviso per . Ciò mostra che gli elementi diagonali nello schema delle differenze divise danno esattamente i coefficienti del polinomio di interpolazione secondo l'approccio di Newton. ${\ displaystyle p \ sinistra (f | x_ {i}, \ dotsc, x_ {j} \ right)}$${\ displaystyle x ^ {ji}}$${\ displaystyle p \ sinistra (f | x_ {i + 1}, \ dotsc, x_ {j} \ right)}$${\ displaystyle p \ sinistra (f | x_ {i}, \ dotsc, x_ {j-1} \ right)}$${\ displaystyle x ^ {ji-1}}$${\ displaystyle x_ {j} -x_ {i}}$${\ displaystyle [x_ {0}, \ ldots, x_ {j}] f}$${\ displaystyle c_ {j}}$${\ displaystyle P}$

Con lo schema di Neville, la valutazione di un luogo può essere eseguita anche in modo ricorsivo: ${\ Displaystyle p \ sinistra (f | x_ {0}, \ dotsc, x_ {n} \ right) (x) = P (x)}$${\ displaystyle x}$

${\ displaystyle {\ begin {array} {crcrccrcrc} p (f | x_ {0}) \\ & \ searrow \\ p (f | x_ {1}) & \ rightarrow & p (f | x_ {0}, x_ {1}) \\ & \ searrow && \ searrow \\ p (f | x_ {2}) & \ rightarrow & p (f | x_ {1}, x_ {2}) & \ rightarrow & p (f | x_ {0}, x_ {1}, x_ {2}) \\\ vdots && \ vdots && \ vdots & \ ddots \\ & \ searrow && \ searrow &&& \ searrow \\ p (f | x_ {n-1 }) & \ rightarrow & p (f | x_ {n-2}, x_ {n-1}) & \ rightarrow & p (f | x_ {n-3}, x_ {n-2}, x_ {n- 1}) & \ cdots & \ rightarrow & p (f | x_ {0}, \ dotsc, x_ {n-1}) \\ & \ searrow && \ searrow &&& \ searrow && \ searrow \\ p (f | x_ {n}) & \ rightarrow & p (f | x_ {n-1}, x_ {n}) & \ rightarrow & p (f | x_ {n-2}, x_ {n-1}, x_ {n} ) & \ cdots & \ rightarrow & p (f | x_ {1}, \ dotsc, x_ {n}) & \ rightarrow & p (f | x_ {0}, \ dotsc, x_ {n}) \ end {array }}}$

Confronto dei metodi di soluzione

Se si desidera determinare tutti i coefficienti del polinomio di interpolazione , l'algoritmo di Newton offre il minimo sforzo richiesto per questo . Il polinomio così determinato può quindi essere valutato con operazioni in un punto. Questo è il motivo per cui l'algoritmo di Newton è adatto quando il polinomio di interpolazione deve essere valutato in molti punti. È inoltre possibile aggiungere in modo efficiente punti di supporto aggiuntivi. Tuttavia, se i punti di supporto oi valori di supporto sono troppo vicini tra loro, c'è il rischio di essere cancellati quando si determinano le differenze divise. ${\ displaystyle P}$${\ displaystyle {\ mathcal {O}} \ left (n ^ {2} \ right)}$${\ displaystyle {\ mathcal {O}} (n)}$

L'algoritmo di Neville-Aitken, d'altra parte, è adatto quando un polinomio di interpolazione deve essere valutato solo in pochissimi punti ed è meno suscettibile di cancellazione. Nuovi punti di supporto possono anche essere aggiunti in modo efficiente all'algoritmo di Neville-Aitken. Quindi z. B. una precisione desiderata dell'interpolazione può essere ottenuta in un punto aggiungendo sempre più punti di interpolazione.

Esempio: interpolazione della funzione tangente

Funzione tangente (blu) e suo interpolante polinomiale di terzo grado (rosso)

Interpola la funzione in punti dati ${\ displaystyle f (x) = \ tan (x)}$

${\ displaystyle x_ {0} = - 1 {,} 5}$	${\ displaystyle f (x_ {0}) = - 14 {,} 101420}$
${\ displaystyle x_ {1} = - 0 {,} 75}$	${\ displaystyle f (x_ {1}) = - 0 {,} 931596}$
${\ displaystyle x_ {2} = 0}$	${\ displaystyle f (x_ {2}) = 0}$
${\ displaystyle x_ {3} = 0 {,} 75}$	${\ displaystyle f (x_ {3}) = 0 {,} 931596}$
${\ displaystyle x_ {4} = 1 {,} 5}$	${\ displaystyle f (x_ {4}) = 14 {,} 101420}$

Soluzione con Lagrange

Le funzioni base di Lagrange sono

${\ displaystyle {\ begin {align} \ 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) \\\ 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) \\\ 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) \\\ 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} \ oltre x_ {3} -x_ {4}} = - {8 \ oltre 243} x (2x-3) (2x + 3) (4x + 3) \\\ 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) \ end {allineato}}}$

così è il polinomio di interpolazione

${\ displaystyle {\ begin {align} P _ {\ text {Lagrange}} (x) = & {\ tfrac {1} {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)} \\ = & - 1 {,} 477474x + 4 {,} 834848x ^ {3} \ end {align}}}$

Soluzione con Newton

Le differenze divise sono qui

${\ displaystyle {\ begin {array} {rrrrrr} x_ {i} & f \ left (x_ {i} \ right) &&&& \\ - 1 {,} 50 & -14 {,} 10140 &&&& \\ &&&&& \\ - 0 {,} 75 e -0 {,} 931596 e {- 0 {,} 931596 - (- 14 {,} 1014) \ oltre -0 {,} 75 - (- 1 {,} 5)} = 17 {,} 5597 &&& \ \ &&&&& \\ 0 {,} 00 & 0 {,} 00000 & {0 - (- 0 {,} 931596) \ over 0 - (- 0 {,} 75)} = 1 {, } 24213 & {1 {,} 24213- 17 {,} 5597 \ over 0 - (- 1 {,} 5)} = - 10 {,} 8784 && \\ &&&&& \\ 0 {,} 75 & 0 {, } 931596 e {0 {,} 931596-0 \ oltre 0 {,} 75-0} = 1 {,} 24213 e {1 {,} 24213-1 {,} 24213 \ oltre 0 {,} 75 - (- 0 {,} 75)} = 0 {,} 00000 & {0 - (- 10 {,} 8784) \ oltre 0 {,} 75 - (- 1 {,} 5)} = 4 {,} 83484 & \ \ &&&&& \\ 1 {,} 50 & 14 {,} 10140 & {14 {,} 10140-0 {,} 931596 \ over 1 {,} 5-0 {,} 75} = 17 {,} 5597 & { 17 {,} 5597-1 {,} 24213 \ oltre 1 {,} 5-0} = 10 {,} 8784 e {10 {,} 8784-0 \ oltre 1 {,} 5 - (- 0 {,} 75)} = 4 {,} 83484 & {4 {,} 83484-4 {,} 83484 \ over 1 {,} 5 - (- 1 {,} 5)} = 0 \\\ end {array}}}$

ed è il polinomio di interpolazione

${\ displaystyle {\ begin {align} P _ {\ text {Newton}} (x) = & - 14 {,} 1014 + 17 {,} 5597 (x + 1 {,} 5) -10 {,} 8784 (x + 1 {,} 5) (x + 0 {,} 75) \\ & {} + 4 {,} 83484 (x + 1 {,} 5) (x + 0 {,} 75) x + 0 (x + 1 {,} 5) (x + 0 {,} 75) x (x-0 {,} 75) \\ = & - 0 {,} 00005-1 {,} 4775x-0 {,} 00001x ^ {2} +4 {,} 83484x ^ {3} \ end {align}}}$

Se si utilizzano valori iniziali più precisi , il primo e il terzo coefficiente scompaiono. ${\ Displaystyle f \ left (x_ {i} \ right)}$

Qualità dell'interpolazione

Stima degli errori

Viene fornita una funzione i cui valori di funzione sono interpolati nei punti dal polinomio . L' intervallo più piccolo che contiene i punti di interpolazione e un punto è indicato da . Inoltre, let ( ) times può essere continuamente differenziato su . Allora ne esiste uno per il quale si applica quanto segue: ${\ displaystyle f}$${\ displaystyle n + 1}$${\ displaystyle f_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle P}$${\ displaystyle I}$${\ displaystyle x_ {i}}$${\ displaystyle x}$${\ displaystyle f}$${\ displaystyle n + 1}$${\ displaystyle I}$${\ displaystyle \ xi \ in I}$

${\ displaystyle f (x) -P (x) = {\ frac {f ^ {(n + 1)} (\ xi)} {(n + 1)!}} \ prod _ {i = 0} ^ { n} (x-x_ {i})}$

In particolare, per quanto riguarda la norma massima, abbiamo su e con : ${\ displaystyle [a, b]}$${\ displaystyle w_ {n} (x) = \ prod _ {i = 0} ^ {n} (x-x_ {i})}$

${\ displaystyle | f (x) -P (x) | \ leq {\ frac {\ | f ^ {(n + 1)} \ | _ {\ infty}} {(n + 1)!}} \ prod _ {i = 0} ^ {n} | x-x_ {i} | \ leq {\ frac {\ | f ^ {(n + 1)} \ | _ {\ infty}} {(n + 1)! }} \ | w_ {n} \ | _ {\ infty}}$

Ottimizzazione degli errori secondo Chebyshev

Per n più grandi , i punti di Chebyshev si raggruppano ai bordi dell'intervallo.

L'errore dipende quindi da una derivazione del e dal prodotto , ovvero i punti di appoggio . A volte sei nella posizione di poter scegliere tu stesso i punti di supporto; ad esempio, quando si esegue un esperimento fisico, o con alcuni metodi per la soluzione numerica di equazioni differenziali . In questo caso, la domanda interessante è per quali punti di supporto la norma massima è minima. ${\ displaystyle f}$${\ displaystyle w_ {n} (x): = \ prod _ {i = 0} ^ {n} (x-x_ {i})}$${\ displaystyle x_ {i}}$${\ displaystyle \ | w_ {n} \ | _ {\ infty}}$

Normalmente i punti di supporto standardizzati sono normalmente considerati per una prova

${\ displaystyle {\ begin {align} w_ {n}: [- 1,1] \ rightarrow \ mathbb {R}, \ w_ {n} (x) = \ prod _ {i = 0} ^ {n} ( x-x_ {i}) \\ {\ text {con}} \ qquad \ forall \, i = 0, \ ldots, n: \ quad x_ {i} \ in [-1,1] \ ,. \ end {align}}}$

Ora si può stimare la norma massima della funzione come segue ${\ displaystyle w_ {n}}$

${\ displaystyle \ | w_ {n} \ | _ {[- 1,1], \ infty} = \ max _ {x \ in [-1,1]} | w_ {n} (x) | \ geq 2 ^ {- n} \,.}$

Chebyshev ha dimostrato che gli zeri dei polinomi di Chebyshev ("punti di Chebyshev") sono punti di supporto ottimali. I polinomi hanno gli zeri per . I punti di supporto selezionati in questo modo forniscono un limite netto alla stima superiore ${\ displaystyle T_ {n + 1} (x) = \ cos ((n + 1) \ arccos (x))}$${\ displaystyle t_ {k} = \ cos \ left ({\ frac {2k + 1} {2n + 2}} \ pi \ right)}$${\ displaystyle k \ in \ {0,1, \ ldots, n \}}$

${\ displaystyle \ | w_ {n} \ | _ {[- 1,1], \ infty} = 2 ^ {- n} \,.}$

Questa istruzione può quindi essere utilizzata con la trasformazione

${\ displaystyle {\ begin {align} \ xi \ in [-1,1] & \ rightsquigarrow x = {\ frac {a + b} {2}} + {\ frac {ba} {2}} \ xi & \ in [a, b] \\ x \ in [a, b] & \ rightsquigarrow \ xi = {\ frac {2x-ab} {ba}} & \ in [-1,1] \ end {allineato}} }$

nel caso di un intervallo generale . La prova fornisce anche la stima ${\ displaystyle [a, b] \ subset \ mathbb {R}}$

${\ displaystyle {\ begin {align} \ | w_ {n} \ | _ {[a, b], \ infty} = \ max _ {x \ in [a, b]} | w_ {n} (x) | = 2 \ sinistra ({\ frac {ba} {4}} \ destra) ^ {n + 1}. \ End {allineato}}}$

Interpolazione polinomiale di 6 punti di interpolazione equidistanti (punti rossi) che giacciono sulla funzione Runge (blu)

Lo stesso con 11 punti di appoggio

Il fenomeno di Runge

La qualità dell'interpolazione migliora quando vengono aggiunti più punti di interpolazione? Generalmente no: con punti di appoggio equidistanti e un alto grado del polinomio, può accadere che la funzione polinomiale assomigli a malapena alla funzione da interpolare, nota anche come fenomeno di Runge . Nel caso borderline, i polinomi tendono a . Se la funzione da interpolare si comporta in modo diverso, ad esempio periodicamente o asintoticamente costante, si verificano forti oscillazioni in prossimità dei limiti dell'intervallo. Le interpolazioni polinomiali sull'intero intervallo sono relativamente inadatte per tali funzioni. ${\ displaystyle x \ to \ pm \ infty}$${\ displaystyle \ pm \ infty}$

I punti di interpolazione di Chebyshev, che sono più vicini ai limiti dell'intervallo, possono ridurre l'errore complessivo dell'interpolazione, ma si consiglia di modificare il metodo di interpolazione, ad esempio per l' interpolazione spline . Runge ha fornito un esempio di questo fenomeno, la funzione Runge a lui intitolata:

${\ displaystyle f (x) = {\ frac {1} {1 + x ^ {2}}} \ ,, \ quad x \ in [-5; 5]}$

Comportamento di convergenza

Tuttavia, ci sono condizioni in cui la qualità dell'interpolazione migliora con un numero crescente di punti di interpolazione: Quando la griglia dei punti di interpolazione diventa sempre più "fine" e una funzione analitica viene interpolata. Più precisamente: sia una funzione analitica sull'intervallo . Per una divisione ad intervalli ${\ displaystyle f}$${\ displaystyle I = [a, b] \ subset \ mathbb {R}}$

${\ displaystyle \ Delta _ {m} = \ {a = x_ {0} ^ {(m)} <x_ {1} ^ {(m)} <\ dotsb <x_ {n_ {m}} ^ {(m )} = b \}, \ qquad m \ in \ mathbb {N}}$

lascia che la sua norma sia definita da

${\ displaystyle \ | \ Delta _ {m} \ | = \ max _ {i} | x_ {i + 1} ^ {(m)} - x_ {i} ^ {(m)} |.}$

Per ogni divisione dell'intervallo c'è un polinomio chiaramente definito che interpola nei punti di interpolazione . Se vale per una sequenza di divisioni di intervallo , allora segue uniformemente . ${\ displaystyle \ Delta _ {m}}$${\ displaystyle P _ {\ Delta _ {m}}}$${\ displaystyle f}$${\ displaystyle \ Delta _ {m}}$${\ displaystyle \ | \ Delta _ {m} \ | \ rightarrow 0}$${\ displaystyle P _ {\ Delta _ {m}} \ rightarrow f}$

Tuttavia, per ogni sequenza si può trovare anche una funzione continua , in modo che non converga uniformemente a (teorema di Faber ). ${\ displaystyle \ {\ Delta _ {m} \} _ {m \ in \ mathbb {N}}}$${\ displaystyle I}$${\ displaystyle f}$${\ displaystyle \ {P _ {\ Delta _ {m}} \} _ {m \ in \ mathbb {N}}}$ ${\ displaystyle f}$

Migliore approssimazione

La relazione tra il polinomio di interpolazione e il polinomio che meglio approssima la funzione rispetto alla norma massima è data come segue: ${\ displaystyle \ | \ cdot \ | _ {\ max}}$

Si danno i seguenti oggetti

• una funzione continua da approssimare: ${\ displaystyle f \ in C ([a, b])}$
• Punti di supporto: ${\ displaystyle x_ {0}, \ ldots, x_ {n} \ in [a, b]}$
• Costante di Lebesgue :${\ displaystyle \ Lambda _ {n}}$
• Polinomio di interpolazione: con${\ displaystyle P \ in P_ {n}}$${\ displaystyle P (x_ {i}) = f (x_ {i})}$
• Migliore approssimazione: con .${\ displaystyle Q \ in P_ {n}}$${\ displaystyle \ | fQ \ | _ {\ max} = \ min _ {R \ in P_ {n}} \ | fR \ | _ {\ max}}$

Quindi si applica la stima

${\ displaystyle \ | fP \ | _ {\ max} = (1+ \ Lambda _ {n}) \ | fQ \ | _ {\ max} \,.}$

generalizzazione

Finora, si presumeva che i punti di supporto del polinomio di interpolazione fossero diversi a coppie. Questo non è il caso dell'interpolazione Hermit . Non solo i valori della funzione, ma anche i valori delle derivate del polinomio di interpolazione sono specificati in più punti di interpolazione. ${\ displaystyle x_ {i}}$${\ displaystyle P}$

Costante di Lebesgue

Lascia che l' operatore che assegna il suo polinomio di interpolazione a una funzione sia definito da ${\ displaystyle f}$${\ displaystyle P (f)}$

${\ Displaystyle \ phi _ {n} \ due punti C ([a, b]) \ rightarrow P_ {n} \ ,, \, f \ mapsto P (f) = \ sum _ {i = 0} ^ {n} f (x_ {i}) l_ {i} \ ,,}$

dove il -esimo è il polinomio di Lagrange . ${\ displaystyle l_ {i}}$${\ displaystyle i}$

Siccome la costante di Lebesgue è la norma dell'operatore di designato. Per questo, è necessario uno standard e spesso è qui alla norma massima accessibile ${\ displaystyle \ Lambda _ {n}}$${\ displaystyle \ phi _ {n}}$ ${\ displaystyle \ | \ cdot \ | _ {\ max}}$

${\ displaystyle \ Lambda _ {n}: = \ | \ phi _ {n} \ | _ {\ max} \,.}$

La norma può essere valutata esplicitamente

${\ displaystyle \ Lambda _ {n} = \ max _ {x \ in [a, b]} \ sum _ {i = 0} ^ {n} | L_ {i} (x) | \,.}$

letteratura

• Hans R. Schwarz, Norbert Köckler: Numerical Mathematics . 5a edizione Teubner, Stoccarda 2004, ISBN 3-519-42960-8

• Stoer, Bulirsch: matematica numerica 1 . 10a edizione. Springer Verlag, Berlino, Heidelberg, New York 2007, ISBN 978-3-540-45389-5 , 2.1 Interpolation by Polynomials, pp. 39–57 (Copre i metodi Lagrange, Neville-Aitken e Newton, l'interpolazione Hermite e la stima dell'errore, ciascuno con esempi e prove). 
• Stampa, Teukolsky, Vetterling, Flannery: Numerical Recipes . L'arte dell'informatica scientifica. 3a edizione. Cambridge University Press, Cambridge 2007, ISBN 978-0-521-88407-5 , 3.2 Polynomial Interpolation and Extrapolation, pp. 118-120 (algoritmo di Neville-Aitken con implementazione C ++). 
• Carl Runge: Sulle funzioni empiriche e l'interpolazione tra ordinate equidistanti . In: Journal of Mathematics and Physics . nastro 46 . BG Teubner, Lipsia 1901, p. 224-243 ( hdl: 1908/2014 - fenomeno Runge). 

link internet

• Pagina di Newton, Lagrange e Cubic Spline con applet Java
• Spiegazioni ed esempi per l'interpolazione di Lagrange

Prove individuali

1. ↑ Martin J. Marsden: un'identità per le funzioni di spline con applicazioni per l'approssimazione di spline con diminuzione delle variazioni . In: Journal of Approximation Theory , 3, 1970, pp. 7-49.
2. ↑ Jochen Werner: 10 aprile . In: Numerical Mathematics , 1a edizione, Vieweg Studium, Nr.32, Vieweg Verlagsgesellschaft, 1992, ISBN 3-528-07232-6 . - 4.1.3. (PDF; 11,7 MB) sam.math.ethz.ch
3. ^ Andrei Nikolajewitsch Kolmogorow et al.: 4 . In: Mathematics of the 19th Century , 1a edizione, Birkhäuser, 1998, ISBN 3-7643-5845-9 . - books.google.de