Interpolazione polinomiale

1

Interpolazione Polinomiale Problema

Rappresentazione Lagrangiana Polinomio interpolante di Newton Errore nell’interpolazione polinomiale

2

Approssimazione ai minimi quadrati nel discreto

1

Interpolazione Polinomiale Problema

Rappresentazione Lagrangiana Polinomio interpolante di Newton Errore nell’interpolazione polinomiale

2

Approssimazione ai minimi quadrati nel discreto

Outline

1

Interpolazione Polinomiale Problema

Rappresentazione Lagrangiana Polinomio interpolante di Newton Errore nell’interpolazione polinomiale

2

Approssimazione ai minimi quadrati nel discreto

Problema

Assegnati n + 1 punti

(x

, y

), i = 1, . . . , n + 1, trovare un polinomio p(x )

p(x

) = y

, i = 1, . . . , n + 1. (1)

Poich `e i punti sono n + 1 `e sufficiente considerare il generico polinomio di grado n

p

(x ) = a

+ a

x + · · · + a

x

.

Usando la base delle potenze, si tratta di determinare i

coefficienti a

risolvendo un sistema lineare di n + 1 equazioni in n + 1 incognite, ottenuto dalle condizioni di interpolazione (1):

a

+ a

x

+ a

x

+ · · · + a

x

= y

...

...

...

a

+ a

x

+ a

x

+ · · · + a

x

= y

La matrice dei coefficienti `e la matrice di Vandermonde.

Essa `e non singolare ⇔ gli x

sono distinti.

V =













1 x

x

. . . x

1 x

x

. . . x

.. .. .. .. ..

.. .. .. .. ..

1 x

x

. . . x











 ove det(V ) = Q

i>j

(x

− x

).

Teorema

Se gli x

sono distinti esiste uno ed un solo polinomio di interpolazione di grado al pi `u n.

Tuttavia la matrice di Vandermonde `e mal condizionata.

Pertanto si calcola il polinomio di interpolazione usando una

rappresentazione del polinomio diversa da quella canonica.

La matrice dei coefficienti `e la matrice di Vandermonde.

Essa `e non singolare ⇔ gli x

sono distinti.

V =













1 x

x

. . . x

1 x

x

. . . x

.. .. .. .. ..

.. .. .. .. ..

1 x

x

. . . x











 ove det(V ) = Q

i>j

(x

− x

).

Teorema

Se gli x

sono distinti esiste uno ed un solo polinomio di interpolazione di grado al pi `u n.

Tuttavia la matrice di Vandermonde `e mal condizionata.

Pertanto si calcola il polinomio di interpolazione usando una

rappresentazione del polinomio diversa da quella canonica.

La matrice dei coefficienti `e la matrice di Vandermonde.

Essa `e non singolare ⇔ gli x

sono distinti.

V =













1 x

x

. . . x

1 x

x

. . . x

.. .. .. .. ..

.. .. .. .. ..

1 x

x

. . . x











 ove det(V ) = Q

i>j

(x

− x

).

Teorema

Se gli x

sono distinti esiste uno ed un solo polinomio di interpolazione di grado al pi `u n.

Tuttavia la matrice di Vandermonde `e mal condizionata.

Pertanto si calcola il polinomio di interpolazione usando una

rappresentazione del polinomio diversa da quella canonica.

Outline

1

Interpolazione Polinomiale Problema

Rappresentazione Lagrangiana Polinomio interpolante di Newton Errore nell’interpolazione polinomiale

2

Approssimazione ai minimi quadrati nel discreto

Rappresentazione lagrangiana

Polinomio interpolante di Lagrange

A ogni punto k −esimo, k = 1, . . . , n + 1, si associa un polinomio L

(x ) di grado n tale che

L

(x

) = 0 per i 6= k , L

(x

) = 1.

Allora x

, . . . , x

, x

. . . , x

sono gli zeri di L

(x ), quindi L

(x ) = α

(x − x

) . . . (x − x

)(x − x

) . . . (x − x

) Affinch `e L

(x

) = 1 basta scegliere

α

= 1/(x

− x

) . . . (x

− x

)(x

− x

) . . . (x

− x

)

Rappresentazione lagrangiana

Polinomio interpolante di Lagrange

A ogni punto k −esimo, k = 1, . . . , n + 1, si associa un polinomio L

(x ) di grado n tale che

L

(x

) = 0 per i 6= k , L

(x

) = 1.

Allora x

, . . . , x

, x

. . . , x

sono gli zeri di L

(x ), quindi L

(x ) = α

(x − x

) . . . (x − x

)(x − x

) . . . (x − x

) Affinch `e L

(x

) = 1 basta scegliere

α

= 1/(x

− x

) . . . (x

− x

)(x

− x

) . . . (x

− x

)

Rappresentazione lagrangiana

Polinomio interpolante di Lagrange

A ogni punto k −esimo, k = 1, . . . , n + 1, si associa un polinomio L

(x ) di grado n tale che

L

(x

) = 0 per i 6= k , L

(x

) = 1.

Allora x

, . . . , x

, x

. . . , x

sono gli zeri di L

(x ), quindi L

(x ) = α

(x − x

) . . . (x − x

)(x − x

) . . . (x − x

) Affinch `e L

(x

) = 1 basta scegliere

α

= 1/(x

− x

) . . . (x

− x

)(x

− x

) . . . (x

− x

)

Rappresentazione lagrangiana

Polinomio interpolante (x

, y

), i = 1, . . . , n + 1

p

(x ) = y

L

(x ) + · · · + y

L

(x )

Polinomio interpolante in forma lagrangiana

Costruzione di L

(x )

function p=plagr(xnodi,k)

%Restituisce i coefficienti del k-esimo pol di

%Lagrange associato ai punti del vettore xnodi if k==1

xzeri=xnodi(2:end) else

xzeri=[xnodi(1:k-1) xnodi(k+1:end)]

end

p=poly(xzeri)

p=p/polyval(p,xnodi(k))

Disegnare i polinomi di Lagrange associati a [-1 -0.7 0.5 1]

Polinomio interpolante in forma lagrangiana

Costruzione di L

(x )

function p=plagr(xnodi,k)

%Restituisce i coefficienti del k-esimo pol di

%Lagrange associato ai punti del vettore xnodi if k==1

xzeri=xnodi(2:end) else

xzeri=[xnodi(1:k-1) xnodi(k+1:end)]

end

p=poly(xzeri)

p=p/polyval(p,xnodi(k))

Disegnare i polinomi di Lagrange associati a [-1 -0.7 0.5 1]

Outline

1

Interpolazione Polinomiale Problema

Rappresentazione Lagrangiana Polinomio interpolante di Newton Errore nell’interpolazione polinomiale

2

Approssimazione ai minimi quadrati nel discreto

Polinomio interpolante di Newton

Si deriva una diversa rappresentazione del polinomio di interpolazione.

Rispetto alla rappresentazione di Lagrange consente di

1

calcolarlo con una minore complessit `a computazionale;

2

derivare da un polinomio interpolante di grado n uno di

grado superiore quando si aggiungono nuovi dati (x

, y

)

usando i calcoli gi `a eseguiti.

Polinomio interpolante di Newton

Si deriva una diversa rappresentazione del polinomio di interpolazione.

Rispetto alla rappresentazione di Lagrange consente di

1

calcolarlo con una minore complessit `a computazionale;

2

derivare da un polinomio interpolante di grado n uno di

grado superiore quando si aggiungono nuovi dati (x

, y

)

usando i calcoli gi `a eseguiti.

Polinomio interpolante di Newton

Si deriva una diversa rappresentazione del polinomio di interpolazione.

Rispetto alla rappresentazione di Lagrange consente di

1

calcolarlo con una minore complessit `a computazionale;

2

derivare da un polinomio interpolante di grado n uno di

grado superiore quando si aggiungono nuovi dati (x

, y

)

usando i calcoli gi `a eseguiti.

Differenze divise

A tale scopo si usano le differenze divise.

Si dice differenza divisa di ordine zero di f (x ) relativa al nodo x

la quantit `a

f [x

] = y

.

Si dice differenza divisa di ordine uno di f (x ) relativa ai nodi x

, x

la quantit `a

f [x

, x

] = y

− y

x

− x

.

Si dice differenza divisa di ordine 2 di f (x ) relativa agli argomenti x

, x

, x

la quantit `a

f [x

, x

, x

] = f [x

, x

] − f [x

, x

]

x − x .

Differenze divise

A tale scopo si usano le differenze divise.

Si dice differenza divisa di ordine zero di f (x ) relativa al nodo x

la quantit `a

f [x

] = y

.

Si dice differenza divisa di ordine uno di f (x ) relativa ai nodi x

, x

la quantit `a

f [x

, x

] = y

− y

x

− x

.

Si dice differenza divisa di ordine 2 di f (x ) relativa agli argomenti x

, x

, x

la quantit `a

f [x

, x

, x

] = f [x

, x

] − f [x

, x

]

x − x .

Differenze divise

A tale scopo si usano le differenze divise.

Si dice differenza divisa di ordine zero di f (x ) relativa al nodo x

la quantit `a

f [x

] = y

.

Si dice differenza divisa di ordine uno di f (x ) relativa ai nodi x

, x

la quantit `a

f [x

, x

] = y

− y

x

− x

.

Si dice differenza divisa di ordine 2 di f (x ) relativa agli argomenti x

, x

, x

la quantit `a

f [x

, x

, x

] = f [x

, x

] − f [x

, x

]

x − x .

La differenza divisa di ordine m di f (x ) relativa agli m + 1 argomenti x

, x

, . . . , x

`e

f [x

, x

, . . . , x

] = f [x

, x

, . . . , x

] − f [x

, x

, . . . , x

]

x

− x

.

Polinomio interpolante di Newton

La rappresentazione di Newton del polinomio di interpolazione dei punti (x

, y

), i = 1, ..., n, `e data da:

p

(x ) = f [x

] + f [x

, x

](x − x

) + f [x

, x

, x

](x − x

)(x − x

)+

· · · + f [x

, x

, . . . , x

](x − x

)(x − x

) . . . (x − x

) Se aggiungo un punto da interpolare, (x

, y

), il nuovo polinomio `e dato da

p

(x ) = p

(x )+f [x

, x

, . . . , x

, x

](x −x

)(x −x

) . . . (x −x

)

Polinomio interpolante di Newton

La rappresentazione di Newton del polinomio di interpolazione dei punti (x

, y

), i = 1, ..., n, `e data da:

p

(x ) = f [x

] + f [x

, x

](x − x

) + f [x

, x

, x

](x − x

)(x − x

)+

· · · + f [x

, x

, . . . , x

](x − x

)(x − x

) . . . (x − x

) Se aggiungo un punto da interpolare, (x

, y

), il nuovo polinomio `e dato da

p

(x ) = p

(x )+f [x

, x

, . . . , x

, x

](x −x

)(x −x

) . . . (x −x

)

Polinomio interpolante di Newton

Tabella delle differenze divise Esempio: (x

, y

), i = 0, . . . , 3

x

→ f [x

]

&

x

→ f [x

] → f [x

, x

]

& &

x

→ f [x

] → f [x

, x

] → f [x

, x

, x

]

& & &

x

→ f [x

] → f [x

, x

] → f [x

, x

, x

] → f [x

, x

, x

, x

]

function c=interpN(x,y)

%Calcola i coeff. del polinomio di Newton n = length(x);

for k = 1:n-1

y(k+1:n) = (y(k+1:n)-y(k)) ./ (x(k+1:n) - x(k));

end c = y;

function pval = HornerN(c,x,z)

% Calcola i valori del polinomio di Newton nei punti del vettore z n = length(c);

pval = c(n)*ones(size(z));

for k=n-1:-1:1

pval = (z-x(k)).*pval + c(k);

end

function c=interpN(x,y)

%Calcola i coeff. del polinomio di Newton n = length(x);

for k = 1:n-1

y(k+1:n) = (y(k+1:n)-y(k)) ./ (x(k+1:n) - x(k));

end c = y;

function pval = HornerN(c,x,z)

% Calcola i valori del polinomio di Newton nei punti del vettore z n = length(c);

pval = c(n)*ones(size(z));

for k=n-1:-1:1

pval = (z-x(k)).*pval + c(k);

end

Outline

1

Interpolazione Polinomiale Problema

Rappresentazione Lagrangiana Polinomio interpolante di Newton Errore nell’interpolazione polinomiale

2

Approssimazione ai minimi quadrati nel discreto

Errore nell’interpolazione polinomiale

Assegnate le n+1 osservazioni {y

}

in corrispondenza dei punti distinti x

, si `e visto come costruire il polinomio

interpolante di grado n p

(x ). Se i valori y

altro non sono che i valori di una funzione f(x) nei punti x

, cio `e y

= f (x

),

i = 1, . . . , n + 1 con f definita in [a, b], ha senso chiedersi quanto sia grande l’errore di interpolazione

E

(x ) = f (x ) − p

(x )

che si commette in un punto x ∈ [a, b] diverso dai punti di interpolazione x

.

Per dare una risposta a tale domanda `e necessario fare alcune

ipotesi di regolarit `a sulla funzione f(x).

Errore nell’interpolazione polinomiale

Sia f (x ) una funzione derivabile n + 1 volte in un intervallo [a, b]

contenente tutti i nodi {x

}

.Si dimostra che l’errore E

(x ) = f (x ) − p

(x )

tra la funzione f (x ) ed il polinomio interpolante di grado n `e del tipo

E

(x ) = ω

(x ) f

(ξ) (n + 1)!

con ξ ∈ [a, b] e

ω

(x ) =

n+1

Y

i=1

(x − x

).

Errore nell’interpolazione polinomiale

Sia f (x ) una funzione derivabile n + 1 volte in un intervallo [a, b]

contenente tutti i nodi {x

}

.Si dimostra che l’errore E

(x ) = f (x ) − p

(x )

tra la funzione f (x ) ed il polinomio interpolante di grado n `e del tipo

E

(x ) = ω

(x ) f

(ξ) (n + 1)!

con ξ ∈ [a, b] e

ω

(x ) =

n+1

Y

i=1

(x − x

).

Errore nell’interpolazione polinomiale

Sia f (x ) una funzione derivabile n + 1 volte in un intervallo [a, b]

contenente tutti i nodi {x

}

.Si dimostra che l’errore E

(x ) = f (x ) − p

(x )

tra la funzione f (x ) ed il polinomio interpolante di grado n `e del tipo

E

(x ) = ω

(x ) f

(ξ) (n + 1)!

con ξ ∈ [a, b] e

ω

(x ) =

n+1

Y

i=1

(x − x

).

Errore nell’interpolazione polinomiale

Sia f (x ) una funzione derivabile n + 1 volte in un intervallo [a, b]

contenente tutti i nodi {x

}

.Si dimostra che l’errore E

(x ) = f (x ) − p

(x )

tra la funzione f (x ) ed il polinomio interpolante di grado n `e del tipo

E

(x ) = ω

(x ) f

(ξ) (n + 1)!

con ξ ∈ [a, b] e

ω

(x ) =

n+1

Y

i=1

(x − x

).

Errore nell’interpolazione polinomiale

L’errore di interpolazione dipende quindi:

dalla regolarit `a della funzione f (x )

dalla disposizione dei punti di interpolazione sull’asse delle ascisse.

Posto M

= max

|f

(x )|, un limite superiore all’errore di interpolazione E

(x ) = f (x ) − p

(x ) `e dato da

|E

(x )| ≤ |ω

(x )|

(n + 1)! M

.

Errore nell’interpolazione polinomiale

L’errore di interpolazione dipende quindi:

dalla regolarit `a della funzione f (x )

dalla disposizione dei punti di interpolazione sull’asse delle ascisse.

Posto M

= max

|f

(x )|, un limite superiore all’errore di interpolazione E

(x ) = f (x ) − p

(x ) `e dato da

|E

(x )| ≤ |ω

(x )|

(n + 1)! M

.

Errore nell’interpolazione polinomiale

L’errore di interpolazione dipende quindi:

dalla regolarit `a della funzione f (x )

dalla disposizione dei punti di interpolazione sull’asse delle ascisse.

Posto M

= max

|f

(x )|, un limite superiore all’errore di interpolazione E

(x ) = f (x ) − p

(x ) `e dato da

|E

(x )| ≤ |ω

(x )|

(n + 1)! M

.

Errore nell’interpolazione polinomiale

L’errore di interpolazione dipende quindi:

dalla regolarit `a della funzione f (x )

dalla disposizione dei punti di interpolazione sull’asse delle ascisse.

Posto M

= max

|f

(x )|, un limite superiore all’errore di interpolazione E

(x ) = f (x ) − p

(x ) `e dato da

|E

(x )| ≤ |ω

(x )|

(n + 1)! M

.

Errore nell’interpolazione polinomiale

Si dimostra che la scelta dei nodi {x

}

per cui, per qualunque x , risulta minimo il valore del termine |ω

(x )|, corrisponde agli zeri reali del polinomio di Chebyshev di grado n+1 definito nell’intervallo [a, b]:

x

= a + b

2 − b − a

2 cos  2(i − 1) + 1 2(n + 1) π



i = 1, . . . , n + 1.

Errore nell’interpolazione polinomiale

Grafico di ω

(x ) nell’intervallo [a, b] = [−1, 1] per n = 6 e {x

}

equispaziati (linea verde)

{x

}

zeri del polinomio di Chebyshev di grado 6 (linea blu)

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1

−0.05

−0.04

−0.03

−0.02

−0.01 0 0.01 0.02 0.03 0.04 0.05

Polinomio di approssimazione ai minimi quadrati

E assegnato un insieme di m punti (x `

, y

), i = 1, . . . , m, che descrivono un certo fenomeno. Vogliamo trovare un polinomio

p

(x ) = c

+ c

x + . . . c

x

di grado n < m che approssimi la configurazione di dati assegnati secondo il criterio dei minimi quadrati, ovvero che minimizzi la norma due del vettore residuo

r = [p

(x

) − y

, p

(x

) − y

, . . . , p

(x

) − y

] ovvero la quantit `a

kAc − y k

che si pu `o scrivere anche come

m

X

i=1

(p

(x

) − y

)

Polinomio di approssimazione ai minimi quadrati

Sia A la matrice di Vandermonde

A =













1 x

x

. . . x

1 x

x

. . . x

.. .. .. .. ..

.. .. .. .. ..

1 x

x

. . . x













Polinomio di approssimazione ai minimi quadrati

Metodo delle equazioni normali

I coefficienti c si trovano risolvendo il sistema delle equazioni normali

A

Ac = A

y

Se le colonne di A sono l.i., M = A

A invertibile simmetrica e definita positiva ⇒ si usa il metodo di Cholesky

Si trova la fattorizzazione di Cholesky M = LL

Si trova la soluzione risolvendo due sistemi triangolari

Polinomio di approssimazione ai minimi quadrati

Metodo delle equazioni normali

I coefficienti c si trovano risolvendo il sistema delle equazioni normali

A

Ac = A

y

Se le colonne di A sono l.i., M = A

A invertibile simmetrica e definita positiva ⇒ si usa il metodo di Cholesky

Si trova la fattorizzazione di Cholesky M = LL

Si trova la soluzione risolvendo due sistemi triangolari

Polinomio di approssimazione ai minimi quadrati

Metodo delle equazioni normali

I coefficienti c si trovano risolvendo il sistema delle equazioni normali

A

Ac = A

y

Se le colonne di A sono l.i., M = A

A invertibile simmetrica e definita positiva ⇒ si usa il metodo di Cholesky

Si trova la fattorizzazione di Cholesky M = LL

Si trova la soluzione risolvendo due sistemi triangolari

Polinomio di approssimazione ai minimi quadrati

Metodo delle equazioni normali

I coefficienti c si trovano risolvendo il sistema delle equazioni normali

A

Ac = A

y

Se le colonne di A sono l.i., M = A

A invertibile simmetrica e definita positiva ⇒ si usa il metodo di Cholesky

Si trova la fattorizzazione di Cholesky M = LL

Si trova la soluzione risolvendo due sistemi triangolari

Polinomio di approssimazione ai minimi quadrati

Problemi

1

M pu `o risultare molto mal condizionata ⇒ soluzioni inaffidabili

2

M, a causa degli errori di calcolo, pu `o non risultare simmetrica definita positiva.

La fattorizzazione di Cholesky si blocca.

3

Si pu `o ”far finta di niente” ed evitare il problema usando la divisione a sinistra

c = M \ (A

y )

Ma...

Polinomio di approssimazione ai minimi quadrati

Problemi

1

M pu `o risultare molto mal condizionata ⇒ soluzioni inaffidabili

2

M, a causa degli errori di calcolo, pu `o non risultare simmetrica definita positiva.

La fattorizzazione di Cholesky si blocca.

3

Si pu `o ”far finta di niente” ed evitare il problema usando la divisione a sinistra

c = M \ (A

y )

Ma...

Polinomio di approssimazione ai minimi quadrati

Problemi

1

M pu `o risultare molto mal condizionata ⇒ soluzioni inaffidabili

2

M, a causa degli errori di calcolo, pu `o non risultare simmetrica definita positiva.

La fattorizzazione di Cholesky si blocca.

3

Si pu `o ”far finta di niente” ed evitare il problema usando la divisione a sinistra

c = M \ (A

y )

Ma...

Polinomio di approssimazione ai minimi quadrati

Alternativa: metodo QR

Metodo pi `u robusto che generalmente fornisce buoni risultati.

E pi `u costoso di quello delle equazioni normali. Infatti il costo ` computazionale `e O(mn

− n

/3) contro O(mn

/2 + n

/6), ma `e pi `u stabile!

A = QR [Q,R]=qr(A)

Fattorizzazione economica: restituisce le prime n colonne di Q

[S,R]=qr(A,0)

Polinomio di approssimazione ai minimi quadrati

Alternativa: metodo QR

Metodo pi `u robusto che generalmente fornisce buoni risultati.

E pi `u costoso di quello delle equazioni normali. Infatti il costo ` computazionale `e O(mn

− n

/3) contro O(mn

/2 + n

/6), ma `e pi `u stabile!

A = QR [Q,R]=qr(A)

Fattorizzazione economica: restituisce le prime n colonne di Q

[S,R]=qr(A,0)

Polinomio di approssimazione ai minimi quadrati

Alternativa: metodo QR

Metodo pi `u robusto che generalmente fornisce buoni risultati.

E pi `u costoso di quello delle equazioni normali. Infatti il costo ` computazionale `e O(mn

− n

/3) contro O(mn

/2 + n

/6), ma `e pi `u stabile!

A = QR [Q,R]=qr(A)

Fattorizzazione economica: restituisce le prime n colonne di Q

[S,R]=qr(A,0)

Polinomio di approssimazione ai minimi quadrati

Trasformo il problema dato in uno pi `u semplice, equivalente a quello dato, la cui soluzione `e ottenuta risolvendo il sistema triangolare

Rc = Y ,

dove, detta S la matrice formata dalle prime n colonne di Q, il termine noto `e

Y = S

y .

Polinomio di approssimazione ai minimi quadrati

c=polyfit(x,y,n)

Il comando polyfit usa il metodo QR per determinare i coefficienti c del polinomio di grado n di approssimazione ai minimi quadrati della configurazione (x , y ).

La soluzione del problema ai minimi quadrati con il metodo QR pu `o essere trovata equivalentemente con il comando “divisione a sinistra”

c = A\y

Polinomio di approssimazione ai minimi quadrati

c=polyfit(x,y,n)

Il comando polyfit usa il metodo QR per determinare i coefficienti c del polinomio di grado n di approssimazione ai minimi quadrati della configurazione (x , y ).

La soluzione del problema ai minimi quadrati con il metodo QR pu `o essere trovata equivalentemente con il comando “divisione a sinistra”

c = A\y