Approssimazione polinomiale su mesh debolmente ammissibili della palla e del tetraedro

(1)

Approssimazione polinomiale su mesh debolmente

ammissibili della palla e del tetraedro

(2)

(3)

Introduzione

Trovare buoni punti per l’approssimazione polinomiale in più variabili, in particolare per l’interpolazione polinomiale, è un difficile problema ancora aperto. Un nuovo spiraglio è stato dato dalla teoria delle mesh ammissibili studiate da Calvi e Levenberg in [3] che sono quasi ottime per l’approssi-mazione ai minimi quadrati e contengono insiemi di interpolazione che si distribuiscono asintoticamente sul dominio come i punti di Fekete.

. . . OMISSIS . . . Nel Capitolo 1 introdurremo le WAM . . . Nel Capitolo 2 . . .

Nel Capitolo 3 . . . Nel Capitolo 4 . . . Nel Capitolo 5 . . .

(4)

(5)

Indice

Introduzione 3

1 Mesh Debolmente Ammissibili (WAM) 7

1.1 Nozioni preliminari . . . 7 1.2 WAM unidimensionali: il segmento ed il cerchio . . . 11 1.3 Propriet`a delle WAM . . . 12

2 WAM in 2 dimensioni 17

2.1 WAM sul disco . . . 17 2.2 Mappatura sul simplesso . . . 20

3 WAM in 3 o pi`u dimensioni 23

3.1 WAM sulla palla . . . 23 3.2 Mappatura sul simplesso . . . 34

4 Approssimazione discreta ai minimi quadrati 45

4.1 Ricerca del polinomio approssimante . . . 45 4.2 Risultati numerici . . . 49 5 Interpolazione su Punti di Fekete Approssimati estratti da

una WAM 55

5.1 Punti (Approssimati) di Fekete . . . 55 5.2 Calcolo dei Punti di Fekete Approssimati . . . 57 5.3 Risultati numerici . . . 59

Conclusioni 65

A Implementazione in Codice Matlab 67

(6)

6 INDICE

A.2.1 File Principale demo3DWAM . . . 69 A.2.2 Creazione delle WAM . . . 71 A.2.3 Creazione e ortogonalizzazione della Matrice di

Van-dermonde, calcolo dei Punti di Fekete Approssimati . 72 A.2.4 Routine aggiuntive . . . 74

(7)

Capitolo 1

Mesh Debolmente

Ammissibili (WAM)

In questo capitolo introdurremo le Mesh Debolente Ammissibili (WAM) spie-gando per quale motivo siano un ottimo strumento su cui basarsi per tro-vare un’approssimazione polinomialme ai minimi quadrati su un dominio compatto, grazie ad un fondamentale teorema di Calvi e Levenberg. Dopo aver dato alcuni esempi, verranno elencate e discusse le caratteristiche e le propriet`a generali delle WAM, indicando la via alla costruzione di mesh in pi`u dimesioni e gettando cos`ı le fondamenta essenziali allo svolgimento del lavoro.

Nel paragrafo 1.1 daremo le definizioni ed i teoremi basilari, spiegando che cosa sono le Mesh Debolente Ammissibili per arrivare ai concetti che renderanno chiaro come sarà possibile uttilizzarle nel proseguio dello scrit-to. Nel paragrafo 1.2 daremo esempi di WAM unidimensionali notevoli, che insieme alle proprietà generali di ogni WAM esposte e dimostrate nel paragrafo 1.3 sarano utili per la costruzione di mesh in più dimensioni.

1.1 Nozioni preliminari

Consideriamo un insieme compatto K ∈ Rd (o Cd) polinomialmente deter-minante, cio`e tale che ogni polinomio nullo su K risulta essere il polinomio nullo. Adottiamo la seguente notazione:

||f ||_X := sup

x∈X

(8)

8 Mesh Debolmente Ammissibili (WAM)

in cui f `e una qualsiasi funzione limitata sull’insieme X. Inoltre, denotiamo con Pdn lo spazio dei polinomi su Rd di grado massimo n e con N la sua

dimensione N := dim(Pdn) = n + d d ∼ n d d! .

Osservazione 1. Notiamo che se A `e un sottoinsieme Pn-determinante di K

compatto, con K ∈ Rd( o Cd), essendo continua la mappa lineare che manda p ∈ Pn in p|A ∈ F (A), lo spazio delle funzioni a valori reali (o complessi),

questo equivale a dire che esiste una costante finita C(A) che dipende da A (e da K) tale che

||p||_K≤ C(A)||p||A, p ∈ Pd. (1.1)

Inseriamo ora un teorema dovuto a Calvi e Levenberg [3], che sar`a la base del nostro lavoro relativo all’approssimazione polinomiale ai minimi quadrati.

Teorema 1.1.1 (Propriet`a P9). Sia K un inseieme compatto in Cd(o Rd) e sia Anun suo sottoinsieme finito Pdn-determinante. Allora, per ogni funzione

f continua su K valgono le seguenti: ||LAn||K ≤ C (An) ||f ||_K+pcard (An) distK f, Pdn (1.2) e ||f − LAn||K ≤ 1 + C (An) 1 +pcard (An) distK f, Pdn , (1.3) dove distK(f, Pdn) `e la distanza uniforme tra f e Pdn, vale a dire

distK

f, Pdn

= infn||f − p||_K _{: p ∈ P}d_no.

Dimostrazione. Prendiamo un bn ∈ Pdn tale che ||f − bn||K = distK(f, Pdn).

Fissiamo ora a ∈ An. Dato che bn `e uno dei candidati per il problema di

minimizzazione per essere LAnf , abbiamo che

|f (a) − LAnf (a)| ≤ ||f − LAn||2,An ≤ ||f − bn||2,An ≤

(9)

1.1 Nozioni preliminari 9 Ne segue che ||LAn||An ≤ ||f ||An+ p card (An)distK f, Pdn .

Basta ora utilizzare il fatto che ||f ||An ≤ ||f ||K e la Definizione 1 di C(An),

applicata al polinomio LAnf . Per ottenere la (1.3), applichiamo

sempli-cemente la (1.2) sostituendo f con f − bn e utilizzando il fatto che `e una

proiezione lineare e distK(f, Pdn) = distK(f − bn, Pdn) ottenendo

||LAnf − bn||K ≤ C(An) h ||f − b_n||_K+pcard (An)distK f, Pdn i ≤ ≤ C(An) h 1 +pcard (An) i distK f, Pdn . Quindi ||f − LAnf ||K ≤ ||LAnf − bn||K+ ||bn− f ||K≤ ≤1 + C(An) h 1 +pcard (An) i distK f, Pdn .

Dalla disuguaglianza (1.3) vediamo che se `e possibile controllare il fattore C(An)pcard (An), allora LAnf ∈ P

d

n sara un’ approssimazione polinomiale

quasi ottima di f .

Sar`a utile trovare insiemi che abbiano una costante C(An) il pi`u piccolo

possibile contemporaneamente una cardinalit`a che non sia eccessivamente elevata. Questo per evitare problemi di complessit`a computazionale e per avere una buona convergenza alla funzione f .

Introduciamo ora due interessanti classi di mesh (nome con il quale denoteremo la discretizzazione di un domino).

Definizione 1.1.1 (Mesh Debolmente Ammissibile). Definiamo una Me-sh Debolmente Ammissibile (WAM) come una successione di sottoinsiemi discreti An⊆ K tali che

||p||K ≤ C(An)||p||An, ∀ p ∈ P

d

n (1.4)

in cui sia card(An) ≥ N che C(An) crescono al pi`u polinomialmente in n.

Definizione 1.1.2. Se {An} `e una successione di sottoinsiemi contenuti in

K come nella definizione precedente, in cui card(An) ≥ N cresce al pi`u

poli-nomialmente in n ma C(An) risulta essere invece una costante indipendente

(10)

10 Mesh Debolmente Ammissibili (WAM) n = 2 4 6 8 10 12 AM 64 4096 46656 262144 106 3 · 106 WAM Palla 27 125 343 729 1331 2197 WAM Tetra 15 85 259 585 1111 1885 P.Fek 10 35 84 165 286 455 n = 14 16 18 20 AM 7.5 · 106 1.7 · 107 3.4 · 107 6.4 · 107 WAM Palla 3375 4913 6895 9261 WAM Tetra 2955 4369 6175 8421 P.Fek 680 969 1330 1771

Tabella 1.1: Cardinalit`a delle AM, WAM sulla Palla e sul Tetraedro e Punti di fekete approssimati nel caso d = 3.

E’ stato dimostrato in [3] che ove sussista una disuguaglianza di Markov di grado r (i.e. ∃ M, r > 0 tali che ||∇||K ≤ M (deg p)r||p||K) `e sempre

possibile ottenere facilmente una AM di cardinalit`a O(nrd_{). Nei compatti}

convessi come ad esempio il triangolo o il disco in 2D oppure il tetraedro e la palla in 3D questo vale sempre, con r = 2. Perci`o `e possibile ottenere una Mesh Ammissibile con O(n4_{) punti nel primo caso, O(n}6_{) nel}

secon-do. Una cos`ı elevata cardinalità ha pesanti inconvenienti computazionali e renderebbe intrattabili anche per n relativamente bassi problemi come l’ap-prossimazione ai minimi quadrati; possiamo quindi considerare le WAM, che hanno una cardinalità molto più bassa, nel caso di questa tesi, veranno crea-te WAM con O(nd) punti e costante C(An) = O(logdn). Per convincerci

(11)

1.2 WAM unidimensionali: il segmento ed il cerchio 11

1.2 WAM unidimensionali: il segmento ed il

cer-chio

Vedi bene se davvero è dovuto alla proprietà P10 oppure va bene la solita limitazione per l’appross di funz con polinomi. Nell’articolo [1] sono state trovate WAM per il segmento [0, 1] ed il cerchio. Grazie alla Proprietà P10 delle WAM, possiamo dire che una volta trovato un insieme di punti di Fekete per un certo dominio, questo ne è anche una WAM. Vediamo quindi quali sono questi insiemi, rimandando il lettore interessato alle dimostrazioni a [1], con riferimenti ulteriori a [5] e [11].

Proposizione 1.2.1. L’insieme An di n + 1 punti di Chebishev-Lobatto `e

una WAM di grado n per il segmento unidimensionale.

Dimostrazione. Per la dimostrazione rimandiamo a [5] e [11]. Aggiungiamo solo che l’insieme An di n + 1 punti di Chebishev-Lobatto `e quasi-ottimo

per l’interpolazione polinomiale unidimensionale, avendo card(An) = n + 1 e

costante (di Lebesgue) C(An) = O(log n) (utilizzando la Propriet`a P2 della

WAM, che verrà introdotta nel paragrafo 1.3). Entrambi i valori sono al più polinomiali e quindi Anè una WAM del tipo desiderato.

Osservazione 2. In particolare, una WAM per il segmento [0, 1] `e 1 2+ 1 2cos jπ n j con j = 0, 1, . . . , n , mentre una WAM per il segmento [−1, 1] `e

cosjπ n j con j = 0, 1, . . . , n .

Proposizione 1.2.2. Per la circonferenza, una WAM unidimensionale di grado n risulta essere l’insieme An di 2n + 1 punti equispaziati su di essa.

Dimostrazione. Per la dimostrazione rimandiamo a [5] e [11].

Osservazione 3. In particolare, la WAM relativa al cerchio unitario {(x1, x2) :

x2₁+ x2₂ = 1} `e data dall’insieme di punti {(cos φ_k, sin φk)}k,

con

φk=

2πk

(12)

1.3 Propriet`

a delle WAM

Riportiamo di seguito le principali propiet`a conosciute delle WAM e alcu-ne delle dimostrazioni di tali propriet`a. Per le dimostrazioni non trattate rimandiamo a [3]:

P1: Le WAM sono invarianti rispetto alle trasformazioni affini e manten-gono la stessa costante C(An).

P2: Ogni sequenza di insiemi unisolventi di interpolazione la cui costante di Lebesgue Λn cresca al pi`u polinomialmente rispetto ad n `e una WAM

la cui costante C(An) `e proprio la costante di Lebesgue.

P3: Ogni sequenza di sovrainsiemi di una WAM le cui cardinalit`a crescono polinomialmente con n `e una WAM con la stessa costante C(An).

P4: L’unione finita di WAM `e una WAM per la corrispondente unione di compatti e C(An) `e il massimo tra le costanti corrispondenti.

P5: Il prodotto cartesiano finito di WAM `e una WAM in cui C(An) `e il

prodotto delle costanti corrispondenti.

P6: In Cd, una WAM per la frontiera ∂K `e una WAM per K.

P7: Data una trasformazione polinomiale πs di grado s, allora πs(Ans) `e

una WAM per πs(K) con costante C(Ans).

P8: Ogni insieme K che soddisfi una disuguaglianza polinomiale di Markov della forma ||∇p||K ≤ M nr||p||K ha un AM con O(nrd) punti.

P9: L’approssimazione polinomiale ai minimi quadrati di f ∈ C(K): Il polinomio LAnf che approssima f ai minimi quadrati in una WAM `e

tale che

||f − LAnf ||K / C(An)

p

card(An) min {||f − p||K, p ∈ Pdn} .

P10: Punti di Fekete: la costante di Lebesgue dei punti di Fekete estratti da una WAM pu`o essere limitata con Λn≤ N C(An) (che `e la classica

(13)

1.3 Propriet`a delle WAM 13

Dimostrazioni

Per le dimostrazioni delle Proprietà P1, P2 e P8 si rimanda a [3]. La Proprietà P9 è invece stata già dimostrata nel Teorema 1.1.1.

Proposizione 1.3.1 (Proprietà P3). Ogni sequenza di sovrainsiemi di una WAM le cui cardinalità crescono polinomialmente con n è una WAM con la stessa costante C(An).

Dimostrazione. Sia Anuna WAM del compatto K ∈ Rd(Cd). Banalmente,

chiamando Bn la nuova WAM ed essendo An ⊆ Bn, possiamo asserire che

per ogni polinomio p ∈ Pdn vale

||p||_K ≤ C(A)||p||An ≤ C(A)||p||Bn

che grazie alla Osservazione 1 `e equivalente a dire che Bn `e una WAM con

costante C(Bn) = C(An) e si conclude.

Proposizione 1.3.2 (Proprietà P4). L’unione finita di WAM è una WAM per la corrispondente unione di compatti e C(An) è il massimo tra le costanti

corrispondenti.

Dimostrazione. Denotiamo con A(1)n , . . . , A(m)n le WAM sugli m compatti

K1, . . . , Kme con C(A(1)n ), . . . , C(A(m)n ) le relative costanti. Naturalmente si

ha An ⊆ K, con Smi=1A (i)

n e Sm_i=1Ki. Risulta card(An) ≤Pmi=1card(A (1) n )

e questa cresce polinomialmente, essendo somma finita di cardinalit`a che crescono polinomialmente. Poich´e per i ∈ {1, . . . , m} si ha

||p||_K_i ≤ C(A(i)_n )||p||_A(i)

n , p ∈ Pn (1.5)

allora possiamo dire che

||p||_K= max

i ||p||Ki

e dato che questo massimo sar`a raggiunto per un certo λ ∈ {1, . . . , m}, per il quale vale naturalmente la (1.5),

||p||_K= ||p||Kλ≤ C (An) ||p||_A(λ) n ≤ max i C(A (i) n )||p||An

e si conclude, dato che C(An) = maxiC(A(i)n ) `e il massimo tra costanti che

(14)

Proposizione 1.3.3 (Proprietà P5). Il prodotto cartesiano finito di m WAM è una WAM per il corrispondente prodotto cartesiano di compatti e C(An) è il prodotto delle costanti corrispondenti.

Dimostrazione. Denotiamo con A(1)n , . . . , A(m)n le WAM sugli m

compat-ti K1, . . . , Km e con C(A(1)n ), . . . , C(A(m)n ) le relative costanti.

Natural-mente, si ha An ⊆ K, con

×

mi=1A (i)

n e

×

mi=1Ki. Risulta card(An) ≤

Qm

i=1card(A (1)

n ) e questa cresce polinomialmente, essendo prodotto finito

di cardinalit`a che crescono polinomialmente. Per m = 1 il teorema `e banalmente vero.

Sia ora m > 1 e sia valida la tesi per ogni s ≤ m − 1. Per sempli-cit`a, supponiamo che ognuna delle WAM A(i)n sia P1n -determinante, con

A(i)n ⊆ Ki ⊆ R: il caso generale `e simile, solamente molto pi`u

complica-to rispetcomplica-to alle notazioni e ai formalismi. Possiamo dire quindi che fissacomplica-to xm ∈ Km, p(x1, . . . , xm−1, xm) risulta essere un polinomio in Pm−1n . Per

l’ipotesi induttiva, abbiamo che

×

m−1_i=1 A(i)n `e una WAM per

×

m−1_i=1 Ki, il

dominio di questo polinomio, qualsiasi sia il valore di xm∈ Km. Perci`o, vale

|p(x1, . . . , xm−1, xm)| ≤ m−1

Y

i=1

C(A(i)_n ) max

e

xi∈A(i)n ∀i∈{1,...,m−1}

|p(x_e1, . . . ,xem−1, xm)|

Ora, per ogni m − 1-upla di {x_ei}i fissata, si ha che |p(xe1, . . . ,xem−1, xm)| `e un polinomio in una variabile su Km⊆ R e quindi

C(A(i)_n ) max

e

xi∈A(i)n ∀i∈{1,...,m}

|p(x_e1, . . . ,xem,exm)| = ≤ m Y i=1 C(A(i)_n )||p||An

e si conclude, poich´e C(An) = Qmi=1C(A (i)

n ) `e prodotto di costanti che

(15)

1.3 Propriet`a delle WAM 15

Dimostrazione. `E una conseguenza della definizione di WAM e del teorema del principio del massimo.

Proposizione 1.3.5 (Propriet`a P7). Sia Bn una WAM di Q e t : Q → K

una mappa polinomiale suriettiva di grado k, cio`e t(y) = (t1(y), . . . td(y))

con tj ∈ Pdk. Allora An= t(Sn), con Sn = Bkn, `e una WAM di K tale che

C(An) = C(Bkn).

Dimostrazione. Osservando che per ogni x ∈ K esiste almeno un y ∈ Q tale che x = t(y) e che ∀ p ∈ Pdn la composizione p(t(·)) `e un polinomio di grado

≤ kn, abbiamo che

|p(x)| = |p(t(y))| ≤ C(Bkn)||p(t(·))||Bkn = C(Bkn)||p||t(Bkn) .

Proposizione 1.3.6 (Propriet`a P10). La costante di Lebesgue dei punti di Fekete Approssimati estratti da una WAM (cf. Capitolo 5) pu`o essere limitata con Λn≤ NnC(An).

Dimostrazione. Consideriamo una WAM di K, An. Per estrarre i Punti di

Fekete Approssimati Fn massimizzeremo VDM su di un insieme finito di

cardinalit`a (card(An))Nn, come in (5.1) , cio`e calcoleremo

|VDM(b₁, . . . , bNn)| = max {|VDM(a1, . . . , aNn)| : ai ∈ An, i = 1, . . . , Nn} .

Si noti che VDM non `e identicamente nullo su An, dato che questi `e Pdn

-determinante; quindi Fn`e unisolvente per Pdn. Questi punti sono pressapoco

buoni come i punti standard di Fekete per K: se a ∈ Fn, grazie alla (5.2)

possiamo dire che

||`a||K ≤ C(An)||`a||An ≤ C(An) ,

risultando ||`a||An ≤ 1 per ogni a ∈ An (`e la classica limitazione della

Costante di Lebesgue per i Punti di Fekete).

Quindi si conclude, notando che la Costante di Lebesgue di Fn`e limitata

da C(An)Nn.

(16)

Per dare un’idea, gi`a nel Capitolo 2 verranno migliorati i risultati di [1] in cui si costruisce una WAM sul disco con circa 2n2 punti e C(An) = O(log2n)

con le coordinate polari standard, utilizzando essenzialmente la propriet`a P2 per Chebyshev in una variabile e l’interpolazione trigonometrica e utilizzan-do le propriet`a P2 e P7, si ottengono WAM per il triangolo e per i trapezoidi lineari, ancora con 2n2 punti e C(An) = O(log2n), semplicemente

(17)

Capitolo 2

WAM in 2 dimensioni

In questo capitolo, riportando parte del lavoro eseguito da Bos, Sommariva e Vianello in [4], vedremo come costruire WAM polari simmetriche di car-dinalità ridotta sul disco unitario. Utilizzando mappa biettiva dal disco al simplesso unitario bidimensionale costruiremo una WAM di cardinalità ri-dotta su quest’ultimo ed infine su un qualsiasi triangolo, grazie alla proprietà P1 delle WAM. Nel paragrafo 2.1 vedremo nei particolari come costruire una WAM di cardinalità ridotta sul disco grazie alle coordinate polari simme-tri. Nel paragrafo 2.2 vedremo come sarà possibile sfruttare i risultati del paragrafo precedente per costruire WAM su ogni triangolo, grazie ad una semplice proprietà trigonometrica.

2.1 WAM sul disco

Una WAM simmetrica con circa n2 _{punti sul disco unitario K = {x =}

(x1, x2) : x21+ x22 ≤ 1} pu`o essere ottenuta lavorando con le coordinate polari

simmetriche, cio`e

(x1, x2) = (r cos(θ), r sin(θ)), −1 ≤ r ≤ 1, 0 ≤ θ < π (2.1)

come si vede nella seguente

Proposizione 2.1.1. La sequenza di griglie polari simmetriche

(18)

18 WAM in 2 dimensioni

`e una WAM del disco unitario con C(An) = O(log2n), card(An) = n2+n+1

per n pari e card(An) = n2+ 2n + 1 per n dispari.

Dimostrazione. La restrizione di un polinomio p ∈ P2n al disco nelle

coordi-nate simmetriche polari q(r, θ) = p(r cos θ, r sin θ) di cui in (2.1) diventa un polinomio di grado n in r per ogni valore fissato di θ ed un polinomio trigono-metrico di grado n in θ per ogni valore fissato di r. Si osservi che `e possibile prendere θ ∈ [0, 2π] per tali polinomi trigonometrici, giacch´e il dominio delle coordinate rimane lo stesso (l’intero disco). Allo stesso modo, la griglia po-lare simmetrica non cambia prendendo θk∈ {2kπ/(2n + 2), 0 ≤ k ≤ 2n + 1}

in (2.2), precisamente 2n + 2 punti equispaziati sul cerchio. Ora, per ogni p ∈ P2n possiamo scrivere

|p(x1, x2)| = |q(r, θ)| = |p(r cos θ, r sin θ)| ≤ c1log n max

j |q(rj, θ)| ∀θ

in cui c1non dipende da θ, dato che gli {rj} sono gli n+1 punti di

Chebyshev-Lobatto dell’intervallo [−1, 1]. Inoltre |q(r_j, θ)| ≤ c2log n max

k |q(rj, θk)| ∀ rj

in cui c2non dipende da r, dato che i {θk} corrispondono sempre e comunque

a 2n + 2 punti equispaziati in [0, 2π]. Perci`o |p(x₁, x2)| ≤ c1c2log2n max

j,k |q(rj, θk)| = c1c2log 2_n||p||

An

per ogni punto (x1, x2) del disco, cio`e An `e una WAM per il disco con

C(An) = O(log2n). Concludiamo osservando che il numero di punti distinti

della griglia polare simmetrica `e (n + 1)(n + 1) = n2+ 2n + 1 per n dispari, mentre per n pari, sottraendo le ripetizioni del centro, `e (n + 1)(n + 1) − n = n2+ n + 1.

(19)

2.1 WAM sul disco 19

Osservazione 5. Si osservi che la WAM della Proposizione 2.1.1 contiene i punti di Chebyshev-Lobatto relativi al diametro verticale θ = π/2 solamente per n dispari (mentre contiene sempre i punti di Chebyshev-Lobatto relativi al diametro orizzontale θ = 0) e quindi non `e invariante rispetto a rotazioni di 90◦. Perch`e contenga sempre i punti di Chebyshev-Lobatto relativi al diametro verticale θ = π/2 , definiremo la mesh come di seguito:

{(rj, θk)}j,k = cosjπ n , 0 ≤ j ≤ n × kπ n + 2, 0 ≤ k ≤ n + 1 , n pari (2.3) vale a dire 2n + 4 punti equispaziati sul cerchio. La cardinalit`a di questa WAM `e, sottraendo le ripetizioni del centro, card(An) = (n + 1)(n + 2) −

(n + 1) = n2+ 2n + 1 = (n + 1)2 anche per n pari. Questa WAM `e ora invariante rispetto a rotazioni di 90◦.

Proposizione 2.1.2. Si consideri il sottospazio dei polinomi pari, vale a dire i polinomi di grado pari m = 2n, n = 0, 1, 2, . . . che scritti nella base monomiale contengano solamente potenze pari. La sequenza di griglie polari sul primo quadrante del disco unitario

Bm= {(rjcos θk, rjsin θk)} (2.4) con {(rj, θk)}j,k = cosjπ m, 0 ≤ j ≤ n × kπ m, 0 ≤ k ≤ n `

e una WAM per i polinomi pari sul (primo quadrante del) disco, con C(Bm) =

O(log2m) e con card(Bm) = n2+ n + 1.

Dimostrazione. La restrizione di un polinomio pari p di grado m = 2n sul disco unitario nelle coordinate polari simmetriche diventa un polinomio di grado n in r2 per ogni valore fissato di θ e un polinomio di grado n in cos2θ per ogni valore fissato di r, vale a dire p(x1, x2) = p(r cos(θ), r sin(θ)) =

g(r2, cos2θ). Ora, i valori che g assume sul disco unitario sono determinati completamente dai valori che essa assume per r ∈ [0, 1], θ ∈ [0, π/2] (il pri-mo quadrante del disco). Ricordando la seguente identit`a trigonometrica, cos2t = (1 + cos 2t)/2, possiamo vedere facilmente che gli {r2_j} sono esat-tamente i punti di Chebyshev-Lobatto di grado n per l’intervallo [0,1], cos`ı come lo sono i {cos2θk}. Quindi, dato un qualsiasi polinomio pari p di

gra-do m = 2n, procedengra-do allo stesso mogra-do della Proposizione 2.1.1 possiamo scrivere

|p(x₁, x2)| = |g(r2, cos2θ)| = O(log2m) max j,k |g(r

2

j, cos2θk)| =

(20)

20 WAM in 2 dimensioni

per ogni punto (x1, x2) del disco, con la costante relativa al simbolo O(·)

indipendente da (x1, x2). Si conclude osservando che il numero di punti

distinti di Bn si ottiene sottraendo le n ripetizioni del centro ed `e perci`o

(n + 1)(n + 1) − n = n2+ n + 1.

2.2 Mappatura sul simplesso

Utilizzando i risultati della sezione precedente, mostreremo come costruire una WAM con all’incirca n2punti sul simplesso unitario. Lo strumento base `e la trasformazione quadratica standard

u2_{+ v}2 _{≤ 1, u ≥ 0, v ≥ 0 = Q → K = {x}

1+ x2≤ 1, x1≥ 0, x2 ≥ 0}

(u, v) 7→ (u2, v2)

dal primo quadrante del disco nel simplesso unitario.

Proposizione 2.2.1. La sequenza di griglie trapezoidali di Chebyshev-Lobatto A_n= {(r_j2cos2θk, rj2sin2θk)} (2.5) con {(r_j, θk)}j,k = cosjπ 2n, 0 ≤ j ≤ n × kπ 2n, 0 ≤ k ≤ n

`e una WAM del simplesso unitario, con C(An) = O(log2n) e con card(An) =

n2 + n + 1. In particolare, i punti delle mesh giacenti sui lati sono i corrispondenti n + 1 punti di Chebyshev-Lobatto di grado n.

Dimostrazione. La griglia polare B2n = {(rjcos θk, rjsin θk)} con {rj, θk}

come in (2.4) `e una WAM per i polinomi pari sul primo quadrante del disco unitario, grazie alla Proposizione 2.1.2. Ora, la trasformazione qua-dratica π2 : (u, v) 7→ (u2, v2) dal primo quadrante al simplesso unitario `e

invertibile e grazie a una piccola estensione delle proprietà P7 delle WAM (in realtà abbiamo bisogno di identificare solamente le WAM per i poli-nomi della forma p ◦ π2) abbiamo quindi che An = π2(B2n) è una WAM

per il simplesso unitario. Inoltre, card(An) = card(B2n) = n2 + n + 1 e

C(An) = C(B2n) = O(log22n) = O(log2n). Osservando come nella

Pro-posizione 2.1.2 che gli {r2_j} sono i punti di Chebyshev-Lobatto di grado n per [0, 1], possiamo notare che i punti della mesh relativi ai cateti del sim-plesso sono esattamente i suoi punti di Chebyshev-Lobatto. D’altra parte, osservando che anche i {cos2θk} sono i punti di Chebyshev-Lobatto di

(21)

2.2 Mappatura sul simplesso 21

{(cos2_θ

k, 1 − cos2θk)} sono esattamente i suoi punti di Chebyshev-Lobatto.

Questo si pu`o vedere semplicemente proiettando questi punti sull’asse delle ascisse, ottenendo {(cos2θk, 0)} ( `E una trasformazione affine, in quanto il

nostro segmento no `e parallelo alle rette di proiezione sull’asse x2 = 0). A

questo punto, notiamo che {(cos2θk, 0)} al variare di k `e proprio l’insieme

dei punti di Chebyshev-Lobatto del segmento [0, 1]. Per la Propriet`a P1 anche {(cos2θk, 1 − cos2θk)} `e una WAM, stavolta del segmento di estremi

(0, 1) e (1, 0), con la stessa C(An). Inoltre i punti della WAM giacciono

su una griglia composta da segmenti che si intersecano; pi`u precisamente sulle intersezioni di raggi di centro l’origine con segmenti paralleli all’ipote-nusa, ottenuti grazie alla trasformazione quadratica su una griglia di raggi che si intersecano con archi circolari nel primo quadrante. Una tale griglia spezza il simplesso nell’unione di piccoli trapezoidi che degenerano in trian-goli nell’origine. Il fatto che i punti della griglia relativi ad ogni segmento di raggio siano esattamente i suoi punti di Chebyshev-Lobatto `e un’imme-diata conseguenza di geometria elementare, precisamente del Teorema di Talete.

(22)

(23)

Capitolo 3

WAM in 3 o pi`

u dimensioni

In questo capitolo vedremo costruire WAM polari simmetriche di cardinalità ridotta sulla palle e simplessi unitari di ogni dimensione sfruttando i risultati del Capitolo 2, soffermandoci particolarmente sul caso tridimensionale che verrà poi implementato in linguaggio Matlab nei Capitoli 4 e 5 e nell’Ap-pendice A. Nel paragrafo 3.1 vedremo nei particolari come costruire una WAM di cardinalità ridotta sulla palla in 3 e più dimensioni. Nel paragrafo 3.2 vedremo come sarà possibile sfruttare i risultati del paragrafo precedente per costruire WAM su ogni simplesso e poliedro in 3 e d dimensioni.

3.1 WAM sulla palla

Definizione 3.1.1 (Coordinate sferiche generalizzate). Le coordinate sferi-che (generalizzate) sono un sistema di coordinate per R3 o più in generale per Rn. Una coordinata è data dalla distanza dall’origine, che può esse-re pensata come la lunghezza del raggio della palla centrata nell’origine e passante per il punto considerato. Le altre coordinate sono angoli che de-terminano univocamente il punto su questa palla.

In R3 le coordinate sono date da   x y z  =   r sin θ cos φ r sin θ sin φ r cos θ   , (3.1)

(24)

24 WAM in 3 o pi`u dimensioni

possono essere sfruttate su Rn , utilizzando n − 2 angoli polari θ1, . . . , θn−2

ed un angolo azimutale φ:             x1 x2 .. . xk .. . xn−1 xn             =              r cos θ1 r sin θ1cos θ2 .. . r Qk−1 i=1 sin θi cos θk .. .

r sin θ1sin θ2· · · cos φ

r sin θ1sin θ2· · · sin θn−2sin φ

             . (3.2)

Se n > 3 si pu`o parlare di coordinate ipersferiche.

Definizione 3.1.2 (Coordinate sferiche simmetriche generalizzate). Le coor-dinate sferiche simmetriche generalizzate sono coorcoor-dinate sferiche genera-lizzate in cui i domini di definizione dei parametri r, φ, θ1, . . . , θn−2 sono i

seguenti:    r ∈ [−1, 1] , φ ∈ [0, π) , θ1, . . . , θn−2∈ [0, π) .

Una WAM simmetrica con circa n3 punti sulla palla unitaria K = {x = (x1, x2, x3) : x12+x22+x23 ≤ 1} pu`o essere ottenuta lavorando con le coordinate

sferiche simmetriche, cio`e

(x1, x2, x3) = (r sin(θ) cos(φ), r sin(θ) sin(φ), r cos(θ)), (3.3)

r ∈ [0, 1], θ ∈ [0, π), φ ∈ [0, π) come si vede nella seguente

Proposizione 3.1.1. La sequenza di griglie sferiche simmetriche

An= {(rjsin θkcos φl, rjsin θksin φl, rjcos θk)} (3.4)

con {(r_j, θk, φl)}_j,k,l= cosjπ n × kπ n + 1 × lπ n + 1 , j, k, l ∈ {0, 1, 2, . . . , n} `e una WAM della palla unitaria con C(An) = O(log3n), card(An) = n3+

(25)

3.1 WAM sulla palla 25

Dimostrazione. La restrizione di un polinomio p ∈ P3n alla palla nelle

coor-dinate sferiche simmetriche q(r, θ, φ) = p(r sin θ cos φ, r sin θ sin φ, r cos θ) di-venta un polinomio di grado n in r per ogni valore fissato di θ e φ, un polinomio trigonometrico di grado n in θ per ogni valore fissato di r e φ ed un polinomio trigonometrico di grado n in φ per ogni valore fissato di r e θ. Imitando la dimostrazione in 2 dimensioni possiamo prendere θ e φ ∈ [0, 2π] per tali polinomi trigonometrici, giacch´e il dominio delle coor-dinate rimane lo stesso (l’intera palla). Allo stesso modo, la griglia sferica simmetrica non cambia prendendo θk ∈ {2kπ/(2n + 2), 0 ≤ k ≤ 2n + 1}

e φl ∈ {2lπ/(2n + 2), 0 ≤ l ≤ 2n + 1} in (3.4), precisamente 2n + 2 punti

equispaziati sul cerchio per ogni variabile. Ora, per ogni p ∈ P3n possiamo

scrivere

|p(x1, x2, x3)| = |q(r, θ, φ)| = |p(r sin θ cos φ, r sin θ sin φ, r cos θ)| ≤

≤ c1log2n max

j,k |q(rj, θk, φ)| ∀φ

in cui c1non dipende da φ, dato che gli {rj} sono gli n+1 punti di

Chebyshev-Lobatto dell’intervallo [−1, 1] e i {θk} corrispondono a 2n + 2 punti

equispa-ziati in [0, 2π]. Questo poich´e considerando fissato l’angolo φ ci si ricondu-ce esattamente alla situazione relativa alla Proposizione 2.1.1 e si possono quindi usare i risultati trovati in 2 dimensioni. Ripetendo il ragionamento utilizzato nella Proposizione 2.1.1 relativamente all’angolo, possiamo notare che

|q(rj, θk, φ)| ≤ c2log n max

l |q(rj, θk, φl)|, ∀ rj, ∀ θk

in cui c2 non dipende n´e da r n´e da θ, dato che i {φl} corrispondono a 2n + 2

punti equispaziati in [0, 2π]. Perci`o |p(x₁, x2, x3)| ≤ c1c2log3n max

j,k,l |q(rj, θk, φl)| = c1c2log 3_n||p||

An

per ogni punto (x1, x2, x3) della palla, cio`e An`e una WAM per la palla con

C(An) = O(log3n). Per concludere, notiamo che la WAM di cui in (3.4)

viene creata prendendo una WAM bidimensionale e ruotandola attorno ad uno dei suoi assi, pi`u precisamente `e l’unione per l ∈ {0, 1, n} di WAM bidimensionali come in (2.2), ognuna ruotata di un angolo φlrispetto all’asse

x3. Queste WAM hanno in comune i punti sull’asse x3, che sono n + 1,

perciò alla fine si ottengono n ripetizioni di questi n + 1 punti che andranno eliminate. Quindi la cardinalità della WAM è pari a (n + 1)2(n + 1) − n(n + 1) = (n + 1)3− n2_{− n = n}3_{+ 2n}2_{+ 2n + 1 per n dispari, mentre per n pari `}_e

(26)

Possiamo a questo punto costruire una WAM simmetrica con circa nd punti sulla palla unitaria d-dimensionale K = {x = (x1, . . . , xd) :Pdi=1x2i ≤

1} utilizzando con le coordinate sferiche simmetriche generalizzate, come si vede nel seguente

Corollario 3.1.2. Consideriamo le coordinate sferiche simmetriche gene-ralizzate d-dimensionali, utilizzando per comodit`a la seguente notazione:

• r `e la distanza dall’origine; • φ `e l’angolo azimutale;

• θ(1)_{, θ}(2)_{, . . . , θ}(n−2) _{sono gli n − 2 angoli polari.}

La sequenza di griglie sferiche simmetriche d-dimensionali

An= {(x1, . . . , xd)} (3.5) con        x1 x2 .. . xd−1 xd        =          rjcos θ(1)k1 r sin θ(1)_k 1 cos θ (2) k2 .. .

rjsin θ_k(1)₁ sin θ_k(2)₂ · · · cos φk

rjsin θ(1)_k₁ sin θ_k(2)₂ · · · sin θ(d−2)_k_d−2 sin φk

         e n rj, φk, θ (1) k1 , . . . , θ (d−2) kd−2 o j,k,k1,...,kd−2 = cosjπ n × kπ n + 1 d−2

×

i=1 kiπ n + 1 prendendo j, k, k1, . . . , kd−2∈ {0, 1, 2, . . . , n}

`e una WAM della palla unitaria con C(An) = O(logdn), card(An) = nd+

nd−1_{+ . . . + n + 1 per n pari e card(A}

n) = (n + 1)d per n dispari.

Dimostrazione. Per induzione su d, sfruttando l’idea della Proposizione 3.1.1 Caso base

(27)

Passo induttivo

Sia ora vera la tesi per k ≤ d − 1, vediamo che varr`a quindi anche per k = d. Infatti, la restrizione di un polinomio p ∈ Pdn alla palla nelle coordinate

sferiche simmetriche q(r, θ(1), . . . , θ(d−2), φ) = p(x1, . . . , xd) con (x1, . . . , x2)

come in (3.5) diventa un polinomio di grado n in r per ogni valore fissato di φ e θ(i)∀i, un polinomio trigonometrico di grado n in θ(i)_{∀i, per ogni valore}

fissato di r, φ e θ(a)_{, ∀a ∈ {1, 2, . . . , n} r {i} ed un polinomio trigonometrico}

di grado n in φ per ogni valore fissato di r e θi, ∀i.

Imitando le dimostrazioni in 2 e 3 dimensioni possiamo prendere θ(i) ∈ [0, 2π] ∀i e φ ∈ [0, 2π] per tali polinomi trigonometrici, giacch´e il domi-nio delle coordinate rimane lo stesso (l’intera palla d-dimensionale). Allo stesso modo, la griglia sferica simmetrica non cambia prendendo ∀i θ(i)_k

i ∈

{2kπ/(2n + 2), 0 ≤ k_i ≤ 2n + 1} e φ_l ∈ {2lπ/(2n + 2), 0 ≤ l ≤ 2n + 1} in (3.5), precisamente 2n + 2 punti equispaziati sul cerchio per ogni variabile. Ora, per ogni p ∈ Pdn possiamo scrivere

|p(x1, . . . , x3)| = |q(r, θ(1), . . . , θ(d−2), φ)| ≤ ≤ c₁logd−1n max j,k1,...,kd−2 |q(r_j, θ_k(1) 1 , . . . , θ (d−2) kd−2 , φ)| ∀φ

in cui c1non dipende da φ, dato che gli {rj} sono gli n+1 punti di

Chebyshev-Lobatto dell’intervallo [−1, 1] e i {θki} corrispondono a 2n + 2 punti

equispa-ziati in [0, 2π], ∀i. Questo vale per il fatto che considerando fissato l’angolo φ ci si riconduce esattamente alla situazione in d − 1 dimensioni ed `e quindi possibile giustificare la stima grazie l’ipotesi induttiva. Ripetendo il ragiona-mento utilizzato nella Proposizione 2.1.1 relativamente all’angolo, possiamo notare che

|q(rj, θ_k(1)₁, . . . , θ(d−2)_k_d−2 , φ)| ≤ c2log n max l |q(rj, θ

(1)_{, . . . , θ}(d−2)_{, φ}

l|, ∀ rj, ∀ θ(i)_k_i

in cui c2 non dipende n´e da r n´e da alcun θ(i), dato che i {φl} corrispondono

a 2n + 2 punti equispaziati in [0, 2π]. Perci`o |p(x₁, . . . , xd)| ≤ c1c2logdn max

j,k,l |q(rj, θk, φl)| = c1c2log d_n||p||

An

per ogni punto (x1. . . , xd) della palla d-dimensionale, cio`e An `e una WAM

per la palla d-dimensionale con C(An) = O(logdn). Per concludere, notiamo

(28)

Denotando con nm =Pm_i=0ni, che per l’ipotesi `e la cardinalita’ di una WAM

m-dimensionale se m ≤ d−1, notiamo che in questo modo per n pari vengono ripetuti n+1 volte i punti della WAM giacenti sul piano (d−2)-dimensionale di rotazione e quindi si ottengono alla fine n ripetizioni di questi nm punti

che andranno eliminate. Sappiamo che i punti sono nm=Pmi=0ni dato che

prendiamo in considerazione una WAM (d − 2)-dimensionale e vale l’ipotesi induttiva. Quindi, per n pari la cardinalit`a della WAM `e

card (An) = nd−1(n + 1) − nd−2n = (n + 1) d−1 X i=0 ni− n d−2 X i=0 ni = = d X i=1 ni+ d−1 X i=0 ni− d−1 X i=1 ni= d X i=1 ni+ 1 = d X i=0 ni = nd e quindi si conclude.

Osservazione 7. Ripetendo il ragionamento effettuato in 2 dimensioni, poich´e ci basiamo su mesh invarianti rispetto a rotazioni di 180◦, dobbiamo selezionare almeno n + 2 punti sulla semipalla superiore relativa ad ogni angolo (considerando fissi r ed gli altri angoli), in modo da avere almeno 2n + 1 punti quispaziati su ogni cerchio (il minimo perch´e ogni polinomio trigonometrico di grado n in un dato angolo venga determinato completa-mente).

Vediamo ora come scegliere la WAM sulla palla in d dimensioni in modo che questa sia invariante rispetto a rotazioni di 90◦ rispetto ad ogni angolo. Come accadeva in 2 dimensioni, la WAM della Proposizione 3.1.1 contie-ne i punti di Chebyshev-Lobatto relativi ai diametri verticali φ = π/2 o θ(i) = π/2 ∀i solamente per n dispari (mentre contiene sempre i punti di Chebyshev-Lobatto relativi al diametro orizzontale φ = 0 o θ(i) = 0 ∀i) e quindi non `e invariante rispetto a rotazioni di 90◦. Per poter avere sem-pre nella mesh i punti di Chebyshev-Lobatto relativi ai diametri verticali, prenderemo i punti come di seguito:

(29)

vale a dire 2n + 4 punti equispaziati sul cerchio per ogni angolo. Per d = 3 la cardinalit`a di questa WAM `e card(An) = (n + 1)3, infatti la WAM viene

creata unendo n + 2 WAM bidimensionali come in (2.2), ognuna ruotata di un angolo φl, l ∈ {0, 1, . . . , n + 1} rispetto all’asse x3. Queste WAM hanno

in comune i punti giacenti sull’asse x3, che sono n + 1, perci`o si hanno n + 1

ripetizioni di questi n + 1 punti che andranno eliminate. In definitiva, card(An) = (n + 1)2(n + 2) − (n + 1)(n + 1) =

= (n + 1)3+ (n + 1)2− (n + 1)2 = (n + 1)3 .

Per induzione si vede che ∀d ∈ N vale card(An) = . . . = (n + 1)d. Infatti,

indicando con nd la cardinalit`a della WAM in Rd, si per quanto gi`a visto in

dimensione 2 e 3 che

n2 = (n + 1)2 , n3= (n + 1)3 .

Supponendo che per k ≤ d valga nd = (n + 1)d, dato che le nostre WAM

(d + 1)-dimensionali sono create facendo ruotare n + 2 volte la WAM d-dimensionale di cardinalit`a nd attorno ad uno spazio (d − 1)-dimensionale,

dobbiamo togliere le n+1 ripetizioni eccessive degli nd−1punti che giacciono

sul piano (d − 1)-dimensionale di rotazione1, ottenendo

nd+1= nd(n + 2) − nd−1(n + 1) = nd(n + 1) + nd− (n + 1)d−1(n + 1) =

= (n + 1)d(n + 1) + (n + 1)d− (n + 1)d= (n + 1)d+1

e quindi vale anche per k = d+1 e si conclude. Questa WAM `e ora invariante rispetto a rotazioni di 90◦ rispetto ad ogni angolo.

Proposizione 3.1.3. Si consideri il sottospazio dei polinomi pari, vale a dire i polinomi di grado pari m = 2n, n = 0, 1, 2, . . . che scritti nella base monomiale contengano solamente potenze pari. La sequenza di griglie polari sul primo quadrante del disco unitario

Bm= {(rjsin θkcos φl, rjsin θksin φl, rjcos θk)} (3.7)

con {(r_j, θk, φl)}_j,k,l= cosjπ m × kπ m × lπ m , j, k, l = 0, 1, 2, . . . , n 1

(30)

`e una WAM per i polinomi pari sul primo ottante della palla (e anche sul-la palsul-la, grazie alsul-la parit`a dei polinomi) con C(Bm) = O(log3n) e con

card(Bm) = n3+ n2+ n + 1, per n pari.

Dimostrazione. La restrizione di un polinomio pari p di grado m = 2n sulla palla unitaria nelle coordinate polari simmetriche diventa un poli-nomio di grado n in r2 per ogni valore fissato di θ e φ, un polinomio di grado n in cos2θ per ogni valore fissato di r e φ ed un polinomio di gra-do n in cos2_{φ per ogni valore fissato di r e θ, vale a dire p(x}

1, x2, x3) =

p(r sin θ cos φ, r sin θ sin φ, r cos θ) = g(r2, cos2θ, cos2φ). Ora, i valori che g assume sulla palla unitaria sono determinati completamente dai valori che essa assume per r ∈ [0, 1] e θ, φ ∈ [0, π/2] (il primo ottante della palla). Esattamente come `e stato fatto nella Proposizione 2.1.2, possiamo vedere facilmente che gli {r_j2} sono esattamente i punti di Chebyshev-Lobatto di grado n per l’intervallo [0, 1], cos`ı come lo sono i {cos2θk} ed i {cos2φl},

dato che i due ultimi insiemi differiscono solo per il nome della variabile utilizzata (φ e θ) ed essendo l’insieme di definizione di l uguale a quello di k. Quindi, dato un qualsiasi polinomio pari p di grado m = 2n, procedendo allo stesso modo della Proposizione 3.1.1 possiamo scrivere

|p(x₁, x2, x3)| = |g(r2, cos2θ, cos2φ)| ≤

≤ c1c2O(log2m) max j,k |g(r

2

j, cos2θk, cos2φ)| ∀φ .

Notiamo ora che fissati j e k,

|g(r_j2, cos2θk, cos2φ)| ≤ c3O(log m) max j,k,l |g(r

2

j, cos2θk, cos2φl)|

in cui c3 non dipende da alcun parametro, per cui possiamo asserire che

|p(x1, x2, x3)| = . . . = c1c2c3O(log3m) max j,k,l |g(r

2

j, cos2θk, cos2φl)| =

= O(log3m)||p||Bm

per ogni punto (x1, x2, x3) della palla, con la costante relativa al simbolo

O(·) indipendente da (x1, x2, x3). Dato che la nostra WAM tridimensionale

`e stata creata dall’unione di n + 1 copie, ognuna ruotata di un angolo φl

rispetto all’asse x3, di una WAM bidimensionale come in (2.2), concludiamo

osservando che per n pari il numero di punti distinti di Bm si ottiene

(31)

essere

card (Bm) = (n + 1)2− n (n + 1) − n(n + 1) = (n + 1)3− 2n(n + 1) =

= n3+ n2+ n + 1.

Un esempio di come si presenta la WAM per r = 1 si trova nella Figura 3.1.

Figura 3.1: Come si presenta per rj = 1 la WAM sul 1◦ ottante per i

polinomi pari in 3 variabili.

Corollario 3.1.4. Si consideri il sottospazio dei polinomi pari, vale a dire i polinomi di grado pari m = 2n, n = 0, 1, 2, . . . che scritti nella base mo-nomiale contengano solamente potenze pari. La sequenza di griglie sferiche sul primo 2d-ante della palla d-dimensionale unitaria

(32)

32 WAM in 3 o pi`u dimensioni con        x1 x2 .. . xd−1 xd        =          rjcos θ (1) k1 r sin θ(1)_k 1 cos θ (2) k2 .. .

rjsin θ(1)_k₁ sin θ(2)ik2· · · cos φk

rjsin θ(1)_k₁ sin θ_k(2)₂ · · · sin θ(d−2)_k_d−2 sin φk

         e n rj, φk, θ (1) k1 , . . . , θ (d−2) kd−2 o j,k,k1,...,kd−2 = cosjπ m × kπ m d−2

×

i=1 kiπ m prendendo j, k, k1, . . . , kd−2∈ {0, 1, 2, . . . , n}

`e una WAM per i polinomi pari sul primo 2d-ante della palla d-dimensionale unitaria, con C(Bm) = O(logdm) e con card(Bm) = nd+ nd−1+ . . . + n + 1

per n pari.

Dimostrazione. Per induzione su d, sfruttando l’idea della Proposizione 3.1.3. Caso base

Per d = 1 vale banalmente. Per d = 2 e d = 3 abbiamo gi`a visto nelle Proposizioni 2.1.2 e 3.1.3 che le WAM in 2 e 3 dimensioni cos`ı costruite soddisfano i criteri imposti dalla tesi.

Passo induttivo

Sia ora vera la tesi per k ≤ d − 1, vediamo che varr`a quindi anche per k = d. Infatti, la restrizione di un polinomio pari p di grado m = 2n sulla palla d-dimensionale unitaria nelle coordinate polari simmetriche diventa un polinomio di grado n in r2 per ogni valore fissato di φ e θ(i) ∀i, un polino-mio di grado n in cos2θ(i) ∀i, per ogni valore fissato di r, φ e θ(a)_{, ∀a ∈}

{1, 2, . . . , n}r{i} ed un polinomio di grado n in cos2_{φ per ogni valore fissato}

di r e θi, ∀i, vale a dire p(x1, . . . , xd) = g(r2, cos2θ(1), . . . , cos2θ(d−2)cos2φ).

Ora, i valori che g assume sulla palla unitaria sono determinati completa-mente dai valori che essa assume per r ∈ [0, 1] e θ(i), φ ∈ [0, π/2], ∀i (il primo 2d-ante della palla).

(33)

grado n per l’intervallo [0, 1], cos`ı come lo sono i {cos2θ_k(i)

i} ∀i ed i {cos

2_φ l}.

Quindi, dato un qualsiasi polinomio pari p di grado m = 2n, fissando l’angolo φ possiamo notare che considerando fisso quest’angolo, otteniamo una delle WAM (d − 1)-dimensionali con le quali costruiamo per rotazione la nostra WAM d-dimensionale. Perci`o ci siamo ricondotti a studiare una WAM d − 1-dimensionale, che grazie all’ipotesi induttiva, ci d`a

|p(x1, . . . , xd)| = |g(r2, cos2θ(1), . . . , cos2θ(d−2), cos2φ)| ≤

≤ c₁O(logd−1m) max j,k1,...,kd−2 |g(r2_j, cos2θ_k(1) 1 , . . . , cos 2_θ(d−2) kd−2 , cos 2_{φ)| ∀φ .} e naturalmente |g(r2_j, cos2θ_k(1) 1 , . . . , cos 2_θ(d−2) kd−2 , cos 2_{φ)| ≤ c} 2O(log m)||p||Bm con ||p||Bm = max j,k1,...,kd−2,l |g(r2_j, cos2θ_k(1) 1 , . . . , cos 2_θ(d−2) kd−2 , cos 2_φ l)|

in cui c2 non dipende da alcun parametro, per cui possiamo asserire che

|p(x1, . . . , xd)| = . . . = c1c2O(logd−1m)O(logdm)||p||Bm =

= O(logdm)||p||Bm

per ogni punto (x1, . . . , xd) della palla, con la costante relativa al simbolo

O(·) indipendente da (x₁, . . . , xd).

Dato che la nostra WAM d-dimensionale `e stata creata dall’unione di n + 1 copie, ognuna ruotata di un angolo φl rispetto ad un piano (d −

2)-dimensionale, di WAM (d − 1)-dimensionali come in (3.8), concludiamo osservando che il numero di punti distinti di Bm si ottiene sottraendo le

eccessive n ripetizioni degli n + 1 punti della WAM (d − 1)-dimensionale giacenti sull’asse di rotazione(d − 2)-dimensionale e che quindi la cardinalit`a di Bm per n pari risulta essere

(34)

3.2 Mappatura sul simplesso

Utilizzando i risultati della sezione precedente, mostreremo come costruire una WAM con all’incirca n3 punti sul simplesso unitario tridimensionale. Lo strumento base `e la trasformazione quadratica standard

u2_{+ v}2_{+ w}2 _{≤ 1, u, v, w ≥ 0 = Q → K = {x}

1+ x2+ x3≤ 1, x1, x2, x3 ≥ 0}

(u, v, w) 7→ (u2, v2, w2)

Come prima, possiamo estendere tutto ci`o a d dimensioni costruendo una WAM con all’incirca nd punti sul simplesso unitario d-dimensionale: usere-mo la trasformazione quadratica standard generalizzata

( _d X i=1 u2_i ≤ 1, u_i≥ 0 ∀i ) = Q → K = ( _d X i=1 xi ≤ 1, x1 ≥ 0 ∀i ) (u1, . . . , ud) 7→ (u21, . . . , u2d)

dal primo quadrante della palla dimensionale nel simplesso unitario d-dimensionale.

Vediamo ora un fatto che ci sar`a utile nella dimostrazione del teorema che segue, ovvero :

Lemma 3.2.1. Data una sequenza di punti di Chebyshev-Lobatto di grado n in [0, 1], {cos2θk}k∈In con θk= (kπ)/(2n) e In= {0, 1, . . . , n}, si ha che

questa `e uguale alla sequenza di punti {sin2θk}k∈In.

Dimostrazione. Proveremo ora che ∀k ∈ {0, 1, . . . , n} si ha sin2θk = cos2θn−k.

Ricordiamo che vale cos2t = (1 + cos 2t)/2 e applichiamo la propriet`a a sin2θk e cos2θn−k. Otteniamo

sin2θk= 1 − cos2θk= 1 − 1 + cos 2θk 2 = 1 − cos 2θk 2 = 1 − cos2kπ_2n 2 = = 1 − cos kπ n 2 ,

(35)

Possiamo ora terminare la dimostrazione, notando che avremo quindi          sin2θ0 = cos2θn sin2θ1 = cos2θn−1 .. . sin2θn= cos2θ0 e concludendo che cos2_θ k k∈In =sin 2_θ k k∈In (3.9) per θk= kπ 2n e In= {0, 1, . . . , n} .

Siamo ora pronti per dimostrare la

Proposizione 3.2.2. La sequenza di griglie trapezoidali di Chebyshev-Lobatto A_n=

r2_jsin2θkcos2φl, r2jsin2θksin2φl, rj2cos2θk

(3.10) con {(r_j, θk, φl)}j,k,l= cosjπ 2n × kπ 2n × lπ 2n , j, k, l = 0, 1, 2, . . . , n `

e una WAM del simplesso unitario, con C(An) = O(log3n) e con card(An) =

n3 + n2 + n + 1. Inoltre, fissando 2 dei 3 parametri di An in (3.10)

otte-niamo una WAM bidimesionale del tipo costruito nella Proposizione 2.2.1 o una sua trasformazione affine. Ci`o accade in particolare restringendo la WAM tridimensionale di cui in (3.10) ad ogni faccia del simplesso. Perci`o, fissando 2 dei 3 parametri di Antroviamo una WAM unidimensionale,

com-posta esattamente dagli n+1 punti di Chebyshev-Lobatto relativi al segmento risultante.

Dimostrazione. La griglia B2n = {(rjsin θkcos φl, rjsin θksin φl, rjcos θk)}

con {rj, θk} come in (3.7) `e una WAM per i polinomi pari sul primo ottante

della palla unitaria, grazie alla Proposizione 3.1.3. Ora, la trasformazio-ne quadratica π2 : (u, v, w) 7→ (u2, v2, w2) dal primo ottante al simplesso

(36)

simpleso unitario. Inoltre, card(An) = card(B2n) = n3 + n2 + n + 1 e

C(An) = C(B2n) = O(log32n) = O(log3n). Vediamo ora come si presenta

la WAM considerando fisso uno dei 3 parametri che la determinano, ot-tenendo cos`ı una WAM bidimensionale basandoci sulla notazione presente nella 3.2. Vediamo innanzitutto come si presenta la WAM sulle facce del

Figura 3.2: Identificazione di un punto P nel simplesso unitario, attraverso rj, cos2θk e cos2φl.

tetraedro (possiamo trovare due disegni esplicativi nelle Figure 3.3 e 3.4). Poiché essa è stata creata partendo da una WAM bidimensionale come in (2.2) (che è esattamente quella della faccia 4AOB) e unendone n + 1 copie, ruotate ognuna di un angolo φl rispetto all’asse x3, ognuna di queste copie

risulta essere una WAM congruente a quella in (2.2): per l = 0 (cioè φ = 0) otteniamo la faccia 4AOB, mentre per l = n (cioè φ = π) otteniamo la faccia 4BOC. Inoltre ∀ l ∈ {1, . . . , n − 1}, cioè fissando un angolo φl nella

WAM (vedi Figura 3.5) otteniamo ancora delle WAM come in (2.2), ruotata per`o di un angolo φl rispetto all’asse x3. Prendiamo ora la WAM relativa

alla faccia 4ABC, per cui vale (r2 = 1). Possiamo proiettare i punti di questa sull’asse x3 = 0 attraverso una trasformazione affine (poich´e le rette

(37)

Figura 3.3: WAM del simplesso per rj = 1, cio`e ristretta alla faccia 4ABC.

(38)

proiettare), ottenendo γ (A4ABC) =

r2_jsin2θkcos2φl, r2jsin2θksin2φl, 0

(r2=1) = =

sin2θkcos2φl, sin2θksin2φl, 0 =

=sin2θk cos2φl, sin2φl, 0

.

Al fine di studiare la WAM bidimensionale possiamo evitare di considerare l’ultima coordinata (costante), ed utilizzare il Lemma 3.2.1 per valutare sin2θk ottenendo

γ (A4ABC) =cos2θk cos2φl, 1 − cos2φl

, (3.11)

che vedremo essere esattamente la WAM relativa alla faccia 4AOC. Infatti, quest’ultima viene creata dalla rotazione attorno all’asse x3 degli n + 1 punti

di Chebyshev-Lobatto del segmento AO, che si ha quando θ = π/2, cio`e k = n. Utilizzando la funzione quadratica standard (u, v) 7→ (u2, v2) otteniamo una WAM come in (2.2). Questa `e data esattamente dai punti

(A4AOC) = rj2sin2θ cos2φl, rj2sin2θ sin2φl, cos2θ

θ=

π 2

= =

r_j2cos2φl, r2jsin2φl, 0 = rj2 cos2φl, 1 − cos2φl, 0

. Trascuro il valore di x3 (che `e sempre nullo) ed ottengo, notando che vale

sempre j = k ⇒ r2_j = cos2θk. Infatti, si ha

r_j2= cos2 jπ 2n = cos2 kπ 2n = cos2θk (3.12)

Quindi si ha {r2_j}_j = {cos2θk}l e le WAM di γ(4ABC) e 4AOC risultano

essere in pratica identiche e del tipo desiderato, quello di (2.2), cosa che vale anche per 4ABC, per la propriet`a P1 delle WAM. Perci`o, come conse-guenza abbiamo che anche la WAM ristretta allo spigolo AC risulta essere composta dai punti di Chebyshev-Lobatto relativi ad esso.

Notiamo infine che ∀ k ∈ {1, . . . , n − 1}, cio`e fissando un angolo θk nella

WAM considerando fisso il valore di k , otteniamo l’intersezione 4A0OC0 del poliedro con un piano come in Figura 3.6. Ora, la WAM risultante `e (notare che 0 6= sin2θk = costante, poich´e k 6= n)

(39)

Figura 3.5: Restrizione bidimensionale della WAM per j ∈ {1, . . . , n − 1} fissato.

che pu`o essere trasformata in A4AOC semplicemente proiettandola sul piano

x3 = 0 (vedi Figura 3.8) e moltiplicandola per un fattore (sin2θk)−1

attra-verso una trasformazione affine che in questo caso `e equivalente a γ(·), con

γ (x1, x2, x3) = sin2θk −1   1 0 0 0 1 0 0 0 0     x1 x2 x3  

ottenendo, grazie a (3.12) ed al fatto che il domino di definizione di j e k `e lo stesso insieme,

γ A4A0_OC0 = . . . = r_j2 cos2φ_l, sin2φ_l, 0 = cos2θ_k cos2φ_l, sin2φ_l, 0

che è equivalente alla WAM A4AOC poiché il dominio di j è lo stesso di

quello di k.

Possiamo agire in maniera simile per dimostrare che ∀ j ∈ {1, . . . , n − 1}, cio`e fissando rj nella WAM, otteniamo l’intersezione del poliedro con un

piano parallelo al piano x1+ x2+ x3 = 1 (vedi Figura 3.5). Ora, la WAM

risultante `e (notare che 0 6= r2_j = costante, poich´e j 6= n)

(40)

(41)

Figura 3.7: Restrizione bidimensionale della WAM per l ∈ {1, . . . , n − 1} fissato.

(42)

che pu`o essere trasformata in A4AOC proiettandola ancora su piano x3 =

0 e moltiplicandola per`o stavolta per un fattore (r2_j)−1, attraverso una trasformazione affin, che in questo caso `e equivalente aeγ(·), con

e γ (x1, x2, x3) = r2j −1   1 0 0 0 1 0 0 0 0     x1 x2 x3   ottenendo e

γ A4A0_B0_C0 = . . . = sin2θ_k cos2φ_l, sin2φ_l, 0

(3.9)

= =cos2_θ

k cos2φl, sin2φl, 0

che `e equivalente alla WAM A4AOC.

Se fissiamo 2 dei 3 parametri della WAM, considereremo una restrizione unidimensionale di questa. Ci muoveremo in questo senso: fissato un para-metro, per quanto già visto ci riconduciamo ad una WAM ottenuta come trasformazione affine di un’altra WAM, del tipo di cui in (2.2). A que-sto punto, fissando un ulteriore parametro andremo a considerare uno dei segmenti della WAM, come è già stato fatto nella Proposizione 2.2.1 e per quanto visto la WAM sarà composta dagli n + 1 punti di Chebyshev-Lobatto relativi al segmento stesso, per ogni coppia di (rj, θk) o di (rj, φl) oppure di

(θk, φl) fissati. In particolare, questo accade per gli spigoli del tetraedro e

quindi si conclude.

Osservazione 8. Una volta trovata una WAM sul simplesso unitario tridi-mensionale, avremo anche una WAM su ogni tetraedro con le stesse costanti e cardinalità, grazie alla Proprietà P1 delle WAM. Sarà infatti sufficiente mappare i punti attraverso la trasformazione affine standard tra tetraedri. Corollario 3.2.3. La sequenza di griglie trapezoidali di Chebyshev-Lobatto

(43)

3.2 Mappatura sul simplesso 43 e n rj, φk, θ_k(1)₁ , . . . , θ(d−2)_k_d−2 o j,k,k1,...,kd−2 = cosjπ 2n × kπ 2n d−2

×

i=1 kiπ 2n prendendo j, k, k1, . . . , kd−2∈ {0, 1, 2, . . . , n}f `

e una WAM del simplesso unitario d-dimensionale, con C(An) = O(logdn)

e con card(An) = nd+ nd−1+ . . . + n + 1.

Dimostrazione. Per d = 1 vale banalmente. Per d = 2 e d = 3 abbiamo gi`a visto nelle Proposizioni 2.2.1 e 3.2.2 che le WAM in 2 e 3 dimensioni cos`ı costruite soddisfano i criteri imposti dalla tesi. Vediamo ora cosa accade per un d generico.

Prendendo la griglia B2nuguale alla Bmin (3.8) abbiamo una WAM per i

polinomi pari sul primo ottante della palla unitaria, grazie alla Proposizione 3.1.3 (in cui, ricordiamo, si ha proprio m = 2n. Ora, la trasformazione quadratica π2 : (u1, . . . , ud) 7→ (u21, . . . , u2d) dal primo 2d-ante al simplesso

unitario d-dimensionale è invertibile e seguendo la tecnica dimostrativa della Proposizione 3.2.2, grazie a una piccola estensione delle Proprietà P7 delle WAM (in realtà abbiamo bisogno di identificare solamente le WAM per i polinomi della forma p ◦ π2) abbiamo che An = π2(B2n) è una WAM del

simpleso unitario. Inoltre, card(An) = card(B2n) = Pd_i=1ni e C(An) =

(44)

(45)

Capitolo 4

Approssimazione discreta ai

minimi quadrati

In questo capitolo vedremo come sia possibile costruire facilmente un poli-nomio che approssimi una funzione continua f ai minimi quadrati su una WAM di un dominio prefissato. Nel paragrafo 4.1 spiegheremo il procedi-mento utilizzato per estrarre il polinomio approssimante ed il funzionaprocedi-mento degli algoritmi sui quali si basa. Nel paragrafo 4.2 illustreremo i risultati ottenuti applicando il procedimento di cui sopra alle WAM della palla e del simplesso costruite nel Capitolo 3, mostrando le stime degli errori assoluti di approssimazione commessi e la norma dell’operatore di proiezione.

4.1 Ricerca del polinomio approssimante

Consideriamo una WAM {An} di un insieme compatto polinomialmente

determinante K ∈ Rd (o K ∈ Cd)

A_n= {a1, . . . , aM}, M ≥ N = Nn= dim(Pdn) (4.1)

e la matrice rettangolare di tipo Vandermonde associata

V (a; p) := [pj(ai)], 1 ≤ i ≤ M, 1 ≤ j ≤ N, (4.2)

in cui a = (ai), mentre p = (pj) `e una data base per Pdn. Per comodit`a,

considereremo p come un vettore colonna p = (p1, . . . , pN)t

(46)

46 Approssimazione discreta ai minimi quadrati

Infatti, data una base per Pdn, per trovare il polinomio che approssima una

data funzione f ai minimi quadrati su un insieme di punti polinomialmente determinante An possiamo calcolare i coefficienti w1, . . . , wN ∈ R relativi

agli elementi della base che determinano il polinomio approssimante come segue: Lf (x) = N X i=1 wipi(x) .

Se a1, . . . , aN sono gli elementi di An, i coefficienti wisi calcolano facilmente

risolvendo il sistema lineare          w1p1(a1)+ . . . +wNpN(a1) w1p1(a2)+ . . . +wNpN(a2) . . . . w1p1(aN)+ . . . +wNpN(aN) = f (a1) f (a2) .. . f (aN)

che equivale in forma matriciale ad Aw = b con A ∈ N × N, vale a dire      w1p1(a1)+ . . . +wNpN(a1) w1p1(a2)+ . . . +wNpN(a2) .. . . .. ... w1p1(aN)+ . . . +wNpN(aN)           w1 w2 .. . wN      =      f (a1) f (a2) .. . f (aN)     

ovvero utilizzando semplicemente il comando Matlab w=A\b, con A = V (a; p) e b = (f (a1), . . . , f (aN))t.

Nel nostro caso i punti sono per`o M >> N e avendo A ∈ RM ×N e b = (f (a1), . . . , f (aM))t ci troviamo a che fare con un sistema

sovradeter-minato. Computazionalmente per`o non cambia nulla: il comando y=A\b di Matlab `e costruito in modo tale da risolvere i sistemi lineari cercando la migliore soluzione ai minimi quadrati nel caso che questi sistemi siano sovradeterminati o sottodeterminati.

Sorge ora però un problema: le matrici di Vandermonde sono tipicamente mal condizionate è ciò porta generalmente al calcolo di soluzioni non precise del sistema lineare associato. Per ovviare a tutto questo, opereremo un cambio di base attraverso due iterazioni della fattorizzazione QR ottenendo una matrice sensibilmente migliore.

Riportiamo ora il procedimento di cui sopra, insieme ad alcuni impor-tanti risultati come esposti da Sommariva e Vianello in [4].

(47)

4.1 Ricerca del polinomio approssimante 47

2. Q1 = Q2R2 ;

3. Q = Q2 ; T = R−11 R −1 2 .

Questo corrisponde ad un cambio di base da p alla base ortonormale discreta ϕ = (ϕ1, . . . , ϕN)t= Ttp (4.3)

rispetto al prodotto interno

hf, gi =

M

X

i=1

f (ai)g(ai) (4.4)

(qui viene usata la fattorizzazione QR con Q rettangolare M × N e R trian-golare superiore N × N ). Si osservi che la matrice di Vandermonde nella nuova base

V (a; ϕ) = V (a; p)T = Q `

e una matrice (unitaria) numericamente ortogonale, vale a dire Qt_{Q = 1.}

Due ortogonalizzazioni sono in generale sufficienti, a meno che la matrice originaria V (a; p) sia talmente mal condizionata (regola del pollice: nume-ro di condizionamento più grande del reciproco della precisione di macchi-na) che l’algoritmo fallisca. Questo ben noto fenomeno nell’ortogonalizza-zione numerica di Gram-Schmidt, chiamato twice is enough (due volte è abbastanza) è stato ampiamente studiato e spiegato in [7].

Denotando con LAn l’operatore discreto di proiezione ai minimi quadrati,

possiamo scrivere LAnf (x) = N X j=1 M X i=1 f (ai)ϕj(ai) ! ϕj(x) = M X i=1 f (ai)gi(x) (4.5) dove gi(x) = Kn(x, ai), i = 1, . . . , M ; Kn(x, y) := N X j=1 ϕj(x)ϕj(y) (4.6)

in cui Kn(x, y) `e il reproducing kernel (cf. [6]) corrispondente al prodotto

interno. In termini matriciali, l’insieme rilevante di generatori di Pdn (che

non `e una base quando M > N ) diviene semplicemente

(48)

dove la matrice di trasformazione T e la matrice ortogonale (unitaria) Q sono calcolate una volta per tutte per una mesh fissata. Inoltre, la norma dell’operatore ai minimi quadrati `e data da

||LAn|| = max x∈K M X i=1 |g_i(x)| = max x∈K||QT t_p(x)|| 1 . (4.8)

La propriet`a P9 ci assicura che le WAM descritte nella sezione prece-dente possono essere utilizzate direttamente per l’approssimazione ai mi-nimi quadrati di funzioni con un errore che quasi ottimale ed un fattore O(n log2n).

In basso riportiamo alcuni test numerici, tutti effettuati utilizando ba-siche funzioni linerari di Matlab [10], test che sono una piccola modifica di quelli gi`a proposti da Sommariva in [4].

Ricordando che essendo LAn una proiezione su P

d

n, per ogni funzione

continua f abbiamo

||f − LAnf || ≤ (1 + ||LAn||) min {||f − p||K, p ∈ P

d

n} (4.9)

e quindi, basandoci sui risultati computazionali esposti nella Tabella 4.2 possiamo dire che il fattore O(n log2n) dato dalla proprietà P9 è una stima decisamente rozza del limite reale, che è molto più piccolo. Vale la pena notare che cos`ı come le costanti di Lebesgue per l’interpolazione, anche le norme degli operatori polinomiali ai minimi quadrati sono invarianti rispetto alle trasformazioni affini, cos`ı che queste sono le stesse per ogni palla e per ogni simplesso tridimensionale.

Ai fini del calcolo computazionale, ipotizziamo di aver trovato trovato i coefficienti w che descrivono il polinomio approssimante come

LAnf (x) = w1ϕ1(x) + . . . + wNϕN(x)

utilizzando la base ϕ: `e facile convincersi del fatto che i coefficienti w che esprimono il polinomio approssimante rispetto alla base p, i.e.

LAnf (x) = w1p1(x) + . . . + wNpN(x)

sono quelli dati dalla relazione

w = T w. (4.10)

(49)

4.2 Risultati numerici 49

simplessi, possiamo calcolare le matrici Q e T per un dato grado una volta per tutte, con una data base p ed una WAM di riferimento An su un

in-sieme di riferimento (ad esempio la palla ed il simplesso unitari). Quindi, l’approssimazione polinomiale ai minimi quadrati di grado n per una data funzione f in K pu`o essere calcolata come

Lnf (x) = M

X

i=1

f (α(ai))gi(x), g(x) = QTtp(α−1(x))

in cui x = α(t) = At + b `e la trasformazione affine dall’insieme compatto di riferimento della famiglia1 a K.

Osservazione 10. Attraverso unioni finite e utilizzando la proprietà P4 è immediato costriuire una WAM per un poligono partendo dalla dalla WAM (3.10), una volta che abbiamo una triangolazione del poliedro. Quest’ulti-ma può essere ottenuta da uno degli algoritmi di triangolazione ampiamente usati nel contesto della geometria computazionale. La costante di una tale WAM può essere limitata dal massimo delle costanti corrispondenti ai sim-plessi che la formano, quindi è O(log3n) a prescindere del numero di lati del poliedro e del fatto che questo sia concavo o convesso. D’altra parte, la cardinalità della WAM è all’incirca di n3 volte il numero dei simplessi. Quin-di, il limite teorico della norma dei corrispondenti operatori di proiezione ai minimi quadrati dato dalla proprietà P9 è ancora ||LAn|| = O(n

3/2_log3_n)

in cui la costante relativa al simbolo O(·) `e ora proporzionale alla radice quadrata del numero dei simplessi.

4.2 Risultati numerici

Diamo innanzitutto una lista delle funzioni-test utilizzate per testare la bont`a del metodo, elencate nella Tabella 4.1. Nelle Figure 4.1 e 4.2 si pos-sono trovare invece le immagini delle WAM di grado n = 6 rispettivamente per la palla e per il tetraedro unitari.

Riportiamo inoltre i risultati numerici ottenuti sviluppando in linguag-gio Matlab (vedi Appendice A) quanto studiato fino ad ora. Nella Tabella 4.2 troviamo le norme (4.8) degli corrispondenti operatori di proiezione ai minimi quadrati per le WAM della palla e del simplesso, valutate numeri-camente trovando il massimo su una mesh molto fine, confrontandole con il valore della limitazione teorica data dalla propriet`a P9 delle WAM, i.e.

1

(50)

(51)

4.2 Risultati numerici 51

(52)

52 Approssimazione discreta ai minimi quadrati indice f (x) = 1 ((x − 2/5)2+ (y − 2/5)2+ (z − 2/5)2)1/2 2 ((x − 1/2)2+ (y − 1/2)2+ (z − 1/2)2)1/2 3 (x + y + z)20 4 e(x−1/2)2+(y−1/2)2+(z−1/2)2 5 e−100((x−1/2)2+(y−1/2)2+(z−1/2)2) 6 cos(30(x + y + z)) 7 1 8 ex+y+z 9 1/(1 + 16(x2+ y2+ z2)) 10 e(x2+y2+z2)3/2 11 e−(x2+y2+z2) 12 e−(x2+y2+z2)−1 13 cos(x2_{+ y}2_{+ z}2₎ 14 cos(x + y + z) 15 (x2+ y + xz)4

Tabella 4.1: funzioni test.

card(An) · log3(n). Come anticipato, possiamo notare che la limitazione

teo-rica si rivela essere esagerata già per n piccolo. Nel codice è stata usata come base polinomiale p il prodotto delle basi di Chebyshev dei minimi rettan-goli contenenti la palla unitaria nel primo caso ed il simplesso unitario nel secondo. p è stata ottenuta ottenuta moltiplicando tra loro le componenti di tre basi unidimensionali di Chebyshev di grado n (una per ogni variabi-le)2 e selezionando come componenti i prodotti il cui grado totale non sia maggiore di n. Essa fornisce una matrice di Vandermonde iniziale che non è eccessivamente malcondizionata, permettendoci di lavorare con una buona base già dopo due sole ortogonalizzazioni con una buona base. Nella Tabella 4.3 riportiamo gli errori in norma infinito commessi nel calcolo del polinomio approssimante ai minimi quadrati sulle WAM di grado n = 10 della palla e del tetraedro per ogni funzione test. Si noti che relativamente al tetraedro, per poter lavorare con gradi di n si rende necessaria la ricerca di una base p migliore, in quanto la matrice di Vandermonde si rivela fortemente mal-condizionata per n ≥ 16. Il calcolo della norma dell’operatore di proiezione ai minimi quadrati viene quindi falsato, risultando dell’ordine delle migliaia

2_{ognuna composta dai polinomi di Chebyshev fino al grado n, cio`}_{e {T}

0(x), . . . , Tn(x)}

(53)

4.2 Risultati numerici 53 n = 2 4 6 8 10 12 14 16 18 20 LIM B 2 30 107 243 445 719 1068 1494 2000 2587 LIM T 1 25 93 218 407 666 999 1409 1898 2467 ||LAn||B 2.4 4 5.8 7.6 9.5 11.5 13.3 15.4 17.4 19.4 ||LAn||T 2.6 4.3 5.9 7.4 9 10.7 12.6 24.1 X X

Tabella 4.2: ||LAn||B e ||LAn||T sono le norme degli operatori di proiezione

polinomiale ai minimi quadrati sulla palla e sul tetraedro al variare di n. LIM B e LIM T sono le limitazioni teoriche per la palla e per il tetraedro unitari date dalla propriet`a P9 delle WAM.

funzione 1 2 3 4 5 6 7

Err. Palla 3e-03 3e-02 2e+03 6e-04 3e-01 2e+00 5e-15 Err. Tetra 3e-03 3e-04 1e-03 6e-08 4e-05 1e+00 7e-15

funzione 8 9 10 11 12 13 14 15

Err. Palla 4e-08 5e-02 8e-04 8e-07 4e-03 1e-06 3e-09 3e-15 Err. Tetra 4e-11 8e-04 8e-06 2e-08 4e-04 3e-08 1e-11 3e-12

Tabella 4.3: Errori in norma infinito commessi nel calcolo del polinomio approssimante ai minimi quadrati sulle WAM di grado n = 10.

(54)

(55)

Capitolo 5

Interpolazione su Punti di

Fekete Approssimati estratti

da una WAM

In questo capitolo vedremo come a partire da una WAM An della palla o

del tetraedro sia possibile costruire un insieme Fn di buoni punti di

inter-polazione, detto insieme di Punti di Fekete Approssimati. Nel paragrafo 5.1 verranno introdotti i concetti ed i risultati fondamentali necessari per poter lavorare con i Punti di Fekete. Nel paragrafo 5.2 verr`a spiegato come cal-colare praticamente questi Punti di Fekete con Matlab. Nel paragrafo 5.3 verranno invece illustrerati i risultati ottenuti applicando il procedimento di cui sopra alle WAM della palla e del simplesso costruite nel Capitolo 3, mostrando le stime degli errori assoluti di approssimazione commessi e la costante di Lebesgue dell’operatore di interpolazione.

5.1 Punti (Approssimati) di Fekete

Definizione 5.1.1. Data una qualsiasi base {ϕj}j di Pdn, un Insieme di

Punti di Fekete `e una famiglia di punti (a1, . . . , aNn) con Nn = dim(P

d n) = n+d

d che massimizza il valore assoluto del Determinante di Vandermonde

VDM(a1, . . . , aNn) = det(ϕi(aj)).

Definizione 5.1.2. Sia ora Anuna WAM per K con costante C(An).