Approximate Vanishing Ideal

Passiamo adesso al secondo metodo cui abbiamo accennato in precedenza, che parte sempre dal presupposto di avere dati approssimati in quanto legati al mondo reale e considera dei polinomi che non si annullano esattamente su dei punti ma assumono su di essi valori molto piccoli. Come già stato evidenziato, quando le coordinate dei punti sono dati (imprecisi) la base di Gröbner risultante è numericamente instabile. Quindi verrà introdotto l'Ap- proximate Vanishing Ideals Algorithm (AVI) che è numericamente stabile e che calcola un insieme di polinomi che si annullano quasi nei punti dati e che formano quasi una border bases.

Consideriamo la situazione seguente comune nelle applicazioni industriali. È dato un insieme nito di punti X = {p1, . . . , ps} rappresentanti misure

aette da errore ricavate da un esperimento. Le loro coordinate verranno chiamate input. Inoltre, esistono uno o più valori misurati in ogni punto che verranno denominati output. L'obbiettivo è quello di costruire funzioni polinomiali delle coordinate dei punti pi che adattano gli input misurati agli

output misurati. Il modello polinomiale allora viene vericato un un espe- rimento di convalida: gli input provenienti da un altro insieme di dati, che non sono stati usati nel processo di adattamento, sono sostituiti come valori delle indeterminate corrispondenti nei polinomi costruiti. Le valutazioni così ottenute vengono confrontate con gli output realmente misurati.

Per calcolare il vanishing ideal di un insieme nito di punti è stato introdotto l'algoritmo di Buchberger-Möller. Nella situazione descritta in precedenza, il vanishing ideal esatto che viene calcolato non produce polinomi ai quali può essere attribuito un signicato sico perchè ignorano la natura inesatta dei dati. Per esempio, l'algoritmo calcola polinomi che si annullano esattamente nei punti dati, ma possono esserci polinomi che passano quasi attraverso i punti.

Verrà richiesto quindi che i polinomi si annullino approssimativamente nei punti, ossia che | f(p) |< ε per qualche valore ε che verrà chiamato numero soglia. Inoltre, poichè la proprietà di assumere valori piccoli nei punti di X non si preserva tramite moltiplicazione per scalare, richiederemo questa proprietà solo per polinomi unitari, ossia per polinomi i cui vettori dei coef- cienti hanno norma euclidea uguale ad 1.

Combinando quindi la volontà di generalizzare la nozione di vanishing ideal di un insieme di punti alla congurazione empirica e il bisogno di prevenire il problema che abbiamo discusso, giungiamo alla denizione seguente: Denizione 3.3.12. Sia X = {p1, . . . , ps} un insieme nito di empirical

point in Rn e sia P = R[x

(1) La mappa R-lineare eval : P → Rs _{denita da}

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

è chiamata la evaluation map associata ad X.

(2) L'ideale IX= ker(eval(f )) ⊂ P è chiamato il vanishing ideal di X.

(3) Dato ε > 0, un ideale J ⊆ P è chiamato un ε-approximate vanishing ideal di X se esiste un sistema di generatori G di J tali che

k eval(g) k< ε e k g k= 1.

Qui k g k denota la norma euclidea del vettore dei coecienti di g. Cerchiamo sistemi di generatori aventi una struttura particolare che assi- curi che nelle vicinanze esista un sistema di generatori di un reale vanishing ideal. Questa struttura viene descritta dalla nozione di approximate border basis. Per arrivare a questa nozione si parte dalla singular value decompo- sition (SVD) per matrici di numeri reali; verrà data inoltre la denizione di ε-approximate kernel di una matrice reale e un'interpretazione in termini di un problema di total least squares. si userà la SVD per adattare l'algoritmo di Buchbeger-Möller al problema approssimato. L'algoritmo risultante sarà chiamato Approximate Vanishing Ideal Algorithm (AVI-algorithm). Produce un order ideal O di termini e una O-border bases approssimata.

Una piccola modica dell'AVI-algorithm calcola polinomi che nella maggior parte dei casi sono vicini ad essere una base di Gröbner di un approximate vanishing ideal. Comunque, a causa della loro instabilità numerica , questo non può essere certicato in tutte le situazioni. Una particolare caratteri- stica dell'algoritmo AVI è che di frequente produce il vanishing ideal di un insieme di punti più piccolo. Questo è in parte dovuto al fatto che punti vicini vengono considerati approssimativamente uguali e verranno identica- ti dall'algoritmo. Può essere considerato anche un problema correlato: dati polinomi f1, . . . , fs ∈ P = R[x1, . . . , xn] che 'quasi' deniscono un ideale

zero- dimensionale (cioè esistono polinomi 'vicini' che deniscono un ideale I ⊂ P tali che dim_R(P/I) > 0), trovare una border bases del più piccolo ideale vicino. L'idea per risolvere questo problema è simile all'idea alla base dell'algortimo AVI: usare la SVD per rendere l'usuale algoritmo per la border bases più stabile numericamente.

sia di tipo algebrico piuttosto che un'equazione dierenziale. Una secon- da assunzione è che,in accordo con quanto stabilito prima, ci si restringe a considerare un output dipendente da diversi input.

Ricordiamo adesso la Singular Value Decomposition (SVD) di una matrice di numeri reali; Rn _{è dotato del prodotto scalare standard e della norma}

euclidea. Con abuso di notazione, col nucleo di una matrice intenderemo il nucleo dell'applicazione lineare associata.

Teorema 3.3.13. ( Singular Value Decomposition) Sia A ∈ Matm,n(R)

(1) Ci sono matrici ortogonali U ∈ Matm,n(R) e V ∈ Matm,n(R) e una

matrice S ∈ Matm,n(R) della forma S =

 D 0 0 0  tale che A = U · S · Vtr _{= U ·} D 0 0 0  ·Vtr

dove D = diag(s1, . . . , sr) è una matrice diagonale.

(2) In questa decomposizione, è possibile ottenere s1 ≥ s2 ≥ . . . ≥ sr> 0.

I numeri s1, . . . , sr dipendono solo da A e sono chiamati i valori

singolari di A.

(3) Il numero r è il rango di A.

(4) Le matrici U e V hanno la seguente interpretazione:

le prime r colonne di U = ONB dello spazio delle colonne di A le ultime m-r colonne di U = ONB del nucleo di Atr

le prime r colonne di V = ONB dello spazio delle righe di A = ONB dello spazio delle colonne di Atr

le ultime n-r colonne di V = ONB del nucleo di A

Dimostrazione Si veda ad esempio G.H.Golub e C.F.van Loan, Matrix Computation, sezione 2.5.4 e teorema. Per il punto (3) si osservi che

La SVD di una matrice reale ci permette di denire e calcolare il suo approximate kernel.

Corollario 3.3.14. Sia A ∈ Matm,n(R), e sia ε > 0 dato. Sia k ∈ {1, . . . , r}

scelto in modo tale che sk > ε ≥ sk+1. Forma la matrice ˜A = U ˜SVtr ponendo

sk+1 = . . . = sr = 0 in S.

(1) Abbiamo min{k A − B k: rank(B) ≤ k} =k A − ˜A k= sk+1. ( Qui

k . . . kdenota la 2-operator norm di una matrice.)

(2) Il sottospazio vettoriale apker(A, ε) = ker( ˜A) è il ker di dimensione maggiore di una matrice la cui distanza Euclidea da A è al più ε. È chiamato l'ε-approximate kernel di A.

(3) Le ultime n-k colonne vk+1, . . . , vn di V sono una base ortonormale di

apker(A, ε). Esse soddisfano k Avi k< ε.

Dimostrazione. Vedi [matrix computations.Golub,Van Loan] sezione..e il teorema. Per il punto (3) osserviamo che

k Avi k=k (A − ˜A)vi k≤k A − ˜A k< ε.

Il numero ε > 0 in questo corollario viene chiamato numero soglia. Per matrici provenienti da dati provenienti da misurazioni, c'è a volte un grande gap nelle sequenze dei valori singolari (s1, . . . , sr), cosicchè esiste una scelta

naturale per il numero soglia. La matrice ˜A viene anche chiamata la ε- truncation della SVD di A e talvolta ci si riferisce a k come al rango numerico di A. L'approximate kernel di una matrice può essere interpretato come segue.

TSL interpretazione dell'Approximate Kernel L'esemplicazione seguente segue quelle esposte in P.P.N de Groen, An introduction to total least square e reinterpreta i risultati in questo contesto. Piuttosto che usare il classico metodo dei minimi quadrati, questa impostazione porta a consi- derare il problema del total least square (TLS). Per esempio, supponiamo di avere un insieme nito di punti come dato in input: X = {p1, . . . , ps} ⊂ Rn

e valori provenienti da misurazioni in output q1, . . . , qs ∈ R. Se vogliamo

interpolare questi dati linearmente, stiamo cercando un sottospazio ane n- dimensionale ˆc⊥ _{= (c}

1, . . . , cn, 1)⊥ maggiormente vicino ai punti che rappre-

sentano i dati, cioè che minimizzano J(c) = Ps i=1(zi

tr_·ˆc)2_{dove z}

i = (pi, −qi).

Poichè zitr· ˆc/ k ˆc k è la distanza da zi al sottospazio, vogliamo minimizzare

dei minimi quadrati minimizza la distanza euclidea di un iperspazio ane ad un dato insieme di punti input/output, e non solo la componente output delle distanze. In questa applicazione questo vuol dire che permettiamo errori in tutte le componenti.

Adesso questi problemi di TLS verranno collegati al problema di interpo- lazione in gradi più alti e all'approximate kernel di una matrice. Sia A ∈ M atm,n(R) e i ∈ {1, . . . , n}. Scegliamo la i-esima componente per per deomo-

geneizzare il sistema lineare di equazioni A·x = 0. Sia A0 _{la matrice ottenuta}

cancellando la i-esima colonna di e sia ai la i-esima colonna di A. La TLS

soluzione del sistema lineare (usualmente sovradeterminato) A0 _{· x = −a} i

minimizza la somma della distanza euclidea dei vettori colonna di A0 _{ad un}

sottospazio ane (c1, . . . , ˆci, cn)⊥. Se esiste, corrisponde al nucleo del mini-

mizzatore della norma di Frobenius k A − B k2 _{soggetta al rank(B) < n}

(vedi P.P.N de Groen, An introduction to total least square, Sec 5). Questo problema di minimizzazione è risolto dalla SVD, e il vettore singolare destro corrispondente al più piccolo valore singolare di A è la soluzione richiesta dell'i-esimo problema di TLS provvedendo che la sua componente i-esima non sia zero.

Se usiamo un numero soglia ε e calcoliamo la ε-truncation ˜Adella SVD di A, cerchiamo tante soluzioni possibili al problema di TLS A0_{· x = a}

i per le quali

esiste un sistema lineare risolubile B0 _{· x = b}

i che è il più vicino al sistema

A0_{·x = a}

i, e non più distante di quanto specicato dal numero soglia. Questo

è il modo in cui useremo la SVD nel seguito. Va osservato che, confrontato alla classica soluzione dei minimi quadrati, l'approccio con la SVD permette implicitamente che tutte le colonne di A ( che saranno evaluation vector di termini nei punti che costituiscono i dati in input) contengono 'rumore', non solo le colonne corrispondenti al lato destro della deomogeinizzazione ( che corrisponderà all'evaluation vector dei leading term dei polinomi normaliz- zati della border bases).

Passiamo ora a descrivere l'Approximate vanishing ideals of point.

Approximate Vanishing Ideals Nel mondo delle approssimazioni è im- probabile che un polinomio si annulli esattamente in un dato punto. Diremo che un polinomio f ∈ P si annulla ε-approssimativamente in un punto p ∈ Rn

se | f(p) |< ε, dove ε è un numero reale positivo chiamato numero soglia. Ovviamente, se i coecienti di f ∈ P sono molto piccoli, è sempre vero che f si annulla ε-approssimativamente in p. Abbiamo perciò la necessità di misu- rare la grandezza di un polinomio tramite la norma Euclidea del suo vettore dei coecienti. Se questa norma è uguale ad uno, si dirà che il polinomio è unitario. Normalizzare vuol dire dividere un polinomio o un vettore con la

sua norma. Siamo pertanto interessati a polinomi unitari che si annullano in un punto dato.

Adesso sia X = {p1, . . . , ps} ⊆ Rn sia un insieme nito di punti. Possiamo

valutare i polinomi nei punti di X. Questo denisce un evaluation homomor- phism evalX: X → Rs dato da f → (f(p1), . . . , f (ps)). Diremo che f ∈ P si

annulla ε-approximately su X se k evalX(f ) k< ε.

Ricordiamo adesso una nozione che sarà centrale in questa sezione( vedi de- nizione 3.3.12): un ideale I ⊆ P è chiamato un ε-approximate vanishing ideal di X se esistono polinomi unitari f1, . . . , fm ∈ P tali che k evalX(f ) k< ε per

i = 1, . . . , m e tali che I = (f1, . . . , fm). In altre parole, stiamo richiedendo

che I sia generato da polinomi unitari che si annullano ε-approximately su X.

L'obbiettivo sarà quello di presentare un algoritmo che usa la SVD per cal- colare un ε-approximate vanishing ideal di un insieme nito di punti X = {p1, . . . , ps} ⊂ Rn dati dalle loro coordinate (approssimate). A questo scopo,

modichiamo l'usuale algoritmo di Buchberger-Möller (vedi B.Buchbergere H.M.Möller, The construction of multivariate polynomials with preasigned zeros.)in diversi modi: tratteremo tutti i termini dello stesso grado simul- taneamente, rimuoviamo polinomi 'piccoli' nel vanishing ideal, e calcoliamo una border bases approssimata (anzichè una Gröbner basis).

La discussione seguente si concentra intorno al concetto di ε-approximate border bases che è denita come segue.

Denizione 3.3.15. Sia O = {t1, . . . , tµ} ⊆ Tn un order ideal di termini,

e sia ∂O = {b1, . . . , bν} il suo border, e sia G = {g1, . . . , gν} una O-border

prebases dell'ideale I = (g1, . . . , gν) in P . Ciò vuol dire che gj è della forma

gj = bj−

Pµ

i=1cijti con cij ∈ R.

Un altro ingrediente importante per il teorema è la versione stabilizzata della riduzione di Gauβ. Il calcolo della forma row echelon ridotta è necessa- ria, perchè abbiamo bisogno di conoscere tutti i possibili leading term conte- nuti in certi spazi vettoriali di polinomi a dobbiamo esser sicuri di accettare solo leading term il cui corrispondente leading coecient sia grande abba- stanza. Il metodo seguente per trovare l'elemento pivot più adatto è costruito dopo il calcolo della decomposizione QR. La sua adeguatezza numerica segue dai lavori di Shirayangi e Sweedler.

Lemma 3.3.16. (Stabilized Reduced Row Echelon Form). Sia A ∈ Matm,n(R)

e sia dato τ > 0. Siano a1, . . . , an le colonne di A. Consideriamo le seguenti

(1) Sia λ1 =k a1 k. Se λ1 < τ, sia R = (0, . . . , 0) ∈ Matm,1(R). Al-

trimenti, sia Q = ((1/λ1)a1) ∈ M atm,1(R) e R = (λ1, 0, . . . , 0) ∈

M atm,1(R).

(2) Per i = 2, . . . , n, calcola qi = ai −Pi−1_j=1hai, qiiqj e λi =k qi k. Se

λi < τ, aggiungi una colonna nulla a R. Altrimenti, aggiungi la colonna

(1/λi)qi a Q e la colonna (λiha1, q1i, . . . , λihai−1, qi−1i, λi, 0, . . . , 0) ad

R.

(3) iniziando dall'ultima riga e lavorando verso l'alto, usa la prima entrata diversa da zero di ogni riga di R per cancellare le entrate diverso da zero sopra essa.

(4) Per i = 1, . . . , m, calcola la norma %i della i-esima riga di R. Se

%i < τ, poni questa riga uguale a zero. Altrimenti, dividi questa riga

per %i. Allora restituisci la matrice R

Questo è un algoritmo che calcola una matrice R ridotta in forma row- echelon. Lo spazio delle righe di R è contenuto nello spazio delle righe della matrice A che è ottenuta da A ponendo uguali a zero le colonne la cui norma è minore di τ. Qui gli elementi pivot di R non sono uguali ad 1, ma le sue righe sono vettori unitari.

Inoltre, se le righe di A sono unitarie e mutualmente ortogonali, i vettori riga di R dieriscono meno di τm√n dai vettori unitari nello spazio delle righe di A.

Dimostrazione. La matrice Q contiene una base ortonormale dello spazio delle colonne della matrice A che è ottenuta da A rimuovendo le colonne la cui norma è minore di τ. Le colonne della matrice R, che è la matrice R dopo il passo (2), contiene le coordinate delle colonne di A in questa base ortonormale. Poichè abbiamo R = Qtr_{A, lo spazio delle righe di R ed A}

corrispondono. Lo spazio delle righe di R è contenuto in quello di R.

Resta da provare l'ultima aermazione. Una riga v di R può essere scritta come una combinazione lineare v = c1w1 + . . . + cmwm delle righe wi di

R, dove ci ∈ R. Inoltre, per i = 1, . . . , m, usiamo R = R per scrivere

wi = qi1u1+ . . . + qimum dove u1, . . . , um sono le righe di A e qij ∈ K. Ora

ogni riga uj dierisce dalla corrispondente riga rj di A per al più n entrate che

sono state poste uguali a zero, ognuna delle quali ha valore assoluto minore di τ. Quindi abbiamo k uj − rj k< τ √ n. Se poniamo ˜wi = qi1r1+ . . . + qimrm e ˜v = c1w˜1+ . . . + cmw˜m, di conseguenza k v − ˜_{v k6}Pm i,j=1ciqij(uj− rj) k6 τ √ nPm j=1 k Pm i=1ciqij k6 τ m √ n

poichè Q è ortogonale e k v k= 1. Da questo segue la tesi.

La procedura nel lemma può essere stabilizzata ulteriormente usando il meto- do di Gram-Schmidt modicato o le trasformazioni di Givens o Householder. Inoltre, le stime fornite per gli errori sono abbastanza grezze e possono essere ranate. Tuttavia, la versione del lemma è suciente per i risultati che si vedranno nel seguito. Prima di continuare è bene dare qualche chiarimen- to. Scalando le coordinate dei punti di X in maniera appropriata, possiamo assumere che siano nell'intervallo [−1, 1]. Questo assunto non solo rende più facile formulare stime per l'errore per l' algoritmo che vedremo, ma ci permette anche di migliorarne la stabilità numerica .

Algoritmo 3.3.17. The Approximate Vanishing Ideal Algorithm . (AVI-Algorithm).

Sia X = {p1, . . . , ps} ⊂ [−1, 1]n⊂ Rn,P = R[x1, . . . , xn], sia

eval : P → Rs

la evaluation map associata eval(f) = (f(p1), . . . , f (ps)) e siano ε > τ > 0

numeri positivi piccoli. Scegliamo inoltre un term ordering σ. Consideriamo la seguente sequenza di istruzioni.

A1 Inizia con la lista G = ∅, O = [1], una matrice M = (1, . . . , 1)tr _∈

M ats,1(R), e d = 0.

A2 Aumenta d di uno e sia L la lista di tutti i termini di grado d in ∂O, ordinati in maniera decrescente rispetto a σ. Se L = ∅, restituisci la coppia (G,O) e stop. Altrimenti, sia L = (t1, . . . , tl).

A3 Sia m il numero di colonne di M. Forma la matrice A = (eval(t1), . . . , eval(tl), M) ∈ M ats,l+m(R).

Usando la sua SVD, calcola una matrice B i cui vettori colonna sono una base ortonormale dell'approximate kernel apker(A, ε).

A4 Usando il lemma, calcola la forma row echelon ridotta stabilizzata di Bt_r

rispetto al τ dato. Il risultato è una matrice C = (cij) ∈ M atk,l+m(R)

tali che cij = 0 per j < ν(i). Qui ν(i) denota l'indice di colonna del

pivot nella i-esima riga di C.

A5 Per tutti i j ∈ {1, . . . , l} tali che esista un i ∈ {1, . . . , k} con ν(i) = j (ossia per l'indice di colonna relativo al pivot), aggiungi il polinomio

cijtj +Pl_j0_=j+1cij0t_j0 +Pl+m

j0_=l+1cij0u_j0

alla lista G,dove uj0 è il (j0 − l)-esimo elemento di O.

A6 Per ogni j = l, l −1, . . . , 1 tali che la j-esima colonna di C non contiene l'elemento pivot, aggiungi il termine tj come un nuovo elemento di O

e aggiungi la colonna eval(tj) ad M come nuova prima colonna.

A7 Usando la SVD di M, calcola una matrice B i cui vettori colonna sono una base ortonormale di apker(M, ε).

A8 Ripeti i passi A4-A7 nchè B è vuota. Continua poi col passo A2. Questo è un algoritmo che calcola una coppia (G, O) di insiemi

G = {g1, . . . , gν} e O = {t1, . . . , tµ}

con le seguenti proprietà:

(a) L'insieme G consiste di polinomi unitari che generano un δ-approximate vanishing ideal di X, dove δ = ε√ν + τ ν(µ + ν).

(b) L'insieme O = {t1, . . . , tµ} contiene un order ideal di termini tali che

non ci sono in hOiK polinomi unitari che si annullano ε-approximately

su X.

(c) L'insieme ˜G = {(1/LCσ(g))g | g ∈ G} è una O-border prebases.

(d) L'insieme ˜G è una η-approximate border bases per η = 2δ + 2νδ2/γε + 2νδ√s/ε.

Qui γ denota il più piccolo valore assoluto del coeciente del border term di uno dei polinomi gi

Dimostrazione. Proviamo prima la nitezza. Quando si inizia con un grado nuovo nel passo A2, la matrice M ha m = #O dove O è la lista corrente di termini. Nel passo A6 allarghiamo M con delle nuove prime colonne che sono linearmente indipendenti dalle altre colonne. Chiaramente, questo può accadere solo un numero nito di volte, e solo un numero nito di termini sono aggiunti ad O. Nel passo A5 costruiamo nuovi elementi di G che hanno leading term in ∂O. Quindi anche questo può avvenire solo un numero nito di volte. Arriveremo eventualmente ad una situazione in

cui tutte le nuove colonne eval(ti) di A nel passo A3 porterebbero ad una

contraddizione producendo o un nuovo elemento di G o una nuova colonna di M. Così dobbiamo eventualmente ottenere L = ∅ e l'algoritmo termina. Ora dimostriamo (a). Sia g ∈ G. Tramite la costruzione della stabilizzata forma row echelon ridotta , il vettore dei coecienti c di g è unitario. Il vettore c dierisce meno di τm√n da un vettore unitario ˜c in apker(A). Inoltre, le colonne di A sono vettori di valutazione di termini che sono ordinati in maniera decrescente rispetto a σ. Va notato che ˜c è un vettore unitario nello spazio delle colonne di B. Sia ˜g = Pl+m

i=1 ˜citi il suo polinomio associato.

Scriviamo ˜c = a1b1+ . . . + akbk dove aj ∈ R e bj è la j-esima colonna di B.

Allora abbiamo k eval(˜g) k=k k X j=1 ajeval( l+m X i=1 bijti) k6 k X j=1 | ai | ε 6 ε √ k k X j=1 | ai |2 = ε√k.

Per ottenere un bound per k, possiamo usare k 6 #∂O = ν. Dal lemma, abbiamo k g − ˜g k≤ τµ√µ + ν se usiamo ν come un upper bound (grezzo) per il numero di righe di Bt_r e µ + ν per le sue colonne. Poichè X ⊂ [−1, 1]n,

la norma del vettore di valutazione di un termine è ≤ 1. Il numero di termini nel supporto di g − ˜g è limitato da µ+ν. Quindi otteniamo k eval(g − ˜g) k≤k g − ˜g k√µ + ν < τ µ(µ + ν).

Per dimostrare (b), osserviamo che le colonne della matrice nale M sono precisamente i vettori di valutazione dei termini in O. Dopo il loop nei passi A4- A8, abbiamo apker( M)= {0}. Perciò nessun polinomio unitario in hOiK ha un vettore di valutazione che è minore di ε. Adesso dimostriamo

che O è un order ideal di termini. Supponiamo che t ∈ O e xit ∈ ∂O viene

messo in O nel passo A6. Dobbiamo dimostrare che tutti i divisori di xit

sono in O. Se ciò non succede, esiste una indeterminata xj tale che t = xjt0

e xit0 = LTσ(g) per qualche g ∈ G. Allora xit = LTσ(xjg) è il leading term

di un polinomio unitario di grado d il cui evaluation vector è minore di ε. Ma il loop nei passi A4-A8 assicura che tutti i leading term di questo tipo vengono individuati, in contraddizione a xit ∈ O. Quindi tutti i divisori xit0

di xit sono in O.

Per dimostrare (c), usiamo il fatto che C è una forma row echelon ridotta. G e O sono aggiornate nei passi A5 e A6, i polinomi g ∈ G soddisfano Supp(g − LMσ(g)) ⊆ O. La lista L viene aggiornata in A2, e abbiamo

LTσ(g) ∈ ∂O.

Inne dimostriamo (d). Scriviamo gi = γibi+ hi dove γi ∈ R è il coeciente

il corrispondente elemento della border bases. Indicando con ω il più piccolo valore singolare della evaluation matrix M di O, abbiamo

k eval( ˜hi) k=k M · vi k> ω k vi k= ω k ˜hi k

dove v denota il vettore dei coecienti di ˜hi. Questo fornisce

ω k ˜hi k6k eval(gi) k + k eval(bi) k6 δ/ | γi | +

√ s. Per cui ogni coeciente cij di ˜hi soddisfa

cij 6 δ/(ωγ) +

√

s/ω < δ/(εγ) +√s/ε.

Data una coppia di neighbor (i, j), l' S-polinomio Sij = xkg˜i − xl˜gj

rispettivamente Sij = ˜gi− xkg˜j ha un normal remainder della forma

S_ij0 = N R_{O, ˜G}(Sij) = xkg˜i− xlg˜j −P_νcνg˜ν

rispettivamente

S_ij0 = ˜gi− xkg˜j−P_νcνg˜ν

dove i cν ∈ R sono alcuni dei coecienti dei polinomi ˜hi. Così otteniamo

k eval(S0

ij) k< 2δ +

P

ν(δ/(εγ) +

√

s/ε) k eval(˜gν) k≤ η, come richiesto.

Facciamo ora delle osservazioni riguardo al teorema e alla dimostrazione. Osservazione 3.3.18. L'aermazione che le coordinate dei punti di X siano nell'intervallo [−1, 1] non è necessaria per la correttezza dell'AVI-Algorithm. è stato solo usato per provare i bound stabiliti per δ e η. Comunque, una quan- tità adeguata di data scaling è essenziale per le prestazioni e il comportamento numerico dell'algoritmo.

Osservazione 3.3.19. Nel teorema, i bound ssati per δ e η sono piutto- sto grezzi. Usando un'analisi più ranata, possono migliorare sensibilmente. Negli esempi pratici, il comportamento delle border bases approssimate cal-

Nel documento Basi Border (pagine 97-111)