Altre scritture dei polinomi interpolanti

Scrittura dei polinomi interpolanti in funzione dei polinomi nodali[modifica | modifica wikitesto]

Definizione 5.1
Definisco polinomio nodale
 

Cerchiamo una scrittura equivalente dei polinomi interpolanti:

e tenendo conto dell'espressione di :
Osservo che:
e valutando in :
quindi, tornando all'espressione del polinomio interpolante:

Considerazioni sui costi computazionali[modifica | modifica wikitesto]

Poniamo

dove .
Ci si chiede qual è il costo computazionale della valutazione di in un assegnato. Sono necessarie:

  1. sottrazioni per calcolare (al denominatore)
  2. sottrazioni per calcolare gli nella produttoria, e questo equivale a calcolare le entrate della matrice con 0sulla diagonale principale, tale che .
  3. operazioni per calcolare gli , in particolare per calcolare ogni , una volta che gli sono noti, sono necessari solo prodotti. Siccome gli sono ho in totale operazioni.
  4. addizioni (defivano dalla sommatoria) e moltiplicazioni per calcolare , divisione tra due numeri già noti,
  5. operazioni per la valutazione del polinomio nodale di cui già conosco i fattori.
    più una quantità trascurabile dell'ordine di operazioni.

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

Supponiamo di aggiungere un nuovo punto ai dati: si vuole calcolare un nuovo polinomio interpolante di grado .

Gli sono già stati calcolati, si ha che il nuovo polinomio è:

, quindi
Inoltre
e si ricava che
quindi le operazioni totali in più, avendo già calcolato , sono una Sottrazione per , sottrazioni per , moltiplicazioni per , addizioni per la sommatoria, moltiplicazioni per , 2 operazioni per l'ultimo termine.

In totale ho addizioni e moltiplicazioni.

Forma di Newton[modifica | modifica wikitesto]

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

viene riscritto in funzione della base dei polinomi nodali, ponendo
Gli vengono posti uguali alla differenza divisa di ordine k.

Definizione 5.2

Si indica con la differenza divisa di ordine ( nodi). La differenza divisa si definisce induttivamente, ponendo:

 

Vogliamo dimostrare che

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

Lemma 5.1 (formula di Neville)

Dato un insieme di indici, e definendo il polinomio valutato nei nodi per , si ha che:

è un polinomio interpolante.

 
Dimostrazione

Il lemma dà una rappresentazione ricorsiva del polinomio interpolante.

  1. Per calcolare l'espressione di si tiene conto che il termine è nullo, quindi rimane
  2. Valutando invece si annulla il secondo termine, e rimane:
  3. per un generico , si ha:

Ho quindi verificato tutte le condizioni di interpolazione.

 


Teorema 5.3 (dimostrazione della forma di Newton)

è un polinomio interpolante.

 
Dimostrazione

Dimostro l'asserto per induzione.

  1. Se , ottengo che , per definizione.
  2. Per ipotesi induttiva, assumo che sia vero che il polinomio di Newton è il polinomio interpolante per il grado rispetto alla base nodale, e lo dimostroper .
  3. Supponiamo che sia il polinomio interpolante di grado rispetto alla base delle date dai polinomi nodali di indice , allora possiamo scriverlo come:
    voglio dimostrare che .Considero la formula di interpolazione di Neville. Allora
    Dall'iptesi di induzione segue che:#* è il polinomio interpolante di grado sui nodi , e per ipotesi di induzione il coefficiente del termine di grado massimo è .#* è il polinomio interpolante rispetto ai nodi e il coefficiente del suo termine di grado massimo è .Quindi, nel polinomio , in base alla formula di Neville e a quanto osservato, il coefficiente del termine di grado massimo è:
 


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 si ha:

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

 

Algoritmo alla Neville[modifica | modifica wikitesto]

Considero i due vettori colonna e dove . L'algoritmo alla Neville porta alla costruzione di una matrice triangolare inferiore A, dove le entrate sono determinate nel seguente modo:

Ad esempio, presi 6 punti la matrice che risulta dall'algoritmo di Neville è:

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 diventa la differenza divisa tra gli elementi e , per ogni j.

Numero di operazioni effettuate: per ogni elemento faccio una divisione e due sottrazioni, e la triangolare inferiore ha elementi, quindi vengono effettuate operazioni additive e operazioni moltiplicative.

Algoritmo di Hornern[modifica | modifica wikitesto]

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

Raccolgo tra gli ultimi tre addendi:
Poi raccolgo tra gli ultimi due addendi:
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.

 PrecedenteSuccessivo