Quadratura numerica

Quadratura numerica

Alvise Sommariva

Universit`a degli Studi di Padova Dipartimento di Matematica Pura e Applicata

Quadratura numerica

Il problema della quadratura numerica consiste nell’approssimare l’integrale definito di una funzione f in un intervallo avente estremi di integrazione a, b (non necessariamente finiti) cio`e

I(w )(f ) := I(w )(f , a, b) = Z b a f(x) w (x)dx con I_N(w )(f ) := N X k=1 wif(xi)

Formule interpolatorie

Sia w : (a, b) → R una funzione non negativa, con (a, b) non necessariamente limitato, tale che

1. Rb

a |x| n_w

(x) dx < +∞ per tutti gli n ∈ N; 2. Rb

a g(x) w (x) dx = 0 per qualche funzione continua e non

negativa g implica g ≡ 0 in (a, b).

La funzione w `e detta peso. Le funzioni peso pi`u comuni sono 1. w_{(x) = 1 con x ∈ [−1, 1] (peso di Legendre);}

2. w(x) = √1

1−x2 con x ∈ (−1, 1) (peso di Chebyshev);

3. w_{(x) = (1 − x}2)γ−(1/2) _{con x ∈ (−1, 1), γ > (−1/2) (peso di} Gegenbauer);

4. w_{(x) = (1 − x)}α_{· (1 + x)}β _{con x ∈ (−1, 1), α > −1, β > −1} (peso di Jacobi);

Formule interpolatorie

Supponiamo sia I = (a, b) (o I = [a, b]) con a < b finiti,

x₁, . . . , xN un insieme di N punti a 2 a 2 distinti di I ed f ∈ C (I).

Allora esiste finito I(w )_{(f ). Infatti se I `e limitato, per il teorema di}

Weierstrass e l’integrabilit`a della funzione w , abbiamo |I(w )(f )| :=     Z b a f(x) w (x)dx    ≤ Z b a |f (x)| w(x)dx ≤ kf k∞kwk 1 < +∞

Se pN−1(x) =PNi=1f(xi)Li(x)`e il pol. che interpola (xi, f (xi))

con i = 1, . . . , N, (Li `e l’i-simo polinomio di Lagrange)

Formule interpolatorie

Definizione. Una formula di quadratura Z b a f(x)w (x)dx _≈ N X i=1 wif(xi) (2) per cui wk = Z b a Li(x) w (x)dx, k = 1, . . . , N (3) si dice interpolatoria.

Definizione. Una formula Rb

a f(x)w (x)dx ≈

PM

i=1wif(xi) ha

Formule di Newton-Cotes

Si supponga [a, b] un intervallo chiuso e limitato di R e sia w ≡ 1. Per semplicit`a di notazione, in questo caso porremo I := I(w )= I1.

Il primo esempio di formule interpolatorie che consideriamo sono le regole di tipo Newton-Cotes chiuse che si ottengono integrando l’interpolante di f in nodi equispaziati

xk = a + (k − 1) (b − a)

N_{− 1} , k = 1, . . . , N. Esempi:

◮ N=2, regola del trapezio,g.d.p.=1:

I_{(f ) ≈ S1}(f ) := S1(f , a, b) := (b−a) (f (a)+f (b))₂

Formule di Newton-Cotes

Figura: Regola del trapezio e di Cavalieri-Simpson per il calcolo di R2

Errori formule di Newton-Cotes

Denotiamo con Pk lo spazio dei polinomi di grado k. Allora

valgono le seguenti formule d’errore:

◮ regola del trapezio,g.d.p.=1:

E1(f ) := I (f ) − S1(f ) = −h

3

12 f(2)(ξ) per qualche ξ ∈ (a, b).

◮ regola di Cavalieri-Simpson,g.d.p.=3: E3(f ) := I (f ) − S3(f ) = −h 5 90 f(4)(ξ), h = b_−a 2 per qualche ξ ∈ (a, b);

Si noti il legame tra formule dell’errore e g.d.p.:

◮ nel caso della formula dei trapezi, se f ∈ P₂, allora potrebbe

essere essere f(2)_{(ξ) 6= 0, mentre se f ∈ P}

1, allora f(2)(ξ) = 0;

◮ nel caso della formula di Cavalieri-Simpson, se f ∈ P₄, allora

potrebbe essere essere f(4)_{(ξ) 6= 0, mentre se f ∈ P}3, allora

Formule di Newton-Cotes composte

Si suddivida l’intervallo (chiuso e limitato) [a, b] in N subintervalli Tj = [xj, xj+1] tali che xj = a + jh con h = (b − a)/N. Dalle

propriet`a dell’integrale Z b a f(x) dx = N₋₁ X j=0 Z x_j+1 xj f_{(x) dx ≈} N₋₁ X j=0 S(f , xj, xj+1) (4)

Formule di Newton-Cotes

Figura: Formula dei trapezi compostaR2

Formule dei trapezi composte

Formula composta dei trapezi: fissati il numero N di subintervalli e i punti xk = a + kh dove h = b−a_N `e definita da

Formule di Cavalieri-Simpson composte

Formula composta di Cavalieri-Simpson: fissati il numero N di subintervalli e i punti xk = a + kh/2 dove h = b−a_N sia

Formule gaussiane

Nelle formule interpolatorie di Newton-Cotes (come ad esempio la regola del Trapezio o di Cavalieri-Simpson) i nodi x1, . . . , xn sono

equispaziati e il grado di precisione δ `e generalmente uguale almeno a n − 1 ma in alcuni casi, come per la regola di Cavalieri-Simpson, uguale al numero di nodi n. Vediamo ora formule Pn

k=1wkf(xk)

◮ hanno grado di precisione δ maggiore di 2n − 1;

◮ per qualche funzione f : (a, b) → R continua approssimino

I(w )(f ) :=Rb

a f(x)w (x) dx, con (a,b) non necessariamente

Formule gaussiane

Teorema. Per ogni n ≥ 1 esistono e sono unici dei nodi x1, . . . , xn

e pesi w1, . . . , wn per cui il grado di precisione sia almeno 2n − 1. I

nodi sono gli zeri del polinomio ortogonale di grado n, φn(x) = An· (x − x1) · . . . · (x − xn)

e i corrispettivi pesi sono wi = Z b a Li(x)w (x)dx = Z b a Li(x)w (x)dx, i = 1, . . . , n.

Vantaggi integrali con peso

Diamo di seguito l’idea sul perch`e si utilizzino funzioni peso w per il calcolo di integrali. Se dobbiamo approssimareRb

a g(x) dx con g

regolare allora di solito non sar`a difficile calcolare numericamente il valore dell’integrale, mentre se g `e poco regolare sar`a molto pi`u oneroso ottenere buoni risultati.

Introducendo una funzione peso w , e supposto che f = g /w sia regolare, si considera il calcolo di

Vantaggi integrali con peso

Teorema. Sia (a, b) un intervallo limitato e si supponga w _{: (a, b) → R sia una funzione peso, I}(w )=Rb

a f(x)w (x)dx e

Im(w )(f ) :=Pm_k=1wif(xi) una formula di quadratura avente g.d.p.

n_{. Allora ricordato che kI}nk∞= supf_{∈C (a,b)\0}|In(f )|/kf k∞,

kwk1 = Rb a w(x)dx, abbiamo |I(w )− Im(w )(f )| ≤  kwk1+ kIm(w )k_∞  · min qn∈Pnkf − q nk∞.

Esempio

Consideriamo il calcolo approssimato Z 1

−1

exp (x)√_{1 − x dx = 1.7791436546919097925911790299941.} (7)

◮ Non `e suggerito il calcolo dell’integrale con formule composte

poich`e la funzione exp (x)√<sub>1 − x `e poco regolare.</sub>

◮ Non `e indicato usare formule gaussiane con peso w (x) = 1

poich`e la funzione exp (x)√<sub>1 − x `e poco regolare.</sub>

◮ Si suggerisce di usare formule gaussiane con peso di Jacobi

Formula trapezi composta

La funzione trapezi composta appena esposta calcola i nodi e i pesi della omonima formula composta.

f u n c t i o n [ x , w]= trapezi_composta ( N , a , b )

% FORMULA DEI TRAPEZI COMPOSTA. % INPUT :

% N : NUMERO SUBINTERVALLI . % a , b : ESTREMI DI INTEGRAZIONE . % OUTPUT :

% x : NODI INTEGRAZIONE .

% w : PESI INTEGRAZIONE ( INCLUDE I L PASSO ! ) .

h=(b−a ) /N ; % PASSO INTEGRAZIONE .

x=a : h : b ; x=x ’ ; % NODI INTEGRAZIONE .

w=ones ( N +1 ,1) ; % PESI INTEGRAZIONE .

Formula Cavalieri-Simpson composta

La funzione simpson composta appena esposta calcola i nodi e i pesi della omonima formula composta.

f u n c t i o n [ x , w]= simpson_composta ( N , a , b )

% FORMULA DI SIMPSON COMPOSTA. % INPUT :

% N : NUMERO SUBINTERVALLI . % a , b : ESTREMI DI INTEGRAZIONE . % OUTPUT :

% x : INTEGRAZIONE .

% w : PESI INTEGRAZIONE ( INCLUDE I L PASSO ! ) .

h=(b−a ) /N ; % AMPIEZZA INTERVALLO .

x=a : ( h / 2 ) : b ; x=x ’ ; % NODI INTEGRAZIONE .

w=ones ( 2 ∗ N +1 ,1) ; % PESI INTEGRAZIONE .

Esempio 1

Vogliamo approssimare l’integrale R1

−1x20dx= 2/21 ≈ 0.09523809523810 tramite le formule

composte dei trapezi e Cavalieri-Simpson. Perch`e il paragone sia veritiero, decidiamo che il numero di valutazioni della funzione integranda sia uguale. Scriviamo nel file demo composte.m

N=11; %SCEGLIERE DISPARI .

a=−1; b =1; f=inline (’ x . ˆ 2 0 ’) ;

% a =0; b =1; f= i n l i n e ( ’ exp ( x ) ’ ) ;

N_trap=N −1; % TRAPEZI COMPOSTA.

[ x_trap , w_trap ]= trapezi_composta ( N_trap , a , b ) ; fx_trap=f e v a l( f , x_trap ) ; I_trap=w_trap ’ ∗ fx_trap ; N_simpson=(N −1) / 2 ; % CAV . SIMPSON COMPOSTA.

[ x_simp , w_simp ]= simpson_composta ( N_simpson , a , b ) ; fx_simp=f e v a l( f , x_simp ) ; I_simp=w_simp ’ ∗ fx_simp ;

Esempio 1

Ricordando che il risultato `e 0.09523809523810, otteniamo i poco soddisfacenti

[ TRAPEZI COMPOSTA ] [ PTS ] : 11

[ TRAPEZI COMPOSTA ] [ RIS ] : 0 . 2 0 4 6 2 6 3 1 5 0 5 0 2 4 [ SIMPSON COMPOSTA ] [ PTS ] : 11

[ SIMPSON COMPOSTA ] [ RIS ] : 0 . 1 3 9 4 9 2 0 0 3 6 4 4 4 7

Posto N = 51 nella prima riga di demo composte.m [ TPZ . COMP . ] [ PTS ] : 51

[ TPZ . COMP . ] [ RIS ] : 0 . 1 0 0 5 2 3 2 8 8 3 6 7 4 2 [ CS . COMP . ] [ PTS ] : 51

Esempio 2

Approssimiamo R1

0 exp (x)dx = exp(1) − 1 ≈ 1.718281828459046

tramite le formule composte dei trapezi e Cavalieri-Simpson. Perch`e il paragone sia veritiero, decidiamo che il numero di valutazioni della funzione integranda sia uguale. Modifichiamo la funzione f nel file demo composte.m e ricaviamo

[ TPZ . COMP . ] [ PTS ] : 11

[ TPZ . COMP . ] [ RIS ] : 1 . 7 1 9 7 1 3 4 9 1 3 8 9 3 1 [ CS . COMP . ] [ PTS ] : 11

[ CS . COMP . ] [ RIS ] : 1 . 7 1 8 2 8 2 7 8 1 9 2 4 8 2

Esempio 2: errore

Nel caso della formula dei trapezi composta, abbiamo E₁(c)_{(f ) := I (f ) − S1}(c)(f ) = −(b − a)

12 h

2_f(2)_{(ξ), h =} (b − a)

N per qualche ξ ∈ (a, b) e quindi

|E1(c)(f )| ≤     −(b − a) 12 h 2 _max x_∈(0,1)exp(x)    ≤ 1 12h 2_exp(1)

Esempio 2: errore

Nel caso della formula di Cavalieri-Simpson composta, abbiamo E₃(c)_{(f ) := I (f ) − S3}(c)(f ) = −(b − a) 180  h 2 4 f(4)(ξ) da cui |E3(c)(f )| ≤      −(b − a) 180  h 2 4 max x_∈(0,1)exp(x)      ≤ ₁₈₀1  h₂ 4 exp(1) Nel nostro esempio h = 0.4 e quindi

Formule gaussiane in Matlab

Il calcolo di nodi e pesi delle formule gaussiane, per una fissata funzione peso w non `e semplice. Di seguito ci interesseremo al caso particolare delle funzioni peso di Jacobi. A tal proposito aiutano le routines gauss.m e r jacobi.m di W. Gautschi e D. Laurie che possono essere scaricate dalla homepage del primo autore. La funzione gauss jacobi.m, se registrata nella stessa cartella di gauss.m e r jacobi.m, calcola i nodi x =_{xi}i=1,...,n e i pesi

w = {wi}i=1,...,n della formula gaussiana (avente g.d.p. 2n − 1)

Formule gaussiane in Matlab: scalatura

Specialmente per le formule con peso w (x) ≡ 1 si ha spesso da effettuare l’integrale Rb

a f(x)dx con (a, b) diverso da (−1, 1). In tal

caso si osserva che se γ(t) = (a(1 − t)/2) + (b(1 + t)/2), per {tk}

e {wk} nodi e pesi della formula di Gauss-Legendre,

Z b a f(x)dx = Z 1 −1 b_{− a} 2 f(γ(t))dt ≈ n X k=1 b_{− a} 2 wkf(γ(tk)) e quindi Z b a f_{(x)dx ≈} n X k=1 w_k∗f(x_k∗)

con w_k∗= b−a₂ wk, xk = γ(tk) = (a(1 − tk)/2) + (b(1 + tk)/2).

Formule gaussiane in Matlab: demo

Scriviamo quindi nel file demo gauss jacobi N=11; alpha=0; b e t a=0; a=−1; b =1; f=inline (’ x . ˆ 2 0 ’) ; % a =0; b =1; f= i n l i n e ( ’ exp ( x ) ’ ) ; [ x , w]= gauss_jacobi ( N , alpha ,b e t a) ; xx=a∗(1−x )/2+b∗(1+x ) / 2 ; ww=(b−a ) ∗w / 2 ; fxx=f e v a l( f , xx ) ; I=ww ’ ∗ fxx ; f p r i n t f(’ \n\ t [ N] : % 3 . 0 f [ I ] : %1.15 e \n\n ’, N , I )

calcolando cos`ı con una formula gaussiana di 11 nodi l’integrale R1

Formule gaussiane in Matlab: demo ed esempio 1

Dalla shell di Matlab/Octave >> demo_gauss _ ja c ob i [ N ] : 11 [ I ] : 9 . 5 2 3 8 0 9 5 2 3 8 0 9 5 5 1 e−02 >> I I = 9 . 5 2 3 8 0 9 5 2 3 8 0 9 5 5 1 e−02 >> Iex=2/21; a b s( I−Iex ) a n s = 2 . 7 7 5 5 5 7 5 6 1 5 6 2 8 9 1 e−16

che va confrontato, a parit`<sub>a di nodi, con 5.28 · 10</sub>−3 <sub>e 1.85 · 10</sub>−4 rispettivamente delle formule dei trapezi e Cavalieri-Simpson composte. Si osservi che il grado di precisione della formula gaussiana con n = 11 `e 2n − 1 = 21 e quindi l’integraleR1

−1x20dx

Formule gaussiane in Matlab: demo ed esempio 2

Dalla shell di Matlab/Octave, rimaneggiando i commenti del codice, >> demo_gauss _ ja c ob i [ N ] : 11 [ I ] : 1 . 7 1 8 2 8 1 8 2 8 4 5 9 0 4 5 e+00 >> Iex=exp( 1 )−exp( 0 ) ; I =1.71828182845904 5 e +00; >> a b s( Iex−I ) a n s = 4 . 4 4 0 8 9 2 0 9 8 5 0 0 6 2 6 e−16

Formule gaussiane in Matlab: demo ed esempio 3

Approssimiamo in un file Matlab/Octave demo comparison.m R1

−1exp (x)

√

1 − x dx = 1.77914365469190979259 . . . . mediante la formula dei trapezi composta, Cav.-Simpson composta,

Gauss-Legendre e Gauss-Jacobi con α = 1/2, β = 0.

N=11; a=−1;b =1; Iex = 1 . 7 7 9 1 4 3 6 5 4 6 9 1 9 0 9 7 9 2 5 9 1 1 7 9 0 2 9 9 9 4 1 ; g=inline (’ exp ( x ) . ∗ s q r t (1−x ) ’) ; f=inline (’ exp ( x ) ’) ;

[ xt , wt ]= trapezi_composta ( N , a , b ) ; % TPZ .

fxt=f e v a l( g , xt ) ; It=wt ’ ∗ fxt ; et=a b s( Iex−It ) ; [ xcs , wcs ]= simpson_composta ( N , a , b ) ; % C . S .

fxcs=f e v a l( g , xcs ) ; Ics=wcs ’ ∗ fxcs ; ecs=a b s( Iex−Ics ) ; [ xgl , wgl ]= gauss_jacobi ( N , 0 , 0 ) ; % G . L .

fxgl=f e v a l( g , xgl ) ; Igl=wgl ’ ∗ fxgl ; egl=a b s( Iex−Igl ) ; [ xj , wj ]= gauss_jacobi ( N , 0 . 5 , 0 ) ; % G . J .

Formule gaussiane in Matlab: demo ed esempio 3

Con ovvia notazione, a parit`a di valutazioni della funzione integranda, abbiamo

>> demo_compar i so n

[ TPZ ] : 4 . 4 e−02 [ CS ] : 6 . 2 e−03 [ GL ] : 5 . 3 e−04 [ GJ ] : 6 . 7 e −16

>>

Cubatura e Metodo Montecarlo

Si parla di cubaturaquando l’integrale Iw(f ) =

Z

Ω

f(x)w (x)dx (8)

`e da calcolarsi in un dominio Ω ⊂ Rm <sub>con m > 1. Il problema `e</sub>

particolarmente difficile per dimensioni m ≫ 1. In tal caso, un classico approccio consiste nell’applicare il Metodo Montecarlo. Per semplicit`a tratteremo il caso del cubo m dimensionale Ω = [0, 1]m<sub>, e w (x) ≡ 1. Nella sua versione pi`u semplice, il</sub> Metodo Montecarlo consiste nell’approssimare (8) con

QN(f ) = N

X

k=1

wkf(xk)

dove x1, . . . , xN sono generati casualmente da una distribuzione

Cubatura e Metodo Montecarlo

Si conosce n stima probabilistica dell’errore |I (f ) − IN(f )| ≈

q

I(f2_{) − (I (f ))}2_/√_N

Si osservi che la convergenza, seppure erratica e lenta, non dipende dalla dimensione m.

Cubatura e Metodo Montecarlo

Calcoliamo quale test Z 1 0 Z 1 0 Z 1 0 Z 1 0

Cubatura e Metodo Montecarlo

Salviamo in demo sobol: Npow=10; N=4ˆ Npow ; f=inline (’ x . ∗ c o s ( y ) . ∗ exp (w) . ∗ ( z . ˆ 1 0 ) ’,’ x ’,’ y ’,’w ’,’ z ’) ; Iex=(1/2) ∗(s i n( 1 )−s i n( 0 ) ) ∗(exp( 1 ) −1) ∗ ( 1 / 1 1 ) ; % MONTECARLO . X=r a n d( N , 4 ) ; fX=f e v a l( f , X ( : , 1 ) , X ( : , 2 ) , X ( : , 3 ) , X ( : , 4 ) ) ; Imc=sum( fX ) / N ; % SOBOL .

Cubatura e Metodo Montecarlo

In forma tabulare, posto eMC l’errore assoluto del Metodo

Montecarlo, e con eQMC quello di Quasi-Montecarlo con la

Metodo Montecarlo e domini non ipercubi

Osserviamo che se il dominio Ω ´e contenuto in un ipercubo I ⊂ Rd_{, allora il metodo Montecarlo pu`o essere applicato}

integrando la funzione F = f · XΩ dove

XΩ(P) =



1 se P ∈ Ω 0 altrimenti Osserviamo che

◮ Evidentemente, non `e un problema valutare F se f non `e

definita nel complementare di Ω perch`e ivi l’integranda F `e nulla.

◮ L’integrale su un generico ipercubo si pu`o ottenere facilmente