Calcolo di punti quasi ottimali per
l’interpolazione polinomiale sul triangolo
Indice
1 Introduzione 3 2 Richiami 3 3 Triangolo 6 3.1 Punti di Fekete . . . 6 3.1.1 Algoritmo di ricerca . . . 6 3.1.2 Primo metodo . . . 7 3.1.3 Secondo metodo . . . 8 3.2 Punti di Lebesgue . . . 11 3.2.1 Algoritmo di ricerca . . . 11 3.2.2 Primo Metodo . . . 13 3.2.3 Secondo Metodo . . . 14 4 Esperimenti Numerici 17 5 Codice 19 5.1 Demo . . . 195.2 Funzioni richiamate dalle demo . . . 24
6 Coordinate BSV 35 6.1 Punti di Fekete . . . 35
1
Introduzione
La ricerca di punti di ottimo per l’interpolazione polinomiale rimane una ques-tione aperta in ambito matematico. Mentre per il caso unidimensionale vi sono importanti risultati teorici, meno si sa riguardo al caso multidimensionale. Il problema consiste nel ricercare le disposizioni di punti che permettano l’in-terpolazione polinomiale col minor errore possibile. In letteratura, riguardo a queste configurazioni, si trovano diversi risultati numerici, in particolare rispetto a specifici domini nel caso bivariato. Nelle pagine seguenti illustr-eremo come sia stato possibile migliorare i risultati finora raggiunti riguardo ai punti nel triangolo. Nello specifico mostreremo come sia stato possibile trovare dei buoni punti approssimati di Fekete e come siano stati usati per la successiva stima dei punti di ottima interpolazione.
2
Richiami
La costante di Lebesgue ha un ruolo fondamentale nell’interpolazione polino-miale in quanto indica al variare dei punti da interpolare la stabilit`a di tale pro-cesso e la qualit`a dell’errore rispetto a quello della migliore approssimazione. Richiamiamo ora la definizione di tale costante nel caso multivariato.
Indichiamo conPn lo spazio dei polinomi di grado totale1 ne con Ω un dominio compatto di Rd. Si dimostra che N≡ dim(Pn) = n+d
n .
Sia {zk} un insieme unisolvente su Ω per l’interpolazione polinomiale di grado N cio`e tale che la cardinalit`a di {zk} sia uguale alla dimensione diPn e inoltre se pΩ{zk}= 0 necessariamente p≡ 0.
Fissiamo nel dominio Ω una base {pi, i = 1, . . . , N}diPn e denotiamo con V = V(z1, z2, . . . , zN) la matrice le cui componenti sono
Vij = {pj(zi) : i, j = 1, . . . , N} Tale matrice quadrata `e nota come matrice di Vandermonde.
Definiamo ora i polinomi di Lagrange
Lk(z) = det(V(z1, . . . , zk−1, z, zk+1, . . . , zN))
det(V(z1, . . . , zN)) k = 1, . . . , N
`E facile osservare che Lk(zs) = δks e che quindi per l’unicit`a del polinomio interpolatore corrispondano nel caso unidimensionale a
Lk(z) = n Y i=0,i6=k z − zi zk− zi = z − z0 zk− z0· · · z − zk−1 zk− zk−1 z − zk+1 zk− zk+1 · · · z − zm zk− zn Esiste per l’unisolvenza di {zk} un’unico polinomio p∈ Pntale che p(zk) = fk. Si dice che il polinomio pinterpolale coppie (zk, fk). Dalle propriet`a dei polinomi di Lagrange abbiamo
Supponiamo ora di non possedere gli esatti valori fk, ma un loro arrotonda-mento ˜fkdovuto ad esempio ad una approssimazione del loro valore. Otteni-amo il polinomio interpolatore
˜p(z) = n X k=0
˜fkLk(z) Possiamo ora studiare la differenza fra i due polinomi:
p(z) −˜p(z) = n X k=0 (fk− ˜fk)Lk(z) |p(z) − ˜p(z)|≤ n X k=0 fk− ˜fk |Lk(z)| infine, ponendo Λn= max z∈Ω n X k=0 |Lk(z)| otteniamo kp(z) − ˜p(z)k∞≤ max k fk− ˜fk · Λn
Il valore Λn `e noto comecostante di Lebesguedell’ insieme di punti {zi}. Dalla definizione data si nota subito come la costante di Lebesgue sia in funzione dei punti {zi}, del dominio Ω e dello spazioPn.
Sottolineiamo l’importanza di tale costante nel seguente modo. Conside-riamo il polinomio di miglior approssimazione p∗ ∈ Pn, ossia il polinomio che meglio approssima f in norma infinito. Considerando che p = INf (poli-nomio interpolatore di f) abbiamo che in generale p∗ 6= INf, ma sicuramente p∗= INp∗. Otteniamo allora
||f − INf||∞ = ||f − p∗+ INp∗− INf||∞ ≤ ||f − p∗||∞+ ||IN||∞||p∗− f||∞ ≤ (1 + ||IN||∞)||f − p∗||∞ = (1 + Λn)||f − p∗||∞
Fissati Ω ePn, i punti che minimizzano tale la costante sono detti ipunti di Lebesgue. Osserviamo che questi punti non sono noti nemmeno nel ca-so univariato. In [3] si asserisce che nel caca-so dell’intervallo limitato [a, b] gli “expanded-Chebyschev”
(a + b − (a − b)cos ((2j − 1)π/(2n)) cos (π/(2n)) )/2 sono quasi ottimi.
Un’approccio allo studio dei punti di Lebesgue sono i punti di Fekete. Osserviamo che indipendentemente dalla dimensione essi vengono defini-ti come i pundefini-ti che massimizzano il valore assoluto del determinante della matrice di Vanderdermonde V
max {zi}
Importante `e notare che i punti di Fekete sono indipendenti dalla scelta del-la nostra base, infatti un cambio di base non farebbe altro che moltiplicare il determinante per una costante indipendente dai punti.
Poich´e i punti massimizzano |det(V)| necessariamente |Lk(z)| = |det(V(z1, . . . , zk−1, z, zk+1, . . . , zN))| |det(V(z1, . . . , zN))| ≤ 1 e quindi Λn= max z∈Ω N X 1 |Lk(z)|≤ N =n + d n
Per quanto riguarda il caso unidimensionale esistono dei risultati noti riguar-do questi punti che coinciriguar-dono con i Gauss-Legendre-Lobatto [5],analiticamente poco si sa riguardo ai casi in dimensione maggiore, cio`e in cui Ω sia un compat-to di Rdcon d > 1. In ambito multivariato i punti di Fekete sono noti in pochi domini quali le circonferenze e nel caso dell n-cubo per lo spazio dei polinomi tensoriali2di grado N.
Il nostro proposito, dopo i lavori di [1, 4, 6, 7, 9, 11, 12], `e di calcolare sul simplesso unitario dei punti che abbiano per un grado prefissato n costanti di Lebesgue Λn e determinanti di matrici di Vandermonde particolarmente favorevoli.
In particolare definiremo un algoritmo, poi implementato in Matlab, che per gradi inferiori a 20 permetta il calcolo di tali punti, le cui costanti vengono paragonate con altre gi`a note per certi set.
2sono i polinomi p(x) =P
σcσxσ11· · ·x
σd
3
Triangolo
3.1
Punti di Fekete
In questa sezione intendiamo calcolare in Matlab dei punti del triangolo che abbiano valore assoluto dei determinanti di Vandermonde paragonabili, se non migliori, di quelli ottenuti numericamente da lavori precedenti con particolare riferimento a [11].
Per semplicit`a sceglieremo di volta in volta un opportuno triangolo di ri-ferimento. Ci ´o non `e restrittivo in quanto si dimostra che una trasformazione (affine) tra due triangoli T1e T2mappa punti di Fekete di T1in punti di Fekete di T2. Grazie a questa propriet`a, in seguito utilizzeremo il simplesso 2− di-mensionale di coordinate (0, 0), (0, 1), (1, 0) per l’implementazione degli algo-ritmi proposti e il triangolo equilatero di base per la stampa grafica dei risul-tati. Il passaggio da uno all’altro avviene mantenendo inalterate le coordinate baricentriche dei punti.
3.1.1 Algoritmo di ricerca
La ricerca dei punti approssimati di Fekete nel simplesso 2−dimensionale `e stata effettuata con la funzionefminconpresente nell’optimization toolbox di Matlab che ha come utilizzo quello di minimizzare/massimizzare una partico-lare funzione obiettivo. Nel nostro caso la funzione obiettivo riceve in input un set di punti del simplesso e restituisce il valore assoluto del determinante della matrice di Vandermonde rispetto a una particolare base polinomiale. Sot-tolineiamo l’importanza della capacita’ di questo ottimizzatore di distribuire automaticamente il carico di lavoro su diversi processori e quindi il calcolo distribuito avviene senza dover modificare il codice scritto per il singolo pro-cessore. Questo permette di sfruttare nativamente la potenza di calcolo di un cluster.
La routinefminconusa quattro differenti algoritmi di ricerca e a seconda del tipo di problema si decide la scelta pi `u opportuna. Il nostro problema di ottimo `e di tipo vincolato, poich´e gli N = n+dn
= (n + 1)(n + 2)/2 punti di Fekete devono appartenere al triangolo di riferimento. In questo caso la scelta difmincon`e ricaduta sull’algoritmoactive-set. Per le caratteristiche degli algoritmi e le loro peculariet`a si rimanda alla documentazione online su
www.mathworks.com.
La base scelta `e quella ortonormale di Dubiner-Legendre ossia la base di polinomi bivariati {gk} tale che
Z Ω
gk(x)gs(x) dx = δks implementata dalla nostra routinedubiner_leg.
ottimizzazione. L’implementazione della valutazione del valore assoluto del determinante della matrice di Vandermonde in Matlab avviene tramite
-abs(det(dubiner_leg(n, points)))
Osserviamo che il segno “−” `e richiesto perch`e fminconminimizza la fun-zione obiettivo.
Per la ricerca del massimo `e necessario il calcolo approssimato o in forma chiusa del gradiente e dell’hessiana della funzione obiettivo. Nel nostro caso non vengono esplicitati tramite una funzione ma approssimati numericamente di volta in volta dall’ottimizzatore. `E importante sottolineare che l’ottimiz-zatore si bloccher`a al raggiungimento di un massimo locale, potenzialmente distante dal massimo globale.
Il problema di avvicinarsi il pi `u possibile al massimo globale `e stato af-frontato in momenti successivi con due metodologie differenti. Nel primo non si `e assunta nessuna congettura sulla disposizione dei punti nel simplesso, vin-colando i punti unicamente a non uscire dal dominio. Nella seconda si `e pro-ceduto facendo delle assunzioni quali la disposizione dei punti lungo il bordo e la disposizione dei punti nel dominio secondo qualche simmetria.
3.1.2 Primo metodo
Nel primo metodo quale valore iniziale fornito ad fminconsi `e scelta una disposizione casuale di punti all’interno del triangolo equilatero Ω avente ver-tici (0, 0), (0, 1), (1/2,√3/2). Cosa importante da sottolineare e che distingue questo metodo dal successivo ´e che si richiede solo che i punti appartengano al triangolo di riferimento (inclusi i suoi lati).
Poich´efminconrisolve problemi di ottimizzazione vincolata, tale routine agisce spostando la distribuzione dei punti (e quindi la soluzione) all’inter-no del simplesso. Questo ha prodotto risultati soddisfacenti andando in al-cuni gradi a migliorare il valore assoluto del determinante di Vandermonde ottenuto con i punti di Taylor-Wingate-Vincent [11] relativamente alla base ortonormale di Dubiner-Legendre.
Per gradi elevati questo metodo richiede un alto numero di iterazioni e di valutazioni della funzione obiettivo che abbiamo implementato tramite il codice Matlab
-abs(det(dubiner_leg(n, points)))
I punti per cui si valuta il valore assoluto del determinante della matrice di Van-dermonde vengono passati tramite la matricepointsdi dimensione “Nx2”. La funzionedubiner_leg`e per `o stata implementata per ricevere in input punti
appartenenti al triangolo rettangolo Ω∗di coordinate (0, 0), (0, 1), (1, 0). Questo, come visto in precedenza, non crea problemi in quanto trasformazioni affi-ni mappano punti di Fekete in punti di Fekete. I punti verranno determinati nel triangolo equilatero Ω, mappati nel nel triangolo rettangolo Ω∗dove verr´a valutato il valore assoluto del determinante della matrice di Vandermonde.
Fekete. Inoltre non risiedono in un massimo locale, cosa che avrebbe altrimenti vanificato l’uso dell’ottimizzatore.
Questo primo metodo `e utilizzabile in Matlab lanciando la demo
demo_simplex_fek_freePts.m
All’interno di tale script `e possibile settare il grado polinomiale che si vuole ricercare tramite la variabile Me il set di punti iniziali scelto tramite la vari-abilestPts. Oltre alle diverse possibilit`a di set di punti iniziali (casuali, APF o da file) si trova anche implementata la possibilit`a di utilizzare la funzione
shakePts(points, k) che “scuote” i punti che le vengono passati in input mantenendoli all’interno del simplesso. La perturbazione dipende dal para-metroke vale
(rand(1,1)-1/2)/k
per ciascuna delle coordinate dei punti. Quindi minore sar`ak, maggiore sar`a la perturbazione. L’azione avviene punto dopo punto e controlla ad ogni step che vengano soddisfatti i vincoli imposti, in caso contrario ripete l’operazione. Questa opzione `e stata implementata per poter utilizzare quei set di punti i-niziali che gi`a risiedono in un massimo locale (perch`e ad esempio risultato di una precedente ottimizzazione [11]) e verificare numericamente se una loro perturbazione possa portare a risultati migliori.
Nella Tabella 1 si mostrano alcuni risultati ottenuti per il grado 6 tramite questo primo metodo. I risultati riportati in tabella riflettono i risultati rag-giunti anche negli altri gradi. I punti con il determinante maggiore, ragrag-giunti pure dal nostro metodo, rimangono i punti di TWV [11]; tuttavia, in alcuni casi, certe disposizioni iniziali di punti casuali (salvate poi su file con il prefissox0) hanno portato a superare questi risultati.
Si osservi che i punti migliori trovati mostrano numericamente la validit´a della congettura di Bos [2] riguardo ai punti sul bordo del simplesso. Notiamo infatti che, fissato un grado d, sui lati del simplesso si trovano d + 1 punti disposti come i punti di Gauss-Legendre-Lobatto [5] 1-dimensionali.
Questa osservazione ci consentir`a l’implementazione del secondo metodo ed un alleggerimento del costo computazionale del problema.
3.1.3 Secondo metodo
Per ridurre il numero di punti, e quindi di variabili da passare all’ottimizza-tore, diminuendo cos`ı il tempo di calcolo, si ipotizza la valenza della conget-tura di Bos che ipotizza che i punti di Fekete sui lati siano disposti come quelli di Gauss-Legendre-Lobatto. Di conseguenza si fissano i punti sui lati del trian-golo e si ottimizzano solo quelli interni al simplesso. Su ogni lato i punti fissati saranno “d + 1” di cui 2 sugli estremi e “d − 1” interni e quindi abbiamo un totale di “3· d” punti distinti sui lati. Vediamo subito che per un fissato grado “d” i punti interni sono i punti totali meno i punti sui lati, ossia:
(d + 1)(d + 2)
2 − 3· d =
(d − 1)(d − 2) 2
Tabella 1:Il grado 6 trattato dal primo metodoa 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Random pts Optim. pts 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 APF Wam pts Optim. pts
Random Points Optim. Points APF from WAM Optim. Points Det: 3.36e04 Det: 1.98e29 Det: 3.71e28 Det: 9.66e28
Leb: 52e3 Leb: 4.93 Leb: 12.08 Leb: 8.11
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Shake APF Wam pts Optim. pts 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 BSV Fek. M=6 TWV Points M=6
Shake APF from WAM Optim Points BSV Points TWV Points Det: 7.08e23 Det: 1.98e29 Det: 2.29e29 Det: 2.29e29 Leb: 28.59 Leb: 4.93 Leb: 4.17 Leb: 4.17
aAlcuni punti di grado 6 nel triangolo. In ordine l’ottimizzatore ha utilizzato come punti di
triangolo. Dividiamo il triangolo equilatero di riferimento Ω avente vertici (0, 0), (1, 0), (1/2,√3/2)nei tre triangoli formati a partire dal baricentro e dai tre vertici del simplesso (vedi Figura 1). Scegliamo uno di questi triangoli, di-ciamo Ω∗, prendiamo un punto P all’interno di Ω∗e calcoliamo le coordinate baricentriche (λ1, λ2, λ3) rispetto a quest’ultimo. Utilizzando queste coordinate possiamo identificare altri due punti all’interno dei due triangoli rimanenti ot-tenuti con le permutazioni (λ3, λ1, λ2) (λ2, λ3, λ1) ruotando P di 2π/3 e 4π/3 rispetto al baricentro. La Figura 1a mostra una di queste orbite.
Per poter sfruttare questo tipo di costruzione il numero di punti all’interno del simplesso deve essere sempre un multiplo di tre. Questo non `e per `o sempre possibile e per alcuni gradi sar `necessario fissare, oltre ai bordi, anche un punto nel baricentro del triangolo (si veda la nota a fine paragrafo).
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 P (a) orbita 3 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 P (b) orbita 6 Figura 1: Punti di orbita 3 e 6 nel triangolo
Prendiamo come esempio illustrativo il caso in cui il grado sia “d = 12”. Con il metodo precedente avevamo 91 punti liberi di muoversi nel triangolo. Ora invece sono solo 18 in quanto sono fissati 36 punti sui bordi, 1 nel baricen-tro e rimangono (12 + 1)(12 + 2)/2 − 36 − 1 = 54 punti all’interno del simplesso. La posizione di questi 54 punti, grazie alle ipotesi fatte sopra, viene definita muovendone solamente 54/3 = 18.
La Figura 1b mostra un orbita di ordine sei nel triangolo equilatero. Viene spontaneo domandarsi che risultati otterremmo sfruttando anche le orbite di ordine sei, ossia sfruttando sia le rotazioni che le riflessioni del triangolo.
possono confrontare con altri nella Tabella 2, si sono ottenuti forzando i punti interni ad appartenere tutti ad orbite di ordine 3.
Per riprodurre questi risultati in Matlab, abbiamo implementato la demo
demo_simplex_fek_orbpts.m
All’interno di essa `e possibile settare il grado polinomiale tramite il parametro
Me il numero di orbite di ordine sei tramite il paramentroN orb6. I determi-nanti ottenuti in questo modo hanno superato in molti casi i migliori conosciuti fino ad ora.
Nella Figura 2 si possono osservare i punti di ottimo trovati (BSV) per il grado dodici e confontarli con i punti di Taylor-Wingate-Vincent (TWV). Nel-la TabelNel-la 2 si possono confrontare i risultati raggiunti da quelli presenti in letteratura.
Nota
Mostriamo come i punti interni del simplesso siano, a meno dell’eventuale baricentro, sempre divisibili per 3. L’asserto `e vero per d = 1, d = 2, d = 3. In generale i punti interni sono #d = (d−1)(d−2)2 . Se mod (d, 3) ≡ 1 allo-ra mod (#d, 3) ≡ 0. Inoltre #d+1 = #d+ (d − 1), #d = d2 −3d+2 2 , #d+1 = d(d−1) 2 = d2 −d 2 = d2 −3d+2 2 + d2 −d 2 − d2 −3d+2 2 = #d+ (d − 1). Di conseguenza essendo mod (#d, 3) = 0abbiamo mod (#d+1, 3)≡ mod (#d+(d−1), 3)≡ mod (#d, 3) + mod (d − 1, 3) = mod (d − 1, 3) = 0. Quindi se µ = d + 1, mod (µ, 3) = 2 implica mod (#mu, 3) = 0. Infine da #d+2 = #d+1+ d abbi-amo mod (#d+2, 3) = mod (d + 1 + d, 3) = mod (#d+1, 3) + mod (d, 3) = 0 + 1 = 1. Cio`e se mod (µ, 3) = 0 allora mod (#µ, 3) = 1.
3.2
Punti di Lebesgue
In questa paragrafo intendiamo mostrare come `e stato possibile migliorare le costanti di Lebesgue per i set di punti approssimati di Fekete precedentemente trovati. Illustreremo dapprima l’algoritmo proposto e successivamente entr-eremo nello specifico dei due metodi utilizzati. Come in precedenza nel pri-mo metodo i punti vengono vincolati unicamente a rimanere all’interno del dominio mentre nel secondo metodo sfrutteremo le rotazioni e le simmetrie illustrate precedentemente.
3.2.1 Algoritmo di ricerca
L’algoritmo di ricerca utilizzato per i punti di Lebesgue nel triangolo `e analogo a quello visto per la ricerca dei punti di Fekete. In Matlab si `e fatto di nuovo uso della funzionefminconche tra le sue subroutines sceglie l’implementazione dell’algoritmoactive-set.
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 BSV Points M=12
(a) BSV: Det 7.21e115
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 TWV Points M=12 (b) TWV: Det 6.15e115 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 BSV Points M=12 TWV Points M=12 (c) BSV - TWV
La valutazione della costante di Lebesgue Λn `e fornita approssimativa-mente. Per prima cosa si stabilisce una mesh di controllo, ad esempio una WAM sul triangolo di riferimento. Il calcolo di tale valore `e avvenuto quindi per stima su una determinata griglia. Sia A la matrice di Vandermonde definita dai punti interni al triangolo mentre sia B la matrice di Vandermonde generata dai punti della mesh di controllo (valutate entrambe relativamente alla base di Dubiner-Legendre). Si valuta quindi Λ∗
n = ||A′\B′|| doveA'B'fornisce la soluzione del problema ai minimi quadrati A′X = B′. Si vede facilmente che se la mesh `e sufficientemente fitta allora Λ∗
n≈Λn.
La differenza principale dai metodi precedenti `e l’utilizzo della nuova fun-zione obiettivo:
leb_obj(n, points, V_controlmesh)
che restituisce la stima della costante di Lebesgue Λn dei puntipoints con-siderati rispetto ad un mesh sceltacontrolmeshRispetto al metodo precedente la nostra ricerca dipende quindi dal tipo di griglia su cui decidiamo di stimare tale costante e, in particolare, fissato un determinato tipo di griglia, dipender`a anche dalla cardinalit`a dei punti presenti in essa.
La scelta di questamesh di controllo `e ricaduta sulle WAM. In Matlab tale griglia viene generata tramite la funzione:
computing_symplex_wam(wam_degree)
Mentre la matrice B sopra menzionata `e fornita da
dubiner_leg(n,controlmesh)
`E importante osservare che la funzione obiettivoleb_objcontrolla la gran-dezza della costante di Lebesgue trovata e, se troppo grande (maggiore di 1e30) o se risultaNaN, la sostituisce con il valore 1e30 leggermente perturbato. Ques-ta aggiunQues-ta si ´e resa necessaria in quanto in alcuni casi capiQues-ta che l’ottimizza-tore, dopo una determinata iterazione o calcolando numericamente il gradi-ente con opportune differenze finite, diventi instabile e interrompa il processo perdendo i risultati raggiunti fino a quel momento. Ricordiamo infatti che l’ot-timizzatore, alla fine della sua ricerca, non restituisce l’ultimo valore trovato, ma l’ottimo tra i valori raggiunti.
La perturbazione sul valore 1e30 `e stata pensata per “ingannare” il gradi-ente approssimato dall’ottimizzatore e forzarlo cos`ı a muovere i punti fino al raggiungimento di una configurazione con costante di Lebesgue inferiore. Non `e quest’ultimo un requisito fondamentale della funzione obiettivo, ma permet-te di continuare la ricerca senza crash anche parpermet-tendo da punti con costanti di Lebesgue pessime.
3.2.2 Primo Metodo
precedentemente. Questo ha prodotto ottimi risultati, andando a superare o ad affiancare le migliori costanti di Lebesgue sul triangolo note in letteratura.
Bisogna sottolineare che non `e stato sufficiente chiamare un’unica volta l’ot-timizzatore, ma si `e dovuto far ricorso a piu’restart dell’algoritmo di ottimiz-zazione. In alcuni restart `e stato anche necessario cambiare la cardinalit`a del-la mesh di controllo per poter ottenere una maggiore precisione in quanto del-la funzione fminconnon possiede il gradiente della funzione, ma una sua
ap-prossimazione numerica derivante dalle valutazioni della funzione obiettivo fatte fino a quel momento.
In particolare considerato un set di punti fornito a fine ciclo dafmincon, esso pu `o essere riutilizzato come set di punti iniziale dello stesso ottimizzatore. All’ inizio di ogni “restart” viene ristabilita la cardinalit`a della mesh di control-lo e riapprossimato il gradiente della funzione obiettivo. Ci `o pu `o portare a degli ulteriori minoramenti della costante di Lebesgue. L’aumento del numero di punti della mesh di controllo porta ad avere una maggiore precisione nei risultati.
L’azione combinata dei restart e dell’aumento della cardinalit`a della mesh di controllo ha permesso di raggiungere i risultati riportati nella Tabella 2
L’implementazione di questa ricerca pu `o essere testata lanciando
demo_simplex_leb.m
Nella Figura 3 si mostrano i punti di Lebesgue trovati per il grado dodici e il confronto con i punti approssimati di Fekete di partenza.
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 BSV Leb. Points M=12
(a) BSV Leb Points
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 BSV Leb. M=12 BSV Fek. M=12 (b) BSV Leb-Fek Points Figura 3: BSV Leb. e BSV Fek. Points a confronto
3.2.3 Secondo Metodo
Poich`e la ricerca dei punti di Lebesgue risulta computazionalmente pi `u elevata rispetto a quella per i punti di Fekete, la ricerca di tali punti per gradi maggiori di 12 risulta assai dispendiosa. Si `e quindi deciso di riutilizzare, come visto prima, le rotazioni del triangolo.
questo modo otteniamo un notevole alleggerimento di variabili per l’ottimiz-zatore e la possibilit`a di utilizzare come punti di partenza i punti di Fekete trovati in precedenza con tali rotazioni. Si `e infatti rivelato di fondamentale importanza nella minimizzazione della costante di Lebesgue la buona scelta della configurazione iniziale di punti.
La differenza con il metodo precedente sta quindi nell’utilizzo di una dif-ferente funzione obiettivo che assolva alle richieste fatte. In particolare tale funzione `e stata implementata da:
obj_simplex_leb_orbpts(x, pts, M, N_orbit_free, V_controlmesh)
dovexsono i punti da ottimizzare, la variabileMindica il grado polinomiale,
ptsi punti nel triangolo fissati per ipotesi,N orbit freeindica il numero di orbite di ordine tre e sei,V controlmesh la matrice generata dalla mesh di controllo come spiegato in precedenza.
La routine che ne implementa l’utilizzo `e
demo_simplex_orbleb.m
all’interno della quale `e possibile settare il grado polinomialeMe la variabile
fileindicante il file contenente le coordinate dei punti di partenza, nel nostro caso i punti di Fekete trovati in precedenza.
Come nel metodo precedente la minimizzazione della costante di Lebesgue `e avvenuta grazie a diversi “restart” della demo. In particolare si `e partiti dai punti di Fekete ed una mesh di controllo di grado doppio rispetto al grado analizzato, ed ad ogni restart si sono utilizzati come punti di partenza i pun-ti precedentemente otpun-timizzapun-ti e una mesh di controllo di grado raddoppiato. Grazie a questo metodo `e stato possibile spingersi all’ottimizzazione di punti di Lebesgue fino al grado 18. Si pensa che l’uso di clusters possa permettere di ottenere punti aventi costanti di Lebesgue molto piccole per grado maggiore di 18, permettendo pure di affrontare il pi ´u complesso problema di calcolare i punti di Lebesgue per il tetraedro. Inoltre i set di punti trovati a cui `e stato im-posto avere sui lati i punti Legendre Gauss Lobatto univariati, possono essere utilizzati nei metodi spettrali [8].
Dai risultati raggiunti ed elencati nella Tabella 2 sembrerebbe che la costante di Lebesgue Λnabbia andamento lineare con coefficente angolare≈ 1
Tabella 2:Determinanti della matrice di Vandermonde e costanti di Lebesgue dei pi `u importanti set di punti.a
Grado BSV. Leb. BSV. Fek. BP. Leb. BP. Fek. TWV Hesthaven
1 1.00 5.87e1 1.00 5.88e1 1.00 5.87e1 1.00 5.88e1 - - 1.00 5.88e01 2 1.49 2.43e4 1.67 3.14e4 1.49 2.43e4 1.66 3.14e4 - - 1.67 3.14e04 3 1.97 2.01e8 2.11 3.45e8 1.97 2.00e6 2.11 3.41e8 2.11 3.45e8 2.11 3.45e08 4 2.42 4.32e13 2.73 9.62e13 2.45 2.84e13 2.61 8.64e13 - - 2.73 9.62e13 5 2.89 2.14e20 3.61 8.03e20 2.97 1.88e20 3.14 7.66e20 - - 3.61 8.03e20 6 3.39 3.18e28 4.17 2.29e29 3.65 2.54e28 3.87 2.00e29 4.17 2.29e29 4.17 2.29e29 7 4.09 1.07e38 5.20 2.59e39 4.36 1.72e38 4.66 1.84e39 - - 5.20 2.59e39 8 4.55 7.41e50 6.89 1.36e51 5.44 2.64e49 5.93 6.35e50 - - 6.89 1.36e51 9 5.27 2.37e64 6.97 3.79e64 6.69 2.28e62 7.39 8.72e63 6.80 2.39e64 6.97 3.79e64 10 5.92 4.57e79 8.24 1.05e80 8.71 5.42e76 9.82 4.95e78 - - 8.24 1.05e80 11 6.65 4.43e96 8.02 9.67e96 11.25 8.95e92 12.93 1.20e95 - - 8.02 9.67e96 12 6.97 2.85e115 8.55 7.22e115 15.34 3.68e110 17.79 1.27e113 9.67 6.15e115 8.55 7.22e115 13 7.74 5.71e135 9.81 4.46e136 21.02 1.18e130 24.50 6.00e132 - - 9.81 4.46e136 14 8.29 9.95e157 10.89 2.51e159 29.65 1.08e151 34.69 1.27e154 - - 10.90 2.51e159 15 9.04 1.89e182 11.40 9.66e183 42.37 7.17e173 49.57 1.23e177 10.01 4.60e183 11.40 9.66e183 16 8.56 2.70e209 12.72 3.36e210 61.45 1.26e198 71.88 5.39e201 - - 12.72 3.36e210 17 9.11 7.86e237 13.60 1.01e239 100.6 7.85e221 101.4 1.10e229 - - 15.50 9.34e238 18 9.88 1.44e268 14.38 4.10e269 147.3 2.11e249 151.0 1.33e257 14.73 1.04e269 14.55 2.43e269 Grado Warb. Leb. Warb. Fek. Heinrichs Chen Babuska APF WAM 1 APF WAM 2
1 1.00 5.87e1 1.00 5.87e1 - - - - 1.00 5.87e1 1.00 5.87
2 1.66 3.14e4 1.66 3.14e4 - - 1.67 3.14e4 1.67 3.14e4 1.67 3.14e4 3 2.11 3.45e8 2.11 3.45e8 - - 2.11 3.45e8 2.26 3.01e8 2.20 3.24e8 4 2.66 9.53e13 2.66 9.53e13 - - 2.69 9.58e13 3.12 6.50e13 2.93 7.84e13 5 3.12 7.73e20 3.75 7.99e20 - - 3.30 7.91e20 4.14 4.63e20 3.76 5.91e20 6 3.70 2.14e29 3.82 2.04e29 3.68 1.84e29 3.79 2.21e29 5.34 1.00e29 7.26 1.01e29 7 4.27 2.20e39 4.54 1.93e39 - - 4.39 2.32e39 12.96 6.547e38 7.39 1.24e39 8 4.96 9.56e50 5.70 7.03e50 - - 5.09 1.01e51 10.09 3.082e50 13.29 5.31e50 9 5.73 1.84e64 6.60 2.15e64 5.59 1.42e64 5.91 1.93e64 11.32 5.170e63 11.69 1.54e64 10 6.67 1.78e79 9.17 6.57e78 - - 7.08 1.75e79 11.63 9.616e78 16.30 1.92e79 11 7.89 8.32e95 11.84 1.84e95 - - 8.33 7.88e95 14.62 3.398e95 10.00 1.60e96 12 9.36 2.28e114 16.06 2.34e113 7.51 2.59e115 10.06 1.84e114 14.78 1.909e114 21.48 7.54e114 13 11.47 3.23e134 12.08 4.41e134 - - 12.04 2.29e134 18.41 7.051e134 26.48 2.59e135 14 13.95 2.96e156 30.33 3.92e154 - - - - 23.76 1.152e157 20.02 1.12e158 15 17.61 1.54e180 42.61 5.31e177 9.25 - - - 29.51 1.720e181 20.76 1.66e182 16 22.19 5.40e205 60.89 3.50e202 - - - - 26.56 3.588e207 29.35 7.71e208 17 28.20 2.10e232 28.70 2.11e233 - - - - 36.41 4.196e235 27.27 4.28e236 18 35.87 3.16e261 128.42 1.76e257 11.86 - - - 36.35 1.180e265 46.26 1.90e267
aNel caso di pi `u configurazioni possibili per un determinato grado e metodo, `e stato riportato solo il valore del determinante
4
Esperimenti Numerici
Il primo proposito di questa sezione `e di indicare brevemente i metodi utilizzati per avere dei punti quasi-ottimali relativamente alla costante di Lebesgue Λn e al valore assoluto del determinante di Vandermonde V (rispetto alla base ortonormale di Dubiner-Legendre). In alcuni casi abbiamo ottenuti punti su un triangolo di riferimento via una generalizzazione di algoritmi noti seguita da un processo di ottimizzazione, in altri abbiamo reperito i dati accessibili dalle pertinenti pubblicazioni. Per i set disponibili abbiamo quindi valutato con precisione la costante di Lebesgue Λne il valore assoluto del determinante della matrice di Vandermonde | det (Vn)|.
In letteratura si `e spesso discusso su come calcolare punti sul triangolo che avessero determinanti di Vandermonde il cui valore assoluto fosse particolar-mente elevato o aventi costante di Lebesgue particolarparticolar-mente piccola.
In alcuni casi come in [4, 7, 1, 12] sono state individuate particolari config-urazioni aventi la particolarit´a di sfruttare le simmetrie del triangolo e speciali disposizioni simmetriche dei punti sui lati.
In [4, 7, 11] i punti vengono determinati con coordinate baricentriche (λ1, λ2, λ3) con 0≤ λi ≤ 1 eP3i=1λi = 1. Se i vertici del triangoloT sono V1, V2, V3, ogni suo punto P lo si pu ´o descrivere univocamente come la combinazione convessa P =PλiVi. In [4, 7] se nella disposizione ci sta il punto (λ1, λ2, λ3)
allora ci stanno pure le sue permutazioni. Se due coordinate baricentriche sono uguali allora si dice che il punto ha orbita 3 e le permutazioni possibili sono 3 mentre se tutte le coordinate baricentriche di P sono distinte allora si dice che il punto ha orbita 6 che `e pari al numero delle sue permutazioni. Osserviamo che esiste un solo punto che ha tutte le coordinate baricentriche uguali, che corrisponde al baricentro.
Per compattezza, in due questi articoli si cita un solo punto per ogni orbita 1, 3, 6 deducendo le altre possibili per permutazione. Quindi nelle tabelle com-pare (a, a, b) per citare non solo (a, a, b) ma pure (a, b, q) e (b, a, a). Il nostro primo lavoro `e stato di avere su file una descrizione meno sintetica che citasse tutti gli elementi e non solo uno rappresentativo. In altre parole nelle nostre tabelle compare tanto (a, a, b) quanto (a, b, q) e (b, a, a).
Osserviamo che la nostra base ortonormale di Dubiner-Legendre ha quale riferimento il simplesso unitario, cio`e il triangolo avente vertici V1=(0, 0), V2=(1, 0), V3=(0, 1). Se P ha coordinate baricentriche (λ1, λ2, λ3) da
P = λ1(0, 0) + λ2(1, 0) + λ3(0, 1) = (λ2, λ3)
deduciamo che per determinare le coordinate cartesiane di P basta selezionare 2 delle 3 coordinate baricentriche dello stesso.
uni-variata dei Gauss-Legendre-Lobatto. In particolare, in [12], si introduce una generalizzazione della distribuzione di base via un parametro di warping α.
Per ottenere risultati migliori abbiamo usato le loro idee per generare famiglie di punti sul simplesso unitarioT basate su punti di Gauss-Jacobi-Lobatto (e non solo Gauss-Legendre-Lobatto). L’ottimizzatore ha cercato di volta in volta quegli esponenti della funzione peso di Jacobi che fornissero le migliori dis-tribuzioni relativamente alla costante di Lebesgue o al valore assoluto del de-terminante della matrice di Vandermonde relativa alla base di Dubiner-Legendre nei punti della distribuzione. Nel caso dei punti di Warburton, si `e ottimizzato pure il coefficiente di warping.
Di seguito abbiamo implementato pure l’algoritmo di Heinrichs [6]. Purtrop-po la descrizione dell’algoritmo `e risultata incompleta e non siamo riusciti a riprodurre quanto affermato dall’autore. In particolare l’algoritmo produce punti che non appartengono al simplesso unitario, nonostante sia affermato il contrario. Ci ´o nonostante, i punti forniti dalla pubblicazione, anche se solo per alcuni gradi, sono di ottima qualit´a. Similmente in [11] vengono forniti dei punti il cui determinante della matrice di Vandermonde `e molto elevato in modulo. L’algoritmo non `e di semplice implementazione e non `e forni-to dagli auforni-tori. Siamo comunque riusciti a calcolare le coordinate delle loro distribuzioni di punti da quelle presenti per alcuni gradi sulla pubblicazione. In [11] si afferma comunque che possono fornire a richiesta insiemi per un qualsiasi grado inferiore a 18.
5
Codice
5.1
Demo
demo_simplex_fek_freePts.m
1 clear all;
2
%---3 % Setting polynomial degree and starting points (see below)
4 %---5 M = 17; 6 stPts = 2; 7 8 %---9 % Starting points
10 % stPts: 0 APF from WAM, 1 random pts, 2 file pts, 3 shake file pts 11
%---12 switch stPts
13 case 0
14 % Computing AFP from WAM
15 pts_wam = computing_symplex_wam(M); 16 V_wam = dubiner_leg(M,pts_wam); 17 moms = ones(size(V_wam,2),1); 18 startPts = computing_fekete_points(pts_wam,V_wam,2,moms,1); 19 case 1 20 startPts = random_tri([0 0;0 1;1 0],(M+1)*(M+2)/2); 21 case 2
22 startPts = recover_points('points/BSV_fek_M17');
23 case 3
24 startPts = shakePts(recover_points('points/BSV_fek_M17'),30);
25 end
26
27
%---28 % Setting fmincon parameters
29
%---30 options = optimset('MaxIter',1e4,'MaxFunEvals',1e4,'Display','iter',...
31 'Algorithm','active-set','TolCon',1e-400,'ObjectiveLimit',1e300,...
32 'TolX',1e-60,'TolFun',1e-60,'FunValCheck','on');
33 [A,b] = simplexConst(M);
34
35
%---36 % Starting optimization (down scale obj function to avoid
37 % very big number error; why not log10 instead of
38 % \1e100? To avoid log complex number error)
39 %---40 if (M < 12) 41 [pts,fval] = fmincon(@(x)-abs(det(dubiner_leg(M,x))),... 42 startPts,A,b,[],[],[],[],[],options); 43 elseif (M < 16) 44 [pts,fval] = fmincon(@(x)-abs(det(dubiner_leg(M,x)))/1e100,... 45 startPts,A,b,[],[],[],[],[],options); 46 elseif (M < 18) 47 [pts,fval] = fmincon(@(x)-abs(det(dubiner_leg(M,x)))/1e150,... 48 startPts,A,b,[],[],[],[],[],options); 49 else 50 [pts,fval] = fmincon(@(x)-abs(det(dubiner_leg(M,x)))/1e200,... 51 startPts,A,b,[],[],[],[],[],options); 52 end 53 54
56 %---57 detV_startPts = abs(det(dubiner_leg(M,startPts))); 58 detV_optimPts = abs(det(dubiner_leg(M,pts))); 59 controlmesh = computing_symplex_wam(150); 60 V_controlmesh = dubiner_leg(M,controlmesh); 61 V_optimPts = dubiner_leg(M,pts); 62 V_startPts = dubiner_leg(M,startPts); 63 L_loc_optimPts = norm(V_optimPts'\V_controlmesh',1); 64 L_loc_startPts = norm(V_startPts'\V_controlmesh',1); 65 66 %---67 % Print results 68
%---69 fprintf('\n \t POLYNOMAIL DEGREE: %d',M);
70 fprintf('\n \n \t CONDITION NUMBER:')
71 fprintf('\n \t START POINTS: %2.2e',cond(V_startPts));
72 fprintf('\n \t OPTIM POINTS: %2.2e',cond(V_optimPts))
73 fprintf('\n \n \t VANDERMOND DETERMINANTS');
74 fprintf('\n \t START POINTS: %2.2e', detV_startPts);
75 fprintf('\n \t OPTIM POINTS: %2.2e', detV_optimPts);
76 fprintf('\n \n \t LEBESGUE CONSTANTS');
77 fprintf('\n \t START POINTS: %2.2e',L_loc_startPts); 78 fprintf('\n \t OPTIM POINTS: %2.2e',L_loc_optimPts);
79 fprintf('\n');
demo_simplex_fek_orbpts.m
1 clear all;
2
%---3 % Setting polynomial degree and number of orbit
4
%---5 M = 17; % M major equal 4
6 N_orb6 = 0; % Remember: N_orb6 must be less equal than N_pts_free/6
7
8
%---9 % Setting the boundary points and adding barycentric point if necessary
10 % Setting fmincon parameters
11 % Setting boundary limits
12 %---13 14 N_pts=(M+1)*(M+2)/2; 15 pts = gauss_lobatto_simplex_boundary(M); 16 N_pts_free = N_pts-M*3; 17 if(mod(N_pts_free,3)==1) 18 pts = [pts; 1/3 1/3]; 19 N_pts_free = N_pts_free-1; 20 end 21
22 options = optimset('MaxIter',1e6,'MaxFunEvals',1e5,'Display','iter',...
23 'Algorithm','active-set','TolCon',1e-400,'ObjectiveLimit',1e300,...
24 'TolX',1e-60,'TolFun',1e-60,'FunValCheck','on','UseParallel','always');
25
26 N_orbit_free = [(N_pts_free-6*N_orb6)/3, N_orb6];
27 [A, b] = simplexConstOrbit(N_orbit_free); 28 lb = zeros(sum(N_orbit_free)*2,1)';
29 up = ones(sum(N_orbit_free)*2,1)';
30
31
%---32 % Setting random starting points
33
35 startOrb3 = [0 0;1 0;1/3 1/3]; 36 startOrb6 = [0 0;1/2 0;1/3 1/3]; 37 x0 = random_tri(startOrb3,N_orbit_free(1)); 38 x0 = [x0; random_tri(startOrb6,N_orbit_free(2))]; 39 40
%---41 % Starting optimization (down scale obj function to avoid
42 % very big number error; why not log10 instead of
43 % \1e100? To avoid log complex number error)
44 %---45 46 if (M < 12) 47 [pts_founded] = fmincon(@(x)obj_simplex_orbpts(x,pts,... 48 M,N_orbit_free) ,x0,A,b,[],[],lb,up,[],options); 49 elseif (M < 16) 50 [pts_founded] = fmincon(@(x)obj_simplex_orbpts(x,pts,... 51 M,N_orbit_free)/1e100 ,x0,A,b,[],[],lb,up,[],options); 52 elseif (M < 18) 53 [pts_founded] = fmincon(@(x)obj_simplex_orbpts(x,pts,... 54 M,N_orbit_free)/1e150 ,x0,A,b,[],[],lb,up,[],options); 55 else 56 [pts_founded] = fmincon(@(x)obj_simplex_orbpts(x,pts,... 57 M,N_orbit_free)/1e200 ,x0,A,b,[],[],lb,up,[],options); 58 end 59 60 %---61 % Generating pts output 62 %---63 64 x = []; 65 for i=1:N_orbit_free(1) 66 x = [x ;orbit3_simplex(pts_founded(i,:))]; 67 end 68 pts = [x ; pts]; 69 x = []; 70 for i=1:N_orbit_free(2) 71 x = [x ;orbit6_simplex(pts_founded(i+N_orbit_free(1),:))]; 72 end 73 pts = [x ; pts]; 74 75
%---76 % Computing and print Lebesgue constant and Vandermonde determinant
77 %---78 79 controlmesh = computing_symplex_wam(150); 80 V_controlmesh = dubiner_leg(M,controlmesh); 81 V_pts = dubiner_leg(M,pts); 82 V_det = abs(det(V_pts)); 83 L_loc = norm(V_pts'\V_controlmesh',1);
84 fprintf('\n \t POLYNOMIAL DEGREE: %d',M);
85 fprintf('\n \t CONDITION NUMBER: %2.2e',cond(V_pts));
86 fprintf('\n \t LEBESGUE CONSTANT: %6.2f',L_loc);
87 fprintf('\n \t VANDERMONDE DETERMINAT: %2.2e', V_det);
demo_simplex_leb_freePts.m
1 clear all;
2 warning('off','all');
3
%---4 % Setting polynomial degree, starting points (see below) and degree of
6
%---7 M = 7; 8 stPts = 0;
9 mesh_degree = 40;
10 file = 'BSV_leb_M7'; %to set if stPts=0
11 12 %---13 % Starting points 14 % stPts: 0 file pts, 1 random pts 15 %---16 17 switch stPts 18 case 0 19 fid = fopen(file);
20 startPts = fscanf(fid, '%g %g', [2 inf]);
21 fclose(fid); 22 startPts = startPts'; 23 case 1 24 startPts = random_tri([0 0;0 1;1 0],(M+1)*(M+2)/2); 25 end 26 27 %---28 % Setting fmincon parameters
29
%---30 options = optimset('MaxIter',1e5,'MaxFunEvals',2e5,'Display',...
31 'iter','Algorithm','active-set','TolCon',1e-400,'ObjectiveLimit',...
32 1e300, 'TolX',1e-60,'TolFun',1e-6,'FunValCheck','on');
33 lb = zeros(1,(M+1)*(M+2));
34 up = ones(1,(M+1)*(M+2));
35 [A,b] = simplexConst(M);
36
37
%---38 % Generating control mesh
39 %---40 41 controlmesh = computing_symplex_wam(mesh_degree); 42 V_controlmesh = dubiner_leg(M,controlmesh); 43 44 %---45 % Starting optimization 46 %---47 [pts, fval] = fmincon(@(x)leb_obj(M,x,V_controlmesh),... 48 startPts,A,b,[],[],lb,up,[],options); 49 pts = reshape(pts,(M+1)*(M+2)/2,2); 50 51
%---52 % Computing Vandermonde determinants and Lebesgue constants
53 %---54 detV_startPts = abs(det(dubiner_leg(M,startPts))); 55 controlmesh = computing_symplex_wam(150); 56 V_controlmesh = dubiner_leg(M,controlmesh); 57 V_optimPts = dubiner_leg(M,pts); 58 V_startPts = dubiner_leg(M,startPts); 59 L_loc_optimPts = norm(V_optimPts'\V_controlmesh',1); 60 L_loc_startPts = norm(V_startPts'\V_controlmesh',1); 61 62 %---63 % Print results 64
%---65 fprintf('\n \t POLYNOMAIL DEGREE: %d',M);
66 fprintf('\n \n \t CONDITION NUMBER:')
68 fprintf('\n \t OPTIM POINTS: %2.2e',cond(V_optimPts))
69 fprintf('\n \n \t VANDERMOND DETERMINANTS');
70 fprintf('\n \t START POINTS: %2.2e', detV_startPts);
71 fprintf('\n \t OPTIM POINTS: %2.2e', abs(det(dubiner_leg(M,pts))));
72 fprintf('\n \n \t LEBESGUE CONSTANTS');
73 fprintf('\n \t START POINTS: %2.2e',L_loc_startPts);
74 fprintf('\n \t OPTIM POINTS: %2.2e',L_loc_optimPts);
75 fprintf('\n');
demo_simplex_leb_orbPts.m
1 clear clear all;
2 warning('off','all');
3
%---4 % Setting polynomial degree, number of orbit, controlmesh degree
5 % and starting points
6
%---7 M = 11; % M major equal 4
8 N_orb6 = 0; % Remember: N_orb6 must be less equal than N_pts_free/6
9 mesh_degree = 150;
10 startPts = 1; % O Random, 1 from file
11 file = 'points/BSV_leb_M11';
12
13
%---14 % Setting fmincon parameters,
15 % Generating controlmesh,
16 % Setting boundary points and add barycentric if necessary
17 % Setting boundary limits 18
%---19
20 options = optimset('MaxIter',4,'MaxFunEvals',3e5,'Display','iter',...
21 'Algorithm','active-set','TolCon',1e-400,'ObjectiveLimit',1e300,...
22 'TolX', 1e-60,'TolFun',1e-60,'FunValCheck','on');
23 24 controlmesh = computing_symplex_wam(mesh_degree); 25 V_controlmesh = dubiner_leg(M,controlmesh); 26 27 N_pts=(M+1)*(M+2)/2; 28 pts = gauss_lobatto_simplex_boundary(M); 29 N_pts_free = N_pts-M*3; 30 if(mod(N_pts_free,3)==1) 31 pts = [pts; 1/3 1/3]; 32 N_pts_free = N_pts_free-1; 33 end 34
35 N_orbit_free = [(N_pts_free-6*N_orb6)/3, N_orb6];
36 [A, b] = simplexConstOrbit(N_orbit_free);
37 lb = zeros(sum(N_orbit_free)*2,1)';
38 up = ones(sum(N_orbit_free)*2,1)';
39
40
%---41 % Setting starting points
51 fid = fopen(file); 52 x1 = fscanf(fid, '%g %g', [2 inf])'; 53 fclose(fid); 54 x0 =[]; k=0; 55 for i = 1:3:N_orbit_free(1)*3 56 k = k+1; 57 x0(k,:) = [x1(i),... 58 x1((M+1)*(M+2)/2+i)]; 59 end 60 end 61 62 %---63 % Starting optimization 64 %---65 66 [pts_founded] = fmincon(@(x)obj_simplex_leb_orbpts(x,pts,...
67 M,N_orbit_free, V_controlmesh) ,x0,A,b,[],[],lb,up,[],options);
68 69 %---70 % Generating pts output 71 %---72 73 x = []; 74 for i=1:N_orbit_free(1) 75 x = [x ;orbit3_simplex(pts_founded(i,:))]; 76 end 77 pts = [x ; pts]; 78 x = []; 79 for i=1:N_orbit_free(2) 80 x = [x ;orbit6_simplex(pts_founded(i+N_orbit_free(1),:))]; 81 end 82 pts = [x ; pts]; 83 84
%---85 % Computing and print Lebesgue constant and Vandermonde determinant
86 %---87 88 controlmesh = computing_symplex_wam(150); 89 V_controlmesh = dubiner_leg(M,controlmesh); 90 V_pts = dubiner_leg(M,[pts(:,1),pts(:,2)]); 91 V_det = abs(det(V_pts)); 92 L_loc = norm(V_pts'\V_controlmesh',1);
93 fprintf('\n \t POLYNOMIAL DEGREE: %d',M);
94 fprintf('\n \t CONDITION NUMBER: %2.2e',cond(V_pts));
95 fprintf('\n \t LEBESGUE CONSTANT: %6.2f',L_loc);
96 fprintf('\n \t VANDERMONDE DETERMINAT: %2.2e', V_det);
5.2
Funzioni richiamate dalle demo
computing_symplex_wam.m 1 function pts=computing_symplex_wam(deg) 2 3 %---4 % OBJECT. 5
%---6 % COMPUTE WAM POINTS FOR UNIT SYMPLEX [0 0; 1 0; 0 1].
7
%---8 % INPUT.
%---10 % deg: WAM DEGREE.
11 %---12 % OUTPUT.
13
%---14 % pts: WAM POINTS ON THE UNIT SYMPLEX [0 0; 1 0; 0 1].
15 %---16 17 n1=2*deg; 18 n2=n1; 19 j1=(0:1:deg-1); 20 j2=(0:1:deg); 21 [rho,theta]=meshgrid(cos(j1*pi/n1),j2*pi/n2); 22
23 % Mapping to the simplex
24 B=[rho(:).*cos(theta(:)) rho(:).*sin(theta(:))]; 25 meshT=[B(:,1).ˆ2 B(:,2).ˆ2]; 26 27 i1=find(rho == 1); 28 i2=find(theta == pi/2); 29 i3=find(theta == 0); 30 31 nodes_x=meshT(:,1); 32 nodes_y=meshT(:,2); 33 34 pts=[nodes_x nodes_y; 0 0]; dubiner_leg.m 1 2 function V=dubiner_leg(n,pts) 3 4 %---5 % OBJECT. 6
%---7 % VANDERMONDE MATRIX WRT THE LEGENDRE MEASURE ON THE UNIT SYMPLEX
8 % [0 0; 1 0; 0 1] OF DEGREE n EVALUATED ON THE POINTS OF THE SYMPLEX pts.
34 V1loc=repmat(V1(:,h+1),1,size(V2loc,2)); 35 V=[V V1loc.*V2loc]; 36 end eval_mod_op.m 1 2 function V=eval_mod_op(deg,ab,a,b,t,c,type) 3 4 if nargin < 3 5 a=0; b=0; 6 end 7 8 L=size(t,1); 9 aa=ab(:,1); 10 bb=ab(:,2); 11 12 switch type
13 case 1 % MONIC JACOBI POLYNOMIALS.
14 V=[zeros(L,1) ones(L,1)];
15 cn=ones(size(ab,1),1);
16 co=ones(size(ab,1),1);
17 case 2 % CLASSICAL JACOBI (SEE WOLFRAM HOMESITE)
18 V=[zeros(L,1) ones(L,1)];
19 [cn,co]=c_standard(deg,a,b)
20
21 case 3 % ORTHONORMAL JACOBI POLYNOMIALS.
22 V=[zeros(L,1) (1/sqrt(ab(1,2)))*ones(L,1)]; 23 % "ab(1,2)" IS "int_-1ˆ1 w(x) dx".
24 [cn,co]=c_orthnrm(deg,a,b);
25
26 case 4 % ORTHONORMAL JACOBI POLYNOMIALS USED BY
27 % DUBINER ORTHONORMAL BASIS OVER THE SYMPLEX.
28 V=[zeros(L,1) (sqrt(8)/sqrt(ab(1,2)))*ones(L,1)]; 29 % "ab(1,2)" IS "int_-1ˆ1 w(x) dx". 30 [cn,co]=c_dub(deg,a,b); 31 32 end 33 34 for ii=1:deg 35 Vloc=cn(ii)*(t-c.*aa(ii)).*V(:,ii+1)-(c.ˆ2)*co(ii)*bb(ii).*V(:,ii); 36 V=[V Vloc]; 37 end 38 39 V=V(:,2:end); 40 41 42 43 44 function [cn,co]=c_dub(ade,a,b) 45 46 [cn_orth,co_orth]=c_orthnrm(ade,a,b); 47 cn=2*cn_orth;
56 57 ab=r_jacobi(1,a,b); 58 an0=ab(1,2); 59 60 n=(1:ade)'; 61 62 if length(n) > 0 63 if abs(b) > 0 64 anloc=(2ˆ(a+b+1)).*gamma(n+a+1).*gamma(n+b+1)... 65 ./((2*n+a+b+1).*gamma(n+a+b+1).*gamma(n+1)); 66 else 67 anloc=2ˆ(a+b+1)./(2*n+a+b+1); 68 end 69 else 70 anloc=[]; 71 end 72 73 an=[an0; anloc]; 74 75 an=an.ˆ(-1/2);
76 an_rat=an(2:end,:)./an(1:end-1,:);
77 cn=cn_st.*an_rat;
78 co=[1; cn(2:end,:).*cn(1:end-1,:)];
79 80 81 82 83 function [cn,co]=c_standard(deg,a,b) 84 85 s=a+b; 86
87 % INITIALIZATION TO AVOID SOME POSSIBLE OVERFLOW PROBLEMS FOR NEGATIVE s.
88 if (deg > 0) 89 cn1=0.5*gamma(2+s+1)/gamma(s+2); 90 else 91 cn1=[]; 92 end 93 94 n=2:deg; n=n'; 95 96 if (abs(s-floor(s)) > 0) 97 cnloc=(1./(2*n)).*(gamma(2*n+s+1)./gamma(2*n+s-1))... 98 .*(gamma(n+s)./gamma(n+s+1)); 99 else 100 cnloc=(1./(2*n)).*(2*n+s).*(2*n+s-1)./(n+s); 101 end 102 103 cn=[cn1; cnloc]; 104
105 co=[1; cn(2:end,:).*cn(1:end-1,:)];
9 10 if deg > 0 11 aa=ab(:,1); 12 bb=ab(:,2); 13 else 14 ab=r_jacobi(1,a,b); 15 aa=[]; 16 bb=[]; 17 end 18 19 switch type
20 case 1 % MONIC JACOBI POLYNOMIALS. 21 V=[zeros(L,1) ones(L,1)];
22 cn=ones(size(ab,1),1);
23 co=ones(size(ab,1),1);
24
25 case 2 % CLASSICAL JACOBI (SEE WOLFRAM HOMESITE)
26 V=[zeros(L,1) ones(L,1)];
27 [cn,co]=c_standard(deg,a,b);
28
29 case 3 % ORTHONORMAL JACOBI POLYNOMIALS.
30 V=[zeros(L,1) (1/sqrt(ab(1,2)))*ones(L,1)]; 31 % "ab(1,2)" IS "int_-1ˆ1 w(x) dx". 32 [cn,co]=c_orthnrm(deg,a,b); 33 end 34 35 for ii=1:deg 36 Vloc=cn(ii)*(x-aa(ii)).*V(:,ii+1)-co(ii)*bb(ii)*V(:,ii); 37 V=[V Vloc]; 38 end 39 40 V=V(:,2:end); 41 42 43 44 45 46 function [cn,co]=c_orthnrm(ade,a,b) 47 48 [cn_st,co_st]=c_standard(ade,a,b); 49 50 ab=r_jacobi(1,a,b); 51 an0=ab(1,2); 52 53 n=(1:ade)'; 54 55 if length(n) > 0 56 if abs(b) > 0 57 anloc=(2ˆ(a+b+1)).*gamma(n+a+1).*gamma(n+b+1)... 58 ./((2*n+a+b+1).*gamma(n+a+b+1).*gamma(n+1)); 59 else 60 anloc=2ˆ(a+b+1)./(2*n+a+b+1); 61 end 62 else 63 anloc=[]; 64 end 65 66 an=[an0; anloc]; 67 68 an=an.ˆ(-1/2);
69 an_rat=an(2:end,:)./an(1:end-1,:);
71 co=[1; cn(2:end,:).*cn(1:end-1,:)]; 72 73 74 75 76 77 function [cn,co]=c_standard(deg,a,b) 78 79 s=a+b; 80
81 % INITIALIZATION TO AVOID SOME POSSIBLE OVERFLOW PROBLEMS FOR NEGATIVE s.
82 if (deg > 0) 83 cn1=0.5*gamma(2+s+1)/gamma(s+2); 84 else 85 cn1=[]; 86 end 87 88 n=2:deg; n=n'; 89 90 if (abs(s-floor(s)) > 0) 91 cnloc=(1./(2*n)).*(gamma(2*n+s+1)./gamma(2*n+s-1))... 92 .*(gamma(n+s)./gamma(n+s+1)); 93 else 94 cnloc=(1./(2*n)).*(2*n+s).*(2*n+s-1)./(n+s); 95 end 96 97 cn=[cn1; cnloc]; 98
99 co=[1; cn(2:end,:).*cn(1:end-1,:)];
gauss_lobatto_simplex_boundary.m 1 %---2 % gauss_lobatto_symplex_boundary 3 %---4 5 function [pts] = gauss_lobatto_simplex_boundary(polynomial_degree) 6 7 %---8 % OBJECT. 9 %---10 %
11 % COMPUTATION OF GAUSS LOBATTO POINTS ON THE SYMPLEX BOUNDARY
12 %
13
%---14 % INPUT.
15
%---16 %
17 % polynomial_degree: POLYNOMIAL DEGREE
18 %
19
%---20 % OUTPUT.
21
%---22 %
23 % pts: GAUSS LOBATTO POINTS ON THE SYMPLEX'S BOUNDARY [0 1;1 0;0 0]
24 %
25
%---26 % FUNCTIONS USED IN THIS ROUTINE.
27
%---28 %
30 %
31 % ---32
33 %LGL Points on the interval [0, 1]
34 lgl = (lglnodes(polynomial_degree)+1)./2;
35
36 x = [lgl, zeros(polynomial_degree+1,1)];
37 y = [zeros(polynomial_degree,1), lgl(1:end-1)];
38 xy= [sort(lgl(2:end-1),'ascend'), lgl(2:end-1)];
39 40 pts = [x; y; xy]; 41 42 end lglnodes.m 1 function [x,w,P]=lglnodes(N) 2 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 4 % 5 % lglnodes.m 6 %
7 % Computes the Legendre-Gauss-Lobatto nodes, weights and the LGL Vandermonde
8 % matrix. The LGL nodes are the zeros of (1-xˆ2)*P'_N(x). Useful for numerical
9 % integration and spectral methods.
10 %
11 % Reference on LGL nodes and weights:
12 % C. Canuto, M. Y. Hussaini, A. Quarteroni, T. A. Tang, "Spectral Methods 13 % in Fluid Dynamics," Section 2.3. Springer-Verlag 1987
14 %
15 % Written by Greg von Winckel - 04/17/2004
16 % Contact: gregvw@chtm.unm.edu 17 % 18 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 19 20 % Truncation + 1 21 N1=N+1; 22
23 % Use the Chebyshev-Gauss-Lobatto nodes as the first guess 24 x=cos(pi*(0:N)/N)';
25
26 % The Legendre Vandermonde Matrix
27 P=zeros(N1,N1);
28
29 % Compute P_(N) using the recursion relation
30 % Compute its first and second derivatives and
31 % update x using the Newton-Raphson method.
46 47 end 48
49 w=2./(N*N1*P(:,N1).ˆ2);
obj_simplex_orbpts.m
1 function [V_det] = obj_simplex_orbpts(x,pts_freeze,...
2 polynomial_degree,N_orbit_free)
3 4 %
5 % OBJECT FUNCTION FOR fmincon
6 %---7 % INPUT.
8
%---9 % x: fmincon VARIABLE
10 % pts_freeze: KNOW POINTS (I.E. BOUDARY GAUSS LOBATTO POINTS)
11 % polynomial_degree: POLYNOMIAL DEGREE
12 % N_pts_free: NUMBER OF NOT FIXED POINTS
13 % (JUST TO IMPROVE THE OBJ FUNCTION SPEED)
14
%---15 % OUTPUT:
16
%---17 % V_det : VANDERMONDE DETERMINANT
18 %---19 20 21 if (N_orbit_free(1) > 0) 22 x3 = zeros(N_orbit_free(1)*3,2); 23 for i=1:N_orbit_free(1)
24 x3_toval = [x(i), x(sum(N_orbit_free)+i)];
55 end orbit3_simplex.m 1 function [pts] = orbit3_simplex(point) 2 3 %---4 % ON THE SYMPLEX [0 0; 1 0; 0 1] 5 %---6 % INPUT. 7
%---8 % point : POINT IN THE SYMPLEX
9 %---10 % OUTPUT:
11
%---12 % pts : POINTS OBTAINED FROM SIMPLEX ROTATIONS
13 %---14 15 lm1 = 1 - point(1,1) - point(1,2); 16 lm2 = point(1,2); 17 lm3 = point(1,1); 18 pts = [point; lm1 lm3; lm2 lm1]; 19 20 end orbit6_simplex.m 1 function [pts] = orbit6_simplex(point) 2 3 %---4 % ON THE SYMPLEX [0 0; 1 0; 0 1] 5 %---6 % INPUT. 7
%---8 % point : POINT IN THE SYMPLEX
9
%---10 % OUTPUT:
11
%---12 % pts : POINTS OBTAINED FROM SIMPLEX ROTATIONS AND REFLECTIONS
5 pts(i,2) = rand(1,1); 6 while(inpolygon(pts(i,1),pts(i,2),triangle(:,1),triangle(:,2)) == 0) 7 pts(i,1) = rand(1,1); 8 pts(i,2) = rand(1,1); 9 end 10 end 11 end recover_points.m 1 %recupera punti 2 function [pts] = recover_points(file_name) 3 fid = fopen(file_name); 4 pts = fscanf(fid, '%f %f', [2 inf]); 5 fclose(fid); 6 pts = pts'; 7 end r_jacobi.m 1 2 function ab=r_jacobi(N,a,b) 3 4 nu=(b-a)/(a+b+2); 5 mu=2ˆ(a+b+1)*gamma(a+1)*gamma(b+1)/gamma(a+b+2); 6 if N==1
7 ab=[nu mu]; return
8 end 9 10 N=N-1; 11 n=1:N; 12 nab=2*n+a+b; 13 nuadd=(bˆ2-aˆ2)*ones(1,N)./(nab.*(nab+2)); 14 A=[nu nuadd]; 15 n=2:N; 16 nab=nab(n); 17 B1=4*(a+1)*(b+1)/((a+b+2)ˆ2*(a+b+3)); 18 B=4*(n+a).*(n+b).*n.*(n+a+b)./((nab.ˆ2).*(nab+1).*(nab-1)); 19 abadd=[mu; B1; B']; 20 ab=[A' abadd]; 21 end save_points.m 1 function [] = save_points(pts,file_name) 2 fid = fopen(file_name, 'w'); 3 for i=1:size(pts,1)
4 fprintf(fid, '%1.25f %1.25f\n', pts(i,1), pts(i,2));
5 end
6 fclose(fid);
7 end
shakePts.m
1 function [out_pts] = shakePts(in_pts,k)
2 out_pts =[];
3 for i=1:size(in_pts,1)
5 out_pts(i,2) = in_pts(i,2) + (rand(1,1)-1/2)/k;
6 while(out_pts(i,1) < 0+eps || out_pts(i,2) < 0+eps || ... 7 out_pts(i,1)+out_pts(i,2) > 1-eps)
8 out_pts(i,1) = in_pts(i,1) + (rand(1,1)-1/2)/k;
9 out_pts(i,2) = in_pts(i,2) + (rand(1,1)-1/2)/k;
10 end
11 end
12 end
simplexConst.m
1 function [A,b] = simplexConst(degree)
2
3
%---4 % Generating matrix A and vector b for the fmincon linear inequalities.
5 % Every point must satisfy the "A1 x ≤ b1" linear inequality.
6 %---7 8 n_pts = (degree+1)*(degree+2)/2; 9 A1 = [0 -1;1 1;-1 0]; 10 b1 = [0; 1; 0]; 11 12 A2 = A1; 13 for i = 1:n_pts-1 14 A2 = blkdiag(A2, A1); 15 end 16 A = [A2(:,1:2:n_pts*2-1) A2(:,2:2:n_pts*2)]; 17 18 b = b1; 19 for i = 1:n_pts-1 20 b = vertcat(b,b1); 21 end simplexConstOrbit.m
1 function [A,b] = simplexConstOrbit(N_orbit_free)
6
Coordinate BSV
Riferimenti bibliografici
[1] M. G. Blyth, C. Pozrikidis, A Lobatto interpolation grid over the triangle, IMA J. Appl. Math. 71(1), 153-169 (2006)
[2] L. Bos, Bounding the Lebesgue function for Lagrange interpolation in a simplex, J. Approx. Theory, 38 (1983), pp 43-59.
[3] J. P. Boyd, A numerical comparison of seven grids for polynomial interpolation
on the interval, Comput. Math. Appl. 38 (1999), no. 3-4, 3550.
[4] Q. Chen and Ivo Babuska, Approximate optimal points for polynomial
inter-polation of real functions in an interval and in a triangle, Comput. Methods
Appl. Mech. Engrg., 128 (1995), pp 405-417.
[5] W. Gautschi, Orthogonal polynomials: computation and approximation, Num. Math. and Scient. Comput., Oxford University Press, Oxford 2004. [6] W. Heinrichs, Improved Lebesgue constants on the triangle, J. Comput. Phys.
207(2), 625-638 (2005)
[7] J. S. Hesthaven, From electrostatics to almost optimal nodal sets for polynomial
interpolation in a simplex, SIAM J. Numer. Anal. 35, 655-676 (1998)
[8] G. Karniadakis, S.J. Sherwin, Spectral/hp Element Methods for CFD
Nu-merical Mathematics and Computation, Oxford University Press, London,
(1999).
[9] R. Pasquetti, F. Rapetti, Spectral element methods on unstructured meshes, Journal of Scientific Comput. (2010)
[10] A. Sommariva, M. Vianello Computing approximate Fekete points by QR
fac-torizations of Vandermonde matrices, Comput. Math. Appl. 57, 1324-1336
(2009).
[11] M. A. Taylor, B. A. Wingate, R. E. Vincent An algorithm for computing Fekete
points in the triangle, SIAM J. Number. Anal. 38 (2000) 1707-1720
