Slide Integrazione Numerica

Claudio Estatico
([email protected])
Integrazione numerica
1
Integrazione Numerica
Integrazione numerica
1)
2)
3)
4)
5)
Formule di quadratura.
Grado di esattezza.
Metodo dei coefficienti indeterminati.
Formule di Newton-Cotes semplici. Formule
di Newton-Cotes composite.
Errore delle Formule di Newton-Cotes.
2
Integrazione Numerica
Integrazione numerica
Consideriamo il problema di calcolare l’integrale definito
b
I ( f ) = ∫ f ( x)dx
a
di una funzione f:[a,b]→
→R.
Le formule di quadratura sono formule che consentono il
calcolo (approssimato) di integrali definiti. Queste sono
particolarmente utili per il calcolo tramite elaboratore.
3
Integrazione Numerica
L’approssimazione dell’integrale definito
b
I ( f ) = ∫ f ( x)dx
a
viene fatta per mezzo di una formula di quadratura del
tipo
n
In ( f ) = ∑α j f (x j )
j =0
che rappresenta una media pesata degli n+1 valori assunti
dalla funzione f nei punti, detti nodi, x0,x1,…,xn , con pesi
fissati α0,α
α1,…,α
αn .
4
Integrazione Numerica
Fissato n, intendiamo quindi 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 (GdE, 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
n
innanzitutto che
∑α
n
j =0
j
=b−a
infatti I n ( p0 ) = ∑ α j 1 = I ( p0 ) = b − a
j =0
5
Integrazione Numerica
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
I n ( x ) = I ( x ) i = 0,1,..., n
i
i
6
Integrazione Numerica
i = 0,1,..., n
Poichè l’integrale esatto I ( x )
calcola facilmente per via analitica, infatti
i
b
I ( x ) = ∫ x dx =
i
i
b
i +1
a
−a
i +1
i +1
si
i = 0,1,..., n ,
imponendo l’esattezza della formula di quadratura fino al
grado n otteniamo n
i +1
i +1
∑x α
j =0
ossia il sistema lineare
i
j
j
=
b
−a
i +1
V α =c
i = 0,1,..., n
t
con V matrice (n+1)*(n+1) di Vandermonde
(non singolare) e c vettore dei termini noti.
j −1
i −1
Vi , j = x
7
Integrazione Numerica
V α =c
t
Riassumendo, dal sistema lineare
con
1 x0 x02 L x0n 
 c0 


 
n
2
1 x1 x1 L x1 
 c1 
i +1
i +1
b −a

2
n


con ci =
V = 1 x2 x2 L x2
c = c2


 
i +1
M M
M
M
M
M 

c 
2
n
1
x
x
L
x
 n
n
n
n 

si ottiene il vettore α = (α 0 α1 ... α n )t contenente i coefficienti della formula di quadratura
n
In ( f ) = ∑α j f (x j )
j =0
8
Integrazione Numerica
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 è però conveniente dal punto di vista
computazionale poiché molto costoso ed instabile.
Risulta invece molto utile considerare nodi equispaziati,
in modo da semplificare il calcolaro dei coefficienti della
formula di quadratura. Tali coefficienti possono essere
così calcolati preliminarmente, “una volta per tutte”.
9
Integrazione Numerica
Formule di Newton-Cotes (semplici)
Sono formule di quadratura sull’intervallo [a,b] costruite
su nodi equispaziati di passo h
x j = x0 + jh,
j = 0,..., n
x0 = a , x n = b ,
h = (b − a ) / n
Fissato h, in tali formule i pesi α j 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
x0 = a + h , x n = b − h ,
h = (b − a ) /( n + 2)
10
Integrazione Numerica
Tramite il cambio di variabile x = x0 + ht si ottiene
b
n
a
0
I ( f ) = ∫ f ( x)dx = h ∫ f ( x0 + ht )dt
che conduce alla formula di quadratura seguente
n
n
j =0
j =0
I n ( f ) = ∑ α j f ( x j ) = h∑ w j f ( x j )
con w j valori fissi, calcolati una volta per tutte, dipendenti
solo dal tipo di formula (ossia se aperta o chiusa, e dal
numero di punti n).
11
Integrazione Numerica
Si ottengono così semplici tabelle contenenti i pesi al
variare del grado n.
Si osservi che:
i) se la formula è chiusa, allora
n
∑w
j =0
j
=n
i) se la formula è aperta, allora
n
∑w
j =0
Vediamo alcuni esempi.
j
= n+2
12
Integrazione Numerica
Si ottengono così semplici tabelle contenenti i pesi al
variare del grado n.
Vediamo alcuni esempi.
Formula dei rettangoli (n=0, aperta, GdE=1)
è la formula aperta ottenuta per n=0. è anche detta
formula del punto medio. Si ha
w0 = 2
da cui
a+b
a+b
I 0 ( f ) = 2h f 
 = (b − a ) f 

 2 
 2 
13
Integrazione Numerica
Formula dei trapezi (n=1, chiusa, GdE=1)
è la formula chiusa ottenuta per n=1. Si ha
w0 = 1 / 2
w1 = 1 / 2
da cui
h
b−a
I1 ( f ) = [ f (a ) + f (b)] =
[ f (a ) + f (b)]
2
2
14
Integrazione Numerica
Formula di Cavalieri-Simpson (n=2, chiusa, GdE=3)
è la formula chiusa ottenuta per n=2. Si ha
w0 = 1 / 3
w1 = 4 / 3
w2 = 1 / 3
da cui

b−a 
a+b
I2 ( f ) =
f (a ) + 4 f 
 + f (b)

6 
 2 

Ovviamente si potrebbe aumentare il valore di n……
15
Integrazione Numerica
.
16
Integrazione Numerica
.
17
Integrazione Numerica
.
18
Integrazione Numerica
.
19
Integrazione Numerica
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,…
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
esattezza n+1 (il primo dispari successivo all’n pari).
20
Integrazione Numerica
Nella pratica, non si utilizzano formule di Newton-Cotes
di grado elevato nella forma precedente, detta
semplice.
Questo poiché l’utilizzo di formule di grado elevato in
aritmetica finita risulta essere numericamente
instabile (per n>6, i pesi α0, α1, …, αn non risultano
più essere tutti di segno positivo, e questo crea
problemi nel calcolo tramite elaboratore…).
21
Integrazione Numerica
Formule di Newton-Cotes composite
Consideriamo una discretizzazione di n+1
equispaziati su [a,b] di passo h=(b-a)/n
xi = x0 + ih,
punti
i = 0,..., n
Per l’additività dell’integrale si ha
b
n
I ( f ) = ∫ f ( x)dx = ∑
a
xi
∫
f ( x)dx
i =1 xi −1
Per approssimare I(f) possiamo quindi sommare
(opportune approssimazioni de)gli n integrali sui domini
22
di ampiezza minore.
Integrazione Numerica
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.
23
Integrazione Numerica
Formula dei rettangoli composita
Considerando la formula dei rettangoli semplice su
ciascuno degli n sottointervalli [xi-1,xi], i=1,…,n
 xi −1 + xi 
∫x f ( x)dx = ( xi − xi −1 ) f  2 
i −1
xi
si ottiene la formula dei rettangoli composita
n
I
(C )
0
( f ) = h∑
i =1
 xi −1 + xi 
f

 2 
24
Integrazione Numerica
.
25
Integrazione Numerica
Formula dei trapezi composita
Considerando la formula dei trapezi semplice su ciascuno
degli n sottointervalli [xi-1,xi], i=1,…,n
xi − xi −1
∫x f ( x)dx = 2 [ f ( xi −1 ) + f ( xi )]
i −1
xi
si ottiene la formula dei trapezi composita
I
(C )
1
n −1
h

( f ) =  f (a ) + 2∑ f ( xi ) + f (b)
2
i =1

26
Integrazione Numerica
.
27
Integrazione Numerica
Formula di Simpson composita
Considerando la formula di Cavalieri-Simpson semplice su
ciascuno degli n/2 sottointervalli [x2i-2,x2i], i=1,…,n/2
x2 i − x 2 i − 2
[
]
f
(
x
)
dx
=
f
(
x
)
+
4
f
(
x
)
+
f
(
x
)
2
i
−
2
2
i
−
1
2
i
∫
6
x2 i −2
x2 i
per n pari si ottiene la formula di Simpson composita
I
(C )
2
n / 2 −1
h

( f ) =  f (a ) + 4∑ f ( x2i −1 ) + 2 ∑ f ( x2i ) + f (b)
3
i =1
i =1

n/2
28
Integrazione Numerica
Errore nelle formule di Newton-Cotes
Consideriamo l’errore che si commette approssimando
l’integrale mediante la formula di quadratura
En ( f ) = I ( f ) − I n ( f )
Svolgendo opportuni calcoli, per le formule di NewtonCotes dei rettangoli e di Simpson, semplici e composite,
posto Mn=maxx∈∈[a,b]|f(n)(x)|, si ottiene la tabella seguente,
che permette di stimare l’errore massimo En ( f )
commesso
29
Integrazione Numerica
.
Formule semplici
M2
Rettangoli
E0 ( f ) ≤
(b − a ) 3
24
M2
Trapezi
(b − a ) 3
E1 ( f ) ≤
12
M4
Simpson E2 ( f ) ≤
((b − a ) / 2) 5
90
Formule composite
M2
E (f) ≤
(b − a )h 2
24
M2
(C )
(b − a )h 2
E1 ( f ) ≤
12
M4
(C )
E2 ( f ) ≤
(b − a ) h 4
180
(C )
0
30
Integrazione Numerica
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
b
E
(C )
2
e
4
(f)≤
(b − a )h
180
In questo caso, se vogliamo un errore minore di τ=10-6,
integrando su [a,b]=[0,3], occorre utilizzare n+1 nodi con
e
 (b − a ) 
(b − a )
 <τ
180
 n 
b
4
6
3
10 e 5
ossia n >
3 ≈ 72.1
180
4
31