Formule di

Formule di

Integrazione Numerica

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(-x²));

• difficoltà nel calcolare analiticamente la primitiva F in a e/o b (ad es. F può essere espressa in forma integrale);

• i valori di f(x) sono noti solo in alcuni nodi x_i=0,…,n (ad esempio a seguito di misure sperimentali).

) ( )

( d

) ( )

( f f x x F b F a

I

a

= −

= ∫

Formule di quadratura

Noti i valori assunti dalla funzione integranda f(x) in un insieme di nodi x_i=0,…,n distinti in [a,b], si definisce formula di

quadratura o di integrazione numerica una formula del tipo:

) ( )

( )

( )

( d

)

( ^*

0

f R f

S f

R x

f c x

x

f ⁿ _{n n n}

i

i i

b

a =

∑

∫

Pesi o coefficienti

{ }

∑

= ⁿ

i

i i

n f c f x

S

0

*( ) ( )

) ( )

( )

( f I f S^* f

R_n = − _n

Somma o parte approssimante ideale Resto o errore di troncamento

Errore di propagazione

I dati iniziali possono essere affetti da errore:

) ( )

( )

( )

( d

)

( ^*

0 0

f R f

R f

S f

R c

f c x

x

f ⁿ _{n n n}

i

i i n

i

i i b

a =

∑

∑

∫

ε

∑

= ⁿ

i

i i

n f c f

S

0

) (

∑

= ⁿ

i

i

ci

f R

0

*( )

ε

Somma o parte approssimante Errore di propagazione sui dati

n i

f x

f ( _i ) = _i +

ε

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 x

=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 interpolatorie

A prescindere dalla distribuzione dei nodi, ed utilizzando l’espressione di Lagrange per il polinomio interpolatore:

n i

x x

l c

f R f

c x

x

f ^b

i a i n

n

i

i i

i b

a ( )d ( ) ( ) ( )d 0,...,

0

=

= +

+

=

∑ ∫

∫

ε

) ( )

( )

( )

( ^*

0

x E x

E x

l f x

f ⁿ _{n n}

i

i

i + +

=

∑

=

⇓







= +

=

∫

∫ ∫

+

b

a n n

b a

n b n

a n

n

x x

x x f x

n x

x x f

x x E x

R

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 )

( f R

f R

n n

) 1

(

,..., 0 )

(

= +

=

=

ν

ν x

x f

k x

x

f ^k

per 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è E_n(x)=0), quindi la formula di quadratura interpolatoria è esatta per ogni polinomio di grado m≤n (cioè R_n(x)=0), quindi υ≥n. Inoltre:

1 2 +

≤

≤ n

n ν

[

]

=

Π(x) (x x₀)(x x₁)L(x x_n) ² 0 x

0 )

( )

( )

( )

( d

) ( 0

0 0

>

⇒

= +

Π

= Π

<

=

∑

∫

i

i i

b

a 14243

Cioè esiste un polinomio di grado 2n+2 per cui la formula di quadratura non è esatta. In definitiva per il grado di precisione delle 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:

n a h b

n i

ih a

x_i −

=

= +

= 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 x_i 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:

)) ( ( )

)(

2 ( 1 ) (

) (

) (

) (

! 2

)) ( ) (

( )

( )

( )

( )

( )

(

) 2 ( 1 0

0 1

1 0 1

0 0 1

) 2 ( 2

1 1 0

0

x f

x x x

x x x

x f x

x x

x f x

x x f

x l f x

l f x

E x

l f x

f ⁿ _{n o}

i

i i

ξ π ξ

−

−

− + + −

−

= −

= +

+

= +

=

∑

=

] , [ )

12 ( d

)) ( ( ) )(

2 ( ) 1

(

2

) d (

) (

) (

) (

) ) (

(

) 2 ( 3 1

0 1

1 0

0 1

0 1

1 0

1 0

1

b a h f

x x

f x x x

x f

R

f f

x h x

x x f x

x x

x f x

f S

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 ( 3

2 2 1

1 0

x x f

x l f x

l f x

l f x

f = _o + + +π ξ

] , [ )

90 ( d

)) ( ( )

! ( 3 ) 1 (

) 4

3 ( d

) ( )

(

) 4 ( 5 2

2 1

0 2

0 2

b a h f

x x

f x f

R

f f

h f x

x l f f

S

b a b a i

i i

∈

−

′′′ =

=

+ +

=

=

∫

∫ ∑

τ τ

ξ π

⇓

Formula dei 3/8 (n+1=4, υ =3)

Formula dei 3/8: la funzione è approssimata con un polinomio di terzo grado:

] , [ )

80 ( ) 3

3 3

8 ( d 3

)

( ⁽⁴⁾

5 3

2 1

0 h f a b

f f

f h f

x x

b f

a = + + + − ∈

∫

Formula di Milne-Boole (n+1=5, υ =5)

Formula di Milne-Boole: la funzione è approssimata con un polinomio di quarto grado:

] , [ )

945 ( ) 8

7 32

12 32

7 45 ( d 2

)

( ⁽⁶⁾

7 4

3 2

1

0 h f a b

f f

f f

h f x

x

b f

a = + + + + − ∈

∫

Formule di Newton-Cotes: precisione

Il resto delle formule di Newton-Cotes assume l’espressione:









−

−

=

= +

∫

+ +

n n

n n n n

t n t

t t

n h f

f R

0

) 1 2 (

d ) (

) 1 (

! 1

) ) (

( γ L

γ ξ









−

−

=

= +

∫

+ +

n n

n n n n

t n t

t t

n h f

f R

0 2

) 2 3 (

d ) (

) 1 (

! 2

) ) (

( γ L

γ ξ

Grado di precisione υ=n

n+1 pari

n+1 dispari Grado di precisione

υ=n+1

Formule di Newton-Cotes: esempio

Esempio 7.3.1: si approssimi il seguente integrale con la formula del trapezio e di Cavalieri-Simpson:

8 45

25 )

( d

(x) )

( ^{1 4 2}

0 = − +

=

∫

f I

Trapezio:

dove

2 ))

1 ( )

0 ( 2 (

) 1

1( f = f + f = −

S

Cav.-Sim.: ^{(1) 1.7916}

2 4 1

) 0 6 (

) 1

2(  = −



 



  +



 

 + 

= f f f

f S

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 x_i 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 ( 2

d )

( ⁽²⁾

3

1 h f a b

f h x

x

b f

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:

m m j

a j b

a X

X

X _j, _j ] _j 0, ,

[ ₊₁ = + − = K

In ogni sottointervallo [X_j,X_j+1], j=0,…m-1 si applica la formula del trapezio con h=(b-a)/m:

] ,

[ )

12 ( )

2(

d ) ( d

) (

1 1

0

) 2 3 (

1

0

1 1

0

1

+

−

=

−

= +

−

=

 ∈



 



− +

+

=

=

=

∑

∑

∑∫

∫

j j j

m

j

j m

j

j j

m

j x x b

a

x x h f

f h f

x x f x

x

f ^j

j

τ τ

] , [ )

12 ( ) 2 (

d 2 )

( ⁽²⁾

1 2

1

0 b a h f a b

f f

h f x x

f ^m _m

j j b

a − ∈

−



 



 + +

=

∑

∫

Formula delle parabole ( υ =3)

L’intervallo di integrazione è decomposto in m sottointervalli:

m m j

a j b

a X

X

X _j, _j ] _j 0, ,

[ ₊₁ = + − = K

In ogni sottointervallo [X_j,X_j+1], j=0,…m-1 si applica la formula dei Cavalieri-Simpson con h=(b-a)/2m:

] , [ )

180 ( ) 2 (

3 4 d

)

( ⁽⁴⁾

4 2

1

1 2 1

0

1 2

0 b a h f a b

f f

f h f

x x

f ^m _m

j

j m

j

j 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 trapezi

Per 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 ) ) (

( )

( )

( )

( b a h ² f ⁽²⁾ τ

f S f

R f

S f

I = _h + _h = _h − −

) 2 (

12 ) ) (

( )

( )

( )

( ⁽²⁾

2 2

/ 2

/ 2

/ b a h f σ

f S

f R

f S

f

I _{h h h} 



 



− 

−

= +

=

Passo h → Passo h/2 →

( ^{( ) ( )})

3 ) 1 ( 4

/ ) ( )

( _{/2 /2}

2

/ f R f R f S f S f

R_h ≅ _h ⇒ _h ≅ _h − _h

Se f⁽²⁾(x) varia poco in [a,b] ⇒ f ⁽²⁾(τ ) ≅ f ⁽²⁾(σ )

Criterio di Runge: formula delle parabole

Formula delle parabole:

( ) ^{( )}

180 ) ) (

( )

( )

( )

( b a h ⁴ f ⁽⁴⁾ τ

f S f

R f

S f

I = _h + _h = _h − −

) 2 (

180 ) ) (

( )

( )

( )

( ⁽⁴⁾

4 2

/ 2

/ 2

/ b a h f σ

f S

f R

f S

f

I _{h h h} 



 



− 

−

= +

=

Passo h → Passo h/2 →

( ^{( ) ( )})

15 ) 1

( 16

/ ) ( )

( _{/2 /2}

2

/ f R f R f S f S f

R_h ≅ _h ⇒ _h ≅ _h − _h

Se f⁽⁴⁾(x) varia poco in [a,b] ⇒ f ⁽⁴⁾(τ ) ≅ f ⁽⁴⁾(σ )

Estrapolazione di Richardson

Il 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:

(

)

3 ) 1 ( )

( )

( )

( f S _/2 f R _/2 f S _/2 f S _/2 f S f

I = _h + _h ≅ _h + _h − _h

(

)

15 ) 1

( )

( )

( )

( f S _/2 f R _/2 f S _/2 f S _/2 f S f

I = _h + _h ≅ _h + _h − _h

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 .

1 1

d )

(

0 1

0

= = − ≅

= ∫ ^{e x e e}

e

I

Estrapolazione di Richardson: esempio (

)

6 ) 1 ( )

( f = S_1/2 f = e⁰ + e^1/2 +e¹ ≅ S_h

( )

(

)

12 ) 1

( )

( _1/4 ^{0 1/4 3/4 1/2 1}

2

/ f = S f = e + e +e + e + e ≅

S_h

( _/2 ) ⁴

2

/ ( ) ( ) 0.3610

15

1 ₋

−

≅

−

= S f S f

R_{h h h}

7182826 .

1 ) 10 36 . 0 ( 7183188 .

1 )

(e^x = S_h/2 + R_h/2 ≅ + − ⁻⁴ ≅ I

Somme approssimate con passo h e h/2:

Criterio di Runge, stima del resto con passo h/2:

Estrapolazione alla Richardson:









≅

≅

≅

⇒

−

−

−

6 4 2

/

3

10 8 . 0

10 37 . 0

10 58 . 0

Rich h

h

R R

Valore esatto: R K 7182818K

. 1 ) (e^x = I

Formule di quadratura: esercizio

Esercizio 4.2:Valutare con 4 cifre decimali esatte il valore di π/4, mediante integrazione numerica dell’integrale:

) 4 arctan(

1 d

1 ¹

0 1

0 2

=

π

=

∫

I

utilizzando una formula delle parabole basata sulla tavola:

0.941176 0.25

0.876712 0.375

0.8 0.5 1.0

0.0

0.984615 f(x_i)

0.125 x_i

0.566372 0.875 0.719101

0.625

0.64 0.75

0.5 f(x_i)

1.0 x_i

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 = ⇔ =

∞

→

∞

→ S f I f R_n f

n n n

• 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)|≤M_k, k=0,1,…, x∈[a,b] (ad es. funzione con derivate equilimitate), risulti:

) ( )

( lim

! 0 )

lim ( M S f I f

k a b

n n k

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 {S_n(f)}

una successione di formule di quadratura interpolatorie:

) ( )

(

limS_n f I f

n =

∞

allora: →

Nota: una successione di formule di quadratura a coefficienti positivi è convergente (ad esempio formule gaussiane).

∑

= ⁿ

i

i i

n f c f

S

0

) (

se esiste una costante positiva M tale che:

n M

c

n

i

i ≤ ∀

∑

Convergenza: esempio

Esempio 7.9.1: si approssimi il seguente integrale con una successione di formule di Newton-Cotes con n+1 dispari:

6516 .

2 arctg(4)

2 arctg(x)

1 d

1 ⁴

4 4

4 2 = = ≅

+ ⁻

∫

5956 .

3 )

(

9411 .

1 ) (

3288 .

3 )

(

2776 .

2 )

(

4902 .

5 )

(

10 8 6 4 2

=

=

=

=

=

f S

f S

f S

f S

f S Si ha la successione: