Formule di Integrazione Numerica - uniroma1.itriccardo.broglia/Didattica... · Le formule di...
Transcript of Formule di Integrazione Numerica - uniroma1.itriccardo.broglia/Didattica... · Le formule di...
Integrazione numerica: generalità
Problema: valutare l’integrale definito:
Si utilizzano opportune tecniche numeriche quando:• la primitiva di f(x) non e’ esprimibile in forma chiusa (ad
esempio f(x)=sin(x)/x, f(x)=exp(-x2));
• difficoltà nel calcolare analiticamente la primitiva F in ae/o b (ad es. F può essere espressa in forma integrale);
• i valori di f(x) sono noti solo in alcuni nodi xi=0,…,n (ad esempio a seguito di misure sperimentali).
)()(d)()( aFbFxxffIb
a−== ∫
Formule di quadraturaNoti i valori assunti dalla funzione integranda f(x) in un insieme di nodi xi=0,…,n distinti in [a,b], si definisce formula di quadratura o di integrazione numerica una formula del tipo:
)()()()(d)( *
0fRfSfRxfcxxf nnn
n
iii
b
a+=+=∑∫
=
Pesi o coefficienti{ } nici ,...,0=
∑=
=n
iiin xfcfS
0
* )()(
)()()( * fSfIfR nn −=
Somma o parte approssimante ideale
Resto o errore di troncamento
Errore di propagazione
I dati iniziali possono essere affetti da errore:
)()()()(d)( *
00fRfRfSfRcfcxxf nnn
n
iii
n
iii
b
a++=++= ∑∑∫
==
ε
∑=
=n
iiin fcfS
0)(
∑=
=n
iiicfR
0
* )( ε
Somma o parte approssimante
Errore di propagazione sui dati
nifxf iii ,...,0)( =+= ε
In assenza di errori di approssimazione sui calcoli:
Formule di quadratura interpolatoria
Le formule di quadratura interpolatorie sono basate sulla sostituzione della funzione integranda con il suo polinomio interpolatore, su un insieme “opportuno” di nodi xi=0,…,n.
Criteri di scelta della distribuzione dei nodi in [a,b]:• i nodi di interpolazione sono fissati come dato del problema
• nodi equispaziati in [a,b] ⇒ formule di Newton-Cotes• nodi situati opportunamente in [a,b], in modo da ottenere
precisione massima ⇒ formule di quadratura gaussiane.
Formule di quadratura interpolatorieA prescindere dalla distribuzione dei nodi, ed utilizzando l’espressione di Lagrange per il polinomio interpolatore:
nixxlcfRfcxxfb
a iin
n
iiii
b
a,...,0d)()()(d)(
0==++= ∫∑∫
=
ε
)()()()( *
0xExExlfxf nn
n
iii ++=∑
=
⇓
+==
∫∫∫
+
b
a nn
b
a
n
nb
a nn
xxxxfx
xn
xfxxxExR
d],...,,[)(
d!1
))(()(d)()(
0
)1(
π
ξπ
Grado di precisione
Definizione: una formula di quadratura a n+1 nodi si dice che ha grado di precisione υ se:
≠
=
0)(
0)(
fR
fR
n
n
1)(
,...,0)(+=
==
ν
ν
xxf
kxxf kper
per
Data la linearità dell’operatore di integrazione, si ha grado di precisione υ se la formula è esatta per tutti i polinomi di grado k≤υ mentre esiste almeno un polinomio di grado υ+1, per il quale la formula di quadratura non è esatta.
Grado di precisione
L’interpolazione polinomiale su n+1 nodi è esatta per polinomi di grado m≤n (cioè En(x)=0), quindi la formula di quadratura interpolatoria è esatta per ogni polinomio di grado m≤n (cioèRn(x)=0), quindi υ≥n. Inoltre:
12 +≤≤ nn ν
[ ] ℜ∈∀≥−−−=Π xxxxxxxx n 0)())(()( 210 L
0)()()()(d)(0
0
0>⇒=+Π=Π<
=
=∑∫ fRfRfRxcxx nnn
n
iii
b
a43421
Cioè esiste un polinomio di grado 2n+2 per cui la formula di quadratura non è esatta. In definitiva per il grado di precisionedelle formule di quadratura interpolatorie su n+1 nodi si ha:
Formule di Newton-Cotes
Le formule di Newton-Cotes sono formule di quadratura interpolatorie su nodi equispaziati:
nabhniihaxi
−==+= ,,0 K
Possono essere di tipo aperto o chiuso a seconda se nei nodi di interpolazione sono compresi o meno gli estremi (si costruisce il polinomio di interpolazione sui nodi xi i=1,…,n-1).
Formula del trapezio (n+1=2, υ=1)Formula del trapezio: si approssima la funzione con un polinomio di primo grado su due nodi equispaziati:
))(())((21
)()(
)()(
!2))(()()()()()()(
)2(10
01
01
10
10
)2(
21100
xfxxxxxxxxf
xxxxf
xfxxlfxlfxExlfxf on
n
iii
ξ
ξπ
−−+−−
+−−
=
=++=+=∑=
],[)(12
d))(())((21)(
2)(d
)()(
)()()(
)2(3
101
10
01
01
10
101
bafhxxfxxxxfR
ffhxxxxxf
xxxxffS
b
a
b
a
∈−=′′−−=
+=
−−
+−−
=
∫
∫
ττξ
⇓
Formula di Cavalieri-Simpson (n+1=3, υ=3)Formula di Cavalieri-Simpson o della parabola: la funzione èapprossimata con una parabola:
!3))(()()()()()(
)3(
322110xfxxlfxlfxlfxf o
ξπ+++=
],[)(90
d))(()(!3
1)(
)4(3
d)()(
)4(5
2
210
2
02
bafhxxfxfR
fffhxxlffS
b
a
b
ai
ii
∈−=′′′=
++==
∫
∫ ∑=
ττξπ
⇓
Formula dei 3/8 (n+1=4, υ=3)Formula dei 3/8: la funzione è approssimata con un polinomio di terzo grado:
],[)(803)33(
83d)( )4(
5
3210 bafhffffhxxfb
a∈−+++=∫ ττ
Formula di Milne-Boole (n+1=5, υ=5)Formula di Milne-Boole: la funzione è approssimata con un polinomio di quarto grado:
],[)(9458)73212327(
452d)( )6(
7
43210 bafhfffffhxxfb
a∈−++++=∫ ττ
Formule di Newton-Cotes: precisione
Il resto delle formule di Newton-Cotes assume l’espressione:
−−=
+=
∫
++
n
n
nn
nn
tnttt
nfhfR
0
)1(2
d)()1(
!1)()(
Lγ
ξγ
−−=
+=
∫
++
n
n
nn
nn
tnttt
nfhfR
0
2
)2(3
d)()1(
!2)()(
Lγ
ξγ
Grado di precisioneυ=nn+1 pari
n+1 dispariGrado di precisione
υ=n+1
Formule di Newton-Cotes: esempioEsempio 7.3.1: si approssimi il seguente integrale con
la formula del trapezio e di Cavalieri-Simpson:
84525)(d(x))( 241
0+−== ∫ xxxfxffI
Trapezio:
dove
2))1()0((21)(1 −=+= fffS
Cav.-Sim.: 7916.1)1(214)0(
61)(2 −=
+
+= ffffS
Nota: impiegare formule con un grado di precisione più elevato non vuol dire ottenere risultati più accurati!!!
• Esercizio consigliato [GL] 4.1, 7.3, 7.9
Formule di Newton-Cotes aperte
Le formule di Newton-Cotes aperte si ottengono utilizzando per la costruzione dei polinomi solo i nodi xi i=1,…,n-1, il grado di precisione diminuisce:
se n+1 è pari
−=
−=
1
2
n
n
ν
ν
se n+1 è dispari
Formula del punto centrale:
],[)(3
2d)( )2(3
1 bafhfhxxfb
a∈+=∫ ττ
Formule di Newton-Cotes generalizzate
• Per n>7 i coefficienti delle formule di Newton-Cotes hanno segni sia positivi che negativi, si dimostra che ciò può provocare instabilità numerica (aumento di R*(f)).
• Per evitare l’uso di formule di grado elevato e di perdere informazioni, si decompone l’intervallo in sottointervalli in ciascuno dei quali si utilizzano formule di quadratura di grado basso, formule di Newton-Cotes generalizzate.
Formula dei trapezi (υ=1)
L’intervallo di integrazione è decomposto in m sottointervalli:
mjm
abjaXXX jjj ,,0],[ 1 K=−
+=+
In ogni sottointervallo [Xj,Xj+1], j=0,…m-1 si applica la formula del trapezio con h=(b-a)/m:
],[)(12
)(2
d)(d)(
1
1
0
)2(31
01
1
0
1
+
−
=
−
=+
−
=
∈
−++=
==
∑∑
∑∫∫+
jjj
m
jj
m
jjj
m
j
x
x
b
a
xxfhffh
xxfxxf j
j
ττ
],[)(12
)(22
d)( )2(21
10 bafhabfffhxxf m
m
jj
b
a∈
−−
++= ∑∫
−
=
ττ
Formula delle parabole (υ=3)
L’intervallo di integrazione è decomposto in m sottointervalli:
mjm
abjaXXX jjj ,,0],[ 1 K=−
+=+
In ogni sottointervallo [Xj,Xj+1], j=0,…m-1 si applica la formula dei Cavalieri-Simpson con h=(b-a)/2m:
],[)(180
)(243
d)( )4(4
2
1
12
1
0120 bafhabffffhxxf m
m
jj
m
jj
b
a∈
−−
+++= ∑∑∫
−
=
−
=+ ττ
Teorema: Se f(x)∈Cυ+1[a,b], le formule di Newton-Cotes generalizzate tendono all’integrale I(f), quando il numero di nodi tende all’infinito.
Criterio di Runge: formula dei trapeziPer le formule generalizzate è possibile fornire una stima dell’errore di troncamento senza dover calcolare la derivata n+1 della funzione integranda.
Formula dei trapezi:
( ) )(12
)()()()()( )2(2 τfhabfSfRfSfI hhh−
−=+=
)(212
)()()()()( )2(2
2/2/2/ σfhabfSfRfSfI hhh
−
−=+=
Passo h →
Passo h/2 →
( ))()(31)(4/)()( 2/2/2/ fSfSfRfRfR hhhhh −≅⇒≅
Se f(2)(x) varia poco in [a,b] )()( )2()2( στ ff ≅⇒
Criterio di Runge: formula delle paraboleFormula delle parabole:
( ) )(180
)()()()()( )4(4 τfhabfSfRfSfI hhh−
−=+=
)(2180
)()()()()( )4(4
2/2/2/ σfhabfSfRfSfI hhh
−
−=+=
Passo h →
Passo h/2 →
( ))()(151)(16/)()( 2/2/2/ fSfSfRfRfR hhhhh −≅⇒≅
Se f(4)(x) varia poco in [a,b] )()( )4()4( στ ff ≅⇒
Estrapolazione di RichardsonIl criterio di Runge permette di stimare il resto della formula di quadratura con passo h/2, tramite le parti approssimanti valutate con passo h e h/2; si può usare questa stima per fornire una approssimazione più accurata dell’integrale.
Formula dei trapezi:
( ))()(31)()()()( 2/2/2/2/ fSfSfSfRfSfI hhhhh −+≅+=
( ))()(151)()()()( 2/2/2/2/ fSfSfSfRfSfI hhhhh −+≅+=
Formula delle parabole:
Estrapolazione di Richardson: esempio
Esempio 7.5.1: tramite il metodo delle parabole e l’estrapo-lazione alla Richardson, calcolare il seguente l’integrale:
7182818.11d)(1
0
1
0≅−=== ∫ eexeeI xxx
Estrapolazione di Richardson: esempio
( ) 7188611.1461)()( 12/10
2/1 ≅++== eeefSfSh
( )( ) 7183188.124121)()( 12/14/34/10
4/12/ ≅++++== eeeeefSfSh
( ) 42/2/ 1036.0)()(
151 −−≅−= fSfSR hhh
7182826.1)1036.0(7183188.1)( 42/2/ ≅−+≅+= −
hhx RSeI
Somme approssimate con passo h e h/2:
Criterio di Runge, stima del resto con passo h/2:
Estrapolazione alla Richardson:
≅
≅
≅
⇒−
−
−
6
42/
3
108.0
1037.0
1058.0
Rich
h
h
R
R
RValore esatto:
KK7182818.1)( =xeI
Formule di quadratura: esercizioEsercizio 4.2:Valutare con 4 cifre decimali esatte il valore
di π/4, mediante integrazione numerica dell’integrale:
4)arctan(d
11 1
0
1
0 2
π==
+= ∫ xx
xI
utilizzando una formula delle parabole basata sulla tavola:
0.9411760.25
0.8767120.375
0.80.5
1.00.0
0.984615f(xi)0.125xi
0.5663720.875
0.7191010.625
0.640.75
0.5f(xi)1.0xi
Scegliendo il passo e trascurando l’errore di propagazione.
• Esercizio consigliato [GL] 4.4,
Convergenza delle formule di quadratura
Una formula di quadratura è detta convergente se la succes-sione delle parti approssimanti che si ottiene aumentando il numero dei nodi converge al valore esatto dell’integrale, ovvero se all’aumentare dei nodi il resto tende a zero:
0)(lim)()(lim =⇔=∞→∞→
fRfIfS nnnn
• le formule di Newton-Cotes generalizzate verificano la proprietà di convergenza;
• il polinomio interpolatore potrebbe non convergere (feno-meno di Runge) e quindi neanche la formula di quadratura;
• le formule di quadratura interpolatorie sono convergenti in tutti i casi in cui lo è il polinomio interpolatore
Convergenza delle formule di quadratura
Teorema: se f(x)∈C∞[a,b], con [a,b] limitato, posto |f(k)(x)|≤Mk, k=0,1,…, x∈[a,b] (ad es. funzione con derivate equilimitate), risulti:
)()(lim0!
)(lim fIfSMk
abnnk
k
k=⇒=
−∞→∞→
Nota: la convergenza è una conseguenza diretta della convergenza del polinomio interpolatore.
Convergenza delle formule di quadratura
Teorema: se f(x)∈C[a,b], con [a,b] limitato, sia {Sn(f)}una successione di formule di quadratura interpolatorie:
)()(lim fIfSnn=
∞→allora:
Nota: una successione di formule di quadratura a coefficienti positivi è convergente (ad esempio formule gaussiane).
∑=
=n
iiin fcfS
0)(
se esiste una costante positiva M tale che:
nMcn
ii ∀≤∑
=0