Calcolo di formule minimali sul quadrato
(Computation of minimal rules on the square)
Capitolo 1
Preliminari numerici e matematici
1.1 Introduzione
Data una funzione continua f : Ω ⊂ Rd
→ R (ove Ω è un dominio compatto), il problema della cubatura numerica consiste nell'approssimare
I(f ) = ˆ Ω f (x)w(x) dx con la quantità Sn(f ) = n X i=1 wif (xi), wi∈ R, xi∈ R d.
I punti xi, detti usualmente nodi, in generale appartengono a Rd, ma visto che la funzione f è de nita
in Ω, non è infrequente che si ponga il vincolo che ogni xi sia in Ω. Le quantità wi sono dette pesi.
Una tecnica comune per de nire i nodi e i pesi di quadratura consiste nel ssare una famiglia discreta di funzioni continue e linearmente indipendenti {φk}k=1,...,m, con φk: Ω ⊂ Rd→ R e calcolare dei nodi
{xi}i=1,...,n e dei pesi {wi}i=1,...,n per cui
I(φk) = Sn(φk), k = 1, . . . , m.
Formule Sn per cui questo obiettivo è raggiunto con un minimo numero di nodi sono dette minimali
per lo spazio {φk}k=1,...,m. Classicamente, denotato con PN lo spazio dei polinomi il cui grado totale
è inferiore o uguale a N, si pone {φk}k=1,...,muna base di PN e le formule Sn per cui I(φk) = Sn(φk)
per ogni k = 1, . . . , m si dicono avere grado algebrico di esattezza uguale a N. Useremo in seguito l'acronimo ADE per denotare tale quantità.
Nel caso Ω sia un intervallo e w una funzione peso su Ω si dimostra che esistono N +1 2
nodi e pesi per cui la relativa formula Sn ha grado di precisione esattamente uguale a N. Tali formule sono dette
gaussiane e si dimostrano essere minimali (rispetto PN). I corrispettivi nodi e pesi sono calcolabili per
le più classiche funzioni peso grazie ad un algoritmo dovuto a Wi e Gelub e perfezionato da Gautschi e Laurie.
4 CAPITOLO 1. PRELIMINARI NUMERICI E MATEMATICI Nel caso in cui Ω ∈ Rd, con d > 1, l'analisi è maggiormente complessa ed eccetto per rari casi le
formule minimali non sono note in generale. Questo problema si è rivelato molto di cile e negli ultimi anni questo ha portato ad un rallentamento della ricerca, come menzionato da R. Cools in [3]. Nel 2003 esistevano ancora molti gap tra i risultati teorici e pratici [4].
Analizzeremo in questo lavoro il caso in cui Ω sia un quadrato e cercheremo di determinare nu-mericamente formule aventi grado di esattezza N con un basso numero n di nodi e pesi, rispetto a quanto noto in letteratura, migliorando i risultati noti per gradi inferiori a 24 e ottenendone di nuove no a grado 55. In particolare, presentiamo un algoritmo per la costruzione di formule di cubatura in dimensioni maggiori di uno. Data una regola di partenza di n nodi e grado di precisione N, sono al momento noti due approcci diversi. Il primo, introdotto da H. Xiao e collaboratori [7, 15, 16], detto di eliminazione, cerca di ridurre il numero di nodi, mantenendo invariato il grado algebrico di precisione, mentre il secondo approccio, dovuto a M. Taylor, B. Wingate e L. Bos [13, 14], detto di arricchimento, mantenendo invariato il numero di nodi, aumenta la precisione della formula. Qui si è scelto di seguire il primo approccio, ovvero di implementare un algoritmo di eliminazione.
1.2 Cubatura numerica in dimensione generica
Sia Ω ⊂ Rd un prede nito dominio di integrazione, f
j : Ω → R, j = 1, . . . , m funzioni continue
linearmente indipendenti, e consideriamo una forumla di cubatura tale che:
n X i=1 wifj(xi) = ˆ Ω fj(x)w(x) dx , per ogni j = 1, . . . , m. (1.1)
Come anticipato, usualmente si scelgono {fj}j=1,...,m che costituiscono, per qualche N pre ssato, una
base dello spazio PN dei polinomi in Rd di grado totale inferiore o uguale a N, ma altre scelte sono
possibili. Inoltre nei nostri esempi analizzeremo il caso della funzione peso di Legendre, cioè w(x) ≡ 1. De nito il momento j-esimo
mj=
ˆ
Ω
fj(x)dx
e la matrice di Vandermonde V de nita componente per componente da (V )ij = fi(xj) e posto
w = (wi)iil vettore n-dimensionale dei pesi, a nché la formula di cubatura abbia le proprietà richieste,
necessariamente: f1(x1) · · · f1(xn) ... ... fm(x1) · · · fm(xn) w1 ... wn = m1 ... mm ,
o in forma più compatta:
V ·w = m.
1.2. CUBATURA NUMERICA IN DIMENSIONE GENERICA 5 V8k= f1(x1) · · · f1(xk−1) f1(xk+1) · · · f1(xn) ... ... ... ... fm(x1) · · · fm(xk−1) fm(xk+1) · · · fm(xn) , w8k= w1 ... wk−1 wk+1 ... wn ,
avremo in generale V8k·w8k− m 6= 0. Si vorrebbe quindi determinare n−1 nuovi nodi {xi}e n−1 nuovi
pesi {wi} per cui la formula di cubatura sia esatta relativamente alla famiglia di funzioni f1, . . . , fm,
cioè valga (1.1), e quindi se V è la matrice di Vandermonde nei punti {xi}, sia nuovamente V ·w = m.
Numericamente, richiederemo che per una pre ssata tolleranza ε e una certa norma vettoriale k·k, sia kV8k·w8k− mk < ε.
Tra i vari approcci per raggiungere questo proposito, abbiamo scelto il seguente. De nita V ({xi}i)
la matrice di Vandermonde relativa ai nodi {xi}i e alle funzioni {fj}j, consideriamo la funzione
{xi, wi}i=1,...,n−1 F
7−→ V ({xi}i) · w − m (tenendo quindi sia i nodi che i pesi come variabili),
risol-vendo il problema di minimizzare kV8k·w8k− mk. Una volta risolto, se kV8k·w8k− mk < ε, si procede
ulteriormente ad eliminare altri nodi e pesi. Il vantaggio di questa scelta è che potendo forzare le variabili a stare all'interno di una regione pre ssata durante la risoluzione del problema di minimo, è possibile imporre la positività dei pesi della formula di cubatura (proprietà molto importante legata alla sua stabilità). Lo svantaggio di questo approccio è tuttavia quello di aumentare la complessità dell'al-goritmo durante la risoluzione del problema di minimo (le variabili salgono da (n − 1)d a (n − 1)(d + 1), e usualmente n d).
Un primo problema che sorge spontaneo è capire quando l'algoritmo ha tolto abbastanza nodi, ovvero capire quando è stato raggiunto un buon numero di nodi per un certo grado di precisione pre ssato. Si ricordi infatti che, ssato un certo grado, per dimensioni d > 1 non si conosce quale sia il numero minimale di nodi necessari alla formula di cubatura per quel grado. Con riferimento a quanto discusso da H. Xiao e Z. Gimbutas [15], generalizzando il caso 1-dimensionale, in cui per avere una formula esatta su m polinomi servono m
2
nodi, appare naturale pensare che formule di cubatura minimali (su m polinomi) in Rd necessitino di l m
(d+1)m nodi, e riscontri empirici sembrano avvallare
l'ipotesi che questo valore, benché non esatto (in alcuni casi si riescono a trovare formule con ancora meno nodi), costituisca comunque un ordine di grandezza su cientemente preciso per formule minimali multidimensionali. Per questo, calcoleremo formule di cubatura che si avvicinano a questo valore.
1.2.1 Le routine lsqnonlin e fmincon
In questa sezione mostriamo che per calcolare una formula di cubatura, avente n nodi x1, . . . , xn∈ Ωed
npesi w1, . . . , wn, e che abbia grado algebrico di precisione uguale a N, è su ciente cercare uno zero di
6 CAPITOLO 1. PRELIMINARI NUMERICI E MATEMATICI di cubatura quasi minimali. Nei nostri esperimenti numerici in Matlab useremo a tal proposito le routine lsqnonlin e fmincon.
La prima, lsqnonlin, richiede come input una funzione F : Rq → Rm, e dato un punto iniziale x ∈ Rq,
cerca un punto che minimizzi la funzione kF(·)k2
. La seconda, fmincon, necessita semplicemente (oltre al dato iniziale) una funzione T : Rq
→ R, di cui cerca il minimo. In entrambi i casi vengono calcolati dei minimi locali, e quindi a priori non c'è garanzia che tale minimo equivalga a zero (come si vorrebbe in questo caso). Inoltre, entrambe le routine supportano vincoli lineari sulle variabili, il che come già detto permetterà di imporre la positività dei nodi.
Posti quindi come al solito:
V = f1(x1) · · · f1(xn) ... ... fm(x1) · · · fm(xn) (matrice di Vandermonde), w = w1 ... wn , m = m1 ... mm ,
le due funzioni utilizzate rispettivamente da lsqnonlin e fmincon saranno:
F : R q {xi, wi}i=1,...,n −→ 7−→ Rm V ·w − m e T : R q {xi, wi}i=1,...,n −→ 7−→ R kV ·w − mk2.
Si osservi che entrambe le routine hanno come input un singolo vettore, mentre al contrario nel nostro caso le variabili si articolano in una matrice dei nodi (di dimensione d × n) e nel vettore dei pesi (n-dimensionale). Per questo motivo, sorge la necessità di stabilire una codi ca vettoriale di questi dati. Chiamati quindi X la matrice dei nodi e w il vettore pesi, e denotando con (xk)j la j-esima
componente del nodo xk:
X = x1 · · · xn = (x1)1 · · · (xn)1 ... ... (x1)d · · · (xn)d w = w1 ... wn ;
salveremo i dati nel vettore:
v = (x1)1, . . . , (x1)d, w1, (x2)1, . . . , (x2)d, w2, . . . , (xn)1, . . . , (xn)d, wn
T .
1.2. CUBATURA NUMERICA IN DIMENSIONE GENERICA 7 m ≥ n(d + 1) , o equivalentemente n ≤ m d + 1 (infatti n, d, m ∈ N), ma se n ≤l m
d+1m, per quanto visto in precedenza si sarebbe già trovata un'ottima candidata a formula
di cubatura nale. Non solo, ma come si vedrà è anche molto raro che n possa riuscire a scendere sotto tale valore, e in ogni caso questo non vale durante la quasi totalità del tempo di esecuzione dell'algoritmo. Questo problema, apparentemente insormontabile, è in realtà facilmente risolvibile per mezzo di un piccolo arti cio tecnico, e cioè modi care leggermente la funzione F in una F : Rq
→ Rr,
con r = max(q, m), de nita come:
F (v) = F1(v) ... Fm(v) 0 ... 0 .
Con questo stratagemma, non solo lsqnonlin funziona correttamente, ma la complessità del calcolo (specialmente se il tutto è implementato in modo accorto) non ne risulta praticamente in uenzata.
Un'ultima considerazione da fare, per entrambe le routine, è il calcolo della matrice Jacobiana di F e di T , e dell'Hessiano di T , che permette, una volta passati alla routine, di velocizzare e migliorare signi cativamente la ricerca di una soluzione. In seguito, vedremo come calcolare le derivate parziali di F e T partendo dalla semplice conoscenza delle derivate (ovvero Jacobiane ed Hessiane) delle fj.
In questo modo, l'unica variabile che dovrà essere passata all'algoritmo sarà un'opportuna funzione x 7→ ˆf (x)che restistuisca la terzina di oggetti [f(x), J(x), H(x)], ove:
f (x) = f1(x) ... fm(x) , J (x) = ∂f1 ∂x1(x) · · · ∂f1 ∂xd(x) ... ... ∂fm ∂x1(x) · · · ∂f1 ∂xd(x) (Jacobiano di f),
e H(x) è una matrice d×(d·m) che raccolga tutti gli m Hessiani Hfjdegli fj (cioè (Hfj)l,m= ∂l,mfj),
nel seguente modo (non univoco) scelto:
H(x) = Hf1(x) · · · Hfm(x)
.
8 CAPITOLO 1. PRELIMINARI NUMERICI E MATEMATICI standard, dato un generico punto x, questo vuol dire che ˆf calcolerà la tripla [f(ex), J (x), H(e ex)], ove (denotata con xi la i-esima componente del vettore x):
e xi= xi se − 1 ≤ xi≤ 1 1 se xi > 1 −1 se xi < 1 .
1.2.2 Simmetrie
In questa sezione analizzeremo il caso di formule simmetriche, molto utili per ridurre la complessità computazionale dell'algoritmo di ottimizzazione.
Sia Ω ⊂ Rd un dominio chiuso e limitato. Il gruppo di simmetria G di Ω è l'insieme di tutte le
trasformazioni lineari in Rdche mappano Ω in se stesso. Un sottoinsieme S ⊆ G è chiamato sottogruppo
di simmetria di Ω se S è esso stesso un gruppo. Diciamo che due punti x1, x2 ∈ Ωsono in relazione
S-simmetrica se esiste un elemento s ∈ S tale che x2= s(x1). Dato un generico punto x ∈ Ω, l'insieme di tutti i punti di Ω che sono in relazione S-simmetrica rispetto a x prende il nome di orbita di x, e viene indicata con OS
x.
Se, per ogni punto x ∈ X ⊂ Ω, vale che OS
x ⊆ X, diciamo che X è S-simmetrico (o invariante
rispetto a S). Si può vedere facilmente che un insieme S-simmetrico X è l'unione di orbite distinte. Supponiamo ora che l'insieme B contenga un unico punto per ogni orbita contenuta in X . In questo caso diciamo che B è un S-generatore di X . In questo modo, ogni insieme S-simmetrico X può essere scritto come X = ∪x∈BOSx, ove OSxi∩ OxSj = ∅ per ogni xi, xj ∈ Bcon xi6= xj.
Finite quindi le premesse generali, possiamo ora scendere nel dettaglio. Sia dunque Ω ⊂ Rd il
dominio di integrazione, G il suo gruppo di simmetria, e S un suo sottogruppo. Diciamo che una formula di cubatura avente quali nodi x1, . . . , xne pesi w1, . . . , wnè S-simmetrica (o invariante rispetto
a S) se x1, . . . , xn ⊂ Ω è insieme S-simmetrico e se tutti i nodi che appartengono alla stessa orbita
hanno pesi uguali. Chiaramente, ogni formula S-simmetrica R è completamente determinata dai nodi (e rispettivi pesi) che giacciono in un singolo S-generatore B di X . La relazione che intercorre tra una formula di cubatura costruita su un singolo S-generatore B di X e la sua estensione S-simmetrica è l'oggetto del seguente teorema (dovuto a Xiao [15]):
Theorem 1.2.1. Sia x1, . . . , xp, w1, . . . , wp una formula di cubatura di p nodi su B, S-generatore di
Ω, tale che X xi∈XB wiφj(xi) = ˆ B φj(x) dx
sia esatta per un pre ssato insieme {φj}j=1,...,m di funzioni (con opportune proprietà di integrazione)
de nite su Ω. Allora, una volta de niti {x1, . . . , xn} = ∪xi∈BOSxi e w1, . . . , wntali che nodi sulla stessa
1.2. CUBATURA NUMERICA IN DIMENSIONE GENERICA 9 Dimostrazione. Sia φ una funzione arbitraria in {φj}j. Per le proprietà dell'azione del gruppo S,
possiamo scrivere: ˆ Ω φ =X g∈S ˆ g(B) φ =X g∈S ˆ B (g−1◦ φ) =X g∈S 1 det(g) ˆ B φ
ove det(g) denota il determinante della trasformazione ortogonale g. D'altra parte, vale anche la relazione X xi∈X wiφ(xi) = X g∈S X xj∈XB wjφ(g(xj)) = X g∈S X xj∈XB wj(g−1◦ φ)(xj) = X g∈S 1 det(g) X xj∈XB wjφ(xj) , ma: X g∈S 1 det(g) X xj∈XB wjφ(xj) = X g∈S 1 det(g) ˆ B φ .
Come anticipato, il calcolo di formule simmetriche risulta vantaggioso perché riduce notevolmente il numero di variabili del problema (tanto di più quanto più piccolo è l'S-generatore scelto per X ). Tuttavia, restringendo il problema alle sole soluzioni che soddis no vincoli di simmetria, è chiaro che la formula di cubatura simmetrica con cardinalità minima potrebbe non essere ottimale quanto la controparte trovata senza porre questo tipo di vincoli.
Un altro svantaggio evidente è che ovviamente non tutti i possibili domini d'integrazione hanno le stesse proprietà di simmetria (se sono presenti simmetrie), e quindi bisognerebbe sviluppare ogni volta un diverso algoritmo. In questo articolo, si è scelto di implementare due tipi di simmetrie: la simmetria rispetto all'iperpiano x1= 0 e la simmetria rispetto all'origine. Se si è interessati a trasformazioni per
rototraslazioni, è di particolare interesse il
Theorem 1.2.2. Sia x1, . . . , xn, w1, . . . , wnuna formula di cubatura su Ω ⊂ Rdesatta per {pj}j=1,...,m,
base polinomiale di grado δ, e Φ : Rd → Rd una rototraslazione. Allora, la formula di cubatura
Φ(x1), . . . , Φ(xn), w1, . . . , wn è esatta per {pj}j=1,...,m su Φ(Ω).
Dimostrazione. Dato che Φ è una rototraslazione, allora Φ(x) = Rx + v (x, v ∈ Rd, R matrice d × d),
e |det(R)| = 1. Inoltre, essendo una trasformazione lineare, è banale vedere che se pj è un polinomio
di grado minore o uguale di δ, anche pj◦ Φ lo è. Per cui, ricordando la formula di cambiamento di
variabili sotto il segno di integrale, si può scrivere:
10 CAPITOLO 1. PRELIMINARI NUMERICI E MATEMATICI Quindi, per trovare una formula di cubatura simmetrica rispetto ad un altro iperpiano, con solo l'opzione di simmetria rispetto x1= 0 disponibile, è su ciente rototraslare il dominio e la quadratura
di partenza in modo da far coincidere x1= 0con l'iperpiano di simmetria, risolvere il problema, e in ne
rototraslare nuovamente la formula di cubatura ottenuta.
1.3 I casi testati
Anche se molte classi di funzioni potrebbero risultare interessanti, in questo articolo saranno cercate for-mule di cubatura che integrino polinomi multidimensionali (benché comunque l'algoritmo sia progettato per accettare un qualsiasi insieme generico di funzioni fj). Una base che si può considerare naturale
per polinomi di grado N in Rd può essere la semplice base monomiale {xc1
1 · x c2
2 · · · x cd
d }c1+...+cd≤N;
tuttavia, i monomi tendono ad essere mal condizionati anche per gradi moderati, per cui una base ortogonale è solitamente utilizzata.
L'algoritmo è stato testato per due casi. Il primo è un esempio univariato, con dominio di inte-grazione [−1, 1] e in cui {fj}j=1,...,mè la base polinomiale (e ortogonale) di Legendre di un ssato grado
N (quindi in questo caso m = N + 1). I momenti m1, . . . , mm(rispetto alla funzione peso w(x) ≡ 1) si
calcolano facilmente, infatti denotando P0(x), . . . , PN(x)i primi N + 1 polinomi di Legendre, sappiamo
che P0(x) ≡ 1, da cui ovviamente m1= 2, e quindi possiamo scrivere:
mk = ˆ [−1,1] Pk−1(x)dx = ˆ [−1,1] (1·Pk−1(x))dx = ˆ [−1,1] (P0(x)·Pk−1(x))dx = 0 , per ogni k ≥ 2
ricordando che i polinomi di Legendre sono ortogonali (rispetto la funzione peso w(x) ≡ 1). Come si vedrà, in questo caso l'algoritmo riproduce esattamente le formule di cubatura gaussiane.
Il secondo caso testato, più interessante e signi cativo, è quello del quadrato. In questo caso, Ω = [−1, 1]2 e {fj}j=1,...,m è una base ortogonale bivariata costruita a partire dalla base univariata di
Legendre:
fj(x, y) = Pc1(x)·Pc2(y),
j = 1, . . . , m
c1,c2= 0, . . . , N con c1+ c2≤ N
. (1.2) In questo caso quindi, m = (N +1)(N +2)
2 . Inoltre, per un ragionamento del tutto analogo a quello del
caso 1-dimensionale, è banale vedere che con questa base i momenti sono m1= 4 e mk = 0 per ogni
k > 1.
1.3.1 Regole tensoriali
Le formule di cubatura a prodotto tensoriale sono una particolare classe di formule di cubatura mul-tidimensionali costruite a partire da una formula di cubatura univariata. Queste formule si possono ottenere per una diversi domini multidimensionali, ma qui considereremo esclusivamente il quadrato standard [−1, 1]2.
1-1.4. GENERALITÀ SULL'ALGORITMO 11 dimensionale con grado algebrico di precisione N, ad esempio una regola gaussiana (da cui N = 2p−1). Si de nisca quindi la formula di cubatura su [−1, 1]2 avente nodi e pesi:
xi,j= (ti, tj) ∈ Ω wi,j= vi·vj.
Si noti che questa è eettivamente una formula di cubatura su [−1, 1], di precisione 2n−1. Per vederlo, basta semplicemente provare la sua esattezza sul generico monomio ph,k(x, y) = xhyk, con h, k ≥ 0 e
0 ≤ h + k ≤ 2p − 1, ma questo è banalmente vero, infatti:
p X i,j=1 wi,jph,k(xi,j) = p X i=1 p X j=1 vivjthitkj = p X i=1 vithi p X j=1 vjtkj = ˆ [−1,1] xhdx ˆ [−1,1] ykdy = ˆ [−1,1]2 ph,k(x, y) dxdy .
Queste formule tuttavia sono in generale ben lontane dall'essere minimali. Per dare un'idea di questo, in relazione a quanto visto in (1.2.1), consideriamo il rapporto tra il numero approssimato di nodi cui ci vogliamo avvicinare (cioè m
d+1) e il numero di nodi n di una formula di cubatura tensoriale gaussiana:
m n(d + 1),
e scriviamo il tutto (per facilitare i conti) in funzione del numero di nodi p della regola gaussiana di partenza. Sapendo quindi che d = 2, m =(N +1)(N +2)
2 e N = 2p − 1, si ottiene: m n(d + 1) = 2p(2p + 1) 6p2 = 2p + 1 3p , che come è evidente, parte da valori prossimi a 1, ma tende a 2
3 al crescere di p (che come già detto
è legato al grado di precisione dalla relazione N = 2p − 1). Tuttavia, benché le regole tensoriali siano lontane dall'ottimalità, nel caso 2-dimensionale del quadrato esse sono comunque su cientemente vicine al valore obbiettivo l m
d+1m di nodi a cui ci si vuole avvicinare, dall'essere delle eccellenti candidate a
formule di cubatura di partenza1. Inoltre, come si vedrà, nel caso in cui si volesse imporre alla risoluzione
uno dei due vincoli di simmetria implementati nell'algoritmo, esso richiede di partire con una regola che soddis già tale vincolo, e queste regole tensoriali li soddisfano già entrambi, in virtù delle proprietà di simmetria delle formule univariate di Gauss-Legendre, per cui sono adatte come regole di partenza per tutti i casi che aronteremo.
1.4 Generalità sull'algoritmo
Comando: [x, w] = NodesElim( f, y, v, sym, method, posw, B, limit). Input:
• f : funzione [ f, J, H] = f(x) implementata come descritto in (1.2.2). • y : nodi di partenza (sottoforma di matrice d × n).
12 CAPITOLO 1. PRELIMINARI NUMERICI E MATEMATICI • v: pesi di partenza (in forma vettoriale n × 1).
• sym: opzione di simmetria (0: nessuna (prede nito), 1: rispetto all'iperpiano x1= 0, 2: rispetto
all'origine).
• method: metodo di risoluzione (0: lsqnonlin (prede nito), 1: fmincon). • posw : opzione di positività sui pesi (0: generali, 1: positivi (prede nito)).
• B : momenti (vettore m × 1, se non immesso lo calcola tramite la relazione B = V (y)·v). • limit: numero di nodi che si vuole raggiungere (prede nito limit = 0).
Output:
• x: nodi nali (matrice d × n). • w: pesi nali (vettore 1 × n).
Oltre agli input, all'inizio dell'algoritmo vengono de niti altri sei parametri strutturali:
• tol_x : tolleranza di terminazione sulla codi ca vettoriale v dei dati (prede nito tol_x = 10−7).
• tol_fun : tolleranza di terminazione sul valore della funzione obiettivo da minimizzare (che è in entrambi i casi T , si veda (1.2.2), prede nito tol_fun = 0, ovvero vogliamo che termini solo su tol_x).
• tol_check : tolleranza di controllo sul valore della funzione obiettivo T al termine di ogni chiamata del metodo di risoluzione scelto (prede nito tol_x = 10−10).
• max_iter : iterazioni massime permesse al metodo di risoluzione scelto.
Questi quattro parametri coinvolgono ogni tentativo di eliminare nodi, cercando di volta in volta una soluzione con una tolleranza minima (per velocizzare l'esecuzione dell'algoritmo). Una volta giunti alla soluzione nale, l'algoritmo cerca di massimizzarne la precisione con un'ultima chiamata del metodo risolutivo scelto, tramite due ulteriori parametri:
• tol_x_final : tolleranza di terminazione nale su v (prede nito tol_x_final = 10−20).
• tol_fun_final : tolleranza di terminazione nale su T (v) (prede nito tol_fun_final = 0). mentre le iterazioni massime per quest'ultima chiamata vengono automaticamente tarate a 4×max_iter.
Capitolo 2
Ricerca generica
In questa sezione descriviamo il codice utilizzato nel caso generale di formula non simmetrica. L'es-posizione in parte ricalca quella di Xiao-Gimbutas [15], focalizzandosi maggiormente sul calcolo delle matrici Jacobiane ed Hessiane, come richiesto dalle routines Matlab lsqnonlin e fmincon.
2.1 Struttura
Uno pseudocodice di eliminazione per il calcolo di una formula di cubatura con ADE uguale a N, come proposto da Xiao e collaboratori, è il seguente:
Algorithm. Dato un insieme funzioni f1, . . . , fm, e una loro formula di cubatura x1, w1, . . . , xn, wn:
1. While n > 0 :
2. Riordina x1, . . . , xn e w1, . . . , wn in ordine crescente di importanza.
3. for i = 1 : n
4. Eliminazione del nodo (e peso) i-esimo e tentativo di calcolare una nuova formula con n − 1 nodi e uguale ADE.
5. Se riesce, la salva, aggiorna n ed esce dal ciclo for. 6. end for.
7. Se durante il ciclo for non si riesce a eliminare alcun nodo, esci dal ciclo while. 8. end while.
2.2 Ordinamento
Il primo punto da discutere riguarda il riordinamento dei nodi prima dell'eettiva ottimizzazione. A questo proposito manca una solida base teorica, ma sperimentalmente si è notato, con riferimento al lavoro di Xiao e Gimbutas [15], che un buon criterio è quello di de nire per ogni nodo un Signi cance Index de nito come:
14 CAPITOLO 2. RICERCA GENERICA sj = |wj| m X i=1 fi2(xj), j = 1, . . . , n
e quindi procedere tentando di eliminare i nodi in ordine crescente di sj. Si noti comunque come, se
eliminiamo dalla formula di cubatura il nodo j -esimo, il matching dei momenti avviene a meno di un vettore la cui norma al quadrato è ˆsj= |wj|sj. Infatti, ponendo:
V = f1(x1) · · · f1(xn) ... ... fm(x1) · · · fm(xn) (matrice di Vandermonde), w = w1 ... wn , V8k= f1(x1) · · · f1(xk−1) f1(xk+1) · · · f1(xn) ... ... ... ... fm(x1) · · · fm(xk−1) fm(xk+1) · · · fm(xn) , w8k= w1 ... wk−1 wk+1 ... wn , v(k)= f1(xk) ... fm(xk) ;
si ottiene che V ·w − V8k·w8k= wk·v(k), e come si vede, wk·v(k)
2 2 = P iw 2 kf 2 i(xk) = ˆsk. Tuttavia,
si riscontra numericamente che ˆsk non è un buon candidato come Signi cance Index, come invece
apparirebbe intuitivamente, e che invece prendere sj è una scelta molto più e cente (anche se questo
appare controintuitivo).
2.3 Calcolo della matrice Jacobiana
Come abbiamo visto nel pseudocodice, a partire da una certa distribuzione di nodi (e pesi) non esatta, per un certo ADE N, via algoritmi di ottimizzazione quali lsqnonlin e fmincon, è fondamentale per la performance la conoscenza delle matrici Jacobiane (ed Hessiane, nel caso di fmincon) delle rispettive funzioni da passare alle routines, cioè F e T . A tal proposito calcoliamo queste matrici a partire dalla conoscenza delle derivate parziali di fk, ove
f (xi) = f1(xi) ... fm(xi) , Jf (xi) = Jf1(xi) ... Jfm(xi) = ∂f1 ∂x1(xi) · · · ∂f1 ∂xd(xi) ... ... ∂fm ∂x1(xi) · · · ∂fm ∂xd(xi) .
2.3. CALCOLO DELLA MATRICE JACOBIANA 15 V = f1(x1) · · · f1(xn) ... ... fm(x1) · · · fm(xn) ,
vogliamo calcolare la matrice Jacobiana delle funzioni: F : R n(d+1) v −→ 7−→ Rm V ·w − m e T : R n(d+1) v −→ 7−→ R kF (v)k2
Consideriamo innanzitutto F. Scrivendone per esteso la componente k-esima, e tralasciando il momento k-esimo (che essendo costante non in uisce nel calcolo delle derivate), indicato con (xk)j la
j-esima componente del vettore xk:
v = (x1)1, . . . , (x1)d, w1, . . . , (xn)1, . . . , (xn)d, wn
T
7−→ w1fk(x1) + . . . + wnfk(xn) = Fk(v) ,
la cui matrice Jacobiana risulta:
JFk = w1∂f∂xk1(x1), . . . , w1∂x∂fkd(x1), fk(x1), . . . , wn∂x∂fk1(xn), . . . , wn∂x∂fkd(xn), fk(xn) = w1Jfk(x1), fk(x1), . . . , wnJfk(xn), fk(xn)
, (ove Jfkindica lo Jacobiano di fk).
Se ne deduce quindi che la matrice Jacobiana di F è:
JF = w1Jf1(x1) f1(x1) · · · wnJf1(xn) f1(xn) ... ... ... ... w1Jfm(x1) fm(x1) · · · wnJfm(xn) fm(xn) = w1Jf (x1), f (x1), · · · , wnJf (xn), f (xn) .
Ora che abbiamo calcolato JF, calcolare il gradiente di T è immediato, infatti dalla de nizione stessa si ricava:
16 CAPITOLO 2. RICERCA GENERICA
2.4 Calcolo dell'Hessiano
In questa sezione intendiamo calcolare l'Hessiano di T . Posto ∂i:=∂x∂i e ∂i,j:= ∂x∂j∂x∂i, si ottiene:
(HT (v))i,j = ∂i,j(T (v)) = ∂i,j( m X h=1 F2 h(v)) = m X h=1 ∂i,j(Fh2(v)) = 2 m X h=1 ∂j(Fh(v) ∂iFh(v)) = 2 m X h=1 [∂jFh(v) ∂iFh(v) + Fh(v) ∂i,jFh(v)].
Quindi l'Hessiano cercato può essere scritto come HT (v) = 2 m X h=1 [P(1)h (v) + Fh(v)P (2) h (v)] , con P(1) h (v)e P (2) h (v)matrici di dimensione n(d + 1) × n(d + 1). P (1)
h (v)è facilmente ottenibile dallo
Jacobiano di F, infatti chiamando JF[h]e JF
[h]la sua h-esima colonna e h-esima riga rispettivamente,
abbiamo che:
P(1)h (v) = JF[h](v)JF[h](v).
Il calcolo di P(2)
h (v)è invece più complesso. Partendo come in precedenza dalla scrittura per esteso di
Fh:
Fh= w1fh(x1) + . . . + wnfh(xn) ,
notiamo che P(2)
h (v) = ∂i,jFh(v) è matrice diagonale a blocchi, con n blocchi (d + 1) × (d + 1) che
chiamiamo Ch k(v)(k = 1, . . . , n): P(2)h (v) = Ch1(v) ... O Chk(v) O ... Chn(v) ,
Capitolo 3
Ricerca Simmetrica
Nel capitolo precedente, abbiamo calcolato jacobiani, gradienti ed hessiani di certe funzioni necessarie per il calcolo numerico di formule di cubatura del tutto generali. In questo capitolo ci proponiamo di fare altrettanto per il caso di formule simmetriche. Una tipica formula di cubatura simmetrica su Ω ∈ Rd, a partire dai nodi nx
1, . . . , xnsymo e i corrispettivi pesi w1, . . . , wnsym
, de nisce: Snsym(f ) = L X s=1 nsym X k=1 wkf (ϕs(xk)) + nsym X k=1 wkf (xk) (3.1)
in cui le funzioni ϕs dipendono dalla particolare simmetria utilizzata, cosicché ϕs(xk) ∈ Ω per ogni
k, s. Come visto, due tipiche simmerie sono quella rispetto al j-esimo asse cartesiano e quindi con riferimento ad 3.1, L = 1 e
ϕ1(x) =
x1, . . . , xj−1, −xj, xj+1, . . . , xd
oppure rispetto all'origine in cui L = 1 e ϕ1(x) = −x. In Omelyan, Salorijan viene usata invece su
Ω = [−1, 1] × [−1, 1]una formula simmetrica basata su rotazioni di π2. In questo caso, con riferimento ad 3.1, L = 3 e posto x = (x1, x2)abbiamo
ϕ1(x1, x2) = (−x2, x1), ϕ2(−x1, x2) = (x1, x2), ϕ3(x1, x2) = (x2, −x1).
Per semplicità mostriamo come calcolare la matrice Jacobiana nel caso di formule simmetriche rispetto all'origine. Di conseguenza la formula è del tipo
Snsym(f ) = nsym X k=1 wkf (xk) + nsym X k=1 wkf (−xk).
Osserviamo n da ora che il numero di nodi distinti n della formula veri ca n ≤ nsym con la
disug-uaglianza che può essere stretta in quanto un xk potrebbe essere l'origine. Come nel caso delle formule
di cubatura generali, la regola Snsym è esatta rispetto allo spazio vettoriale span
k=1,...,m({f
k}) ⊆ C (Ω) se
20 CAPITOLO 3. RICERCA SIMMETRICA per ogni funzione fk si ha
Snsym(fk) =
ˆ
Ω
fk(x) dx, k = 1, . . . , m
e quindi se si annulla la funzione F = (F1, . . . , Fm)la cui k-esima componente è
Fk(v) = Snsym(fk) − ˆ Ω fk(x) dx = nsym X j=1 wjfk(xj) + nsym X j=1 wjfk(−xj) − ˆ Ω fk(x) dx ove v = (xT 1, w1, . . . , xTnsym, wnsym) ∈ R
d·nsym+nsym. A tale scopo, lsqnonlin richiede, qualora possibile,
la matrice jacobiana JF relativa a F, cioè
(JF )i,j=
∂Fi
∂vj
.
Se la j-esima componente di v indica un peso, diciamo ws, allora
∂Fi
∂vj
(v) = ∂Fi ∂ws
(v) = fi(xs) + fi(−xs),
mentre se corrisponde alla k-sima componente di un nodo, cioè vj = (xs)k, abbiamo
∂Fi ∂vj (v) = ∂Fi ∂(xs)k (v) = ws ∂fi ∂xk (xs) − ws ∂fi ∂xk (−xs) = ws ∂fi ∂xk (xs) − ∂fi ∂xk (−xs) .
La matrice jacobiana JF ha dimensione m × (d + 1)nsyme può essere scritta in forma compatta che la
rende più facilmente valutabile in Matlab. Una volta ottenuta la matrice jacobiana di F, il gradiente della funzione T si ottiene, come nel capitolo precedente, direttamente tramite
∇T (v) = 2(JF (v))TF (v).
3.1 Struttura
Data una formula di cubatura di n nodi totali, simmetrica rispetto all'iperpiano x1 = 0 o rispetto
l'origine. Sia 2nsymil numero di nodi che hanno una controparte simmetrica (distinta), e nc= n−2nsym
il numero dei nodi rimanenti (cioè che coincidono col rispettivo simmetrico). Per quanto visto in (1.2.3), essa è completamente de nita da nvar= nsym+ nc variabili.
Nel caso di ricerche simmetriche, l'algoritmo richiede (per funzionare correttamente) una formula di cubatura di partenza che soddis già il vincolo di simmetria scelto. Inoltre, tale regola deve essere opportunamente ordinata, in modo che i primi nsymnodi siano quelli con una controparte simmetrica
distinta, e i successivi ncnodi siano quelli coincidenti col proprio simmetrico. Invece, non ha importanza
se la regola è ordinata in modo che, per ogni i ≤ nsym, il simmetrico di xi sia proprio xn+1−i. Infatti,
gli ultimi nsymnodi della regola vengono tralasciati durante l'esecuzione dell'algoritmo, e sono ottenuti
semplicemente simmetrizzando i primi nsymnodi.
3.1. STRUTTURA 21 rispetto l'iperpiano x1 = 0esso controlla che, una volta calcolati n, nsym ed nvar, valga la relazione
n = nsym+ nvar. Invece, nel caso di simmetria rispetto l'origine, una volta posti nsym = bnc ed
nvar = dne, esso controlla che, qualora nsym 6= nvar, l'nvar-esimo nodo sia proprio l'origine (a meno
di una tolleranza impostata). E' su ciente che queste proprietà siano veri cate perché l'algoritmo proceda senza fermarsi a causa di errori. Tuttavia, è chiaro che se queste condizioni sono veri cate, ma la regola di partenza non rispetta il vincolo di simmetria scelto, è di cile che l'algoritmo riesca a funzionare e caciemente e soprattutto velocemente. Infatti, dato che in questo caso la vera regola di partenza adottata dall'algoritmo sarà ottenuta simmetrizzando i primi nsym nodi, essa non sarà più
in generale esatta. Comunque, anche in questo caso è possibile (e accade non di rado) che l'algoritmo riesca a togliere dei nodi, e se riesce a toglierne almeno uno, il problema dell'inesatta regola di partenza è risolto, e l'algoritmo procederà con la consueta celerità nelle iterazioni successive. Infatti, è evidente che se ciò accade, l'algoritmo è riuscito a trovare una regola che soddis il vincolo di simmetria scelto a partire da una che non lo soddisfa, e quindi essendo tale la regola di partenza del problema ristretto alle iterazioni successive alla prima, l'algoritmo potrà procedere con la consueta e cienza e celerità. Ed è esattamente per questo motivo che si è scelto di non far controllare all'algoritmo se la regola di partenza soddis o no il vincolo di simmetria scelto, ma solo le proprietà strettamente necessarie a nché esso non si blocchi in seguito ad errori.
3.1.1 Simmetria rispetto all'iperpiano x
1= 0
Algorithm 3.1.1. (eliminazione con simmetria rispetto x1= 0) Dato un insieme funzioni f1, . . . , fm,
e una loro formula di cubatura x1, . . . , xnsym, . . . , xnvar, . . . , xn, w1, . . . , wnsym, . . . , wnvar, . . . , wn
(op-portunamente ordinata) simmetrica rispetto all'iperpiano x1= 0:
1. While n > 0 :
2. Pone ord l'ordinamento di x1, . . . , xnvar e w1, . . . , wnvar in ordine crescente di Signi cance
Index sj.
3. for i = 1 a nvar:
4. Se ord(i) ≤ nsym, toglie i nodi (e pesi) i-esimo e (n + 1 − i)-esimo e tenta di trovare
una nuova regola.
5. Altrimenti, toglie il nodo (e peso) i-esimo e tenta di trovare una nuova regola. 6. Se trova una nuova regola, la salva, aggiorna nsym, nvar e n ed esce dal ciclo for.
7. end for.
8. Se durante il ciclo for non è riuscito a eliminare alcun nodo:
9. Crea una regola temporanea Rtemp aggiungendo come nodo (non simmetrico),
l'origine con peso nullo, e aggiorna in tal modo n = n + 1, nvar = nvar+ 1.
10. Pone ord l'ordinamento di Rtemp in ordine crescente di Signi cance Index sj.
11. for i = 1 a nvar:
22 CAPITOLO 3. RICERCA SIMMETRICA trovare una nuova regola.
13. Se la trova, la salva, aggiorna nsym, nvar e n ed esce dal ciclo for.
14. end for. 15. end if.
16. Se durante il ciclo for non è riuscito ad eliminare alcun nodo, mantiene la regola precedente alla creazione di Rtemp, riaggiornando n = n − 1, nvar= nvar− 1, ed esce dal ciclo while.
17. end while.
3.1.2 Simmetria rispetto all'origine
Questo caso si dierenza dal precedente per un dettaglio importante. Mentre infatti prima la quantità nvar− nsympoteva essere, a priori, arbitrariamente non negativa, qui può essere solo uguale a 1 o a 0,
perché l'unico punto che coincide col proprio simmetrico rispetto all'origine è l'origine stesso. Quindi, in questa situazione, o nvar = nsym+ 1(cioè la regola contiene l'origine), oppure nvar = nsym(cioè non
lo contiene). Perciò, in questo caso, è necessario modi care opportunamente l'algoritmo. Inoltre, se l'origine è presente, è preferibile tentare di togliere prima gli altri nodi, sia per velocizzare l'esecuzione e sia per evitare che l'algoritmo continui eventualmente a togliere e poi aggiungere lo stesso nodo (l'origine) in diverse occasioni (con riferimento al secondo ciclo for dell'algoritmo 3.1.1).
Algorithm 3.1.2. (eliminazione con simmetria rispetto all'origine) Dato un insieme funzioni f1, . . . , fm,
e una loro formula di cubatura x1, . . . , xnsym, . . . , xnvar, . . . , xn, w1, . . . , wnsym, . . . , wnvar, . . . , wn
(op-portunamente ordinata) simmetrica rispetto all'origine: 1. While n > 0 :
2. Pone ord l'ordinamento di x1, . . . , xnvar e w1, . . . , wnvar in ordine crescente di Signi cance
Index sj.
3. for i = 1 a nvar:
4. Se ord(i) ≤ nsym, toglie i nodi (e pesi) i-esimo e (n + 1 − i)-esimo e tenta di trovare
una nuova regola.
5. Se la trova, la salva, aggiorna nsym, nvar e n ed esce dal ciclo for.
6. end for.
7. Se durante il ciclo for non è riuscito a eliminare alcun nodo:
8. Se nvar6= nsymtoglie l'nvar-esimo nodo (e peso), che sarà l'origine, e tenta di
trovare una nuova regola. Se la trova, la salva e aggiorna nsym, nvar e n, altrimenti,
esce dal ciclo while.
9. Altrimenti (se nvar = nsym):
10. Crea una regola temporanea Rtempaggiungendo come nodo (non simmetrico)
3.2. ORDINAMENTO 23 11. Pone ord l'ordinamento di Rtemp in ordine crescente di Signi cance Index sj.
12. for i = 1 a nvar:
13. Se ord(i) ≤ nsym, toglie i nodi (e pesi) i-esimo e (n + 1 − i)-esimo e tenta di
trovare una nuova regola.
14. Se la trova, la salva, aggiorna nsym, nvar e n ed esce dal ciclo for.
15. end for.
16. Se durante il ciclo for non è riuscito ad eliminare alcun nodo, mantiene la regola precedente alla creazione di Rtemp, riaggiornando n = n − 1, nvar= nvar− 1, ed
esce dal ciclo while. 17. end if.
18. end if. 19. end while.
3.2 Ordinamento
Nel caso di vincoli di simmetria l'ordinamento procede secondo lo stesso principio del caso generale, con l'unica dierenza che per i nodi con una controparte simmetrica distinta il Signi cance Index verrà calcolato come la somma degli Index dei due nodi, appunto perché contano come un'unica variabile: togliere un nodo che abbia una controparte simmetrica distinta equivale a togliere due nodi dalla quadratura. Ovviamente, in questo caso i Signi cance Index saranno nvar in totale (uno per ogni
variabile) e non più n.
3.3 Calcolo dello Jacobiano
Per semplicità, si consideri il caso di simmetria rispetto all'origine (come si vedrà l'altro caso è del tutto analogo). Anche in questo caso è necessario capire come calcolare lo Jacobiano (o il gradiente) di F e T a partire dalla sola conoscenza dello Jacobiano di f. Ora le variabili di F non sono più n(d + 1) ma nvar(d + 1), e ricordando che l'algoritmo ottiene la regola completa simmetrizzando i primi nsymnodi,
la sua k-esima componente è:
v = xT1, w1, . . . , xTnvar, wnvar
T
7−→ w1fk(x1) + . . . + wnsymfk(xnsym) +
+ wnsym+1fk(xnsym+1) + . . . + wnvarfk(xnvar) +
24 CAPITOLO 3. RICERCA SIMMETRICA b xi= −x1 i ... −xd i .
Il suo Jacobiano è quindi:
JFk= w1 ∂f k ∂x1(x1) − ∂fk ∂x1(xb1) , . . . , w1 ∂f k ∂xd(x1) − ∂fk ∂xd(bx1) , fk(x1) + fk(bx1), . . . wnsym ∂f k ∂x1(xnsym) − ∂fk ∂x1(bxnsym) , . . . , wnsym ∂f k ∂x1(xnsym) − ∂fk ∂x1(bxnsym) ,fk(xnsym)+fk(xbnsym), . . . ∂fk ∂x1(xnsym+1), . . . , ∂fk ∂xd(xnsym+1), fk(xnsym+1), . . . , ∂fk ∂x1(xnvar), . . . , ∂fk ∂xd(xnvar), fk(xnvar) ! .
Per scrivere il Jacobiano di F in maniera più compatta, si considerino la matrice S(or) ∈ M m×d e
le matrici J(h)
∈ Mm×(d+1), h = 1, . . . , nvar, de nite come segue (.∗ denota il prodotto puntuale tra
matrici): S(or)= −1 · · · −1 ... ... ... −1 · · · −1 , J(h)= J f (xh) + S(or). ∗ J f ( b xh) , f (xh) + f (xbh) , se 1 ≤ h ≤ nsym J f (xh) , f (xh) , se nsym< h ≤ nvar.
In questo modo, si può scrivere semplicemente:
JF = J(1), . . . , J(nvar)
Una volta ottenuto JF, il calcolo del gradiente di T è identico al caso generale:
∇T (v) = 2(JF (v))TF (v).
Nel caso di simmetria rispetto all'iperpiano x1= 0, i conti sono del tutto analoghi, ma questa volta
b xi sarà de nito come:
3.4. CALCOLO DELL'HESSIANO 25 il che si ri ette nel calcolo nale di JF semplicemente nella modi ca della matrice S(or), che diventa:
S(axe)= −1 1 · · · 1 ... ... ... ... −1 1 · · · 1 .
3.4 Calcolo dell'Hessiano
Nel caso di vincoli di simmetria la formula HT (v) = 2 m X h=1 [P(1)h (v) + Fh(v)P (2) h (v)]
per il calcolo dell'Hessiano di T continua a valere, anche se ora HT (v), P(1) h (v)e P
(2)
h (v)sono matrici
di dimensione nvar(d + 1) × nvar(d + 1)invece che n(d + 1) × n(d + 1). Anche il calcolo di P (1) h (v)è
identico (chiamando JF[h] e JF
[h] h-esima colonna e h-esima riga di JF rispettivamente):
P(1)h (v) = JF[h](v)JF[h](v),
e P(2)
h (v) = ∂i,jFh(v)è ancora una matrice diagonale a blocchi:
P(2)h (v) = Ch1(v) ... O Chk(v) O ... Chnvar(v) .
Tuttavia ora il calcolo dei Ch
k(v)è più complesso. Posta la seguente de nizione, nel caso di vincolo di
simmetria rispetto all'origine:
T(or)= 1 · · · 1 ... ... ... 1 · · · 1 (è una matrice d × d), e chiamando S(or)
[h] l'h-esima riga della matrice S
(or)de nita in precedenza, si ottiene che:
26 CAPITOLO 3. RICERCA SIMMETRICA se 1 ≤ k ≤ nsym, e: Chk(v) = C h k(xk, wk) = wkHfh(xk) (Jfh(xk)) T Jfh(xk) 0 , se nsym< k ≤ nvar.
Come per il calcolo dello Jacobiano, nel caso di simmetria rispetto all'iperpiano x1= 0, anche ora
le uniche modi che riguardano le matrici S(or) e T(or). La prima cambia esattamente come descritto
nella sezione precedente, mentre la seconda diventa:
Capitolo 4
Risultati
Il proposito di questa sezione è di discutere i risultati ottenuti con gli algoritmi introdotti nelle sezioni precedenti. In particolare discuteremo come calcolare
I(f ) = ˆ
Ω
f (x) dx
tramite formule di cubatura aventi grado di precisione N Sn(f ) =
n
X
k=1
wkf (xk)
con n particolarmente piccolo, possibilmente minimo. Tratteremo in particolare i casi in cui Ω cor-risponde all'intervallo [−1, 1] e al quadrato [−1, 1] × [−1, 1]. Nel primo dominio ritroveremo le classiche formule gaussiane, mentre nel secondo nuove formule no ad N = 55. I risultati ottenuti saranno usualmente uguali o migliori di quelli noti in letteratura.
4.1 Il caso univariato
In questo caso la base polinomiale univariata scelta è, come anticipato, la base ortogonale di Legendre. In particolare la valutazione della matrice di Vandermonde in questa base è stata ottenuta vettorial-mente a partire dalla relazione a tre termini. Per quanto riguarda la formula di partenza da fornire all'algoritmo introdotto nelle sezioni precedenti, ci sono evidentemente varie scelte. Una prima formula potrebbe essere di tipo Newton-Cotes (basata su nodi equispaziati). Per un ssato grado di precisione N, esiste una tale regola costituita da N + 1 nodi. Quindi, de niti
xk= −1 +
2
N(k − 1) k = 1, . . . , N + 1
e chiamati come al solito V la relativa matrice di Vandermonde, ovvero (V )ij = pi(xj), con {pi(x)}i,
i = 1, . . . , N + 1che denota la base ortogonale di Legendre, ed m il vettore dei momenti (che come mostrato in (1.3) è m1= 2e mk = 0per k = 2, . . . , N + 1), il vettore dei pesi w può essere calcolato
semplicemente risolvendo il sistema lineare
28 CAPITOLO 4. RISULTATI
V ·w = m.
Tuttavia, questa non sembra essere una buona scelta in quanto è noto che al crescere del grado alcuni pesi sono negativi mentre le formule gaussiane con peso di Legendre w ≡ 1 li hanno tutti positivi. Una prima alternativa è quella di scegliere una formula di Feyer che ha per nodi gli zeri dei polinomi di Chebyshev di prima e seconda specie e pesi positivi. Entrambi sono facilmente calcolabili (Waldvogel). Se altrimenti si desidera usare nodi equispaziati, de niamo
b V = V IN +1 ! , m =b m 1 ... 1 ,
dove IN +1 denota la matrice identità di ordine N + 1, e risolviamo il sistema lineare
b
V ·w =mb
cercando il vettore w che ne minimizzi lo scarto. In questo modo, si forzano i pesi ad essere positivi, a discapito della precisione della formula trovata (solitamente si trova kV ·w − mk∞≈ 10−1,
indipen-dentemente dalla grandezza di N). A questo punto, per aumentare la precisione no alla quantità voluta (ad esempio 10−15), lancieremo l'algoritmo con l'opzione limit (con riferimento a (1.4))
imposta-ta ad ∞, in modo da aumenimposta-tare la precisione della formula immessa. L'algoritmo avrà quindi successo proprio in virtù del fatto che i pesi ora sono positivi. Nella tesi abbiamo utilizzato quest'ultima scelta. Testando in questo modo l'algoritmo di eliminazione per N = 1, . . . , 100, risulta che esso riesce sempre a ridursi al numero minimo teorico di nodi (cioè N +1
2
), ed inoltre, se si impone il vincolo di simmetria (rispetto al piano x1 = 0 o all'origine nel caso univariato è la stessa cosa), i risultati
coincidono esattamente con le regole gaussiane calcolate con le routines proposte da W. Gautschi e D. Laurie.
Ad esempio si confrontino i nodi e pesi ottenuti dall'algoritmo per N = 100 (prima e terza colonna) con le regole gaussiane calcolate con l'algoritmo di Gautschi e Laurie (seconda e quarta colonna). Nell'esecuzione dell'algoritmo sono stati impostati il vincolo di simmetria rispetto all'asse x = 0 (che in questo particolare caso è equivalente alla simmetria rispetto all'origine), il vinco-lo di positività dei pesi e l'utilizzo della routine lsqnonlin. Le tolleranze sono state così impostate: tol_x, tol_fun, tol_check = 10−5, tol_x_final, tol_fun_final = 10−25, e max_iter = 100. La regola di partenza, calcolata come spiegato in precedenza, era costituita da 101 nodi e pesi, e la sua precisione (secondo la norma in nito k·k∞) risultava di 1.33 · 10−15. L'algoritmo ha eliminato con
successo 50 nodi no a raggiungere il numero mininale di 51 = 101 2
nodi e pesi, con precisione nale di 3.82 · 10−16, il tutto in un tempo di esecuzione totale di 59.53 secondi. La regola gaussiana ottenuta
con l'algoritmo di Gautschi-Laurie ha una precisione di 2.71 · 10−15. Denotati con x
e, we e xg, wg i
4.1. IL CASO UNIVARIATO 29
xe xg we wg
30 CAPITOLO 4. RISULTATI
4.2 Il quadrato
Riportiamo innanzitutto alcuni dei risultati noti nora in letteratura. Da Möller in [6] si sa che, se una formula ha grado d e nd nodi e pesi, allora vale nd> ¯nd, ove:
¯ nd= (d+2)(d+4) 8 se d è pari, (d+1)(d+3) 8 + j(d+1) 4 k se d è dispari.
Utilizzando varie idee, nora sono state trovate formule con nd= ¯nd, e quindi minimali, solo per bassi
valori del grado d. Comunque, in [9] esperimenti numerici mostrano che tali limiti inferiori di Möller molto probabilmente non potranno mai essere veri cati per d = 17, 25, 33, 41.
Nei lavori di H. Xiao e collaboratori [7, 15, 16], che hanno introdotto per primi algoritmi di elim-inazione, sono state trovate formule di cubatura per il quadrato [−1, 1]2
con pochi nodi no a grado d = 24. In [8], I.P. Omelyan e V.B. Solovyan hanno trovato formule di grado d = 15, 17, 19, 21, 23 con la più bassa cardinalità conosciuta. Tuttavia l'algortimo era dispendioso in termini di tempo, richiedendo per gradi più elevati diversi giorni di calcolo. Usando una tecnica molto diversa, attraverso l'algoritmo di arricchimento da loro introdotto, M. Taylor, B. Wingate e L. Bos hanno trovato nuove formule sul quadrato per gradi d = 10 e d = 12 [13, 14].
In questa sezione mostreremo i risultati ottenuti dall'algoritmo di eliminazione qui presentato, migliorando molti di questi risultati e ottenendo nuove formule di cubatura sul quadrato con un basso numero di nodi, no al grado d = 55. Come descritto nei capitoli precedenti, si è scelto di partire da formule di partenza di tipo tensoriale, da cui segue che per un ssato grado d il numero di nodi di partenza è d+1
2
2
. Inoltre, per motivi di condizionamento, si è scelto di utilizzare come base polino-miale la base ortogonale bivariata costruita a partire dalla base univariata di Legendre, come descritto più dettagliatamente in (1.3). Riportiamo anche le opzioni che sono state impostate nell'algoritmo per ottenere i vari risultati, sotto la dicitura [s, r, p], ove:
s =
0 se nessun vincolo di simmetria è utilizzato
1 se viene usato il vincolo di simmetria rispetto al piano x1= 0
2 se viene usato il vincolo di simmetria rispetto all'origine
r =
1 se la routine utilizzata è lsqnonlin 2 se la routine utilizzata è fmincon
p =
0 se non viene utilizzato il vincolo di positività dei pesi 1 se viene utilizzato il vincolo di positività dei pesi
Si noterà in particolare che la routine utilizzata sarà sempre lsqnonlin, e questo perché anche se entrambe conducono agli stessi risultati, nei nostri esperimenti abbiamo rilevato che usando lsqnonlin l'algoritmo risulta più veloce, anche se non sempre di molto. Questo è dovuto al fatto che, benché il passaggio dell'Hessiana alla routine fmincon ne velocizza l'esecuzione, il calcolo dell'Hessiano può essere in se stesso molto dispendioso.
4.2. IL QUADRATO 31 cosa, si è partito dalla relativa formula tensoriale T e si è utilizzato l'algoritmo con le opzioni [1, 1, 1], no a raggiungere la formula Q, e in seguito partendo dalla formula Q e utlizzando l'algoritmo con le opzioni [0, 1, 1], è stata raggiunta la formula nale indicata nella tabella. In altre parole, questo signi ca che in questo caso prima si è cercata una formula simmetrica rispetto al piano x1 = 0 (solitamente
per risparmiare tempo, date le minori variabili in gioco) e poi la si è ra nata cercando, a partire dal risultato, una formula generica.
Per gradi medio-bassi e dispari, è stato notato che molto spesso la ricerca generica dava luogo a formule simmetriche rispetto all'origine. Per questo motivo il vincolo di simmetria rispetto all'origine è stato usato sempre più spesso per i gradi dispari. Inoltre, al ne di abbreviare notevolmente il tempo di calcolo di tutte le formule di cubatura per gradi alti (d > 25), si è utilizzata la seguente tecnica. Per prima cosa è stata calcolata (partendo come al solito da una formula di tipo tensoriale) la formula di cubatura per il grado 55. Poi, dato che la formula nale così ottenuta sarebbe stata ovviamente esatta anche per il grado 53, la si è usata come regola di partenza per calcolare il caso d = 53. Successivamente la formula così ottenuta è stata usata per calcolare il caso d = 51 e così via per tutti i gradi dispari, il tutto mantenendo il vincolo di simmetria rispetto all'origine. In un secondo momento, per d pari, si è usata come regola di partenza la formula trovata precedentemente per il grado dispari d + 1, ma questa volta imponendo semplicemente la ricerca generica senza nessun vincolo di simmetria. Per questo per d > 25tutti i gradi pari presentano la dicitura [2, 1, 1] , [0, 1, 1].
Le impostazioni di tolleranza utilizzate sono: tol_fun, tol_fun_final = 0, tol_x = 10−7, tol_check =
10−10, tol_x_final = 10−25, e max_iter = 100. L'algoritmo è stato fatto girare su un computer da 2.5 Gb di RAM e processore Intel Core 2 Duo da 2 GHz, e di seguito riassumiamo indicativamente i tempi di calcolo al variare del grado d, considerando il tempo totale impiegato dall'algoritmo per raggiungere la formula di cubatura nale partendo ogni volta da una formula di tipo tensoriale:
ADE tempo 2 − 10 1 − 30sec 11 − 20 1 − 5min 21 − 30 10 − 45min 31 − 40 1 − 5ore 41 − 55 5 − 40ore
Per grado di precisione medio-bassi (2 ≤ N ≤ 24), la cardinalità delle formule ottenute coincide col valore atteso l m
d+1
m
= l(N +1)(N +2)6 m per N = 2 − 7, 10, 12, 14, 16, 18, 24, essendo più basso per N = 9, 11, 13, 15, 17, 19, 21, 23 e restando più alto di un nodo per N = 8, 20, 22. Le formule ottenute dall'algoritmo hanno inoltre la stessa cardinalità di quelle già presenti in letteratura, con l'eccezione dei gradi 15, 16, 17, 19, 21, 23, per cui sono state trovate formule migliori:
32 CAPITOLO 4. RISULTATI
Figura 4.1: Formula di ADE 15 composta da 43 nodi simmetrici rispetto all'origine.
• Per grado N = 16 è stata trovata una nuova formula di 51 nodi, 1 in meno rispetto alla formula migliore conosciuta, dovuta a Xiao e Gimbutas, raggiungendo in questo modo il valore atteso di 51 nodi.
Figura 4.2: Formula di ADE 16 composta da 51 nodi.
4.2. IL QUADRATO 33
Figura 4.3: Formula di ADE 17 composta da 54 nodi simmetrici rispetto all'origine.
• Per grado N = 19 è stata trovata una nuova formula di 67 nodi, 4 in meno rispetto alla formula migliore conosciuta, dovuta a Xiao e Gimbutas, e 3 in meno rispetto al valore atteso di 70 nodi.
Figura 4.4: Formula di ADE 19 composta da 67 nodi simmetrici rispetto all'origine.
34 CAPITOLO 4. RISULTATI
Figura 4.5: Formula di ADE 21 composta da 81 nodi simmetrici rispetto all'origine.
• Per grado N = 23 è stata trovata una nuova formula di 96 nodi, 5 in meno rispetto alla formula migliore conosciuta, dovuta a Xiao e Gimbutas, e 4 in meno rispetto al valore atteso di 100 nodi.
Figura 4.6: Formula di ADE 23 composta da 96 nodi simmetrici rispetto all'origine.
Per gradi di precisione alti (25 ≤ N ≤ 37), i risultati sono sempre prossimi al valore atteso, superandolo di meno di 3 nodi nel caso di grado pari, e restando sempre al di sotto di tale soglia (di 2-4 nodi) nel caso dei gradi dispari. Per gradi ancora più alti (38 ≤ N ≤ 55), la cardinalità delle formule trovate resta sempre prossima al valore atteso per gradi dispari (superandolo di non più di 4 nodi), mentre per gradi pari essa diverge maggiormente ( no a 10-15 nodi in più).
4.2. IL QUADRATO 35
Figura 4.7: Formula di ADE 36 composta da 238 nodi.
Figura 4.8: Formula di ADE 55 composta da 536 nodi simmetrici rispetto all'origine.
Legenda
ADE: Grado algebrico di precisione
MRLB: Limiti inferiori di Moeller-Rasputin. THEO: Cardinalità attesa, ovverol m
(d+1)m, con m =
(ADE+1)(ADE+2)
2 e d = 2.
NE#: Cardinalità della formula trovata con l'algoritmo di eliminazione qui presentato. XG#: Cardinalità dei punti di Xiao-Gimbutas.
CL#: Cardinalità dei punti di R. Cools.
WGT: +: tutti i pesi sono positivi; -: alcuni pesi sono negativi.
36 CAPITOLO 4. RISULTATI ADE MRLB THEO NE# XG# CL# WGT OPZIONI SIMMETRIA
Bibliogra a
[1] L. Bos, S. De Marchi, A. Sommariva and M. Vianello, Computing multivariate Fekete and Leja points by numerical linear algebra, SIAM J. Numer. Anal. 48 (2010), pp. 19841999.
[2] R. Cools, Constructing cubature formulae: the science behind the art, Acta Numerica (1997), pp. 154.
[3] R. Cools, Monomial cubature rules since Stroud, a compilation - part 2, J. Comp. and Appl. Math. 112 (1999), pp. 2127.
[4] R. Cools and H. Schmid, On the (non)-existence of some cubature formulas: gaps between a theory and its applications, Journal of Complexity 19 (2003), pp. 403405.
[5] M. Gentile, A. Sommariva and M. Vianello, Polynomial interpolation and cubature over polygons, J. Comp. and Appl. Math. 235 (2011), pp. 52325239.
[6] H.M. Möller, Polynomideale und Kubaturformeln, Dissertation, Universit at o Dortmund, 1973. [7] S.E. Mousavi, H. Xiao and N. Sukumar, Generalized Gaussian quadrature rules on arbitrary
polygons, Internat. J. Numer. Methods in Engrg. 82 (2010), pp. 99113.
[8] I.P. Omelyan and V.B. Solovyan, Improved cubature formulae of high degrees of exactness for the square, J. Comp. and Appl. Math. 188 (2006), pp. 90204.
[9] H. Schmid, On lower bounds for the number of nodes in cubature formulae for centrally-symmetric product integrals, CF99, Proceedings of the Conference, Krasnoyarsk, 2000, pp. 274284.
[10] A. Sommariva, Software homepage, (http://www.math.unipd.it/marcov/software.html).
[11] A. Sommariva, M. Vianello and R. Zanovello, Nontensorial Clenshaw-Curtis cubature, Numer. Algorithms 49 (2008), pp. 409427.
[12] J. Stoer and R. Bulirsch, Introduction To Numerical Analysis, 2nd ed., Springer- Verlag, 1992. [13] M.A. Taylor, B. Wingate and L. Bos, A cardinal function algorithm for computing multivariate
quadrature points, SIAM J. Numer. Anal. 45 (1) (2007), pp. 193205.
[14] M.A. Taylor, Asymmetric cubature formulas for polynomial integration in the triangle and square, J. Comp. and Appl. Math. 218 (2008), pp. 184191.
38 BIBLIOGRAFIA [15] H. Xiao and Z. Gimbutas, A numerical algorithm for the construction of e cient quadrature rules
in two and higher dimensions, Comput. Math. Appl. 59 (2010), pp. 663676.
