UNIVERSITÀ DEGLI STUDI DI PADOVA
Dipartimento di Matematica "Tullio Levi-Civita"
Corso di Laurea in Matematica
Tesi di Laurea
Su una formula di J. B. Lasserre relativa
all’integrazione sul simplesso
Relatore
Laureando
Dott.
Leonardo Salzano
Alvise Sommariva
1162439
. . . .
Indice
1 Premesse 9
1.1 Motivazioni . . . 9
1.2 Nozioni preliminari . . . 11
1.2.1 Il simplesso . . . 11
1.2.2 Richiami di teoria dell’integrazione . . . 12
1.2.3 Introduzione alla trasformata di Laplace . . . 13
1.2.4 Richiami di integrazione numerica . . . 15
2 Il teorema di Lasserre 21 2.1 Enunciato e dimostrazione . . . 21 2.2 Conseguenze . . . 23 2.3 Esempio . . . 27 3 Esperimenti numerici 29 3.1 Segmento . . . 29 3.2 Triangolo . . . 33 3.3 Tetraedro . . . 35 A Software Matlab 39 A.1 Implementazione in Matlab della formula di Lasserre 2.9 per il simplesso canonico 39 A.1.1 Caso 1-dimensionale . . . 39
A.1.2 Caso 2-dimensionale . . . 40
A.1.3 Caso 3-dimensionale . . . 40
A.2 Script per gli esperimenti . . . 41
A.2.1 Caso 1-dimensionale . . . 41
A.2.2 Caso 2-dimensionale . . . 42
A.2.3 Costruzione esponenti 3D . . . 43
A.2.4 Caso 3-dimensionale . . . 44
A.2.5 Implementazione di Gauss-Legendre . . . 45
A.2.6 Confronto tra la formula di Lasserre e Gauss-Legendre . . . 46
A.3 Script per i grafici . . . 47
A.3.1 Caso 1-dimensionale . . . 47
A.3.2 Caso 2-dimensionale . . . 47
Introduzione
In questa tesi consideriamo il problema di calcolare i momenti di grado totale n della ba-se monomiale su simplessi Sd ⊂ Rd. A tal proposito, troviamo in letteratura vari
approc-ci. Il piú comune consiste nel determinare formule di cubatura aventi nodi {xi}i=1,...η e pesi
{wi}i=1,...η, cosícché se f ∈ C(Sd), ossia allo spazio delle funzioni continue nel simplesso Sd,
allora RSdf (x)dx ≈Pη
i=1wif (xi).
A tal proposito, sono state determinate formule quasi-minimali, cioè tali da avere un grado di precisione prefissato N, ovvero RS
dpN(x)dx =
Pη
i=1wipN(xi) per ogni polinomio di grado
totale minore o uguale a N, con η particolarmente piccolo. Per tali η, dipendentemente da N, esistono dei lower bounds dovuti a Möller, ed é argomento di ricerca trovare set di nodi e pesi con cardinalitá η minore possibile.
Un approccio molto diverso é stato introdotto in vari lavori da J. B. Lasserre. L’autore ha proposto uno strumento alternativo ad una formula di quadratura, per calcolare integrali di polinomi arbitrari, scritti in base monomiale, sul simplesso Sd.
Il nostro proposito, dopo aver descritto tale metodo, è di fornire una sua implementazione in Matlab relativamente a Sd con d = 1, 2, 3, ovvero su un intervallo, un triangolo e un tetraedro.
Per ognuno di questi domini calcoleremo i momenti della base monomiale con gradi totali N, anche non moderati, verificandone l’esattezza e la rapiditá di calcolo.
Capitolo 1
Premesse
1.1
Motivazioni
Il simplesso è un politopo n-dimensionale di fondamentale importanza in svariati campi della matematica, che spaziano tra l’analisi numerica, la ricerca operativa e la bioinformatica. Tra le proprietà del simplesso spicca la sua inclinazione alla scomposizione di oggetti complessi, tramite procedimenti detti complessi simpliciali. Un utilizzo potrebbe essere ad esempio la decomposizione delle strutture delle proteine, come si può vedere nell’immagine che segue.
Figura 1.1: Decomposizione in simplessi della struttura di due proteine.
A questo punto è più semplice calcolare il volume della proteina, cosí da poter fare deduzioni più precise riguardo alle sue funzionalità.
Per calcolare i volumi, lo strumento principe della matematica è il concetto di integrale, infatti il volume di un insieme D ⊂ Rn è dato dalla risoluzione di
Vol(D) = Z
D
1 dµ dove µ indica la misura di Lebesgue in Rn.
di un certo integrale con un’espressione del tipo: Z b a f (x)w(x) dx ≈ N X i=1 f (xi)wi.
dove w(x) è una qualche funzione peso, e dove xi, per i = 1, . . . , N, e wi si dicono
rispettiva-mente nodi e pesi.
Parallelamente a queste tecniche, J. B. Lasserre è riuscito a ricavare una formula mol-to semplice ed elegante, applicabile a polinomi e ad una certa categoria di funzioni dette "positivamente omogenee": Z ∆ f (y) dy = vol(∆)( ˆf0+ t X j=1 ˆ fj(ξj)).
Si può notare fin da subito che questa formula non possiede pesi e nodi, per cui non è una formula di cubatura vera e propria. La filosofia è completamente diversa: al posto di calcolare un’unica funzione su diversi punti distinti (i nodi), nella formula di Lasserre si calcolano diverse funzioni ˆfj, dette polinomi di Bombieri, su un numero notevolmente minore di nodi.
In sintesi, le difficoltà concrete nell’integrazione si possono trovare in "domini complicati" da trattare, a cui si può porre rimedio con le suddivisioni in simplessi, e in funzioni con primitive o difficili da trovare oppure non esprimibili in forme elementari. Per questo tipo di problema-tica la funzione in oggetto può essere approssimata, sotto certe ipotesi, tramite polinomi. Il problema dell’integrazione si può quindi riformulare con l’integrazione di polinomi su simplessi e in particolare, grazie a trasformazioni affini, sul simplesso canonico.
In questo lavoro, dopo un preambolo in cui vengono richiamate le nozioni fondamentali per la derivazione della formula di Lasserre, quest’ultimo tema viene sviluppato e poi analizzato dal punto di vista numerico, tramite esperimenti con software scritti in Matlab e attualmente non presenti nella letteratura.
Verranno confrontati i risultati ottenuti con il valore esatto, mostrando il comportamento degli errori prodotti, sia assoluti che relativi. Si evincerà che la formula di Lasserre è un risultato teorico molto interessante e innovativo, che si presta bene all’integrazione su Matlab di polino-mi (e funzioni positivamente omogenee). In particolare, la sua forza risiede nella possibilità di calcolare i cosiddetti momenti, ovvero elementi della forma:
Z
D
xα dx
al variare di α ∈ NNe con D ⊂ Rnun generico dominio. I momenti sono di centrale importanza
1.2
Nozioni preliminari
1.2.1
Il simplesso
Definizione 1.2.1. In uno spazio affine A di dimensione n, n + 1 punti di V, x0, x1, . . . , xn, si
dicono in posizione generale se i vettori x1−x0, x2−x0, . . . , xn−x0sono linearmenti indipendenti.
Definizione 1.2.2. Sia Rm, con n ≤ m, lo spazio euclideo su R di dimensione m. Si dice simplesso n-dimensionale Sn l’inviluppo convesso di n + 1 punti in posizione generale, detti
vertici.
Si noti che estratti k + 1 punti, x0, x1, . . . , xk, tra n + 1 punti in posizione generale, essi
rimangono in posizione generale, ed è quindi ben definito un k-simplesso che viene detto faccia. E’ interessante vedere quante sono le k-facce di un generico n-simplesso. Chiaramente si tratta del numero di tutti i sottoinsiemi di cardinalità k + 1 di un insieme con n + 1 elementi, ossia
n+1 k+1 =
(n+1)! (k+1)!(n−k)!.
Esempio 1.2.1. Come rappresentato dalla figura sottostante, in R3 S
0 è un punto, S1 è un
segmento, S2 è un triangolo e S3 è un tetraedro.
Figura 1.2: Rappresentazione di simplessi.
Sia ora Vn(K) uno spazio vettoriale di dimensione n su un campo K. Il volume di un
n-simplesso di vertici {v0, ..., vn} è dato dalla seguente formula:
Vol(Sn) = 1 n!det (v1− v0, v2− v0, . . . , vn− v0) Sarà utile successivamente anche la seguente definizione:
Definizione 1.2.3. Si dice simplesso canonico l’inviluppo convesso di e1, . . . , en, dove {ei, i =
1, . . . , n}denota l’usuale base canonica di Vn(K), i.e. ∆ = {x ∈ Rn+ : e
T
1.2.2
Richiami di teoria dell’integrazione
Verrà indicata in questa sezione con µ la misura di Lebesgue su Rn.
Definizione 1.2.4. Una funzione f : A ⊆ Rn → R si dice semplice qualora ∃A
i ⊆ A (i =
1, . . . , m) misurabili, Ai ∩ Aj = ∅ se i 6= j, e ∃fi ∈ R (i = 1, . . . , m) tali che A =
F
iAi e
f (x) :=P
ifiχAi(x)
Definizione 1.2.5. Sia A un insieme misurabile. Se f : A ⊆ Rn→ R è una funzione semplice,
si pone: Z A f := Z A f dµ =X i fiµ(Ai)
Definizione 1.2.6. Siano f : A → R, f ≥ 0, una funzione misurabile e nonnegativa in A, e φn : A → R una successione (monotona crescente) di funzioni semplici tale che φn % f per
n → +∞. Si pone: Z A f = Z A f (x) dµ := lim n→+∞ Z A φn dµ.
Teorema 1.2.1. (di Beppo Levi/Convergenza Monotona) Sia fn : A → R, fn ≥ 0, una
successione monotona crescente di funzioni misurabili e nonnegative, tale che fn % f per
n → +∞. Allora: Z A fn % Z A f.
Corollario 1.2.1. Sia fn : A → R, fn≥ 0, una successione di funzioni misurabili e nonnegative.
Allora: Z A +∞ X n=1 fn= +∞ X n=1 Z A fn.
Teorema 1.2.2. (Lemma di Fatou) Sia fn : A → R una successione di funzioni misurabili tale
che per ogni n ∈ N si ha che fn ≥ 0q.o.. Allora:
Z A f ≤ lim inf n→+∞ Z A fn.
Teorema 1.2.3. (di Lebesgue/Convergenza Dominata) Siano A ⊆ Rn un insieme misurabile e fn : A → R una successione di funzioni misurabili tale che limn→+∞fn(x) = f (x) per q.o.
x ∈ A. Si assuma che esista g ∈ L1(A)tale che |fn(x)| ≤ g(x). Allora f è sommabile in A e si
ha: lim n→+∞ Z A fn= Z A lim n→+∞fn = Z A f.
Teorema 1.2.4. (di Fubini) Sia f ∈ L1(X ×Y )dove X ⊆ Rne Y ⊆ Rmsono insiemi misurabili.
Allora valgono le seguenti:
• Y 3 y 7→ f(x, y) ∈ L1(Y )per q.o. x ∈ X;
• X 3 x 7→ RY f (x, y) dy ∈ L 1(x);
Teorema 1.2.5. (di Tonelli) Sia f : X × Y 7→ R, f ≥ 0 una funzione misurabile nonnegativa, dove X ∈ Rn e Y ∈ Rm sono insiemi misurabili. Allora valgono le seguenti:
• Y 3 y 7→ f(x, y) è misurabile su Y per q.o. x ∈ X; • X 3 x 7→ RY f (x, y) dy è misurabile su X;
• RX(RY f (x, y) dy)dx =RX×Y f.
Teorema 1.2.6. (Cambiamento di variabili) Sia T : O ⊆ Rn → R, dove T ∈ C1(O, Rn) e
O ⊆ Rn è un insieme aperto. Se Jac(T) 6= 0, allora per ogni f : T (O) → R misurabile si ha:
Z T (O) f (y) dy = Z O (f ◦ T )(x)|J ac(T )(x)| dx. (1.1)
1.2.3
Introduzione alla trasformata di Laplace
Definizione e caratterizzazione della convergenza
Definizione 1.2.7. Sia f : D ⊆ R → R una funzione che soddisfa le seguenti proprietà: • f è continua a tratti;
• |f(t)| < M exp (αt) con M, α > 0.
Si definisce trasformata di Laplace la seguente funzione integrale:
F (s) = Z +∞
0
exp (−st)f (t) dt, s ∈ D. (1.2)
Osservazione 1.2.1. Chiaramente la trasformata esiste dove l’integrale generalizzato converge. E’ naturale dunque chiedersi se ci sia un criterio di convergenza. La risposta è affermativa. Vale la seguente:
Proposizione 1.2.1. Se f è una funzione localmente integrabile, ossia integrabile su ogni sottoinsieme compatto del dominio, allora la trasformata di Laplace F(s) di f converge se esiste il limite lim R→+∞ Z R 0 f (t) exp (−ts) dt. Converge assolutamente qualora esista l’integrale
Z +∞ 0 |f (t) exp (−ts)| dt. Proprietà principali • Linearità: L(Pn i=1Kifi(t)) = Pn i=1KiL(fi); • Derivazione: L(f(n)) = snL(f ) −Pn k=1sn−k d k−1f (0) dtk−1 ; • Integrazione: L(Rt 0 f (x) dx) = 1 sLf (t);
• Prodotto di una convoluzione: L(f ∗ g) = L(f)L(g);
• Moltiplicazione per t alla n-esima potenza: (−1)nL(tnf (t)) = dn
Trasformate notevoli
• Delta di Dirac: L(δ) = 1;
• Gradino di Heaviside: L(Θ(t)) = 1 s;
1.2.4
Richiami di integrazione numerica
Formule interpolatorie
Talvolta capita di dover integrare funzioni "difficili" o per le quali non esiste una primitiva esprimibile in termini di funzioni elementari, come ad esempio gli integrali ellittici, ossia una qualunque funzione f definita nel seguente modo:
f (x) = Z x
c
R(t, P (t)) dt
dove R denota una funzione razionale, P la radice quadrata di un polinomio in una variabile di grado 3 o 4 privo di radici multiple e c una costante.
Più in generale si potrebbe dover calcolare integrali del tipo
Iw(f ) = Iw(f, a, b) =
Z b
a
f (x)w(x) dx con a, b ∈ R ∪ {±∞}, a ≤ b e w(x) una funzione peso.
Definizione 1.2.8. Una funzione w : (a, b) → R si dice una funzione peso se: • w è nonnegativa, con (a, b) non necessariamente limitato;
• Rb a |x|
n
w(x) dx < +∞ ∀n ∈ N; • Se Rb
a g(x)w(x) dx = 0 per qualche funzione continua e nonnegativa g, allora g ≡ 0 in
(a, b).
Esempio 1.2.2. Alcune classiche funzioni peso sono le seguenti: • w(x) = 1 con x ∈ [−1, 1], (peso di Legendre);
• w(x) = √ 1
1−x2 con x ∈ (−1, 1), (peso di Chebyshev);
• w(x) = (1 − x2)(γ−12) con x ∈ (−1, 1), γ > −1
2, (peso di Gegenbauer);
• w(x) = (1 − x)α(1 + x)β con x ∈ (−1, 1), α > −1, β > −1, (peso di Jacobi);
• w(x) = exp (−x) con x ∈ (0, +∞), (peso di Laguerre); • w(x) = exp (−x2) con x ∈ (−∞, +∞), (peso di Hermite);
A questo punto lo scopo è quello di cercare di approssimare l’integrale di f come segue:
Iw(f ) ≈ QN(f ) := N
X
i=1
wif (xi) (1.3)
Osservazione 1.2.2. Se l’intervallo (a, b) è limitato, il teorema di Weierstrass e l’integrabilità della funzione peso implicano che se f è continua in (a, b) allora è w-integrabile in (a, b). Infatti, dal momento che kwk1 =
Rb aw(x) dx, Z b a f (x)w(x) dx ≤ Z b a |f (x)|w(x) dx ≤ kf k∞kwk1 < ∞. Se pN −1(x) = N X i=1 f (xi)Li(x)
è il polinomio che interpola le coppie (xi, f (xi)), con i = 1, . . . , N, e ricordando che
Li(x) =QNj6=i x−xj
xi−xj è l’i-esimo polinomio di Lagrange, allora:
Z b a f (x)w(x) dx ≈ Z b a pN −1(x)w(x) dx = Z b a N X i=1 f (xi)Li(x)w(x) dx = = N X i=1 Z b a Li(x)w(x) dx f (xi)
che confrontata con la 1.3 rende wi =
Z b
a
Li(x)w(x) dx, i = 1, . . . , N.
La precedente osservazione motiva la seguente definizione. Definizione 1.2.9. Siano
• (a, b) l’intervallo di integrazione, non necessariamente limitato; • x1, . . . , xN un insieme di punti a due a due distinti;
• f una funzione continua in (a, b) w-integrabile. Una formula di quadratura
Grado di precisione
Definizione 1.2.10. Una formula Z b a f (x)w(x) dx ≈ N X i=1 wif (xi)
ha grado di precisione almeno M se e solo se è esatta per tutti i polinomi p di grado inferiore o uguale a M, ovvero: Z b a pM(x)w(x) dx = n X i=1 wipM(xi), pM ∈ PM.
Inoltre ha grado di precisione esattamente M se e solo se è esatta per ogni polinomio di grado inferiore o uguale a M ed esiste un polinomio di grado M+1 per cui non lo sia.
Teorema 1.2.7. Una formula Z b a f (x)w(x) dx ≈ N X i=1 wif (xi)
è interpolatoria se e solo se ha grado di precisione almeno N-1. Dimostrazione. Da un lato, se la formula è interpolatoria, vale:
Z b a f (x)w(x) dx ≈ N X i=1 wif (xi) con wi = Z b a Li(x)w(x) dx, i = 1, . . . , N. Se f = pN −1 ∈ PN −1, allora pN −1(x) = Pn
i=1pN −1(xi)Li(x)e quindi segue che:
Z b a pN −1(x)w(x) dx = Z b a N X i=1 pN −1(xi)Li(x)w(x) dx = = N X i=1 pN −1(xi) Z b a Li(x)w(x) dx = N X i=1 wipN −1(xi).
Dunque la formula ha grado di precisione almeno N-1.
Viceversa, se la formula è esatta per ogni polinomio di grado N-1, lo è anche per i polinomi di Lagrange Lk ∈ PN −1, da cui Z b a Lk(x)w(x) dx = N X i=1 wiLk(xi) = N X i=1 wiδi,k = wk, k = 1, . . . , N,
Stabilità di una formula di quadratura Siano soddisfatte le seguenti ipotesi:
• (a, b) intervallo limitato; • w una funzione peso in (a, b); • Iw(f ) :=
Rb
a f (x)w(x) dx ≈ S(f ) :=
PN
j=1wjf (xj);
• gli elementi f(xj) siano approssimati da ˜f (xj).
Si vuole ora mostrare come cambia il valore dell’integrale valutando:
Iw(f ) := Z b a f (x)w(x) dx ≈ ˜S(f ) := N X j=1 wjf (x˜ j).
Utilizzando la disuguaglianza triangolare si ha:
|S(f ) − ˜S(f )| = | N X j=1 wj(f (xj) − ˜f (xj))| ≤ N X j=1 |wj||f (xj) − ˜f (xj)| ≤ N X j=1 |wj| ! · max j |f (xj) − ˜f (xj)|. Perciò la quantità N X j=1 |wj|
è un indice di stabilità per la formula di quadratura S.
Definizione 1.2.11. Data una formula di quadratura S, il cui grado di precisione sia almeno 0, si definisce numero di condizionamento di S il seguente:
K(S) = PN
j=1|wj|
PN
j=1wj
dove wj sono i pesi.
Si supponga a questo punto che la formula S abbia grado di precisione almeno 0, ovvero che integri esattamente almeno le costanti. Indicando con {w+
k}k=1,...,N+ e con {w−k}k=1,...,N−
rispettivamente i pesi positivi e quelli negativi, si ha che: Z b a w(x) dx = Z b a 1 · w(x) dx = N X j=1 wj = N X j=1 |wj| − 2 N− X k=1 |w−k|.
Nella seconda uguaglianza si è utilizzato che la formula ha grado di precisione almeno 0. Da questi passaggi si nota che PN
j=1wj <
PN
j=1|wj| se qualche peso è negativo.
con-Richiami di cubatura
Dopo aver analizzato il caso unidimensionale è naturale chiedersi in che modo si possa parlare di quadratura in dimensioni maggiori.
Siano fj : Ω → R per j = 1, . . . , m funzioni continue e tra loro linearmente indipendenti, dove
Ω ⊆ Rn. Lo scopo è quello di dare un’approssimazione del tipo:
N X i=1 wifj(xi) ≈ Z Ω fj(x)w(x) dx ∀j = 1, . . . , m.
Per valutare la qualità di una formula di questo tipo, detta di cubatura, ci si può appoggiare al grado di esattezza. Consideriamo {fj}j come base per lo spazio dei polinomi algebrici di n
su Ω. Per riuscire a costruire tali formule con un fissato grado di esattezza bisogna risolvere le equazioni dei momenti.
Definizione 1.2.12. Si dicono equazioni dei momenti le seguenti: Q(fj) =
Z
Ω
fj(x)w(x) dx con j = 1, . . . , dim(Pnd)
dove Pn
d è lo spazio vettoriale dei polinomi a n variabili di grado massimo d, e dim(Pnd) = n+d
d
. Si noti che all’aumentare del grado di precisione richiesto, crescerà anche il numero di equazioni da risolvere per la determinazione dei nodi. Questo può creare non poche difficoltà. Consideriamo d’ora in poi il peso di Legendre, ovvero ω(x) = 1.
Definizione 1.2.13. Si dice momento j-esimo il seguente: mj =
Z
Ω
fj(x) dx.
L’obiettivo è quello di determinare N − 1 nuovi nodi xi e N − 1 nuovi pesi wi, in modo tale
che la formula di cubatura sia esatta per la famiglia di funzioni f1, . . . , fm.
Posto w = (wi)i, la richiesta precedente coincide con la risoluzione del seguente sistema:
f1(x1) . . . f1(xN) · · · · · · fm(x1) . . . fm(xN) · w1 · · · wN = m1 · · · mN .
In forma più compatta si può scrivere:
V · w = m
dove V è la matrice, detta di Vandermonde, di componenti Vi,j = fi(xj).
Esistono algoritmi di cubatura per determinare formule con un "basso" numero di nodi e grado di precisione prefissato.
Capitolo 2
Il teorema di Lasserre
2.1
Enunciato e dimostrazione
Sia R[x] l’anello dei polinomi reali nella variabile x = (x1, . . . , xn). Un polinomio f ∈ R[x] si
scrive
x 7→ f (x) = X
α∈NN
fαxα.
Definizione 2.1.1. Una funzione f : (R+\ {0})n → R si dice positivamente omogenea di grado
t se f(λx) = λtf (x) ∀λ > 0 e ∀x ∈ (R
+\ {0})n.
Definizione 2.1.2. Si definisce polinomio di Bombieri ˆf relativo a f ∈ R[x] il seguente: x 7→ f (x) = X α∈NN ˆ fαxα = X α∈NN fαα1! · · · αn!xα x ∈ Rn.
Al fine di integrare f su di un arbitrario simplesso Ω ⊂ Rn ci si può ridurre, tramite
un’oppurtuna traformazione affine, ad integrare un relativo polinomio dello stesso grado sul simplesso canonico ∆ = {x ∈ Rn
+ : eTx ≤ 1}, dove e = (1, . . . , 1) ∈ Rn.
Teorema 2.1.1. (di Lasserre) Sia 0 < z ∈ Rn e sia ∆
z = {x ∈ Rn+ : zTx ≤ 1}. Sia f
una funzione positivamente omogenea di grado t ∈ R in (R+\{0})n, tale che t > −(1 + n) e
R ∆z|f | dx < ∞. Allora: Z ∆z f (x) dx = 1 Γ(1 + n + t) Z Rn+ f (x) exp (−zTx) dx. (2.1) Se invece f è un polinomio omogeneo di grado t ∈ N, allora:
Z ∆z f (x) dx = 1 (n + t)! ˆ f 1 z 1 ze. (2.2)
Dimostrazione. Sia z > 0, z ∈ Rn fissato e sia j una funzione definita nel seguente modo: j : R → R
y 7→ j(y) := Z
{x∈Rn: zTx≤y}
f (x) dx. (2.3)
Ponendo per il teorema di cambiamento di variabile u := x
λ, cioè λu := x, si ha | det (Jac)| = λ n e inoltre : Z {u∈Rn: zTu≤y} f (λu)λn du = Z {u∈Rn: zTu≤y} λtf (u)λndu = = λ(n+t) Z {u∈Rn: zTu≤y} f (u) du = λn+tj(y).
Nel penultimo passaggio si è utilizzata l’ipotesi che f sia una funzione positivamente omogenea di grado t ∈ R. Detto ciò, si ha che j(y) = y(n+t)j(1)e si noti che h(1) è ben definito per ipotesi.
Ricordando che t > −(n + 1), si può calcolare la trasformata di Laplace di j(y): H : C → C
λ 7→ H(λ) = Γ(1 + n + t) λ(n+t+1) h(1)
(2.4) con λ ∈ C e <(λ) > 0.
D’altro canto, per λ ∈ R>0, applicando il teorema di Fubini-Tonelli e con un ulteriore cambio
di variabile, si ha: H(λ) = Z ∞ 0 h(y) exp(−λy) dy = Z ∞ 0 exp(−λy) Z {x∈Rn: zTx≤y} f (x) dx dy = = Z Rn+ f (x) Z ∞ zTx exp(−λy) dx = 1 λ Z Rn+ f (x) exp(−λzTx) dx = = 1 λn+t+1 Z Rn+ f (x) exp(−zTx) dx. (2.5)
A questo punto uguagliando 2.4 e 2.5 si ha: Γ(1 + n + t) λ(n+t+1) h(1) = 1 λn+t+1 Z Rn+ f (x) exp(−zTx) dx, ovvero: h(1) = Z ∆z f (x) dx = 1 Γ(1 + n + t) Z Rn+ f (x) exp (−zTx) dx, cioè la 2.1. Ora si osservi che per 0 < z ∈ R, derivando per parti
Z ∞
0
ykexp (−zy) dy = −ykexp (−zy) z ∞ 0 + Z ∞ 0 kyk−1exp (−zy) z dy = = Z ∞ 0 kyk−1exp (−zy) z dy = · · · = k! zk+1 si ottiene che Z ∞ 0 ykexp (−zy) dy = k! zk+1, (2.6)
poichè −yk exp (−zy) z ∞ 0 = 0. Perciò si ha che ∀α ∈ NN: Z Rn+ yαexp (−zTy) dy = 1 zeα1! . . . αn!( 1 z) α = ˆf 1 z 1 ze, ottenendo così 2.2.
Osservazione 2.1.1. Chiaramente nel caso in cui z=e: Z
1 ˆ 1 ˆ
2.2
Conseguenze
Definizione 2.2.1. Una funzione f : (R \ {0})n → R a valori reali si dice completamente
monotona se (−1)k ∂kf
∂xi1...∂xik x ≤ 0 ∀x ∈ (R \ {0})
ne per ogni sequenza di indici 1 ≤ i
1 ≤ · · · ≤
ik ≤ n di lunghezza arbitraria k.
A questo punto si può notare la seguente: sia f : Rn
+ → R+ funzione positivamente omogenea di grado t ∈ R. Si definisca una nuova
funzione ad essa "associata"
hf: Rn+→ R+
z 7→ hf(z) = Γ(1 + n + t)
Z
∆z
f (x) dx.
hf è la trasformata di Laplace di f e il teorema di Bernstein-Hausdorff-Widder-Choquet
garantisce che sia completamente monotona.
Definizione 2.2.2. Sia X uno spazio vettoriale su R, X∗il suo duale e C un cono, ossia C ⊆ X tale che
C = {x : c x ∈ C ∀c ∈ R}. Si definisce cono duale di C il sottoinsieme C∗ ⊆ X∗ così definito:
C∗ = {y ∈ X∗| hy, xi ∀x ∈ C}
dove h·, ·i indica la dualità canonica tra X e il suo duale X∗, i.e. hy, xi = y(x).
Definizione 2.2.3. Sia C ⊆ Rn un cono e C∗ il suo cono duale. Se p ∈ R[x], s ∈ R e
ps(x) = Z
C∗
exp (−yTx) µ(y)
per una qualche misura di Borel µ su C∗, allora µ è chiamata misura di Riesz. Inoltre se µ ha
densità q rispetto alla misura di Lebesgue su C∗, allora q è chiamato kernel di Riesz su ps.
Proposizione 2.2.1. Per ogni funzione positivamente omogenea f : (R+ \ {0})n → R+ di
grado t ∈ R, la funzione hf: Rn+ → R+ z 7→ hf(z) = Γ(1 + n + t) Z {x∈Rn: zTx≤1} f (x) dx (2.8)
è completamente monotona. Inoltre se f = xα−e con 0 ≤ α ∈ Rn allora f è il kernel di Riesz
della funzione
x 7→ x−αY
i
Γ(αi)
Siano ora dati d, x ∈ Rn. Si indichi con d · x il prodotto scalare dT
x e con d ⊗ x ∈ Rn il vettore (d1x1, . . . , dnxn). Sia inoltre Et ∈ R[x] il polinomio omogeneo di grado t con tutti i
coefficienti uguali a 1, ossia
x 7→ Et(x) :=
X
|α|=t
xα.
Con queste premesse si ha la seguente conseguenza al teorema 2.1.1. Corollario 2.2.1. Sia f un polinomio di grado t e si consideri f = Ptj
0fj in cui ogni fj è un
polinomio omogeneo di grado j. Allora: Z ∆ f (y) dy = vol(∆)( ˆf0+ t X j=1 ˆ fj(ξj)) (2.9) dove ξj = e((n + 1) · · · (n + j)) −1 j e ˆf j è il polinomio di Bombieri.
Dimostrazione. Applicando il teorema 2.1.1 e ricordando che vol(∆) = n!1 Z ∆ f (y) dy = t X j=0 Z ∆ fj(y) dy = t X j=0 1 n! ˆ fj(ξj) = vol(∆)( ˆf0+ t X j=1 ˆ fj(ξj)).
Osservazione 2.2.1. Si noti che la 2.9 non è una formula di cubatura poichè dovrebbe essere una scrittura del tipo
Z ∆ f dx = N X i=1 wif (xi), ∀f ∈ R[x]
per un qualche intero N ∈ N e punti xi ∈ ∆, con i relativi pesi wi. Il punto di vista è differente:
invece di calcolare un unico polinomio f di grado t in determinati punti xi, in 2.9 si calcolano
t altri polinomi ˆfj di grado j per j = 1, . . . , t, ciascuno soltanto in un singolo punto.
Corollario 2.2.2. Per ogni d ∈ Rn e t ∈ N vale la seguente: Z ∆ (d · x)tdx = 1 (n + t)! ˆ f (e) = t! (n + t)!Et(d). (2.10)
Dimostrazione. Osservando preliminarmente che (d1x1 + ... + dnxn)t = X |α|=t t! α!(d1x1+ ... + dnxn) α si ha che ˆ f (x) = \(d · x)t= X |α|=t t!α! α! (d1x1+ · · · + dnxn) α = X |α|=t t!(d ⊗ x)α= t!Et(d ⊗ x).
Ora notando che:
ˆ
f (e) = t!Et(d ⊗ e) = t!Et(d)
e richiamando il teorema 2.1.1, si ottiene:
Z Z
Giunti a questo punto il teorema di Lasserre si può estendere anche ad una classe di funzioni omogenee con la seguente proposizione.
Proposizione 2.2.2. Sia M ⊂ Rnun insieme finito di indici e sia f una funzione positivamente
omogenea di grado t ∈ R nella seguente forma: f : (R+\ {0})n→ R
x 7→ X
α∈M
fαxα α ∈ Rn, αi > −1, ∀i = 1, . . . , n
per certi coefficienti (fα)α∈M. Allora
Z ∆ f (x) x = 1 Γ(1 + n + t) ˆ f (e) = 1 n! ˆ f (ξt) (2.11) dove ξt= 1θe ∈ ∆ con θt= Γ(1+n+t)Γ(1+n) e x 7→ ˆf (x) := X α∈M Γ(1 + α1) · · · Γ(1 + αn)fαxα.
Dimostrazione. Sia −1 < α ∈ Rn con |α| = t fissato e sia −1 < z ∈ Rn. Per il teorema 2.1.1 si
ha: Z ∆z xα dx = 1 Γ(1 + n + t) Z Rn+ xαexp (−zTx) dx = 1 Γ(1 + n + t)z −α−e n Y i=1 Γ(1 + αi).
In quest’ultimo passaggio si è utilizzata la 2.6 e Γ(1 + αi) = αi! , da cui Qni=1Γ(1 + αi) =
α1α2...αn.
Sommando ora su tutti gli α ∈ M: Z ∆ f (x) x = z -e Γ(1 + n + t) X α∈M fαz−α n Y i=1 Γ(1 + αi) = ze Γ(1 + n + t) ˆ f (z-e) e ponendo z = e si ottiene la 2.11.
A questo punto è naturale pensare a come applicare questi risultati non solo al simplesso canonico, ma ad uno arbitrario nello spazio.
Sia Ω ⊂ Rn un tale simplesso. Esiste una qualche trasformazione che mappa Ω in ∆. Fissata
una base è sufficiente considerare il cambio di variabile y = A(x − a) dove A è una matrice n × n a valori reali e a ∈ Rn è un vertice di Ω. A questo punto, si ha che:
x ∈ Ω ⇐⇒ y = A(x − a) ∈ ∆.
Se f è un polinomio di grado t, per il teorema di cambio di variabile (si noti J = A implica | det (J)| = det (A), da cui det (J−1) = (det (A))−1):
dove g ha lo stesso grado di f e si è posto f(A−1
y + a) := g(y). A questo punto scrivendo g = Pt
j=0gj(y), dove i gj sono polinomi omogenei di grado j, si
ha che:
gj(y) = gj(A(x − a)).
Inoltre con ∆ 3 ξj = e((n + 1) · · · (n + j)) −1
j, Ψ
j := A−1ξj + a ∈ Ω, si ottiene:
ˆ
gj(ξj) = ˆgj(A(Ψj − a)).
Ora confrontando la 2.12 con la 2.9 si ha che: Z Ω f (x) dx = 1 det (A) 1 n!(ˆg0 + t X j=1 ˆ gj(A(Ψj− a))).
Se f è positivamente omogenea di grado t si può utilizzare la seguente decomposizione (di Waring): x 7→ f (x) = s X i=1 i (ci · x)t
per un numero finito di ci ∈ Rn ed i ∈ {−1, 1}, i = 1, . . . , s.
Ponendo di = (A−1)Tci e applicando la formula 2.12 e il corollario 2.2.2:
Z Ω f (x) dx = 1 det (A) s X i=1 i Z ∆ (ci· A−1y + ci · a)tdy = = s X i=1 i det (A) Z ∆ (ci· a + di · y)tdy = = s X i=1 i det (A) t X k=0 t k (ci· a)t−k Z ∆ (di· y)k dy = = s X i=1 i det (A) t X k=0 t k (ci· a)t−k k! (n + k)!Ek(di) = = 1 det (A) t X k=0 t k k! (n + k)! s X i=1 i(ci· a)t−kEk(di).
2.3
Esempio
Esempio 2.3.1. Si consideri il simplesso canonico 2-dimensionale, ossia ∆ = {x | x · e ≤ 1} = {x | x1+ x2 ≤ 1}.
Considero f(x) := f10x21+ f11x1x2+ f02x2. Al fine di applicare il corollario 2.2.1, calcolo ξ1
e ξ2 ricordando che ξj = e((n + 1) · · · (n + j)) −1 j. Si ha che: ξ1 = e 3 ; ξ2 = e √ 12. Quindi, sfruttando che ∆ = 1
2: Z ∆ f (x) dx = vol(∆)( ˆf0+ t X j=1 ˆ fj(ξj)) = 1 2(f20(ξ1) 2 1+ f11(ξ2)1(ξ2)2 + f01(ξ2)2) = = 1 2( f20 9 + f11 2 + 2 f01 √ 12). Se si considera f(x) := x2 1+ x1x2+ x2 si ottiene: 1 2(2(ξ2) 2 1+ (ξ2)1(ξ2)2 + (ξ1)2) = 1 2(2 1 12+ 1 12+ 1 3) = 7 24. Ed effettivamente, utilizzando il Teorema di Fubini-Tonelli:
Z ∆ f (x) dx = Z ∆ x21+ x1x2+ x2 dx1dx2 = Z 1 0 Z 1−x1 0 x21+ x1x2+ x2 dx1dx2 = = Z 1 0 Z 1−x1 0 x21 dx1dx2+ Z 1 0 Z 1−x1 0 x1x2 dx1dx2+ Z 1 0 Z 1−x1 0 x2 dx1dx2 = = Z 1 0 (1 − x1)x21 dx1+ Z 1 0 (1 − x1)2x1 2 dx1+ Z 1 0 (1 − x1)2 2 dx1 = 7 24. 6 -@ @ @ @ @ @ @ @ 1 1 x1 x2 ba` e3 ba` e √ 12
Capitolo 3
Esperimenti numerici
In questa sezione verranno svolti alcuni esperimenti in Matlab per testare la qualità della for-mula di Lasserre. Sono stati implimentati tre software, denominati Las1dmono, Las2dmono e Las3dmono per l’applicazione della formula rispettivamente sul segmento, sul triangolo e sul tetraedro canonici.
Basandosi su di essi verranno effettuati i calcoli dei momenti fino al grado d’interesse e il risul-tato sarà messo a confronto con quello esatto, mostrando gli errori assoluti e relativi commessi. Verrà inoltre fatto un paragone tra la formula di Lasserre e Gauss-Legendre per l’integrazione sul segmento [0,1].
Parallelamente alla formula di Lasserre esistono comunque formule di quadratura a bassa car-dinalità, reperibili in [8], dette "quasi-minimali". Queste hanno il vantaggio di approssimare integrali definiti di funzioni continue, mentre le formule di Lasserre permettono tale calcolo per polinomi espressi in base monomiale.
3.1
Segmento
Sia V = {xα : α ∈ N} la base monomiale dei polinomi univariati. Utilizzando lo script
esperimentiLasserre_1d si può calcolare, al variare del grado, l’integrale degli elementi di V (ovvero i momenti) sul simplesso canonico unidimensionale (il segmento [0, 1]), applicando la formula di Lasserre e confrontando i risultati con i valori esatti. Questi ultimi sono ottenuti calcolando direttamente la primitiva del monomio della base, ovvero
Z 1 0 xα dx = x α+1 α + 1 x=1 x=0 = 1 α + 1
Tabella 3.1: Risultati del calcolo dei momenti fino a grado 20.
Grado x Risultati esatti Risultati Lasserre
0 1 1 1 0.5 0.5 2 0.333333333333333 0.333333333333333 3 0.25 0.25 4 0.2 0.2 5 0.166666666666667 0.166666666666667 6 0.142857142857143 0.142857142857143 7 0.125 0.125 8 0.111111111111111 0.111111111111111 9 0.1 0.1 10 0.0909090909090909 0.0909090909090908 11 0.0833333333333333 0.0833333333333332 12 0.0769230769230769 0.076923076923077 13 0.0714285714285714 0.0714285714285714 14 0.0666666666666667 0.0666666666666668 15 0.0625 0.0625 16 0.0588235294117647 0.0588235294117647 17 0.0555555555555556 0.0555555555555556 18 0.0526315789473684 0.0526315789473686 19 0.05 0.0500000000000001 20 0.0476190476190476 0.0476190476190475
In particolare, il massimo errore assoluto compiuto nella tabella precedente, per un qualche integrale definito, risulta di circa 1.1 · 10−16, mentre quello relativo di 1.6 · 10−15.
Nella figura 3.1 viene fatto un confronto in scala y-semilogaritmica degli errori assoluti e relativi commessi dalla formula di Lasserre nell’intervallo [0, 1], integrando gli elementi della base monomiale V fino a grado 100.
Superare questa soglia diventa di poca utilità per le applicazioni pratiche e inoltre possono ap-parire alcune problematiche per quanto riguarda l’implementazione della formula di Lasserre. Infatti all’interno sono presenti fattoriali che devono essere gestiti con una certa cautela.
Da questi dati si può constatare la validità dell’implementazione della formula di Lasserre per il caso del segmento unitario. Infatti dalle Tabelle e dalle Figure si nota subito che l’errore è molto piccolo e, pur crescendo con l’aumentare del grado, rimane tollerabile.
Per quanto visto fino ad ora, la formula di Lasserre offre una prospettiva di integrazione numerica del tutto originale, allontanandosi dagli schemi tradizionali delle classiche formule di cubatura che sfruttano nodi e pesi.
E’ utile fare un confronto, almeno nel caso 1-dimensionale, con Gauss-Legendre. Quest’ul-timo è un caso particolare di formula Gaussiana per il peso di Legendre w(x) = 1.
Le Gaussiane sono particolari formule tali che, dati x1, . . . , xN nodi e w1, . . . , wN pesi, hanno
grado di precisione δ = 2N − 1.
Nel 1826 Jacobi ne ha provato l’esistenza con il seguente teorema.
Teorema 3.1.1. 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))2w(x) dx, per i = 1, . . . , N.
Per questo confronto, tra la formula di Lasserre e Gauss-Legendre, si può utilizzare lo script esperimentiLasserreGauss1d che per esempio, ponendo deg=q=20, riporterà in output i seguenti valori:
Tabella 3.2: Calcolo dei momenti fino a grado 20.
Grado x Risultati esatti Risultati Lasserre Risultati Gauss-Legendre
Fino a grado 20, il massimo errore assoluto compiuto dalla formula di Lasserre è di circa 1.6 · 10−16, mentre quello commesso da Gauss-Legendre di 4.4 · 10−16. Per quanto riguarda il massimo errore relativo, la formula di Lasserre è migliore, producendone uno di circa 3.1 · 10−15
contro un 4.08 · 10−15.
Sono tutti valori molto piccoli e tollerabili, si tratta infatti di numeri dell’ordine di grandezza estremamente vicino alla precisione di macchina di Matlab (2.220446049250313 · 10−16), che
3.2
Triangolo
Sia W = {xαyβ : α, β ∈ N} la base monomiale dei polinomi bivariati. Similmente al paragrafo
precedente, utilizzando lo script esperimentiLasserre_2d, si può calcolare, al variare del grado, l’integrale degli elementi di W sul triangolo canonico (di vertici [0, 0], [1, 0], [0, 1] ) con la formula di Lasserre, confrontando i risultati con quelli di formule di cubatura esatte fino a quel grado.
Ad esempio, ponendo deg=q=4, l’output sarà il seguente:
Tabella 3.3: Risultati del calcolo dei momenti fino a grado 4.
Grado x Grado y Risultati esatti Risultati Lasserre
0 0 0.5 0.5 0 1 0.166666666666667 0.166666666666667 1 0 0.166666666666667 0.166666666666667 0 2 0.0833333333333333 0.0833333333333333 1 1 0.0416666666666667 0.0416666666666667 2 0 0.0833333333333333 0.0833333333333333 0 3 0.05 0.05 1 2 0.0166666666666667 0.0166666666666667 2 1 0.0166666666666667 0.0166666666666667 3 0 0.05 0.05 0 4 0.0333333333333333 0.0333333333333333 1 3 0.00833333333333333 0.00833333333333333 2 2 0.00555555555555556 0.00555555555555556 3 1 0.00833333333333333 0.00833333333333333 4 0 0.0333333333333333 0.0333333333333333
Fino al grado due, il massimo errore assoluto commesso dalla formula di Lasserre è di circa 2.7 · 10−17, mentre quello relativo di 2.08 · 10−16.
Da questi dati si può già intuire il buon funzionamento della formula, almeno per gradi piccoli.
Con la funzione tic-toc di Matlab si può calcolare il tempo impiegato per eseguire lo script. Utilizzando un MacBook Air del 2015 con processore 1,6 GHz Intel Core i5 dual-core e 8 GB di RAM, ci vogliono 27.189558 secondi per ottenere i risultati fino a grado 200. Considerando che i momenti calcolati sono ben 20301, non è un conto computazionalmente oneroso.
Tuttavia, come nel caso unidimensionale, non è necessario salire molto con il grado. Infatti nelle applicazioni pratiche, soprattutto con l’aumentare della dimensione, capita raramente di dover utilizzare gradi alti. In tal caso è importante chiedersi se si stia procedendo nel modo corretto nella discussione del problema e se esistono metodi ad hoc.
Tabella 3.4: Massimi errori relativi della formula di Lasserre al variare del grado da 1 a 30.
deg Errore Relativo deg Errore Relativo deg Errore Relativo
1 0 11 1.66533453693773e − 16 21 1.11022302462516e − 16
2 2.77555756156289e − 17 12 1.11022302462516e − 16 22 2.77555756156289e − 17
3 5.55111512312578e − 17 13 2.77555756156289e − 17 23 5.55111512312578e − 17
4 2.77555756156289e − 17 14 1.11022302462516e − 16 24 2.22044604925031e − 16
5 2.77555756156289e − 17 15 1.66533453693773e − 16 25 2.77555756156289e − 17
6 5.55111512312578e − 17 16 2.77555756156289e − 17 26 2.22044604925031e − 16
7 2.77555756156289e − 17 17 1.11022302462516e − 16 27 5.55111512312578e − 17
8 2.77555756156289e − 17 18 1.11022302462516e − 16 28 1.11022302462516e − 16
9 1.11022302462516e − 16 19 1.11022302462516e − 16 29 5.55111512312578e − 17
10 1.11022302462516e − 16 20 1.11022302462516e − 16 30 5.55111512312578e − 16
0 10 20 30 40 50 60 70 80 90 100 Grado 10-17 10-16 10-15 10-14 10-13 Errore assoluto Errore relativo
3.3
Tetraedro
In ambito multivariato il tetraedro è un dominio di primario interesse. Risulta importante per l’integrazione su poliedri ed anche all’interno del metodo degli elementi finiti. Utilizzando lo script esperimentiLasserre_3d si possono vedere gli errori assoluti e relativi commessi dalla formula di Lasserre fino al grado di precisione scelto δ. Tale valore può essere scelto a piacere, ma bisogna essere consapevoli che il costo computazionale è molto alto. Nonostante ciò, a meno di overflow, qualora il risultato aritmetico sia troppo grande per essere rappresentato all’interno dello spazio disponibile per la sua memorizzazione, si può prevedere il buon funzionamento. Per calcolare gli integrali esatti sul tetraedro unitario ∆3, di vertici [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1],
si è utilizzata la seguente formula :
V ol(∆3) = Z 1 0 Z 1−z 0 Z 1−y−z 0 xaybzcdx dy dz = 1 3! a!b!c! (a + b + c)! 1 3+a+b+c 3 .
Si tratta di un caso particolare di una formula più generale e che è possibile ricavare nel seguente modo. Sia σ un simplesso di dimensione n e siano x0, . . . , xn coordinate baricentriche.
L’espansione di (x0+ · · · + xn)d= 1 è la somma di termini della forma:
d! i0! . . . in!
xi0
0 . . . xinn.
Quest’ultima si dice base di Bernstein per lo spazio vettoriale dei polinomi omogenei di grado d in coordinate baricentriche. La somma degli elementi della base è 1 e in essa ci sono n+dd elementi. Apparirà che l’integrale su σ è indipendente dalla decomposizione d = i0 + · · · + in.
Ne consegue che l’integrale di un qualunque elemento della base di Bernstein è V ol(σ)
n+d d
.
Per provare la precedente asserzione sull’indipendenza, è sufficiente mostrarla per ogni n-simplesso canonico, mentre per gli altri sarà sufficiente una trasformazione affine. Si noti innanzitutto che 1 i!j! Z t=1 t=s (t − s)i(1 − t)j dt = (1 − s) 1+j+1 (1 + j + 1)!.
Avendo coordinate 0 ≤ t1 ≤ · · · ≤ tn ≤ 1 per un generico n-simplesso, rispetto al quale
xi = ti+1− ti per 1 ≤ i < n, x0 = t1 e xn = 1 − tn, si vuole ora valutare:
d! i0! . . . in! Z 0≤t1≤···≤tn≤1 ti0 1(t2− t1)i1. . . (tn− tn−1)in−1(1 − tn)in dt1. . . dtn.
A questo punto si nota che si può eliminare tn integrando sull’intervallo [tn−1, 1]. Si ottiene
l’integrale di un altro elemento della base di Bernstein di grado d + 1 sul simplesso canonico di dimensione n − 1. Esplicitamente: d! i0! . . . in−2!(in−1+ in+ 1)! Z 0≤t1≤···≤tn−1≤1 ti0 1 (t2− t1)i1. . . (1 − tn−1)in−1+in+1 dt1. . . dtn−1. Si tratta effettivamente di 1
d+1 volte l’integrale di un elemento della base di Bernstein in
Ritornando agli esperimenti, sono riportati in Tabella 3.3 alcuni valori fino a deg=q=2, dove il massimo errore assoluto commesso è di circa 3.4 · 10−18, mentre quello relativo di circa
7.6 · 10−16. Infine è riportata una Figura 3.3 fino a deg=35. Si noti che il tempo impiegato per ottenere i risultati fino a grado 35 è di 4 minuti e 10 secondi e i momenti calcolati sono ben 8436.
Questi dati confermano la validità dell’implementazione della formula di Lasserre per il caso tridimensionale.
Tabella 3.5: Risultati del calcolo dei momenti fino a grado 2.
Grado x Grado y Grado z Risultati esatti Risultati Lasserre
0 0 0 0.166666666666667 0.166666666666667 0 0 1 0.0416666666666667 0.0416666666666667 0 0 2 0.0166666666666667 0.0166666666666667 0 1 0 0.0416666666666667 0.0416666666666667 0 1 1 0.00833333333333333 0.00833333333333333 0 2 0 0.0166666666666667 0.0166666666666667 1 0 0 0.0416666666666667 0.0416666666666667 1 0 1 0.00833333333333333 0.00833333333333333 1 1 0 0.00833333333333333 0.00833333333333333 2 0 0 0.0166666666666667 0.0166666666666667 0 5 10 15 20 25 30 35 Grado 10-18 10-17 10-16 10-15 10-14 Errore assoluto Errore relativo
Bibliografia
[1] Dyke P., An Introduction to Laplace Transforms and Fourier Series, Springer, 2014. [2] Epstein D., Integrating a barycentric monomial over a simplex, available at:
https://mathoverflow.net/questions/202820.
[3] Folland G.B., Real analysis: modern techniques and their applications, Wiley, 1999. [4] Hammerlin G., Hoffmann K.K., Numerical Mathematics, Springer-Verlag, 1991.
[5] Lasserre J. B., Simple formula for integration of polynomials on a simplex, BIT Numerical Mathematics, BITN-D-20-00061, pg. 1-11, 2000.
[6] Lasserre, J.B., Simple formula for integration of polynomials on a simplex, BIT Numerical Mathematics, pg. 1-11, 2020, reperibile a:
https://doi.org/10.1007/s10543-020-00828-x.
[7] Ördög, R., Szabadka, Z., Grolmusz V., Analyzing the simplicial decomposition of spatial protein structures, BMC Bioinformatics 9, S11, 2008.
[8] Quarteroni A., Saleri F., Introduzione al calcolo scientifico, SpringerVerlag, 2006.
[9] Sommariva A., Pointsets suitable for interpolation or cubature on intervals, simplex (trian-gle), square, disk and polygons, reperibile a:
https://www.math.unipd.it/~alvise/software.html.
Appendice A
Software Matlab
A.1
Implementazione in Matlab della formula di Lasserre
2.9 per il simplesso canonico
A.1.1
Caso 1-dimensionale
1 f u n c t i o n i n t e g r a l e L a s 1 d = L a s 1 d m o n o ( p , exp )
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
3 % F u n c t i o n per c a l c o l a r e con la f o r m u l a di L a s s e r r e gli i n t e g r a l i d e l l a % b a s e m o n o m i a l e sul s i m p l e s s o 1 - d i m e n s i o n a l e , o s s i a il s e g m e n t o [0 ,1]. 5 % A r e a s e g m e n t o . 7 vol =1; 9 % C a l c o l o del p u n t o csi . g r a d o o m o g = exp ; 11 v e t t = [ ] ; for r =1: g r a d o o m o g 13 s o m m a p a r z =1+ r ; v e t t =[ v e t t s o m m a p a r z ]; 15 end pr = p r o d ( vett , ’ all ’ ); 17 csi =( pr )^( -1/ g r a d o o m o g ); 19 % C a l c o l o del p o l i n o m i o di B o m b i e r i a s s o c i a t o a q u e l l o in i n p u t . c o e f f = f a c t o r i a l ( exp ); 21 h = @ ( x ) c o e f f +0* x ^0; b o m b p = @ ( x ) p ( x )* h ( x ); 23 % C a l c o l o dell ’ i n t e g r a l e .
25 i n t e g r a l e L a s 1 d = vol * f e v a l ( bombp , csi );
A.1.2
Caso 2-dimensionale
f u n c t i o n i n t e g r a l e L a s = L a s 2 d m o n o ( p , exp1 , e x p 2 )
2 % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % F u n c t i o n per c a l c o l a r e con la f o r m u l a di L a s s e r r e gli i n t e g r a l i d e l l a
4 % b a s e m o n o m i a l e sul s i m p l e s s o 2 - d i m e n s i o n a l e , o s s i a il t r i a n g o l o di % v e r t i c i [0 0] , [1 0] , [0 1]. 6 % A r e a t r i a n g o l o . 8 vol = . 5 ; 10 % C a l c o l o del p u n t o csi . g r a d o o m o g = e x p 1 + e x p 2 ; 12 v e t t = [ ] ; for r =1: g r a d o o m o g 14 s o m m a p a r z =2+ r ; v e t t =[ v e t t s o m m a p a r z ]; 16 end pr = p r o d ( vett , ’ all ’ ); 18 csi = o n e s (1 ,2)*( pr )^( -1/ g r a d o o m o g ); 20 % C a l c o l o del p o l i n o m i o di B o m b i e r i a s s o c i a t o a q u e l l o in i n p u t . c o e f f = f a c t o r i a l ( e x p 1 )* f a c t o r i a l ( e x p 2 ); 22 h = @ ( x , y ) c o e f f +0* x ^ 0 + 0 * y ^0; b o m b p = @ ( x , y ) p ( x , y )* h ( x , y ); 24 % C a l c o l o dell ’ i n t e g r a l e .
26 i n t e g r a l e L a s = vol * f e v a l ( bombp , csi (1) , csi ( 2 ) ) ;
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
A.1.3
Caso 3-dimensionale
f u n c t i o n i n t e g r a l e L a s = L a s 3 d m o n o ( p , exp1 , exp2 , e x p 3 )
2 % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % F u n c t i o n per c a l c o l a r e con la f o r m u l a di L a s s e r r e gli i n t e g r a l i d e l l a
4 % b a s e m o n o m i a l e sul s i m p l e s s o 3 - d i m e n s i o n a l e , o s s i a il t e t r a e d r o di % v e r t i c i [0 0 0] , [1 0 0] , [0 1 0] , [0 0 1]. 6 % V o l u m e t e t r a e d r o . 8 vol = 1 / 6 ; 10 % C a l c o l o del p u n t o csi . g r a d o o m o g = e x p 1 + e x p 2 + e x p 3 ; 12 v e t t = [ ] ; for r =1: g r a d o o m o g 14 s o m m a p a r z =3+ r ; v e t t =[ v e t t s o m m a p a r z ]; 16 end pr = p r o d ( vett , ’ all ’ ); 18 csi = o n e s (1 ,3)*( pr )^( -1/ g r a d o o m o g ); 20 % C a l c o l o del p o l i n o m i o di B o m b i e r i a s s o c i a t o a q u e l l o in i n p u t . c o e f f = f a c t o r i a l ( e x p 1 )* f a c t o r i a l ( e x p 2 )* f a c t o r i a l ( e x p 3 ); 22 h = @ ( x , y , z ) c o e f f +0* x ^ 0 + 0 * y ^ 0 + 0 * z ^0; b o m b p = @ ( x , y , z ) p ( x , y , z )* h ( x , y , z ); 24 % C a l c o l o dell ’ i n t e g r a l e .
26 i n t e g r a l e L a s = vol * f e v a l ( bombp , csi (1) , csi (2) , csi ( 3 ) )
A.2
Script per gli esperimenti
A.2.1
Caso 1-dimensionale
A.2.2
Caso 2-dimensionale
1 f u n c t i o n e s p e r i m e n t i L a s s e r r e _ 2 d ( q ) % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 3 % V i e n e i m p o s t a t o il g r a d o m a s s i m o d e l l a b a s e m o n o m i a l e in due v a r i a b i l i e % il f o r m a t o dei n u m e r i in o u t p u t . 5 deg = q ; f o r m a t l o n g 7 % V i e n e i m p o r t a t a l a f u n c t i o n per l ’ u t i l i z z o d e l l e f o r m u l e di c u b a t u r a e s a t t e 9 % f i n o al g r a d o p r e s c e l t o , o s s i a deg .[ xyw , xyw_bar , p o i n t s e t _ s t a t s ]= c u b a t u r e _ t r i a n g l e ( deg );
11 X = xyw (: ,1); Y = xyw (: ,2); W = xyw (: ,3);
13 % Si c a l c o l a n o gli e s p o n e n t i d e l l a b a s e e v e n g o n o r a p p r e s e n t i in una m a t r i c e . j = ( 0 : 1 : deg );
15 [ j1 , j2 ]= m e s h g r i d ( j ); dim =( deg + 1 ) * ( deg + 2 ) / 2 ;
A.2.3
Costruzione esponenti 3D
f u n c t i o n [ m a t r i c e e s p ]= c o s t r u i s c o _ e s p o n e n t i _ 3 d ( deg ) 2 A = z e r o s (( deg + 1 ) ^ 3 , 3 ) ; % C r e a z i o n e v e t t o r i 4 o =0: deg ; oo = [ ] ; 6 ooo = [ ] ; for d = 1 : ( deg +1) 8 oo =[ oo o ]; end 10 for d = 1 : ( ( ( deg + 1 ) ^ 3 ) / 3 ) ooo =[ ooo o ]; 12 end 14 for t = 1 : 3 if t ==1 16 for i =0: deg if i ==0 18 for m = 1 : ( ( deg + 1 ) ^ 2 ) A ( m , t )= o ( i + 1 ) ; 20 end 22 24 e l s efor m = ( ( ( i ) * ( ( deg + 1 ) ^ 2 ) ) + 1 ) : ( ( i + 1 ) * ( ( deg + 1 ) ^ 2 ) )
26 A ( m , t )= o ( i + 1 ) ; 28 end 30 end end 32 e l s e i f t ==2 34 for i = 0 : ( l e n g t h ( oo ) -1) if i ==0 36 for m = 1 : ( ( deg + 1 ) ) A ( m , t )= oo ( i + 1 ) ; 38 end 40 42 e l s e
for m = ( ( ( i ) * ( ( deg + 1 ) ) ) + 1 ) : ( ( i + 1 ) * ( ( deg + 1 ) ) )
[ qq , ww ] = s i z e ( m a t r i c e e s p ) ; 76 for q =1: qq c a l c =( m a t r i c e e s p ( q , 1 ) + m a t r i c e e s p ( q , 2 ) + m a t r i c e e s p ( q ,3)) > deg ; 78 if c a l c = = 1 ; r a c c =[ r a c c q ]; 80 end 82 end % V e n g o n o m o d i f i c a t e le r i g h e 84 m a t r i c e e s p ( racc , : ) = [ ] ; m a t r i c e e s p
A.2.4
Caso 3-dimensionale
f u n c t i o n e s p e r i m e n t i L a s s e r r e _ 3 d ( q ) 2 % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % V i e n e i m p o s t a t o il g r a d o m a s s i m o d e l l a b a s e m o n o m i a l e in tre v a r i a b i l i e 4 % il f o r m a t o dei n u m e r i in o u t p u t . deg = q ; 6 f o r m a t l o n g d e g r e e = deg ; 8 % n o t o che i n t _ { 0 } ^ { 1 } i n t _ {0}^{1 - z } i n t _ {0}^{1 - y - z } x ^ a * y ^ b * z ^ c d x d y d z = 10 % = ( 1 / 3 ! ) ( a ! b ! c ! ) / ( a + b + c ) ! * 1 / ( bin (3+ a + b + c ) ( 3 ) ) 12 % Si c a l c o l a n o gli e s p o n e n t i d e l l a b a s e e v e n g o n o r a p p r e s e n t i in una m a t r i c e . [ m a t r i c e e s p ]= c o s t r u i s c o _ e s p o n e n t i _ 3 d ( deg ); 14 L = l e n g t h ( m a t r i c e e s p ); R I S U L T A T I _ L A S S E R R E = [ ] ; 16 R I S U L T A T I _ E S A T T I = [ ] ; 18 for i =1: L a = m a t r i c e e s p ( i , 1 ) ; 20 b = m a t r i c e e s p ( i , 2 ) ; c = m a t r i c e e s p ( i , 3 ) ; 22 p = @ ( x , y , z ) ( x .^ a ) . * ( y .^ b ) . * ( z .^ c ); % A p p l i c a z i o n e d e l l a f o r m u l a di L a s s e r r e . 24 e x p 1 = a ; e x p 2 = b ; 26 e x p 3 = c ; i n t e g r a l e L a s = L a s 3 d m o n o ( p , exp1 , exp2 , e x p 3 ); 28 R I S U L T A T I _ L A S S E R R E =[ R I S U L T A T I _ L A S S E R R E ; i n t e g r a l e L a s ]; In = ( 1 / 6 ) * ( ( f a c t o r i a l ( e x p 1 )* f a c t o r i a l ( e x p 2 )* f a c t o r i a l ( e x p 3 ) ) / . . . 30 f a c t o r i a l ( a + b + c ) ) * ( ( f a c t o r i a l ( 3 ) * f a c t o r i a l ( e x p 1 + e x p 2 + e x p 3 ))/ f a c t o r i a l (3+ e x p 1 + e x p 2 + e x p 3 )); R I S U L T A T I _ E S A T T I =[ R I S U L T A T I _ E S A T T I ; In ]; 32 end 34 % I r i s u l t a t i o t t e n u t i v e n g o n o t a b u l a t i m o s t r a n d o , al v a r i a r e d e g l i 36 % e s p o n e n t i , il r i s u l t a t o dell ’ i n t e g r a l e u t i l i z z a n d o r i s p e t t i v a m e n t e la % f o r m u l a di c u b a t u r a e s a t t a f i n o a deg e la f o r m u l a di L a s s e r r e . 38 % I n f i n e s o n o r i p o r t a t i i m a s s i m i e r r o r i a s s o l u t i e r e l a t i v i . G r a d o _ x = m a t r i c e e s p (: ,1); 40 G r a d o _ y = m a t r i c e e s p (: ,2); G r a d o _ z = m a t r i c e e s p (: ,3); 42 e r r a s s L A S = abs ( R I S U L T A T I _ L A S S E R R E - R I S U L T A T I _ E S A T T I ); M A X _ E R R O R E _ A S S O L U T O _ L A S S E R R E _ v s _ E S A T T I = max ( e r r a s s L A S ); 44 e r r r e l L A S = [ ] ; for k =1: l e n g t h ( e r r a s s L A S ) 46 if R I S U L T A T I _ L A S S E R R E ( k ) = = 0 e r r r e l L A S ( k )= e r r a s s L A S ( k ); 48 e l s e e r r r e l L A S ( k )= e r r a s s L A S ( k ) . / ( abs ( R I S U L T A T I _ L A S S E R R E ( k ) ) ) ; 50 end end 52 M A X _ E R R O R E _ R E L A T I V O _ L A S S E R R E _ v s _ E S A T T I = max ( e r r r e l L A S ); 54
A.3
Script per i grafici
A.3.1
Caso 1-dimensionale
f u n c t i o n g r a f i c i _ 1 d 2 % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % v e t t o r e 1 = [ ] ; 4 v e t t o r e 2 = [ ] ; g r a d o = 1 5 0 ; 6 for q =1: g r a d o [ M A X _ E R R O R E _ A S S O L U T O _ L A S S E R R E _ v s _ E S A T T O , M A X _ E R R O R E _ R E L A T I V O _ L A S S E R R E _ v s _ E S A T T O ] = . . . 8 e s p e r i m e n t i L a s s e r r e _ 1 d ( q ); v e t t o r e 1 =[ v e t t o r e 1 M A X _ E R R O R E _ A S S O L U T O _ L A S S E R R E _ v s _ E S A T T O ]; 10 v e t t o r e 2 =[ v e t t o r e 2 M A X _ E R R O R E _ R E L A T I V O _ L A S S E R R E _ v s _ E S A T T O ]; end 12 b a s e =1: g r a d o ; s e m i l o g y ( base , v e t t o r e 1 ) 14 h o l d on ; s e m i l o g y ( base , v e t t o r e 2 ) 16 x l a b e l ( ’ G r a d o ’ ) l e g e n d ( ’ E r r o r e ␣ a s s o l u t o ’ , ’ E r r o r e ␣ r e l a t i v o ’ ) 18 % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
