Stable Order Ideal Algorithm

Daremo ora alcune denizioni e notazioni che saranno utili in seguito. Per semplicare, assumeremo implicitamente che ogni insieme nito di punti o di polinomi sia una t-upla, in modo che gli elementi possano essere ordinati in qualche modo, e possiamo riferirci al k-esimo elemento usando l'indice k.

Sia n > 1; richiamiamo alcuni concetti relativi all'anello dei polinomi P = R[x1, . . . , xn].

Denizione 3.3.1. Sia X = {p1, . . . , ps}sia un insieme nito e non vuoto di

punti di Rn _{e sia G = [g}

1, . . . , gk] un insieme non vuoto e nito di polinomi.

(a) L'ideale I(X) = {f ∈ P | f(pi) = 0 ∀pi ∈ X} viene chiamato il

vanishing ideal di X.

(b) La mappa R-lineare evalX : P → R

s _{denita da}

eval_X= (f (p1), . . . , f (ps))

viene chiamata la evaluation map associata ad X. Per brevità scriveremo f(X) per indicare evalX(f ).

(c) La evaluation matrix di G associata ad X, indicata con MG(X) ∈

M ats×k(R) ha l'entrata (i, j) uguale a gj(pi), ossia le sue colonne sono

l'immagine dei polinomi gj tramite la evaluation map.

Denizione 3.3.2. Sia Tn _{il monoide dei prodotti delle potenze di P e sia}

(a) La factor closure (abbr. closure ) di O è l'insieme O di tutti i prodotti delle potenze in Tn che dividono qualche prodotto di potenze di

O.

(b) L'insieme O viene chiamato un order ideal se O = O, ossia se O è factor closed.

(c) Sia I ⊆ P un ideale zero-dimensionale,e s = dim(P/I); se O è factor closed e la classe di resto dei suoi elementi forma una base di P/I) allora la chiameremo una quotient bases per I.

(d) Sia O factor closed; il border ∂O di O è denito da ∂O = (x1O ∪ . . . ∪ xnO) \ O

(e) Se O è factor closed allora gli elementi dell'insieme di generatori mini- male dell'ideale monomiale corrispondente a Tn_{\ O vengono chiamati}

i corner di O.

Denizione 3.3.3. Sia O = {t1, . . . , tµ} un order ideal e sia ∂O il suo

border. Sia B = {g1, . . . , gν} un insieme di polinomi della forma

gj = bj −

Pµ

i=1αijtj

dove ogni αij ∈ R. Sia I ⊆ P un ideale contenente B. Se le classi di resto

degli elementi di O formano una base su R di P/I, allora B viene chiamata una border basis di I.

Nel seguito, in modo da misurare la distanza tra punti di Rn_{, useremo la}

norma euclidea k . k. In aggiunta, data E una matrice n × n diagonale posi- tiva, useremo anche la weighted two norm k . kE come denita in Dahlquist

et al. (1974). Per completezza, ricordiamo la loro denizione: k v k:=qPn

j=1v2j e k v kE:=k Ev k.

Ricordiamo anche la denizione di empirical point (vedi Stetter 2004) e Abbott et al.(2007)).

Denizione 3.3.4. Sia p ∈ Rn _{un punto e sia ε = (ε}

1, . . . , εn), con ogni

εi ∈ R+, il vettore delle tolleranze. Un empirical point pε è la coppia

Sia pε _{un empirical point. Deniamo il suo ellissoide delle perturba-}

zioni:

N (pε_{) = {˜p ∈ R}n _{: k ˜p − p k} E≤ 1}

dove E è la matrice diagonale positiva E = diag(1 ε1, . . . ,

1

εn). Questo insieme

contiene tutte le perturbazioni ammissibili del valore specico p, ossia tutti i punti che dieriscono da p meno della tolleranza.

Da ora in avanti assumeremo che gli empirical point hanno tutti la stessa tolleranza ε, cosi come è ragionevole che sia se provengono da dati dal mondo reale misurati con la stessa accuratezza. In particolare questa assunzione ci permette di usare le E-weighted norm di Rn_{per misurare la distanza tra due}

empirical point.

Dato un insieme nito Xε _{di punti empirici tutti con la stessa tolleranza}

ε, introduciamo il concetto dell'insieme di punti leggermente perturbati ˜X tramite la seguente denizione.

Denizione 3.3.5. Sia Xε _{un insieme di empirical point con tolleranza uni-}

forme ε e con X ⊂ Rn_{. Ogni insieme di punti ˜X := { ˜p}

1, . . . , ˜ps} ⊂ Rn i cui

elementi soddisfano

( ˜p1, . . . , ˜ps) ∈Qs_i=1N (pεi)

viene chiamata una perturbazione ammissibile di Xε

Denizione 3.3.6. Gli empirical point pε

1 e pε2 con valori specici p1, p2 ∈ Rn

sono detti distinti se

N (p1) ∩ N (p2) = ∅.

Passiamo adesso alla descrizione del problema formale; useremo il concet- to di punti empirici per descrivere formalmente i dati approssimati: l'input X è visto come l'insieme dei valori specici di Xε, che consiste di s distinti empirical point aventi tutti ε come tolleranza ssata.

Dato l'insieme Xε, vogliamo determinare una base strutturalmente sta-

bile B del vanishing ideal I(X). Intuitivamente, una base B è considerata essere strutturalmente stabile se, per ogni perturbazione ammissibile ˜X di Xε, è possibile creare un base ˜B di I(˜X) per mezzo di una leggera e continua

variazione dei coecienti dei polinomi di B, vale a dire che esiste una base ˜B di I(˜X) i cui polinomi hanno lo stesso supporto dei corrispondenti polinomi di B. Data una base di polinomi B, chiameremo l'unione dei supporti dei suoi polinomi la struttura di B.

Un buon punto di partenza sono appunto le Border Basis. La loro struttu- ra infatti è facilmente calcolabile e completamente determinata dalla quotient basis O sulla quale la border Bases è fondata (vedi denizione 3.3.3). Usando le border basis, il problema di calcolare una rappresentazione strutturalmen- te stabile del vanishing ideal I(X) si riduce così al problema di trovare una quotient bases O per I(˜X) valida per ogni perturbazione ammissibile ˜X. La prossima denizione ssa questa nozione e la generalizza ad ogni altro order ideal.

Denizione 3.3.7. Sia O un order ideal, allora O è stabile rispetto ad Xε se la evaluation matrix MO( ˜X) ha rango massimo per ogni perturbazione ammissibile ˜X di Xε.

La proposizione seguente evidenzia l'importanza della stable quotient bases.

Proposizione 3.3.1. Sia Xε _{un insieme di s distinti empirical point, e sia}

O = {t1, . . . , ts}una quotient bases per I(X) stabile rispetto a Xε. Allora, per

ogni perturbazione ammissibile ˜X di Xε_{, il vanishing ideal I(˜X) ha una O-}

border bases. Inoltre, se ∂O = {b1, . . . , bν} è il border di O allora ˜B consiste

di ν polinomi della forma: gj = bj−

s

X

i=1

αijti per j = 1, . . . , ν (3.3)

dove i coecienti αij soddisfano il sistema lineare

bj( ˜X) =

Ps

i=1αijti( ˜X).

Dimostrazione. Siano ˜X una perturbazione ammissibile di Xε e

eval_X˜ : P → Rs

la evaluation map associata all'insieme ˜X. È facile provare che I(˜X) = ker(eval_X˜) e di conseguenza, che l'anello quoziente P/I(˜X) è isomorfo a Rs

come spazio vettoriale. Poichè O è stabile rispetto all'empirical set Xε, ne

segue che {t1( ˜X), . . . , ts( ˜X)} sono vettori linearmente indipendenti. Inoltre la cardinalità di ˜X eguaglia quella di O, così la classe di resto degli elementi di O forma una base dello spazio vettoriale P/I(˜X) .

Sia vj = bj( ˜X) il vettore di valutazione associato al prodotto di potenze

bj che giace nel border ∂O; ogni vj può essere espresso come

vj =

Ps

i=1αijti( ˜X) per qualche αij ∈ R

Per ogni j deniamo il polinomio gj = bj −Ps_i=1αijti. Per costruzione

eval_X˜(gj) = 0, e così ˜B = {g1, . . . , gν} è contenuta in I(˜X); ne segue che ˜B è

la O-border bases dell'ideale I(˜X).

Osserviamo che i coecienti αij di ogni polinomio gj ∈ ˜B sono le com-

ponenti della soluzione αj del sistema lineare (MO)(I( ˜X))αj = bj( ˜X). Ne segue che αij sono funzioni continue dei punti dell'insieme ˜X e quindi, visto

che O è stabile rispetto a Xε, subiscono solo variazioni continue man mano

che ˜X cambia. Adesso, la denizione di stable border bases segue in maniera naturale.

Denizione 3.3.8. Sia Xε un insieme nito di empirical point distinti, sia

O una quotient bases per il vanishing ideal I(X). Se O è stabile rispetto a Xε

allora la O-border bases B per I(X) si dice che è stabile rispetto all'insieme Xε.

Il problema di calcolare una stable border bases del vanishing ideal di un insieme Xε di empirical point è quindi completamente risolto una volta

che abbiamo trovato una quotient bases O che è stabile rispetto a Xε_{. Se}

abbiamo una O siatta, la proposizione 3.3.1 e l'osservazione successiva sulla continuità dei coecienti αij provano l'esistenza della corrispondente stable

border bases dell'ideale I(X).

Concludiamo osservando che ogni O-border bases del vanishing ideal I(X) è stabile rispetto a Xδ per un valore sucientemente piccolo della tolleranza

δ. Ciò è equivalente a dire che ogni quotient bases O di I(X) ha una regione di stabilità, come dimostra la seguente proposizione.

Proposizione 3.3.2. Sia X un insieme nito di punti di Rne I(X) il suo va-

nishing ideal; sia O una quotient bases per I(X). Allora esiste una tolleranza δ = (δ1, . . . , δn) con δi > 0 tale che O è stabile rispetto a Xδ.

Dimostrazione. Sia MO(X) la evaluation matrix di O associata all'in-

sieme X; allora MO(X) è una matrice strutturata i cui coecienti dipendono

in maniera continua dai punti in X. Poichè, per ipotesi, la O-border bases del vanishing ideal I(X) esiste, ne segue che la matrice è invertibile. Ricordando

che il determinante è una funzione polinomiale nelle entrate della matrice, e osservando che le entrate di MO(X) sono polinomi nelle coordinate dei pun-

ti, possiamo concludere che esiste una tolleranza δ = (δ1, . . . , δn), con ogni

δi > 0 tale che det(MO( ˜X) ) 6= 0 per ogni perturbazione X di X.˜

Tuttavia, poichè la tolleranza ε degli empirical point in Xε _{è data a priori}

dalle misurazioni, la proposizione 3.3.2 non risolve il problema. Se la data tolleranza ε è maggiore della regione di stabilità di una quotient bases O data, la border bases corrispondente non sarà stabile rispetto a Xε_{; questa}

situazione è mostrata nel seguente esempio.

Esempio 3.3.1. Sia Xε _{l'insieme degli empirical point avente}

X = {(−1, −5), (0, 2), (1, 1), (2, 4.1)} ⊂ R2

come insieme di valori specici e ε = (0.15, 0.15) come tolleranza; sia ˜

X = {(−1 + e1, −5 + e2), (e3, −2 + e4), (1 + e5, 1 + e6), (2 + e7, 4.1 + e8)}

una perturbazione ammissibile generica Xε, dove i parametri e

i ∈ R soddi-

sfano

k (e1, e2) kE≤ 1 k (e3, e4) kE≤ 1 k (e5, e6) kE≤ 1 k (e7, e8) kE≤ 1.

Consideriamo dapprima O1 = {1, x, y, x2}, che è una quotient bases per

I(X). La corrispondente border bases B1 di I(X) non è stabile rispetto a Xε.

Consideriamo la perturbazione ˜X = {(−1, −5), (0, 2), (1, 1), (2, 4)} di Xε_.

La evaluation matrix MO1( ˜X) è singolare per cui non esiste una O1- bor-

der bases di I(˜X). Ne segue che O1 non è stabile rispetto a Xε in quanto la

sua 'regione di stabilità' è troppo piccola rispetto alla data tolleranza ε. Adesso consideriamo la quotient bases O2 = {1, y, y2, y3}, che è stabile

rispetto a Xε_{. Infatti, per ogni perturbazione ˜X di X}ε_{, osserviamo che M} O2( ˜X)

è una matrice di Vandermonde il cui determinante è uguale a

(e4− e2+ 3)(e6− e2+ 6)(e8− e2+ 9.1)(e6− e4+ 3)(e8− e4+ 6.1)(e8− e6+ 3.1).

Poichè ogni | ei |≤ 0.15, ne segue che, per ogni perturbazione ˜X, la matrice

MO2( ˜X) è invertibile, e così è sempre possibile calcolare una O2-border bases

dell'ideale I(˜X). Infatti O2 è stabile rispetto a X(δ1,δ2), dove δ1 è illimitato e

Nel seguito aronteremo il problema di trovare un order ideal O stabile rispetto ad un insieme nito di s distinti empirical point, Xε. Se O con-

tiene s prodotti di potenze, cioè se O è una quotient bases di I(X), anche la corrispondente stable border bases viene calcolata. Gli esempi numerici mostrano che O può avere cardinalità minore di s quando la tolleranza sui punti è in un certo senso, troppo grande; questo fenomeno verrà illustrato nell'esempio...Indagheremo poi sulla cause di questa 'terminazione prematu- ra'. Poichè nelle misurazioni del mondo reale la tolleranza ε presente nei dati è relativamente piccola, l'interesse verrà focalizzato su piccole perturba- zioni ˜X dell'empirical set Xε_{. Per questa ragione ci baseremo su un'analisi}

con un errore del primo ordine, presenteremo un algoritmo che calcola uno stable order ideal O. In modo da studiare la stabilità di O useremo alcuni risultati sull'approssimazione al primo ordine delle funzioni razionali e intro- durremo una descrizione parametrica della perturbazione ammissibili ˜X di Xε. Se l'output dell'algoritmo è eettivamente una quotient bases allora la corrispondente stable border bases B esiste per I(X). Per determinare B è suciente trovare il border di O (un semplice calcolo combinatorio), e quindi per ogni elemento del border risolvere un sistema lineare.(vedi proposizione 3.3.1)

Segue ora qualche osservazione sull'approssimazione al primo ordine. Siano e = (e1, . . . , en) indeterminate e sia F = R(e) il campo delle fun-

zioni razionali. Usiamo la notazione del multi-indice per dare l'espansione formale di Taylor di f ∈ F in 0 : f =P |α|>0 Dα_{f (0)} α! e α_.

Ricordiamo che dato α = (α1, . . . , αm) ∈ Nm, abbiamo

| α |= (α1+ . . . + αm)e α! = α1! . . . αm!. In maniera simile Dα _{= D}α1 1 . . . Dαmm (dove D j i = ∂j/∂e j i) e eα = e α1 1 . . . eαmm.

Ogni f ∈ F può essere decomposto in componenti di grado omogeneo nel modo seguente: f =P k>0f dove fk = P |α|=k Dα_{f (0)} α! e α

e dove, per convenzione, D(0...0)_{f = f. Ogni polinomio f}

k viene chia-

mo decomporre una matrice M ∈ Matr×c(F ) in parti omogenee nel modo

seguente.

Denizione 3.3.9. Sia M = (m(i, j)) una matrice in M ∈ Matr×c(F );

deniamo Mk la componente omogenea di grado k di M come la matrice

la cui entrata (i, j) è la componente omogenea di grado k di m(i, j).

Sia v ∈ M ∈ Matr×1(F ) e M ∈ Matr×c(F ) una matrice di rango mas-

simo, con r ≥ c. Deniamo α ∈ Matc×1(F ) e ρ ∈ Matr×1(F ) tramite le

seguenti formule:

α = (MtM )−1Mtv (3.4) ρ = v − M α

Osserviamo che per ogni punto δ ∈ Rn _{che giace nel dominio di α,}

possiamo valutare per ottenere x = α(δ) come la least square solution di M (δ)x ≈ v(δ), e che il resto (residuo) corrispondente è ρ(δ).

Nella nostra applicazione, la matrice M comprende solo entrate polino- miali, in modo che il dominio di α contenga precisamente quei punti δ ∈ Rn

nei quali det(M(δ)t_{M (δ) 6= 0), ossia in cui M(δ) ha rango massimo (in}

M atr×c(R))

La proposizione seguente caratterizza le componenti omogenee di grado 0 e 1 di α e ρ.

Proposizione 3.3.3. Siano r, c ∈ N con r > c; sia v un vettore in Matr×1(F )

e sia M una matrice di rango massimo in Matr×c(F ). Sia α ∈ Matr×1(F )

e ρ ∈ Matr×1(F ) denita come in (2). Allora le componenti omogenee di

grado 0 e 1 di α sono

α0 = (M0tM0)−1)v0 (3.5)

α1 = (M0tM0)−1)(M0tv1+ M1tv0− M0tM1α0− M1tM0α0

e le componenti omogenee di grado 0 e 1 di ρ sono

ρ0 = v0− M0α0 (3.6)

ρ1 = v0− M0α1− M1α0

Dimostrazione Per prima cosa proveremo un semplice risultato sulle componenti omogenee di grado 0 e 1 dell'inversa di una matrice. Sia A un

elemento non singolare di Matc×c(F ) e sia B la sua inversa. Le componenti

omogenee B0 e B1 sono date da

B0 = A−10 B1 = −A−10 A1A−10 = −B0A1B0. (3.7)

Mostreremo questo decomponendo A e B nella somma di componenti omo- genee : A = A0+ A1+ A2+ e B = B0+ B1+ B2+ dove A2+ = P i≥2Ai e B2+ = P

i≥2Bi. Adesso, poiché AB = I, la matrice

identica di ordine c × c, abbiamo

(A0+ A1+ A2+)(B0+ B1+ B2+) = I

e la nostra aermazione si ottiene immediatamente dopo aver decomposto il prodotto in componenti omogenee. Adesso dimostriamo il risultato della proposizione. Poiché M è una matrice di rango massimo, la matrice Mt_{M è}

non singolare cosi possiamo denire

α = A−1Mtv (3.8) ρ = v − M α (3.9) Applicando a 3.9 la homogeneous degree decomposition no al grado 1 ab- biamo

ρ0+ ρ1 = (v0− M0α0) + (v1− M0α1− M1α0)

cosi (3.6) segue.

Poichè A0 = M0tM0 e A1 = M0tM1 + M1tM0 dalla formula 3.7 abbiamo le

prime 2 componenti omogenee di B = A−1 _{≡ A}−1 0 − A

−1

0 A1A−10 . Fino al

grado 1, la formula 3.8 diventa

α0+ α1 = B0(M0tv0 + M0tv1+ M1tv0+ B1M0tv0) = B0(M0tv0 + M0tv1+ M1tv0+ B1M0tv0− A1B0M0tv0) e così α0 = (M0tM0)−1M0tv0 α1 = (M0tM0)−1(M0tv1+ M1tv0− M0tM1α0− M1tM0α0) e la dimostrazione è conclusa

Sia Xε _{= {p}ε

1, . . . , pεs} un insieme nito di empirical point distinti con

valori specici X ⊂ Rn. Rappresenteremo una perturbazione ammissibile di

Xε usando gli innitesimi al primo ordine per la perturbazione in ogni coor- dinata; cioè lo esprimiamo come una funzione di sn variabili di errore

e = (e11, . . . , es1, e12, . . . , es2, . . . , e1n, . . . , , esn).

Specicatamente, la perturbazione ammissibile è ˜X(e) = {˜p1(e), . . . , ˜ps(e)}

dove

˜

pk(e) = (pk1+ ek1, pk2+ ek2, . . . , pkn+ ekn).

Le condizioni sui valori degli ekj tali che ogni ˜pk è una perturbazione

ammissibile sui punti pk sono equivalenti alla seguente:

k (ek1, . . . , eknkE≤ 1 (3.10)

per ogni k.

Osserviamo che le coordinate di ogni punto perturbato ˜pk(e) sono ele-

menti dell'anello dei polinomi R = R[e] e ogni variabile ekj rappresenta la

perturbazione nella coordinata j-esima del valore specico pk. Il dominio del-

l'insieme perturbato ˜X(e), visto come una funzione di sn variabili, è denotata con Dε. Ovviamente, se δ ∈ Dε abbiamo

k δ k2₌Pn j=1 Ps k=1δ 2 kj ≤ Pn j=1sε 2 j, e di conseguenza k δ k≤√s k ε k.

Per tenere evidente la dipendenza dalla variabile di errore e, estendiamo il concetto della denizione 3.3.1, cioè della evaluation map di un polinomio f ∈ P e la evaluation matrix di un insieme di polinomi G = {g1, . . . , gk} ⊂ P,

ad un generico insieme perturbato ˜X(e), usando la seguente notazione : eval_X(e)˜ (f ) = (f (˜p1(e)), . . . , f (˜ps(e))) ∈ Rs

per brevità denotato con f(˜X(e)); e similarmente scriviamo la evaluation matrix

MG( ˜X(e)) = (g1( ˜X(e)), . . . , gk( ˜X(e))) ∈ M ats×k(R).

Presenteremo nel seguito lo Stable Order Ideal algorithm che calcola un order ideal O stabile rispetto all'empirical set Xε

La strategia per calcolare uno stable order ideal O è la seguente. Come nell'algoritmo di Buchberger-Möller l'insieme O viene costruito gradualmen- te: all'inizio O comprende solo 1 come elemento; ad ogni iterazione,un nuovo prodotto di potenze t viene considerato. Se la evaluation matrix MO∪t( ˜X(δ)) ha rango massimo per tutti i δ ∈ Dε allora t viene aggiunto ad O; altrimenti

t viene aggiunto al corner set dell' order ideal.

Una prima osservazione riguarda la scelta dell'elemento t (prodotto di po- tenze) da analizzare ad ogni iterazione: ogni strategia che sceglie un termine ttale che l'insieme O∪t è factor closed può essere applicato. Una tecnica pos- sibile è quella utilizzata nell'algoritmo di Buchberger-Moller, dove l'elemento t è il candidato più piccolo secondo un ordinamento ssato σ. La versione del SOI algorithm qui presentata utilizza quest'ultima strategia. Da notare che σ viene usato come uno strumento di calcolo per la scelta di t; infatti l'insieme nale O non è, in generale, lo stesso ottenuto trattando l'insieme X usando l'algoritmo di Buchberger -Möller con lo stesso term ordering (vedi gli esempi 3.3.2 e 3.3.3). Un'altra osservazione riguarda il controllo princi- pale dell'algoritmo: osserviamo che la condizione sul rango è equivalente a controllare se ρ(δ), la componente del vettore di valutazione t(˜X(δ)) ortogo- nale allo spazio delle colone della matrice MO( ˜X(δ)), si annulla per qualche δ ∈ Dε. Questo controllo, notevolmente semplicato dalla restrizione all'er-

rore al primo ordine richiede un parametro reale γ dipendente dalla norma di ρ2+ =

P

k>2ρk, dove ogni ρk è la componente omogenea di grado k di ρ.

(vedi teorema 3.3.10 )

Descriviamo ora l'algoritmo.

Algoritmo 3.3.10. Stable Order Ideal Algorithm Sia Xε_{= {p}ε

1, . . . , pεs}

un insieme nito di empirical point distinti, con valori specici X ⊂ Rn e

tolleranza comune ε = (ε1, . . . , εn)e sia e = (e11, . . . , esn)le variabili d'errore

i cui vincoli sono deniti in (3.10). Sia σ un term ordering su Tn _{e γ ≥ 0}

(vedi teorema 3.3.11). Consideriamo la successiva sequenza di istruzioni. S1) Inizia con la lista O = [1], L = [x1, . . . , xn], la lista vuota C = [ ] e la

M0 ∈ M ats×1(R)

con tutte le entrate uguali ad 1, e

M1 ∈ M ats×1(R)

con tutte le entrate uguali a 0.

S2) Se L = [ ] allora restituisci l'insieme O e stop. Altrimenti sia t = minσ(L)

e eliminalo da L.

S3) Siano v0 e v1 le componenti omogenee di grado 0 e 1 dell'evaluation

vector v = t(˜X(e)). Calcola i vettori (vedi proposizione 3.3.3) ρ0 = v0− M0α0

ρ1 = v0− M0α1− M1α0

dove

α0 = (M0tM0)−1M0tv0

α1 = (M0tM0)−1(M0tv1+ M1tv0− M0tM1α0− M1tM0α0)

S4) Sia Ct ∈ M ats × sn(R) tale che ρ1 = Cte. Sia k massimo intero tale

che la matrice ˆCt, formata selezionando le prime k righe di Ct, abbia

minimo valore singolare ˆσk maggiore di k ε k. Sia ˆρ0 il vettore che

comprende i primi k elementi di ρ0 e sia ˆCt0 la pseudoinversa di ˆCt.

Calcola ˆδ = − ˆC_t0ρˆ0, che è la norma-2 soluzione minimale del sistema

indeterminato ˆCtδ = ˆˆ ρ0 (Demmel e Higham, 1993).

S5) Se k ˆδ k> (1 + γ)√s k ε k, allora aggiungi il vettore v0 alla matrice

M0 e il vettore v1 alla matrice M1. Aggiungi l'elemento t ad O, e ad L

quegli elementi di {x1t, . . . , xnt} che non sono multipli di un elemento

di L o di C. Continua col passo S2.

S6) Altrimenti aggiungi t alla lista C, e rimuovi da L tutti i multipli di t. Continua col passo S2.

Teorema 3.3.11. L'algoritmo SOI si ferma dopo un numero nito di ite- razioni e restituisce un insieme O ⊂ Tn che è factor closed. Se γ soddisfa

supδ∈Dε k ρ2+(δ) k≤ γ

√

s k ε k2, allora O è un order ideal stabile rispetto all'empirical set Xε_{. In particolare, quando la cardinalità di O = s allora}

I(X) ha una corrispondente border bases rispetto a Xε.

Dimostrazione Per prima cosa aermiamo che ρ0, ρ1, α0, α1 calcolati nel

passo S3 sono le componenti omogenee di grado 0 e 1 di ρ e α come deniti nell'equazione (3.5), dove M = MO( ˜X(e)). Per provare questa aermazione è suciente applicare la proposizione 3.3.3 e osservare che le matrici M0 e M1

coincidono con le componenti omogenee di grado 0 e 1 di M. Chiaramente, questo è vero alla prima iterazione, in quanto M ha tutte le entrate uguali ad 1. Usiamo l'induzione sul numero di iterazioni. Assumiamo che M0 e M1

siano le componenti di grado 0 e 1 di M e supponiamo che il prodotto di potenze t sia aggiunto ad O. Poichè l'ultima colonna di MO∪t( ˜X(e)) è dato da v = t˜X(e)), le cui componenti di grado 0 e 1 sono v0 e v1 rispettivamente,

le nuove matrici [M0, v0] e [M1, v1] sono le componenti di grado 0 e 1 di

MO∪ t( ˜X(e)). Concludiamo che ρ0+ ρ1 e α0+ α1 coincidono con ρ e α, no

al primo ordine. Adesso proviamo la nitezza e la correttezza dell'algoritmo. Proviamo prima la nitezza. Ad ogni iterazione l'algoritmo esegue il passo S5 o il passo S6. Osserviamo che il passo S5 può essere eseguito al massimo s − 1 volte; infatti, quando M0 diventa una matrice quadrata, ossia dopo

s − 1 iterazioni del passo S5, il vettore residuo ρ0 sarà sempre zero, e di

conseguenza, anche la norma-2 soluzione minimale ˆδ calcolata nel passo S4 è zero. Inoltre, il passo S5 è l'unico punto in cui l'insieme L viene allargato (con un numero nito di termini), mentre ogni iterazione rimuove da L almeno un elemento; concludiamo che l'algoritmo raggiunge la condizione L = [ ] dopo un numero nito di iterazioni.

Per dimostrare la correttezza proviamo, per induzione sul numero di ite- razioni, che l'output O è un order ideal stabile rispetto a Xε_{. Questo è vero}

dopo zero iterazioni, cioè dopo che il passo S1 è stato eseguito. Per induzione assumiamo che un numero di iterazioni sia stato eseguito e che l'order ideal O sia stabile; seguiamo i passi della nuova iterazione in cui viene considerato un prodotto di potenze t. Se il passo S6 viene eseguito l'aermazione è vera perchè O non cambia. Altrimenti, se il passo S5 viene eseguito, l'insieme O∗ _{= O ∪ t è factor closed per costruzione. In modo da provare che O}∗ _è

stabile rispetto a Xε mostriamo che ρ(δ) non si annulla per ogni δ ∈ D ε,

poichè ρ(δ) è la componente di t(˜X(δ)) ortogonale alle colonne di MO( ˜X(δ)) e ρ(δ) 6= 0 implica che MO∗( ˜_{X(δ)) ha rango massimo. Deniamo ˆ}ρ(δ) come

implica ρ(δ) 6= 0, così è suciente provare che ˆρ(δ) non si annulla su Dε.

Supponiamo per assurdo che esista ˜δ ∈ Dε che soddisfa:

ˆ

ρ(˜δ) = ˆρ0+ Ctδ + ˆ˜ ρ2+(˜δ) = 0 (3.11)

Sia ξ = ˆC0

tρˆ2+(˜δ) la soluzione norma-2 minimale del sistema lineare

ˆ

Ctξ = ˆρ2+(˜δ) (3.12)

Sostituendo la (3.11) nella (3.10), otteniamo ˆCt(˜δ + ξ) = − ˆρ0. Poichè

˜

δ ∈ Dε abbiamo k ˜δ k6k ˜δ + ξ k. Così otteniamo

k˜δk6k˜δ+ξk6√skεk+k ˆC0 tkk ˆρ2+(˜δ)k= √ skεk+k ˆρ2+(˜δ) k ˆ σk 6(1+γ)√skεk.

Questo contraddice la condizione all'inizio dello step S5, e quindi conclu- diamo che ρ(δ) non si annulla per ogni δ ∈ Dε. L'asserto nale segue dalla

proposizione 3.3.3.

Per implementare l'algoritmo SOI bisogna scegliere un valore γ anche se non è nota una stima di supδ∈Dε k ρ2+(δ) k. Poichè consideriamo piccole

perturbazioni ˜X dell'empirical set Xε, nella maggior parte dei casi ρ0+ ρ1(δ)

è una buona approssimazione lineare di ρ(δ) per ogni δ ∈ Dε. Per questa

ragione supδ∈Dε k ρ2+(δ) k è piccolo e un valore γ << 1 può essere scelto

per ottenere un insieme O stabile rispetto a Xε. Dall'altro lato, se ρ non è

bene approssimato dalle sue componenti omogenee di grado 0 e 1 la strategia mostrata perde il suo signicato, poichè è basata sull'analisi al primo ordine. Passiamo ora ad illustrare qualche esempio numerico. Il parametro γ ha come valore 0.1 e l'ordinamento σ usato è quello lessicograco; i coecienti dei polinomi sono espressi come decimali troncati.

L'esempio seguente mostra che l'ordinamento σ, usato nell'algoritmo SOI, può portare ad una O-border bases che non contiene la τ base di Gröbner di I(X) per ogni ordinamento τ .

Esempio 3.3.2. (La Quotient Basis O non contiene una Gröbner basis). Sia Xε _{un insieme di empirical point distinti aventi}

come insieme di valori specici e tolleranza ε = (0.1, 0.1). Applicando l'algo- ritmo SOI a Xε, otteniamo la quotient basis {1, x, y, xy} che è stabile rispetto

a Xε_.

Sia τ qualche term ordering su Tn _{e O}

τ(I(X)) = Tn\ LTτ{(I(X)} la quo-

tient basis associata a τ. Osserviamo che O 6= Oτ(I(X)): infatti, secondo τ ,

abbiamo o x2 _<

τ xy o y2 <τ xy; inoltre, l'evaluation vector x2(X) o y2(X)

è linearmente indipendente da {1(X), x(X), y(X)} cosicchè uno tra x2 _{o y}2

deve appartenere a Oτ(I(X)). Concludiamo che la O-border bases di I(X)

non contiene nessuna base di Gröbner di I(X).

I seguenti due esempi mostrano come l'algoritmo SOI individui la con- gurazione geometrica più semplice quasi soddisfatta dall'empirical set Xε_.

Nel documento Basi Border (pagine 80-97)