EmmaBazza-Matricola1144237AnnoAccademico2018-2019 Candidato: Prof.AlviseSommariva Relatore: Cubaturasupoligonicurvilinei UniversitàdeglistudidiPadovaDipartimentodiMatematica“TullioLevi-Civita"CorsodilaureainMatematica

(1)

Università degli studi di Padova

Dipartimento di Matematica “Tullio Levi-Civita" Corso di laurea in Matematica

Cubatura su poligoni curvilinei

Relatore:

Prof. Alvise Sommariva

(2)

(3)

Indice

Introduzione 3

1 Estensione dell’algoritmo indomain per poligoni curvilinei 7

1.1 Definizione del dominio S . . . 7

1.2 Monotone Boxes . . . 8

1.3 Winding algorithm . . . 12

2 Generalizzazione dell’algoritmoindomain 15 2.1 Algoritmo . . . 15

2.2 Test Numerici . . . 16

2.2.1 Unione di domini . . . 16

2.2.2 Differenza simmetrica tra domini . . . 17

2.2.3 Differenza tra domini annidati . . . 18

3 Cubatura 21 3.1 Riduzione dei nodi . . . 21

3.2 Cubatura domini curvilinei . . . 23

4 Esperimenti numerici 27 4.1 Esempi numerici su domini non connessi poligonali e curvilinei . . . 27

4.2 Esempi numerici su domini non semplicemente connessi poligonali e cur-vilinei . . . 31

4.3 Dominio non connesso e non semplicemente connesso . . . 34

(4)

(5)

Introduzione

Nel corso degli ultimi anni si è assistito ad una crescita dell’interesse verso formule di cubatura algebrica su domini curvilinei poligonali Ω. L’applicazione piú naturale riguarda regioni che ben approssimano domini ritenuti non standard, il cui bordo é conosciuto solo in alcuni punti campione ed é regolare a tratti.

Dal punto di vista pratico, per questioni di stabilitá numerica e di definizione dell’in-tegrale, si ricercano formule PI type, dove P indica Positive weights e I indica Inside the domain, ovvero per le quali i nodi sono interni alla regione Ω e i pesi di quadratura sono positivi.

A tale proposito, è stato recentemente introdotto in [4] un algoritmo che determina formule PI type a grado di precisione n nel caso di poligoni con forme complicate, ovvero non convessi, non semplici o non semplicemente connessi. In particolare, se una richiesta è una data cardinalità per la regola, si é in grado di fornire una regola PI type, con grado di precisione ADE pari ad n e numero di nodi pari al piú ad Nn = (n + 1)(n + 2)/2,

per mezzo di un’implementazione numerica del teorema di Tchakaloff. Il relativo codice Matlab fa uso del nuovo ambiente polyshape.

La controparte per spline curvilinee é piú delicata, perció viene ora proposto un algoritmo che fornisce regole PI type utilizzabili non solo su poligoni, ma anche su semplici domini spline curvilinei. Tratteremo esclusivamente formule algebriche, ovvero di natura polinomiale, e proporremo regole aventi grado di precisione ADE pari ad n, ovvero che, in aritmetica esatta, integrano correttamente nella regione Ω i polinomi di grado totale al piú n.

In primo luogo, l’algoritmo proposto determina un insieme sufficientemente denso di punti bivariati {ξi} appartenenti al dominio curvilineo spline S attraverso una nuova

routine indomain per poligoni spline curvilinei. Successivamente, valuta la matrice di Vandermonde V = {Vn(X)}i,j = φj(ξi), con {φi} base polinomiale di grado totale δ su

S. In seguito, calcola i momenti γj =

R

SφjdS e, infine, attraverso un’implementazione

(6)

La trattazione è organizzata secondo il seguente programma.

Nel primo capitolo viene presentato l’algoritmo indomain per domini spline curvilinei S semplicemente connessi.

Il secondo capitolo tratta una generalizzazione dell’algoritmo indomain per domini S ottenuti per mezzo di operazioni algebriche tra domini Si semplicemente connessi.

Nel terzo capitolo è presente un breve richiamo dei principali risultati riguardanti il teorema di Tchakaloff e le sue applicazioni, seguito dalla presentazione del nuovo metodo per la determinazione di regole di cubatura PI type in S.

(7)

Capitolo 1

Estensione dell’algoritmo indomain

per poligoni curvilinei

Il proposito di questo capitolo é descrivere un algoritmo che stabilisca se un punto é o meno all’interno di una regione curvilinea.

Osserviamo che nel caso di domini poligonali, ció é giá stato studiato in letteratura e lo stato dell’arte risulta l’algoritmo di Hormann-Agathos, che é implementato in Matlab nella routine inpolygon.

1.1 Definizione del dominio S

Ci avviamo a presentare un algoritmo il cui obiettivo é valutare la posizione di un punto rispetto ad una classe di poligoni curvilinei S, le cui frontiere sono particolari curve di Jordan.

A tal proposito risultano utili seguenti definizioni, riprese da [8] e [1].

Definizione 1.1. Dati k ∈ N ∪ {∞}, una curva parametrizzata di classe Ck ⊂ Rn_{é una}

applicazione r : I −→ Rn di classe Ck_{, dove I ⊂ R é un intervallo. L’immagine di r(I)} sarà detta sostegno della curva.

Definizione 1.2. Una curva (γ, r) si dice chiusa se I = [a, b] e r(a) = r(b). Definizione 1.3. Una curva (γ, r) si dice piana se γ è contenuta in un piano. In particolare, una curva piana ha parametrizzazione r : I −→ R2_.

Definizione 1.4. Una curva (γ, r) si dice semplice se r è iniettiva in I.

(8)

Teorema 1.1.1. Il sostegno di una curva di Jordan é frontiera di due insiemi aperti nel piano, uno dei quali é limitato e si chiama interno della curva, l’altro illimitato, detto esterno.

L’algoritmo fornisce la valutazione in merito alla posizione di un punto rispetto ad un dominio S ⊂ R2 _{semplicemente connesso, per il quale si richiede che la frontiera ∂S:}

i) sia una curva di Jordan di parametrizzazione r : [a, b] −→ R2_{con r(t) = (˜x(t), ˜y(t));}

ii) esistano una partizione {I(k)_}

k=1,...,M di [a, b], e partizioni{I

(k)

j }j=1,...,Mk di ciascun

I(k), tali che le restrizioni di ˜x, ˜y su ciascun I(k)siano spline di grado δksu ciascuno

dei subintervalli {I(k)

j }j=1,...,Mk.

Di conseguenza, l’algoritmo puó essere applicato per stabilire la posizione di un punto rispetto ad approssimazioni di domini Ω, più generali, regolari a tratti, semplici e sempli-cemente connessi, per mezzo di regioni curvilinee spline S. Infatti, dati i vertici Vk∈ ∂Ω,

k = 1, ..., M + 1, si ottiene ∂Ω ≈ ∂S := SM_k=1Vk _ Vk+1, dove ciascun lato curvilineo

Vk _ Vk+1 é dato da una spline curvilinea di grado δk interpolando un sequenza

ordi-nata di punti di controllo Vk = P1,k, P2,k, ..., Pmk−1.k, Pmk,k = Vk+1 con una adeguata

parametrizzazione che determini ciascun I(k)

j e, di conseguenza, ciascun I(k).

1.2 Monotone Boxes

Il primo passo per valutare se un punto sia interno o esterno alla frontiera ∂S di un dominio del tipo precedentemente descritto, consiste nel calcolare un opportuno dominio dato dall’unione di rettangoli e contenente ∂S. In virtú delle proprietá che introduciamo, ciascun rettangolo del nuovo dominio è denominato monotone box e racchiude un tratto della frontiera ∂S, la cui corrispettiva equazione parametrica ˜x è monotona.

Sia I(k)

j = [tj(k); tj+1(k)]la partizione dell’intervallo [a, b] precedentemente introdotta.

Se ˜x0 cambia segno in (tj(k); tj+1(k)), si definisce N_j(k)= {ti(j,k)}i=1,...,lj,k insieme dei punti

ti(j,k) ∈ (tj(k); tj+1(k)) tali che ˜x0(ti(j,k)) = 0, altrimenti si pone Nj(k)= ∅. Si osservi che

la restrizione di ˜x a I(j,k) _{é un polinomio di grado δ}

k, per cui la derivata ˜x0 esiste.

Si consideri T(j,k) _{= {t}

j(k); tj+1(k)} ∪ Nj(k), supponendo che i suoi elementi Ti(j,k) siano

in ordine crescente. A questo punto, posto J(j,k)

i = [Ti(j,k), Ti+1(j,k)], si introducono i rettangoli B_i(j,k):= min t∈J_i(j,k) ˜ x(t), max t∈J_i(j,k) ˜ x(t) × min t∈J_i(j,k) ˜ y(t), max t∈J_i(j,k) ˜ y(t). (1.1) Si osservi che se N(k)

j = ∅, allora é presente un solo monotone box B (j,k)

1 . Inoltre,

(9)

Figura 1.1: Un dominio S di tipo spline curvilineo e i suoi monotone boxes e massimo per ˜y(t) nella formula (1.1) possono essere facilmente effettuate per mezzo della derivata ˜y0_{, studiando i suoi zeri in [T}

i(j,k), Ti+1(j,k)]e la sua valutazione in Ti(j,k)

e Ti+1(j,k). Per costruzione, si ottiene che la restrizione di ˜x su ciascun monotone box

B(j,k)_i è una funzione monotona.

Osservazione 1. In questa implementazione, ciascun monotone box B(j,k) ha l’ascissa che varia nell’intervallo

[min(˜x(T_i(j,k)), ˜x(T_i+1(j,k))), max(˜x(T_i(j,k)), ˜x(T_i+1(j,k)))].

Se si partiziona [T_i(j,k), T_i+1(j,k)] come Sni,j,k−1

s=1 [T

(j,k)

i,s , T

(j,k)

i,s+1] con

T_i(j,k) = T_i,1(j,k) < T_i,2(j,k) < ... < T_i,n(j,k)

i,j,k = T (j,k) i+1

e si definiscono i monotone boxes

B(j,k)_i,s := [T_i,s(j,k), T_i,s+1(j,k)] × min

t∈[T_i,s(j,k),T_i,s+1(j,k)] ˜ y(t), max t∈[T_i,s(j,k),T_i,s+1(j,k)] ˜ y(t)

e quindi si ottiene ∪B_i,s(j,k) ⊆ B contiene S.

Una volta costruito l’insieme B := {B(j,k)

i }, è possibile cercare di stabilire se i punti

analizzati siano nel dominio S osservando la loro posizione rispetto ai monotone boxes. Infatti, dato P = (Px, Py), si considera Q = (Qx, Qy) 6∈ S con Qx= Px e Qy < Py e

si osserva quante volte il segmento QP interseca ∂S. A tal fine, vengono considerati i monotone boxes

(10)

Dato un generico monotone box Bl= [α (l) 1 , β (l) 1 ] × [α (l) 2 , β (l) 2 ] ∈ B(P ), se Py > β (l) 2 , allora

il punto P è esterno a Bl e necessariamente il segmento QP interseca la frontiera ∂S

esclusivamente una volta in Ble sotto P , in seguito al fatto che ˜x è monotona in Bl per

costruzione.

Alternativamente, se P ∈ Bl, sia t∗ l’unica soluzione dell’equazione polinomiale ˜x = Px.

Dopo di che, • se ˜y(t∗_{) < P}

y, allora il segmento QP interseca la frontiera ∂S esclusivamente una

volta in Bl e sotto P ;

• se ˜y(t∗_{) > P}

y, allora il segmento QP non interseca la frontiera ∂S;

• se ˜y(t∗_{) = P}

y, allora P è sulla frontiera ∂S.

La Figura 1.3 mostra queste quattro possibili conformazioni.

Contando le intersezioni tra la frontiera ∂S e il segmento QP all’interno dei monotone boxes Bl ∈ B(P ), siamo solitamente in grado di determinare se il punto P è interno al

dominio S. Come conseguenza di un ben noto Teorema di Jordan, un numero dispari di intersezioni totali indica che il punto si trova all’interno del poligono curvilineo.

Osserviamo che sussistono casi patologici che non permettono al precedente algoritmo di stabilire la posizione del punto P rispetto al poligono curvilineo:

i) Il dominio S può presentare un cambio locale verticale di frontiera da sinistra a destra (o viceversa, da destra a sinistra), ovvero, dato Sk = (˜x(tk), ˜y(tk)) ∈ ∂S,

vale lim t→t−_k ˜ y0_{(t) · lim} t→t+_k ˜ y0_{(t) < 0.}

ii) possono esserci punti P dove la frontiera è localmente un segmento verticale. In questi due casi non è facile determinare quante volte la linea l attraversi ∂S sotto P, ed è quindi necessario ricorrere al winding algorithm.

Osservazione 2. Nell’algoritmo, per stabilire se un punto P = (P_x, Py) appartiene alla

frontiera, si risolve una equazione polinomiale ˜x(t∗) = Pxe poi si testa se ˜y(t∗) = Py.

(11)

Figura 1.2: Evidenziamo un monotone box, per poi osservare le possibili posizioni del punto P rispetto ad esso e alla frontiera.

Figura 1.3: Illustriamo le possibili posizioni del punto P rispetto alla frontiera e al monotone box evidenziato. Ordinatamente incontriamo:

••••• Il punto é esterno al monotone box (in alto a sinistra).

(12)

1.3 Winding algorithm

Nel caso in cui si presenti una situazione per cui é difficile determinare quante volte il segmento QP attraversi ∂S, si ricorre al winding algorithm, ovvero una procedura basata sul Winding Theorem.

Definizione 1.6. Sia γ : [a, b] ⊆ R −→ C un cammino chiuso, e sia P 6∈ γ. Il Winding Number di γ rispetto a P é W (γ, P ) := 1 2πı Z γ 1 z − Pdz

Proposizione 1.3.1. Il Winding Number di un cammino chiuso é una funzione a valori in Z.

Dimostrazione. Sia γ : [a, b] ⊆ R −→ C un cammino chiuso e γ∗ := γ([a, b]) il suo sostegno. Dato z ∈ C \ γ∗_{, poniamo}

φ(t) = e

Rt a

γ0(s)

γ(s)−zds _{∀t ∈ [a, b]}

Segue dal Teorema Fondamentale del Calcolo che in ogni punto di continuitá di γ0 _vale

φ0(t) = φ(t) γ 0_(t) γ(t) − z = φ(t) (γ(t) − z)0 γ(t) − z ⇐⇒ φ0(t) · (γ(t) − z) = φ(t) · (γ(t) − z)0 ⇐⇒ φ0(t) · (γ(t) − z) − φ(t) · (γ(t) − z)0= 0 ⇐⇒ φ(t) (γ(t) − z) 0 = 0

Quest’ultima formula vale in [a, b] tranne al più un numero finito di punti, inoltre la funzione t 7→ φ(t)

(γ(t)−z) é continua in [a, b]. Segue quindi che

φ(t) (γ(t) − z) = φ(a) (γ(a) − z) ∀t ∈ [a, b] per cui φ(b) (γ(b) − z) = φ(a) (γ(a) − z) Essendo γ(a) = γ(b), segue φ(a) = φ(b).

Concludendo 1 = φ(a) = φ(b) = e Rb a γ0(s) γ(s)−zds _{= e}2πıW (γ,z)

(13)

Proposizione 1.3.2. Sia γ : [a, b] −→ R2 una curva chiusa, e sia P = (Px, Py) 6∈ γ, allora W (γ, P ) = 1 2π Z γ (x − Px)dy − (y − Py)dx (x − Px)2+ (y − Py)2

Dimostrazione. Dati z = x + ıy e P = Px+ ıPy, si procede per sostituzione

W (γ, P ) := 1 2πı Z γ 1 z − Pdz = 1 2πı Z γ 1 (x + ıy) − (Px+ ıPy) d(x + ıy)

Si raccoglie ora la ı al denominatore e si moltiplicano numeratore e denominatore per il coniugato di quest’ultimo, ottenendo

W (γ, P ) = 1 2πı Z γ dx + ıdy (x − Px) + ı(y − Py) ·(x − Px) − ı(y − Py) (x − Px) − ı(y − Py) , ovvero: W (γ, P ) = 1 2π Z γ (x − Px)dy − (y − Py)dx (x − Px)2+ (y − Py)2 .

L’algoritmo che proponiamo, attraverso una Gauss-Legendre shifted rule di sufficiente grado di precisione, calcola W (γ, P ), che abbiamo dimostrato essere un intero. Se tale quantità è dispari, allora il punto appartiene a S, altrimenti non è interno al dominio.

La Figura 1.4 illustra la valutazione effettuate dall’implementazione dell’algoritmo in merito alle posizioni di un generico insieme di punti rispetto alla curva.

-25 -20 -15 -10 -5 0 5 10 15 20 25 -20 -15 -10 -5 0 5 10 15 20

(14)

(15)

Capitolo 2

Generalizzazione dell’algoritmo

indomain

2.1 Algoritmo

Presentiamo ora un algoritmo in grado di fornire una valutazione in merito alla po-sizione di un punto rispetto ad un dominio, anche nel caso in cui tale dominio non semplicemente connesso, o non connesso.

In particolare, indicati con S1, S2 due poligoni curvilinei con le specifiche indicate

nel capitolo precedente, siamo in grado di effettuare operazioni di somma o differenza di insiemi, con particolare attenzione per la differenza simmetrica. Tali operazioni tra insiemi ci permettono di compiere una valutazione in merito alla posizione di un punto rispetto a domini recanti buchi o composti da più parti disgiunte.

Dato un punto P = (Px, Py), per stabilire se esso sia interno, esterno o sulla

fron-tiera di un dominio S, ottenuto tramite operazioni algebriche tra n domini {Si}i=1,...,n,

ciascuno del tipo descritto nel precedente capitolo, si applica l’algoritmo presentato in precedenza ad ogni dominio Si.

Di seguito, se si deve valutare se il punto P appartiene a i) Si∪ Sj con i 6= j, si verifica se P appartiene a Si o a Sj;

ii) Si\ Sj con i 6= j, si verifica che P appartenga a Si, ma non a Sj;

iii) (Si \ Sj) ∪ (Sj \ Si) con i 6= j, si verifica che P appartenga a Si, ma non a Sj,

oppure che appartenga ad Sj, ma non a Si.

(16)

2.2 Test Numerici

Prima di procedere, si rende necessario presentare un operatore Matlab, il cui nome è cell array, su cui si fonda l’algoritmo che ci prestiamo ad analizzare.

Il cell array è un data type di Matlab che colleziona dati indicizzati in contenitori chiamati celle. Ciascuna cella può contenere ogni tipo di dato, e celle diverse possono riferirsi a dati di tipo diverso; in particolare è possibile inserire un cell array come con-tenuto di una cella di un altro cell array.

Se si vuole creare un cell array contenente una serie di dati si utilizza l’operatore di costruzione { } e si inseriscono al suo interno i dati separati da una virgola. Se invece si vuole inserire un dato in una specifica posizione di un array si utilizza il coman-do nome_array( ). Per accedere ad un dato conoscencoman-done la posizione, si utilizza il comando nome_array{ }.

Il dominio S é, infatti, descritto da un cell array che presenta come elementi i vari domini {Si}i=1,...,n da cui esso viene generato. L’algoritmo accede in ordine ad ogni

elemento di tale cell array e compie una valutazione su ciascuno di essi, riferendosi sempre al medesimo punto P o al medesimo insieme di punti {Pi}i=1,...,k. Le valutazioni

di appartenenza o meno al dominio Si sono poi memorizzate in un vettore in_all = [ ],

secondo la seguente convenzione:

i) in_all(j) = 1 se Pj appartiene a Si

ii) in_all(j) = 0 se Pj non appartiene a Si

e sommate alle valutazioni precedenti al variare del dominio Si.

Al termine di tale processo il vettore in_all presenta in posizione k un numero intero, se tale valore é dispari allora il punto Pk é interno al dominio complessivo S, altrimenti

é esterno.

Per quando riguarda l’appartenenza alla frontiera, se la valutazione relativa ad un punto Pk= P (k, :)é on(k) = NaN per un qualsiasi dominio Si tra i domini che generano

S, allora verrá memorizzato on_all(k) = NaN. Infatti, un punto vicini alla frontiera di un qualsiasi Si é vicino alla frontiera del dominio S.

Di seguito presentiamo alcuni esempi, con l’intento di illustrare come l’algoritmo possa far fronte alle diverse operazioni insiemistiche tra domini Si, del tipo introdotto

nel precedente capitolo.

2.2.1 Unione di domini

Dati dei domini {Si}i=1,..,m tali che Si∩ Sj = ∅se i 6= j, si considera S = Sm_i=1Si. Il

(17)

interpre-tazione, é evidente come un generico punto P = (Px, Py)sia interno al dominio S se solo

se é interno a un qualsiasi dominio Si.

Consideriamo un dominio formato dall’unione di due poligoni curvilinei connessi, le cui frontiere sono definita da spline cubiche, che soddisfano la condizione not-a-knot. Cia-scuna spline é stata generata interpolando venti punti di controllo equispaziati, ottenuti a partire dalle equazioni parametriche

x1(t) = cos(t), y1(t) = sin(t) e x2(t) = 3 5cos(t) + 1 5cos(−3t) + 2, y2(t) = 3 5sin(t) + 1 5sin(−3t)

valutate in tk = kπ/10 ∈ [0, 2π] k = 1, ..., 20 e rappresentanti rispettivamente una

circonferenza ed un astroide.

La Figura 2.1 mostra, mediante una diversa colorazione, quali punti, tra i 1000 testati, siano interni al dominio S; sono inoltre visibili i monotone boxes utilizzati.

-1 -0.5 0 0.5 1 1.5 2 2.5 3 -1.5 -1 -0.5 0 0.5 1 1.5

Figura 2.1: Dominio S consistente nell’unione di domini.

2.2.2 Differenza simmetrica tra domini

Dati due domini S1 e S2 tali che S2∩ S1 6= ∅, si considera S = (S1\ S2) ∪ (S2\ S1).

Il dominio S risulta quindi essere composto dalle parti dei due domini che non sono in comune, e quindi un generico punto P = (Px, Py) risulta interno ad S se e solo se é

interno al dominio S1 e al contempo esterno ad S2, oppure interno ad S2 e al contempo

(18)

Come in precedenza, illustriamo il comportamento dell’algoritmo. Consideriamo un dominio formato dalla differenza simmetrica di due poligoni curvilinei connessi, le cui frontiere sono definita da spline cubiche, che soddisfano la condizione not-a-knot. Anche in questo caso, ciascuna spline é stata generata interpolando venti punti di controllo equispaziati, ottenuti a partire dalle equazioni parametriche

x1(t) = cos(t) + 2.3, y1(t) = sin(t) e x2(t) = 1 2(1 − 2 cos(t) + cos(2t)), y2(t) = 1 2(2 sin(t) − sin(2t))

valutate in tk = kπ/10 ∈ [0, 2π] k = 1, ..., 20 e rappresentanti rispettivamente una

circonferenza ed una cardioide.

Come si vede dalla Figura 2.2, abbiamo testato su 1000 punti l’algoritmo indomain, ed é evidente dalla colorazione la correttezza del risultato ottenuto.

0 0.5 1 1.5 2 2.5 3 3.5 -1.5 -1 -0.5 0 0.5 1 1.5

Figura 2.2: Dominio S consistente nella differenza simmetrica di due domini.

2.2.3 Differenza tra domini annidati

Dati due poligoni curvilinei S1 e S2 tali che S2 ⊂ S1, consideriamo S = S1 \ S2. Il

dominio S risulta quindi essere il dominio S1 forato, mentre il dominio S2 rappresenta il

foro. Risulta evidente come un generico punto P = (Px, Py) sia interno al dominio solo

se é interno al dominio S1 e, al contempo, esterno ad S2, come nei test precedenti.

(19)

me-diante l’interpolazione di venti punti di controllo equispaziati, partendo dalle equazioni parametriche di una circonferenza

x1(t) = cos(t), y1(t) = sin(t)

valutate in tk = kπ/10 ∈ [0, 2π] k = 1, ..., 20; mentre come poligono curvilineo S2

consideriamo la spline cubica, ottenute mediante l’interpolazione di sei punti di controllo equispaziati, partendo dalle equazioni parametriche di un deltoide

x2(t) = 1 3 2 3cos(t) − 1 3cos(2t) −1 2, y2(t) = 1 3 2 3sin(t) + 1 3sin(2t) valutate in tj = jπ/3 ∈ [0, 2π] j = 1, ..., 6.

La Figura 2.3 mostra, per mezzo di una colorazione differenziata, quali punti siano interni al dominio S, ottenuto attraverso tale differenza tra domini.

-1.5 -1 -0.5 0 0.5 1 1.5 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Figura 2.3: Dominio S consistente nella differenza di due domini.

Per mostrare le capacità del nostro algoritmo, consideriamo piú in generale il caso di npoligoni curvilinei {Si}i=1,...,m tali che

Sm ⊂ Sm−1 ⊂ ... ⊂ S1,

si considera S = S1\ S2\ ... \ Sm. Il dominio S risulta quindi essere l’unione dei domini

di indice dispari forati, e per ciascuno di essi il foro é rappresentato dal dominio di indice pari successivo. I vari domini non hanno punti in comune, si tratta quindi di un’unione di domini forati disgiunti. Chiarita questa interpretazione, é evidente come un generico punto P = (Px, Py)sia interno al dominio solo se é interno al dominio Si con i dispari e,

(20)

La Figura 2.4 mostra quali punti siano interni al dominio S, ottenuto attraverso una differenza tra piú poligoni curvilinei, rappresentati da spline cubiche che approssimano circonferenze e un deltoide.

(21)

Capitolo 3

Cubatura

3.1 Riduzione dei nodi

Trattiamo ora la teoria della compressione della misura, ovvero ci proponiamo di mo-strare come, da una formula di quadratura con alta cardinalitá, pesi positivi e grado di precisione δ, se ne possa estrarre un’altra con il medesimo grado di precisione, pesi positivi, ma con cardinalitá al piú uguale alla dimensione dello spazio vettoriale Pd

δ.

Iniziamo presentando una versione discreta del Teorema di Tchakaloff:

Teorema 3.1.1. Sia µ una misura discreta multivariata il cui supporto è un insieme finito X = {Pi} ⊂ Rd, i = 1, ..., M , con corrispondenti pesi positivi λ = {λi}, i =

1, ..., M , M = card(X) > Nδ e Nδ = dim(Pdδ) = δ+d

d . Allora, esiste una formula

di cubatura per la misura discreta µ, con nodi {Qj} ⊂ X e pesi positivi w = {wj},

j = 1, ..., m con m ≤ Nδ tale che

Z X p(x)dµ = M X i=1 λip(Pi) = m X j=1 wjp(Qj) ∀p ∈ Pdδ.

Qui e in seguito, con Pd

δsi indica lo spazio dei polinomi d-variati di grado non superiore

a δ.

Una delle richieste più comuni, per questioni di stabilità, è che P |wj|rimanga

limi-tata o cresca molto lentamente con δ.

Nelle nostre ipotesi tale proprietá é garantita dal fatto che i pesi sono positivi. Infatti, se la formula di quadratura ha grado di precisione almeno δ,

X

|w_j| =Xwj =

Z

1dµ < +∞.

(22)

Se {φi} è una base di Pd_δ, definita la matrice rettangolare di Vandermonde

V = (vij) = (φj(Pi)), i = 1, .., M j = 1, ..., Nδ,

si desidera calcolare un certo vettore w tale che, posto γ = VT_λ,

VTw = γ

con al più n componenti non nulle. Tali componenti non nulle permettono di individuare i nodi {Qj} ⊆ X, che definiremo in seguito CATCH points (acronimo di

Caratheodory-Tchakaloff) di X.

L’esperienza numerica mostra come il metodo dei Minimi Quadrati Non Negati-vi (NNLS) sia il metodo piú performante per indiNegati-viduare i CATCH points a gradi δ moderati. Tale approccio consiste nel ricercare il vettore w∗ _{tale che}

kVTw∗− γk2= min

w kV

T_{w − γk}

2, w ≥ 0.

La soluzione w∗ _{puó essere calcolata attraverso l’algoritmo di Lawson-Hanson (si}

consulti [7]). La sua applicazione comporta un residuo = kVT_w∗_{− γk} _{contenuto per}

applicazioni a gradi moderati; in particolare, < 10−14 _{per δ ≤ 30 nel caso di domini}

semplici e semplicemente connessi. Vi sono varie versioni di codici NNLS disponibili in Matlab. Una di queste é la funzione lsqnonneg, basata sull’algoritmo di Lawson-Hanson, una cui versione open source é presente nel pacchetto NNLSlab scaricabile da [10].

Se si lavora con domini bucati o domini costituiti da piú regioni distinte e disgiunte, possono nascere dei problemi in seguito all’applicazione dell’algoritmo di Lawson-Hanson attraverso la funzione lsqnonneg. Se non è un problema ricorrere a pesi negativi, si può ricorrere ad un metodo QR che assicura tempi migliori e formule di cubatura che solitamente hanno un numero di condizionamento discretamente buono.

Un metodo alternativo per il calcolo dei CATCH points é il Linear Programming method (LP). Tale approccio consiste nel risolvere attraverso l’algoritmo del simplesso, il sistema lineare:

minu≥0cTu

VTu = b, u ≥ 0

con i vincoli che identificano un politopo in RN _{e il vettore c scelto per essere linearmente}

indipendente dalle righe di Vt_.

(23)

3.2 Cubatura domini curvilinei

Descriviamo, quindi, un algoritmo che computa una formula di cubatura di grado n su S, un dominio del tipo presentato in precedenza. Si vuole costruire una formula di cubatura tale che

Z S pn(x, y)dS = Nn X i=1 wipn(xi, yi)

per ogni polinomio bivariato pn di grado totale al piú n. In particolare, si vuole che la

formula abbia nodi (xi, yi) appartenenti a S, che siano al piú (n + 1)(n + 2)/2, e con i

rispettivi pesi wi positivi. Tale formula sarà stabile in quanto

cond({wi}) = PNn i=1|wi| PNn i=1wi = 1.

L’algoritmo, quindi, determina una regola PI type, dove P indica Positive weights e I indica Inside the domain.

Si inizia calcolando i momenti γi di una prefissata base polinomiale di P2n, {φi} con

i = 1, ..., ν = (n + 1)(n + 2)/2, di grado n su S, ovvero γi =

Z

S

φi(x, y)dS.

Nei nostri esempi, come base polinomiale {φj}é stata usata la base {Tp(α1(x))Tq(α2(y))}

p + q ≤ ncon (x, y) ∈ R, dove:

• R = [a1, b1] × [a2, b2]rappresenta il più piccolo rettangolo con lati paralleli agli assi

delle ascisse e delle ordinate, contenente il dominio;

• Th(·) = cos(h arccos(·))è il polinomio di Chebyshev di grado h;

• αi(s) = 2s−b_b_i_−ai−a_i i, s ∈ [ai, bi], i = 1, 2.

(24)

per p = 1 Z Tp(α1(x))dx = b1− a1 4 · α 2 1(x), mentre, per p ≥ 2 Z Tp(α1(x))dx = b1− a1 2 · p p2_{− 1}Tp+1(α1(x)) − x p − 1Tp(α1(x)) . Fissando I(k) j = [t (k) j , t (k) j+1], Pk,j = (˜x(t(k)j ), ˜y(t (k)

j )), e indicando con Pk,j _ Pk,j+1 l’arco

di ∂S che collega Pk,j a Pk,j+1, otteniamo

γi= I ∂S Φi(x, y)dy = X k,j Z Pk,j_Pk,j+1 Φi(x, y)dy = X k,j Z t(k)_j+1 t(k)_j Φi(˜x(t), ˜y(t))˜y0(t)dt Si osserva che:

i) dal momento che φi é un polinomio di grado n, Φi é un polinomio di grado totale

n + 1;

ii) nell’intervallo I(k)

j , sia ˜x sia ˜y sono polinomi di grado δk.

Ciascun integrale ha quindi quale integranda un polinomio di grado (n + 1)δk+ δk−

1 = (n + 2)δk− 1, che puó essere calcolato numericamente mediante una formula di

Gauss-Legendre con b(n + 2)δk/2cpunti.

Si prosegue definendo una griglia nel piú piccolo rettangolo R contenete il dominio S, facilmente calcolabile a partire dai monotone boxes. Se il grado di precisione desiderato é n, si fissa k = bn1.5_c _{e si considerano i punti P = ((P}

x)i, (Py)j) con (Px)i= a1+ i a2− a1 k − 1 , (Py)j = b1+ j b2− b1 k − 1 . Si ottiene una griglia di punti k-equispaziati in ciascuna direzione.

Successivamente, si stabilisce quali punti P siano strettamente interni al dominio S, ricorrendo alle funzioni definite nei precedenti capitoli. In tal modo si delinea l’insieme P∗ _{= {P}∗

1, ..., Pm∗}.

Si procede costruendo la matrice di Vandermonde V = {φj(Pi∗)}. Un eventuale

cat-tivo condizionamento viene trattato attraverso una ortogonalizzazione QR della matrice V. A tale scopo, posto γ = (γ1, ..., γν), si applica la fattorizzazione QR alla matrice

V ∈ Rm×ν, ovvero

V = QR, Q ∈ Rm×ν, R ∈ Rν×ν. con Q matrice ortogonale e R matrice triangolare superiore.

Quindi, nell’analisi, si sostituisce alla matrice V la matrice Q e si calcolano i nuovi momenti

(25)

Al crescere della dimensione di V , la matrice Q potrebbe non essere ortogonale, ma sarà in ogni caso meglio condizionata.

Giunti a questo punto, si applica la routine lsqnonneg al sistema lineare QTw = ˜γ,

che risolve la formula di Tchakaloff con nodi {P∗

i}i=1,...,m = {(xi, yi)}i=1,...,m e pesi

{wi}i=1,...,m, testando infine se tale regola é tale che

γ_s∗=

m

X

i=1

wiφs(xi, yi), s = 1, ..., m

sia una buona approssimazione di γs, ovvero

kγ_s∗− γsk ≤ toll (3.1)

dove toll é la tolleranza fissata dall’utente, solitamente nell’ordine di 10−12_.

Nel caso in cui non sia soddisfatta la condizione in 3.1, si procede definendo una grigia piú fine, aggiungendo punti all’insieme P∗_{, e reiterando il calcolo dei V e}

(26)

(27)

Capitolo 4

Esperimenti numerici

L’obiettivo di questo capitolo é quello di testare le routines indomain, per la valutazione della posizione dei punti rispetto al dominio considerato, e l’algoritmo per la cubatura.

Tutte le routines Matlab per gli esperimenti numerici sono disponibili in [5] e sono state testate in un computer con CPU AMD A8 da 2.00 Ghz e con 8.00 GB di RAM.

4.1 Esempi numerici su domini non connessi poligonali e

curvilinei

Iniziamo considerando il dominio non connesso S(1)

1 , mostrato in Figura 4.1. -1 -0.5 0 0.5 1 1.5 2 2.5 -1 -0.5 0 0.5 1

Figura 4.1: Il dominio poligonale S(1)

1 , la griglia di punti P rappresentati in verde se

interni, in rosso se esterni al dominio, e i nodi della formula di cubatura PI type per n = 5, segnati in nero.

(28)

esagono regolare, ottenuto attraverso una spline di primo grado che interpola i vertici Vk= (cos(tk) , sin(tk)) con tk=

kπ

3 k = 1, ..., 6;

mentre il secondo è una curva spline di primo grado ottenuta interpolando i vertici Uk= 3 5cos(tk) + 1 5cos(−3tk) + 2 , 3 5sin(tk) + 1 5sin(−3tk) con tk= kπ 5 k = 1, ..., 10. Testeremo l’algoritmo su tre diverse funzioni, aventi diversi livelli di regolarità:

f1(x, y) = (a0x + b0y)n (4.1)

f2(x, y) = exp(−((x − x0)2+ (y − y0)2)) (4.2)

f3(x) = ((x − x0)2+ (y − y0)2)0.5 (4.3)

con n pari al grado di precisione dell’algoritmo, a0= 0.5, b0= 0.2e (x0, y0) = (0.2, 0.8) ∈

S₁(1). La prima funzione è un polinomio di grado n, la seconda una funzione analitica, mentre la terza è una funzioni di classe C0_{, in quanto (x}

0, y0) appartiene al dominio di

integrazione.

Riportiamo in Tabella 4.1 il numero di nodi utilizzati dal nuovo algoritmo, distin-guendo tra interni (nella colonna Int) ed esterni (nella colonna Ext), oltre al numero di nodi precedente alla compressione (nella colonna #). Si osservi come l’algoritmo sia stato costruito per utilizzare unicamente nodi interni al dominio di integrazione.

Riportiamo anche il numero di condizionamento (nella colonna Cond) e il residuo (nella colonna Res) al variare del grado di precisione. Si osservi come l’applicazione dell’al-goritmo di Lawson-Hanson, attraverso la funzione lsqnonneg, assicuri che il numero di condizionamento rimanga pari ad 1.

Tali valori non variano al variare della funzione considerata.

Infine, è riportato anche il tempo in secondi impiegato dal calcolatore per l’esecuzione dell’algoritmo (nella colonna CPU ).

n Int Ext # Cond Res CPU 5 21 0 53 1 2.1e-16 7.1e-02 10 66 0 469 1 1.3e-16 8.8e-02 15 136 0 1702 1 2.7e-16 5.2e-01 20 231 0 13225 1 1.4e-16 6.8e+01 25 351 0 26268 1 2.3e-16 7.7e+01

(29)

La Tabella 4.2 invece presenta l’errore relativo commesso utilizzando il nuovo algorit-mo, al variare del grado di precisione e della funzione. In altri termini, indicato con I(fk)

n

il valore fornito dal metodo e con I(fk) quello ottenuto mediante la routine disponibile in

[10] a grado 100, poniamo ERk(n) = |I(fk) n − I(fk)| I(fk) qualora I(fk)_{6= 0}. n ER1 ER2 ER3

5 6.22e-16 1.83e-03 4.67e-03 10 4.42e-15 2.78e-06 8.61e-06 15 3.06e-15 2.82e-07 2.53e-05 20 9.78e-14 8.33e-11 7.87e-05 25 1.39e-13 1.36e-13 4.95e-05

Tabella 4.2: Errore relativo commesso al variare di della funzione f tra (4.1), (4.2) e (4.3), rispetto ad S(1)

1 .

I risultati esposti non devono sorprendere. In effetti, in virtù della regolarità della funzione, è quanto ci si aspetta dai Teoremi di Jackson.

I risultati ottenuti suggeriscono che il nuovo algoritmo fornisca una buona valutazione della cubatura su domini poligonali, riducendo, inoltre, sensibilmente il numero di nodi e mantenendo il numero di condizionamento pari ad 1.

-1 -0.5 0 0.5 1 1.5 2 2.5 -1 -0.5 0 0.5 1

Figura 4.2: Il dominio curvilineo S(3)

(30)

Di seguito riportiamo nella Tabella 4.3 e nella Tabella 4.4 gli stessi esperimenti nu-merici, ma condotti su un dominio S(3)

1 composto dall’unione di due poligoni curvilinei

spline di terzo grado, soddisfacenti la condizione not-a-knot. La regione è raffigurata nella Figura 4.2.

Il primo poligono curvilineo é ottenuto interpolando i vertici Vk = (cos(tk) , sin(tk)) con tk=

kπ

10 k = 1, ..., 20, mentre il secondo si ottiene interpolando i vertici

Uk= 3 5cos(tk) + 1 5cos(−3tk) + 2 , 3 5sin(tk) + 1 5sin(−3tk) con tk= kπ 10 k = 1, ..., 20. Anche in questo caso abbiamo testato l’algoritmo sulle tre funzioni illustrate in pre-cedenza (4.1), (4.2) e (4.3), fissando i parametri a0= 0.5, b0 = 0.2e (x0, y0) = (2.5, 0) ∈

S₁(3).

Tabella 4.3: Grado di precisione (n), numero di nodi interni (Int), numero di nodi esterni (Ext), numero di nodi precedente alla compressione (#), numero di condizionamento (Cond), residuo (Res) e tempo impiegato dal calcolatore (CPU), rispetto al dominio S₁(3).

n ER1 ER2 ER3

Tabella 4.4: Errore relativo commesso al variare di della funzione f tra (4.1), (4.2) e (4.3), rispetto a S(3)

1 .

(31)

troppo densa del dominio. La cardinalitá delle formule é pari al piú alla dimensione dello spazio polinomiale P2

n, ovvero (n+1)(n+2)/2. Tutte le formule risultano di PI type, come

indicato dalla teoria, infatti tutti i nodi risultano interni e il numero di condizionamento é sempre pari ad 1.

Se non è un problema ricorrere a pesi negativi, si può impiegare un metodo QR per la risoluzione del sistema lineare. Tale metodo assicura tempi di calcolo migliori e formule di cubatura che solitamente hanno un numero di condizionamento discretamente buono.

4.2 Esempi numerici su domini non semplicemente connessi

poligonali e curvilinei

Proseguiamo la nostra verifica, ripetendo i medesimi esperimenti numerici su un dominio poligonale non semplicemente connesso S(1)

2 , del tipo rappresentato in Figura 4.3.

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8

Figura 4.3: Il dominio poligonale S(1)

Il poligono considerato si ottiene per differenza tra due esagoni. Il piú esterno, che rappresenta il poligono forato, é regolare e consiste in una spline di primo grado ottenuta interpolando i vertici

Vk= (cos(tk) , sin(tk)) con tk=

kπ

3 k = 1, ..., 6,

(32)

Di conseguenza, analizziamo il difficile caso di un poligono non semplicemente con-nesso. Anche in questo caso abbiamo testato l’algoritmo su tre diverse funzioni, aventi diversi livelli di regolarità. Facciamo riferimento alle tre funzioni presentate in precedenza (4.1), (4.2), (4.3) ponendo a0= 4.5, b0 = 0.2 e (x0, y0) = (0.3, −0.4) ∈ S2(1).

Tabella 4.5: Grado di precisione (n), numero di nodi interni (Int), numero di nodi esterni (Ext), numero di nodi precedente alla compressione (#), numero di condizionamento (Cond), residuo (Res) e tempo impiegato dal calcolatore (CPU), rispetto al dominio S₂(1).

n ER1 ER2 ER3

2 .

Nel caso di funzione polinomiale, l’errore relativo é contenuto, ma non dell’ordine della precisione di macchina. Se peró confrontiamo i risultati prodotti dal nuovo algoritmo con quelli ottenuti utilizzando l’algoritmo per la cubatura su poligoni (presente in [10]), si ottiene un errore relativo dell’ordine della precisione di macchina.

Di seguito riportiamo nella Tabella 4.7 e nella Tabella 4.8 gli stessi esperimenti nume-rici, ma condotti su un dominio S(3)

2 ottenuto per differenza di poligoni curvilinei spline

(33)

-1 -0.5 0 0.5 1 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Il poligono curvilineo esterno, che rappresenta il poligono forato, é ottenuto interpo-lando i vertici

Vk= (cos(tk) , sin(tk)) con tk=

kπ

10 k = 1, ..., 20, mentre il secondo, che rappresenta il foro, è ottenuto interpolando i vertici

Uk= 2 9cos(tk) − 1 9cos(2tk) −1 2 , 2 9sin(tk) + 1 9sin(2tk) con tk= kπ 3 k = 1, ..., 6.

Abbiamo infine testato l’algoritmo sulle tre funzioni illustrate in precedenza (4.1), (4.2), (4.3), fissando i parametri a0 = 12, b0 = 5 e (x0, y0) = (0.8, 0.2) ∈ S2(3).

(34)

n ER1 ER2 ER3

2 .

Tutte le formule risultano di PI type, come indicato dalla teoria, infatti tutti i nodi risultano interni e il numero di condizionamento é sempre pari ad 1. Inoltre, i risultati mostrano come, in tempi ragionevoli, sia possibile estrarre anche su domini non sem-plicemente connessi, formule di cubatura partendo da una discretizzazione non troppo densa del dominio. Anche in questo caso la cardinalitá delle formule é pari al piú alla dimensione dello spazio polinomiale P2

n, ovvero (n + 1)(n + 2)/2.

Nuovamente, é possibile ricorrere ad un metodo QR per la risoluzione del sistema lineare, ricorrendo a pesi negativi e quindi rinunciando al numero di condizionamento pari ad 1.

4.3 Dominio non connesso e non semplicemente connesso

Proseguiamo le verifica considerando una regione S(3)

3 non connessa e non semplicemente

connessa, ottenuta per differenza di piú domini annidati, del tipo raffigurato in Figura 4.5. -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

(35)

Tale dominio S(3)

3 consiste nell’unione di due domini curvilinei forati, il più piccolo

dei quali è posto all’interno del foro del dominio più esteso.

Quest’ultimo presenta come frontiera esterna una spline cubica che interpola Vk= (2 cos(tk) , 2 sin(tk)) con tk =

kπ

10 k = 1, ..., 20,

mentre come frontiera interna, che descrive il foro, presenta una spline cubica che inter-pola i punti Uk = 10 9 cos(tk) − 5 9cos(2tk) −1 5 , 10 9 sin(tk) + 5 9sin(2tk) con tk = kπ 3 k = 1, ..., 6.

La regione interna, invece, é descritta da due spline cubiche interpolanti rispettivamente Wk = 2 5cos(tk) − 1 5 , 2 5sin(tk) con tk= kπ 10 k = 1, ..., 20, e Tk= 1 5cos(tk) − 1 5 , 3 20sin(tk) con tk= kπ 10 k = 1, ..., 20,

le quali indicano rispettivamente il poligono curvilineo forato e il foro. Tutte le spline cubiche soddisfano la condizione not-a-knot.

Anche in questo caso abbiamo effettuato i test sulle tre funzioni illustrate in prece-denza (4.1), (4.2) e (4.3), fissando i parametri a0= 1.2, b0= 1.5 e (x0, y0) = (1.2, 0.2) ∈

S₃(3).

Riportiamo nella Tabella 4.9 e nella Tabella 4.10 gli stessi esperimenti numerici svolti in precedenza, condotti ora sul dominio S(3)

3

(36)

n ER1 ER2 ER3

3 .

I risultati mostrano come, in tempi ragionevoli, sia possibile estrarre anche su domini particolari come quello preso in esame, formule di cubatura partendo da una discretizza-zione non troppo densa del dominio. Anche in questo caso tutte le formule risultano di PI type e l’impiego di un metodo QR per la risoluzione del sistema lineare comporterebbe un accorciamento dei tempi di calcolo a discapito della positivitá dei pesi.

4.4 Valutazioni indomain

Come test finale, mostriamo il tempo in secondi necessario alla CPU per eseguire m valutazioni indomain. Abbiamo preso in esame le cinque regioni S(1)

1 , S (3) 1 , S (1) 2 , S (3) 2 e

S₃(3) descritte nelle precedenti sezioni, ed abbiamo eseguito diverse valutazioni indomain, variando il numero di punti da testare e monitorando i tempi impiegati dalla CPU per compiere la suddetta valutazione. I risultati sono riportati nella Tabella 4.11.

La routine Matlab incurvpolygonhole, reperibile in [5], che implementa gli algorit-mi introdotti nei prialgorit-mi due capitoli, valuta quali punti di un dato insieme siano interni ad un poligono curvilineo non connesso o non semplicemente connesso.

m S₁(1) S₁(3) S₂(1) S₂(3) S(3)₃ 102 _2.6e-02 _2.8e-02 _2.2e-02 _1.9e-02 _4.3e-02

103 6.4e-02 2.9e-02 7.1e-02 2.5e-02 5.4e-02 104 4.2e-01 8.7e-02 5.3e-01 8.3e-02 2.1e-01 105 _{4.1e+00 6.9e-01 5.3e+00 6.8e-01 1.7e+00}

Tabella 4.11: Tempo impiegato dalla CPU per la valutazione, attraverso l’algoritmo indomain, di m punti rispettivamente in S₁(1), S₁(3), S₂(1), S₂(3) e S₃(3).

I tempi di calcolo rimangono contenuti anche nel caso di valutazioni indomain rispetto a regioni complesse quali S(3)

3 . Il confronto di tali risultati con quelli ottenuti dalle

(37)

Bibliografia

[1] Abate M., Tovena F., Curve e Superfici, Springer, (2006).

[2] Bak J., Newman D. J., Complex Analysis, Undergradued Texts in Math., Springer Verlag, Inc. New York, (1982).

[3] Baker J. A., Plane Curves, Polar Coordinates and Winding Numbers, Math. Magazine vol. 64, n. 2 (Apr., 1991), pp. 75-91.

[4] Bauman B., Sommariva A., Vianello M., Compressed cubature over polygons with applications to optical design, submitted.

[5] Bazza E., https://www.math.unipd.it/∼alvise/TESI_STUDENTI/BAZZA/.

[6] Caratheodory C., Über den Variabilittsbereich der Fourierschen Konstanten von po-sitiven harmonischen Funktionen, Rend. Circ. Mat. Palermo, vol. 32 (1911), pp. 193–217.

[7] Lawson C. L., Hanson R. J., Solving least squares problems, Revised reprint of the 1974 original, Classics in App. Math. 15, SIAM, Philadelphia, (1995).

[8] Pagani C. D., Salsa S., Analisi Matematica 2, Masson, (1998).

[9] Piazzon F., Sommariva A., Vianello M., Caratheodory-Tchakaloff Subsampling, Dolomites Res. Notes Approx. vol. 10 (2017), pp. 5-14.

[10] Sommariva A., https://www.math.unipd.it/∼alvise/software.html.

[11] Sommariva A., Vianello M., Compression of multivariate discrete measures and applications, Numer. Funct. Anal. Optim. vol. 36 (2015), pp. 1198-1223.