Calcolo dei Punti di Fekete Approssimati

abbiamo che det(V₁) `e massimo per gli stessi {a_i}_i che rendono massimo det(V2) e quindi i Punti di Fekete risultano essere gli stessi in entrambi i casi.

5.2 Calcolo dei Punti di Fekete Approssimati

Nella pratica il calcolo dei Punti Approssimati di Fekete come introdotti dal-la Definizione 5.1.2 risulta essere infattibile in pratica, essendo un problema NP-hard. Per questo motivo utilizzeremo un algoritmo greedy euristico per calcolare quelli che saranno gli effettivi Punti di Fekete Approssimati. Dovre-mo quindi cercare un procedimento che data una base {ϕ_j}_j di P³n selezioni in tempi ragionevoli N = Nn punti tra gli M = card(An) punti della WAM in modo che il determinante della matrice di Vandermonde sia il pi`u grande possibile. Non sar`a in generale una soluzione ottima, ma vedremo che sar`a comunque pi`u che soddisfacente.

Prima di introdurre il procedimento vero e proprio che seleziona i Punti di Fekete Approssimati, spiegheremo come funziona il cuore dell’algoritmo, che `e semplicemente il comando y=A\b (backslash) di Matlab. Allo stesso modo di Bos e Levenberg, [2], osserviamo prima di tutto che il coman-do A=chebvan3D(n,WAM) produce la matrice di Vandermonde A = [pj(ai)] dove {pj} `e la base di Chebyshev-Prodotto per P³n (come gi`a fatto nel paragrafo 4.1) e gli a<sub>i</sub> sono gli elementi della WAM. Utilizzeremo per`o V = At ∈ RN ×M: in questo modo il sistema lineare sar`a fortemente in-determinato e Matlab risolver`a questo problema calcolando prima di tutto una fattorizzazione QR di V ( Q ∈ R^{N ×N} ortogonale e R ∈ R^{N ×M} trian-golare superiore) con pivoting delle colonne. In questo modo la procedura seleziona le n colonne pi`u significative tra le M >> N colonne di V cercan-do di massimizzare il valore assoluto del determinante della matrice V∗ che si viene a creare considerando solo le colonne selezionate. Si noti che ogni colonna di V corrisponde ad un punto della WAM e quindi il procedimento fatto si rivela essere una selezione dei punti pi`u significativi della WAM. Si rimanda a [2, 8] per i dettagli. In sostanza Matlab risolve il sistema lineare considerando solo le colonne (quindi i punti) selezionati ottenendo un vettore soluzione y ∈ R^N e restituendo y ∈ R^M, in cui le componenti relative ai punti non scelti sono nulle: resta quinidi solamente da utilizza-re il comando ind=find(abs(w)>0) per otteneutilizza-re un vettoutilizza-re contenente gli indici che identificano i punti scelti, che saranno appunto i Punti di Fekete Approssimati.

de-58

Interpolazione su Punti di Fekete Approssimati estratti da una WAM

scritta in precedenza e denotando con X l’insieme dei punti della WAM, otteniamo l’insieme X∗ dei Punti di Fekete Approssimati attraverso il se-guente

Algoritmo 1. (Punti di Fekete Approssimati) • m = [1, . . . , 1] (vettore colonna di lunghezza N ) • w = Vt\m; ind = find(w 6= 0);

• X_∗ = X(ind); V∗ = V (ind, :)

L’algoritmo restituisce inoltre una matrice V∗ non singolare che corri-sponde ai punti selezionati e si rivela utile per l’interpolazione polinomiale. Si noti che a noi non interessa la soluzione del sistema, ma solamente l’in-sieme dei Punti di Fekete Approssimati e che la fattorizzazione QR non dipende dal vettore destro m introdotto, perci`o questi potr`a avere un valore qualsiasi (diverso da 0); nel caso di questo algoritmo utilizziamo un vettore colonna lungo N i cui valori sono uguali ad 1 per ogni componente.

Riportiamo ora l’enunciato del teorema dovuto a Bos, Calvi e Levenberg, [1], che mostra che i Punti di Fekete ed i Punti di Fekete Approssimati si distribuiscono asintoticamente allo stesso modo sugli stessi insiemi.

Teorema 5.2.1. Sia K ∈ R^d o C^d compatto, senza poli multipli, polino-mialmente convesso e regolare (nel senso della teoria del Pluripotenziale, vedi [9]) e tale che per n = 1, 2, · · · l’insieme An ⊆ K sia una WAM. Siano {b⁽ⁿ⁾₁ , b⁽ⁿ⁾₂ , . . . , b⁽ⁿ⁾_N } i Punti di Fekete Approssimati selezionati dal-l’Algoritmo 2 calcolati a partire da una qualunque base B_n. Denotando con mn la somma dei gradi degli N monomi di grado al massimo n, che `e m_n= dnN/(d + 1). Allora

(1) limn→∞|vdm(b⁽ⁿ⁾₁ , . . . , b⁽ⁿ⁾_N )|^1/mn = τ (K), il diametro transfinito di K; (2) la misura di probabilit`a discreta µ_n := _N¹ PN

j=1δ

b⁽ⁿ⁾_j converge debol-mente alla misura di probabilit`a d’equilibrio pluripotenziale teorico dµ_K di K

I punti di fekete calcolati dall’Algoritmo 1 dipendono dalla base polino-miale utilizzata. Dal Teorema 5.2.1 `e per`o chiaro che questi dovrebbero ave-re asintoticamente la stessa distribuzione (quella dei veri punti di Fekete). Utilizzare basi sbagliate, specialmente per il problema dell’interpolazione, porta ad insiemi di punti inadeguati, a causa del noto cattivo condiziona-mento delle matrici di Vandermonde. Come gi`a fatto per l’approssimazione

5.3 Risultati numerici 59

polinomiale nel paragrafo 4.1, l’algoritmo seguente cerca di ovviare a questo problema, servendosi di cambi di base attraverso la fattorizzazione QR della matrice di Vandermonde (non trasposta, con Q rettangolare ortogonale e R quadrata triangolare superiore). Per avere dettagli e approfondimenti su come funzionano questi cambi di base e sui vantaggi che apportano si guardi l’ottimo lavoro di Bos e Levenberg, [2].

Algoritmo 2. (Punti di Fekete Approssimati con iterazione) • V₀= V ; P0= I;

• for k = 0, . . . , s − 1

V_k= Q_kR_k; U_k= inv(R_k); V_k+1= V_kU_k; P_k+1= P_kU_k; end;

• m = [1, 1, . . . , 1] (vettore colonna di lunghezza N ); µ = Pt sm; • w = Vt

s\µ; ind = find(w 6= 0); • X_∗= X(ind); V∗= V_s(ind, :)

Una moltiplicazione per U_k corrisponde ad un cambio di base nella ma-trice di Vandermonde. Per avere dettagli approfonditi sui vantaggi dovuti a queste ortogonalizzazioni rimandiamo a [2], sottolineando ancora una vol-ta che normalmente si utilizzano solamente 2 iterazioni, grazie alle quali si ottiene una matrice Q ortogonale fino alla precisione di macchina se la matrice V₀ non `e troppo malcondizionata (regola del twice is enough). Ad ogni modo V<sub>2</sub> sar`a in generale quasi ortogonale o comunque abbastanza ben condizionata per applicare l’Algoritmo 1, anche se la matrice iniziale V0 non `

e numericamente di rango massimo.

5.3 Risultati numerici

Nelle Figure 5.1, 5.2, 5.3 e 5.4 troviamo le immagini delle WAM di grado n = 6 e dei Punti di Fekete Approssimati da esse estratti nei casi relativi alla palla e al tetraedro unitari.

Riportiamo ora i risultati numerici ottenuti sviluppando in codice Matlab (vedi Appendice A) quanto studiato fino ad ora. Nella Tabella 5.2 trovia-mo le costanti di Lebesgue (vedi Osservazione 11) relative al polinomio che approssima una funzione interpolandola nei Punti di Fekete Approssimati

60

Interpolazione su Punti di Fekete Approssimati estratti da una WAM

Figura 5.1: WAM e Punti di Fekete Approssimati di grado n = 6 della palla unitaria. I cerchi neri rappresentano i 343 punti della WAM, mentre i pallini verdi gli 84 Punti di Fekete approssimati estratti da tale WAM.

5.3 Risultati numerici 61

Figura 5.2: Punti di Fekete Approssimati estratti da una WAM di grado n = 6 della palla unitaria.

62

Interpolazione su Punti di Fekete Approssimati estratti da una WAM

Figura 5.3: WAM e Punti di Fekete Approssimati di grado n = 6 del tetrae-dro unitario. I cerchi neri rappresentano i 259 punti della WAM, mentre i pallini verdi gli 84 Punti di Fekete approssimati estratti da tale WAM.

5.3 Risultati numerici 63

Figura 5.4: Punti di Fekete Approssimati estratti da una WAM di grado n = 6 del tetraedro unitario.

64

Interpolazione su Punti di Fekete Approssimati estratti da una WAM

funzione 1 2 3 4 5 6 7

Err. Palla 5e-03 3e-02 2e+03 8e-04 3e-01 6e+00 0e-00 Err. Tetra 5e-03 7e-04 3e-03 3e-07 9e-05 2e+00 0e-00

funzione 8 9 10 11 12 13 14 15

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

Tabella 5.1: Errori in norma infinito commessi nel calcolo del polinomio interpolatore sui Punti di Fekete di grado n = 10 sulla palla e sul tetraedro.

n = 2 4 6 8 10 12 14 16 18 20

Limit Λ_n 3 93 483 1484 3492 6981 12498 20653 32115 47613

Λn Palla 4 11 22 42 63 112 145 227 275 325

Λ_n Tetra 2 10 21 41 86 106 147 191 X X

Tabella 5.2: Errori in norma infinito commessi nel calcolo del polinomio interpolatore sui Punti di Fekete di grado n = 10 sulla palla e sul tetraedro.

estratti dalle WAM della palla e del simplesso, confrontata con la stima data dalla propriet`a P10 delle WAM. Relativamente al caso della palla, la costan-te di Lebesgue cos`ı calcolata si rivela drasticamencostan-te minore rispetto a quella stimata dalla propriet`a P10 per ogni valore di n, mentre relativamente al caso del tetraedro questo accade fino al grado n = 16 (si rimanda al para-grafo 4.2 per i dettagli). Nel codice `e stata usata come base polinomiale p il prodotto delle basi di Chebyshev dei minimi rettangoli contenenti la palla unitaria nel primo caso ed il simplesso unitario nel secondo (vedi paragrafo 4.2). Infine nella Tabella 5.1 riportiamo gli errori in norma infinito commes-si nel calcolo del polinomio interpolatore sui Punti di Fekete Approscommes-simati estratti da una WAM di grado n = 10 della palla e del tetraedro per ogni funzione test.

66

Interpolazione su Punti di Fekete Approssimati estratti da una WAM

Appendice A

Implementazione in Codice