Integrazione numerica
(estatico@uninsubria.it)
Lezione basata su appunti del prof. Marco Gaviano
Integrazione numerica 1) Formule di quadratura.
2) Grado di esattezza.
3) Metodo dei coefficienti indeterminati.
4) Formule di quadratura interpolatorie.
5) Formule di Newton-Cotes semplici. Formule di Newton-Cotes composite.
6) Errore delle Formule di Newton-Cotes.
Integrazione numerica
Consideriamo il problema di calcolare l’integrale definito
di una funzione f:[a,b]R.
Le formule di quadratura sono formule che consentono il calcolo (approssimato) di integrali definiti.
b
a
dx x
f f
I ( ) ( )
L’approssimazione dell’integrale definito
viene fatta per mezzo di una formula di quadratura del tipo
che rappresenta una combinazione lineare degli n+1 valori assunti dalla funzione f nei punti, detti nodi, x0,x1,…,xn con coefficienti fissati, detti pesi, 0,1,…,n .
b
a
dx x
f f
I ( ) ( )
n
j
j j
n f f x
I
0
) (
)
(
5
Fissato n, intendiamo approssimare il valore esatto I(f) con In(f). Al variare dai pesi e dei nodi si ottengono differenti formule di quadratura.
Diremo che una formula di quadratura ha grado di esattezza (o precisione algebrica) r>=0 se In(p)=I(p) per ogni polinomio p di grado (al più) r.
Poichè ogni formula di quadratura ha almeno grado di esattezza 0, considerando il polinomio p0(x)=1, otteniamo innanzitutto che
infatti
a b
n
j
j
0
a b
p I p
I
n
j
j
n
) (
1 )
( 0
0
0
Metodo dei coefficienti indeterminati
Per costruire una formula di quadratura, fissati arbitrariamente n+1 nodi distinti x0,x1,…,xn , si possono determinare i pesi 0,1,…,n in modo che la formula abbia grado di esattezza n.
Infatti, grazie alla linearità dell’integrale, è sufficiente imporre la condizione di esattezza sui polinomi della base canonica
n i
x I
x
In ( i ) ( i ) 0,1,...,
7
Poichè l’integrale esatto si calcola facilmente per via analitica, infatti
imponendo l’esattezza della formula di quadratura fino al grado n otteniamo
ossia il sistema lineare
con V matrice (n+1)*(n+1) di Vandermonde (non singolare) e c vettore dei termini noti.
n i
x
I ( ) 0,1,...,
, ,..., 1
, 1 0
) (
1 1
n i i
a dx b
x x
I
b
a
i i
i
i
n i i
a x b
i n i
j
j i
j 0,1,...,
1
1 1
0
c V
t
1 1 ,
ij
j
i x
V
Riassumendo, dal sistema lineare con
si ottiene il vettore contenente i coef- ficienti della formula di quadratura
n n n
n
n n n
x x
x
x x
x
x x
x
x x
x
V
2
2 2
2 2
1 2
1 1
0 2
0 0
1 1 1 1
cn
c c c
c
2 1 0
n
0 1 ...
c V
con 1
1 1
i
a c b
i i
i
n j j
n f f x
I ( ) ( )
9
Il metodo dei coefficienti indeterminati consente, in generale, di ottenere i pesi che conducono a precisione algebrica n per ogni scelta arbitraria degli n+1 nodi x0,x1,…,xn .
Tale metodo non è conveniente dal punto di vista computazionale poiché molto costoso ed instabile.
Una metodologia alternativa conduce alle formule di quadratura interpolatorie.
Formule di quadratura interpolatorie.
Nelle formule di quadratura interpolatorie, fissati arbitrariamente n+1 nodi distinti x0,x1,…,xn , si sostituisce la funzione integranda con il polinomio interpolatore di grado n passante per i punti di (x0,f(x0)), (x1,f(x1)), …, (xn,f(xn)).
Tale polinomio interpolatore, nella forma di Lagrange, conduce ad una esplicita formula per il calcolo dei pesi
0,1,…,n .
Infatti, dalla relazione
dove otteniamo j n x
x
x x x
L
n
j k
k j k
k
j ( ) , 0,1, 2,...,
0
n
j
j j
n x f x L x
p
0
) ( )
( )
(
n
j
j j
n
j
b
a
j j
b
a
n
j
j j
b
a
n n
x f
dx x
L x
f
dx x
L x
f dx
x p
f I
0 0
0
) (
) ( )
(
) ( )
( )
( )
(
ossia, la formula di quadratura interpolatoria con n+1 nodi
ha i pesi 0,1,…,n dati da
n
j
j j
n f f x
I
0
) (
)
(
b
a
j
j L (x)dx
Teorema
Ogni formula interpolatoria con n+1 nodi ha grado di esattezza almeno n.
Dimostrazione
Considerando n+1 nodi di interpolazione, se f è un polinomio di grado al più n allora, per l’unicità del polinomio interpolatore, il polinomio interpolatore pn coincide con f. La tesi si ottiene osservando che le formule interpolatorie sono esatte per costruzione sul polinomio interpolatore.
Formule di Newton-Cotes (semplici)
Sono formule di quadratura interpolatorie su [a,b]
costruite su nodi equispaziati di passo h
Fissato h, in tali formule i pesi dipendono solo da n.
Le formule si dividono in:
•Chiuse se gli estremi a e b sono inclusi tra i nodi
•Aperte se gli estremi a e b non sono inclusi tra i nodi
n j
jh x
xj 0 , 0,...,
n a
b h
b x
a
x0 , n , ( ) /
) 2 /(
) (
,
0 a h, x b h h b a n
x n
j
15
Tramite il cambio di variabile nel caso di formule chiuse si ha
dove
Si ottiene così
con valore fisso, dipendente solo da n.
n
j
j j
n
j
j j
n f f x h w f x
I
0 0
) (
) (
)
(
b n j n j
a
j
j L x dx h L x th dt h t dt
0 0
0 ) ( )
( )
(
k j
k th t
x L
t
n
j k j k
j
0
0 )
( )
(
n j
j t dt
w
0
)
(
ht x
x 0
Analogamente, nel caso formule aperte si ha
Nelle formule di Newton-Cotes, poiché i nodi sono in posizioni fissate, si ottengono pesi 0, 1, …, n che possono essere calcolati una volta per tutte.
Si ottengono così semplici tabelle contenenti i pesi al variare del grado n.
Vediamo alcuni esempi.
1
1
1
1
0 ) ( )
( )
(
n n
j j
b
a
j
j L x dx h L x th dt h t dt
Formula dei rettangoli (n=0 aperta)
è la formula aperta ottenuta per n=0. è anche detta formula del punto medio. Si ha
da cui
) 2 2 (
2 )
0(
b f a
a b b
f a h f
I
2 )
( ,
1
1
1 0 0
0
dt t
w
Formula dei trapezi (n=1 chiusa) è la formula chiusa ottenuta per n=1. Si ha
da cui
)]
( )
( 2 [
)]
( )
( 2 [
)
1( b a f a f b
b f
a h f
f
I
2 / 1 ,
) (
2 / 1 )
1 ( ,
1 )
(
1
0 1
1
1
0 0
0
dt t w
t t
dt t
w t
t
Formula di Cavalieri-Simpson (n=2 chiusa) è la formula chiusa ottenuta per n=2. Si ha
da cui
( )
4 2 )
6 ( )
2( a b f b
f a
a f f b
I
3 / 1 )
1 2 (
), 1 1 2 (
) 1 (
3 / 4 )
2 ( ),
2 ( )
(
3 / 1 )
2 )(
1 2 (
), 1 2 )(
1 2 (
) 1 (
2
0 2
2
2
0 1
1
2
0 0
0
dt t
t w
t t t
dt t t
w t
t t
dt t
t w
t t
t
.
.
.
.
Osservazioni:
i) I pesi delle formule di quadrature di Newton Cotes sono simmetrici rispetto al centro, ossia 0=n,
1=n-1, 2=n-2,… Questo è dovuto alla simmetria della base di Lagrange su nodi simmetrici.
ii) Poichè i pesi sono simmetrici, ogni formula di Newton-Cotes è esatta su ogni funzione dispari integrata su un dominio simmetrico, ossia [-a,a] (si osservi che in tal caso l’integrale definito è sempre uguale a 0). Quindi ogni formula di Newton-Cotes è esatta su ogni polinomio di grado dispari. Ne consegue che le formule di grado pari hanno grado di
25
Nella pratica, non si utilizzano formule di Newton-Cotes di grado elevato nella forma precedente, detta semplice.
Questo poiché :
i) non sempre il polinonio interpolatore converge uniformemente alla funzione, anche se quest’ultima è molto regolare (addirittura infinitamente derivabile), e quindi anche l’integrale può risultare non preciso;
ii) l’utilizzo di formule di grado elevato in aritmetica finita risulta essere numericamente instabile poiché, per n>6, i pesi 0, 1, …, n non risultano più essere tutti di segno positivo.
Formule di Newton-Cotes composite
Consideriamo una discretizzazione di n+1 punti equispaziati su [a,b] di passo h=(b-a)/n
Per l’additività dell’integrale si ha
Per approssimare I(f) possiamo quindi sommare (opportune approssimazioni de)gli n integrali sui domini
n i
ih x
xi 0 , 0,...,
n
i
x
x b
a
i
i
dx x
f dx
x f
f I
1 1
) ( )
( )
(
27
Sfruttando la proprietà additiva dell’integrale rispetto al dominio di integrazione, si suddivide l’intervallo [a,b] in sottointervalli contigui ed equispaziati e si utilizza su ciascun sottointervallo una formula di Newton-Cotes nella forma semplice. Infatti, poiché l’ampiezza h del dominio di integrazione di ogni integrale può essere resa sufficientemente piccola, una formula di Newton-Cotes di grado basso risulta già sufficientemente accurata. In tal modo si ottengono formule di quadratura molto precise e numericamente stabili.
Tali formule vengono dette formule di Newton-Cotes composite.
Formula dei rettangoli composita
Considerando la formula dei rettangoli semplice su ciascuno degli n sottointervalli [xi-1,xi], i=1,…,n
si ottiene la formula dei rettangoli composita
n
i
i
C xi x
f h
f I
1 ) 1
(
0 ( ) 2
( ) ( 1) 12
1
i i
i i
x
x
x f x
x x
dx x
f
i
i
.
Formula dei trapezi composita
Considerando la formula dei trapezi semplice su ciascuno degli n sottointervalli [xi-1,xi], i=1,…,n
si ottiene la formula dei trapezi composita
) ( )
( 2
) 2 (
) (
1
1 )
(
1 h f a f x f b
f I
n
i
i C
)]
( )
( 2 [
)
( 1 1
1
i i
i i
x
x
x f
x x f
dx x x
f
i
i
Formula di Simpson composita
Considerando la formula di Cavalieri-Simpson semplice su ciascuno degli n/2 sottointervalli [x2i-2,x2i], i=1,…,n/2
per n pari si ottiene la formula di Simpson composita
( ) 2 ( ) ( )
4 )
3 ( )
(
1 2 /
1
2 2
/
1
1 2 )
(
2 h f a f x f x f b
f I
n
i
i n
i
i C
( ) 4 ( ) ( )
) 6
( 2 2 2 2 2 2 1 2
2
2 2
i i
i i
i x
x
x f
x f
x x f
dx x x
f
i
i
33
Errore nelle formule di Newton-Cotes
Ricordiamo che se fCn+1[a,b] allora esiste un valore x t.c.
dove pnè il polinomio interpolatore di grado n.
Applicando tale risultato alle formule di quadratura interpolatorie, si ottiene
dove
) ( )
)...(
)(
)!( 1 (
) 1 ( )
( )
( n x x0 x x1 x xn f (n 1) x
x n p
x f x
E
b
a
n x
b n
a
n n
n x dx
n dx f
x p
x f f
I f
I f
E ( )
)!
1 (
) )) (
( )
( ( )
( )
( )
(
) 1
(
) )...(
)(
( )
( 0 1 n
n x x x x x x x
Otteniamo così la seguente espressione per l’errore delle formule di quadratura interpolatorie
con , dove l’ultima uguaglianza è dovuta ad una generalizzazione del teorema della media.
Nelle formule di Newton-Cotes, poiché l’insieme dei nodi è equispaziato, è possibile calcolare esplicitamente gli integrali
b n(x)dx b (x x0)(x x1)...(x xn)dx
b
a n b n
a
n x
n
n x dx
n dx f
n x f f
E ( )
)!
1 ) (
)! ( 1 (
) ) (
(
) 1 ( )
1
(
a,b
Ad esempio, per n=1, risolvendo analiticamente l’integrale
otteniamo la seguente espressione per l’errore commesso dalla formula di quadratura dei trapezi semplice
dove , sebbene non sia conosciuto esplicitamente.
, ) 12 (
) '' )! (
1 (
) ''
( 3
1 f b a
dx n x
f f E
b
a
n
, 6
) ) (
)(
( )
(
3 1
a dx b
b x
a x
dx x
b
a b
a
a,b
Le espressioni trovate per l’errore possono essere facilmente estese al caso della formula di quadratura composite: basterà sommare i contributi dei singoli errori su ogni sottointervallo.
Ad esempio nel caso della formula di quadratura dei trapezi composita, considerando l’errore all’intervallo i- esimo [xi-1,xi], i=1,…,n
dove , e sommando tali errori, si ottiene l’errore
3 3
1 1
) (
1 12
) '' 12 (
' ) '
! ( 2 ) ''
(
1
f h x
f x dx
f x f
E i i i i
x
x i i
i
i
x ,i1 xi
commesso dalla formula dei trapezi composita
con dato dal teorema della media.
Come conseguenza, poiché h=(b-a)/n, si ha che l’errore tende a zero per n.
Si osservi che tale risultato è dovuto alla riduzione a zero dell’ampiezza h di ciascun sottointervallo [xi-1,xi], i=1,…,n.
'' ) 12 (
) '' (
12 12
) '' (
2
1 1
2 3
) ( 1
f a h b
n f a b
h h f f
E
n
i
i n
i C i
a,b
Svolgendo calcoli analoghi per le formule di Newton-Cotes dei rettangoli e di Simpson, semplici e composite, posto Mn=maxx[a,b]|f(n)(x)|, si ottiene la tabella seguente
4 4 )
( 2 4 5
2
2 2 )
( 1 2 3
1
2 2 )
( 0 2 3
0
) 180 (
) ( )
2 / ) 90 ((
) ( Simpson
) 12 (
) ( )
12 ( )
(
Trapezi
) 24 (
) ( )
24 ( )
(
Rettangoli
composite Formule
semplici Formule
h a M b
f E
a M b
f E
h a M b
f E
a M b
f E
h a M b
f E
a M b
f E
C C C
Esempio: numero di nodi con f.d.q. di Simpson composita Sia f(x)=ex. In tal caso Mn=maxx[a,b]|f(n)(x)|= eb per ogni n.
Si eottiene che l’errore commesso dalla formula di quadratura di Simpson composita è maggiorato da
In questo caso, se vogliamo un errore minore di 10-6, integrando su [a,b]=[0,3], occorre utilizzare n+1 nodi con
4 )
(
2 ( )
) 180
( e b a h
f E
b
C
1 . 72 180 3
10 ossia )
) ( 180 (
4 5
3 4 6
e
n n a a b
eb b
