Teoria dell'approssimazione

In matematica , la teoria dell'approssimazione riguarda il modo in cui le funzioni possono essere approssimate da funzioni più semplici , fornendo una caratterizzazione quantitativa degli errori introdotti da queste approssimazioni.

Problematico

Il problema dell'approssimazione è sorto molto presto in geometria, per le funzioni trigonometriche  : si tratta di funzioni di cui conosciamo le proprietà (parità, differenziabili, valori in punti particolari) ma che non sono espresse da d ' operazioni eseguibili a mano (le quattro operazioni ). Ciò ha portato alla nozione di sviluppo seriale . È stato così possibile costituire tabelle trigonometriche , quindi, con un approccio simile, tabelle logaritmiche , e in generale tabelle per le funzioni comunemente usate nella scienza come la radice quadrata .

Un problema particolarmente interessante è quello di approssimare funzioni da altre definite solo dalle operazioni di base di un computer , come l'addizione e la moltiplicazione, al fine di creare librerie di funzioni matematiche che a loro volta l'esecuzione producono valori il più vicino possibile al valori teorici. Questa è chiamata approssimazione polinomiale o razionale (cioè da funzioni razionali ).

L'obiettivo è fornire un'approssimazione quanto più precisa possibile di una data funzione reale, in modo da fornire i valori più esatti possibili, con una precisione prossima all'aritmetica in virgola mobile di un computer . Questo obiettivo viene raggiunto utilizzando un polinomio di alto grado e / o restringendo il dominio su cui il polinomio deve approssimare la funzione. L'accorciamento del dominio può spesso essere effettuato, sebbene ciò richieda l' approssimazione della composizione da parte di altre funzioni affini della funzione. Le moderne biblioteche matematiche spesso riducono il dominio dividendolo in più piccoli segmenti e impiegano un polinomio di basso grado su ogni segmento.

Una volta scelti il ​​dominio e il grado del polinomio, si sceglie il polinomio stesso in modo da minimizzare l'errore nel caso peggiore. In altre parole, se f è la funzione reale e P il polinomio che deve avvicinarsi a f , dobbiamo minimizzare il limite superiore della funzione nel dominio. Per una funzione "adeguata", un polinomio ottimo di grado N è caratterizzato da una curva di errore il cui valore oscilla tra + ε e - ε e che cambia segno N + 1 volte, dando un errore nei casi peggiori di ε . È possibile costruire funzioni f per le quali questa proprietà non vale, ma in pratica è generalmente vero. |P-f|{\ displaystyle | Pf |}

• Errore tra il polinomio ottimo di grado 4 e il logaritmo naturale ln (in rosso), e tra l'approssimazione di Chebyshev di ln (in blu) nell'intervallo [2, 4]. Il passo verticale è 10 −5 . L'errore massimo per il polinomio ottimale è 6,07 × 10 −5 .

• Errore tra il polinomio ottimo di grado 4 e l' esponenziale e (in rosso), e tra l'approssimazione di Chebyshev ed exp (in blu) nell'intervallo [−1, 1]. Il passo verticale è 10 −4 . L'errore massimo per il polinomio ottimo è 5,47 × 10 −4 .

In ogni caso, il numero di estremi è N + 2, cioè 6. Due degli estremi sono le estremità del segmento. Le curve in rosso, per il polinomio ottimo, sono di “livello”, cioè oscillano esattamente tra + ε e - ε . Se un polinomio di grado N porta ad una funzione di errore che oscilla tra gli estremi N + 2 volte, allora questo polinomio è ottimale.

Approssimazione per polinomi

stati

Sia f una funzione continua su un intervallo reale chiuso [ a , b ] . Sia P un polinomio di grado n .

Notiamo l'errore di approssimazione tra P e f . ε=P-f{\ displaystyle \ varepsilon = Pf}

Se esiste e tale che a≤X0<X1<⋯<Xnon+1≤b{\ displaystyle a \ leq x_ {0} <x_ {1} <\ cdots <x_ {n + 1} \ leq b}S∈{-1,1}{\ displaystyle s \ in \ {- 1, \; 1 \}}

∀io∈{0,...,non+1},ε(Xio)=(-1)ioS‖P-f‖∞{\ displaystyle \ forall i \ in \ {0, \ ldots, n + 1 \}, \ varepsilon (x_ {i}) = (- 1) ^ {i} s \ | Pf \ | _ {\ infty}},

allora P è un ottimale approssimazione polinomiale di f tra polinomi di grado minore o uguale a n nel senso della norma sup su [ un , b ]  :

P=arg⁡minQ∈Rnon[X]‖f-S‖∞,[a,b]{\ Displaystyle P = \ operatorname {arg} \ min _ {Q \ in \ mathbb {R} _ {n} [X]} \ | fS \ | _ {\ infty, [a, b]}} Dimostrazione

Cominciamo mostrandolo su un grafico. Mettiamoci in posa . Supponiamo che sia un polinomio di grado che possiede le proprietà di cui sopra, nel senso che oscilla tra estremi di segni alternati, da a . NON=4{\ displaystyle N = 4}P{\ displaystyle P}non{\ displaystyle n}P-f{\ displaystyle Pf}non+2{\ displaystyle n + 2}+ε{\ displaystyle + \ varepsilon}-ε{\ displaystyle - \ varepsilon}

La funzione di errore potrebbe essere simile al grafico rosso:P-f{\ displaystyle Pf}

P-f{\ displaystyle Pf}raggiunti estremi (di cui due alle estremità), che hanno la stessa grandezza in valore assoluto situati in 6 intervalli sul grafico sopra. non+2{\ displaystyle n + 2}

Sia ora un polinomio di approssimazione di grado ottimo. Ciò significa che gli estremi della sua funzione di errore devono avere tutti un valore assoluto strettamente inferiore a , in modo che si trovino rigorosamente all'interno del grafico dell'errore per . Q{\ displaystyle Q}non{\ displaystyle n}ε{\ displaystyle \ varepsilon}P{\ displaystyle P}

La funzione di errore per potrebbe avere una rappresentazione grafica simile al grafico blu sopra. Ciò significa che deve oscillare tra numeri rigorosamente positivi e strettamente negativi diversi da zero per un numero totale di volte. Ma è uguale a quale è un polinomio di grado . Deve avere almeno le radici situate tra diversi punti in cui la funzione polinomiale assume valori diversi da zero. Tuttavia, in un anello integrale, un polinomio di grado diverso da zero non può avere più radici. Quindi è identicamente zero, vale a dire che . Q{\ displaystyle Q}(P-f)-(Q-f){\ displaystyle (Pf) - (Qf)}NON+2{\ displaystyle N + 2}(P-f)-(Q-f){\ displaystyle (Pf) - (Qf)}P-Q{\ displaystyle PQ}non{\ displaystyle n}non+1{\ displaystyle n + 1}non{\ displaystyle n}non{\ displaystyle n}P-Q{\ displaystyle PQ}P=Q{\ displaystyle P = Q}

Approssimazione di Chebyshev

È possibile ottenere polinomi molto vicini a un polinomio ottimale espandendo una data funzione con polinomi di Chebyshev e quindi tagliando l'espansione in una certa misura. Questo processo è simile all'espansione in serie di Fourier di una funzione nell'analisi di Fourier , ma utilizza i polinomi di Chebyshev invece delle solite funzioni trigonometriche .

Calcoliamo i coefficienti nell'espansione di Chebyshev di una funzione f  :

f(X)≃∑non=0∞vsnonTnon(X){\ displaystyle f (x) \ simeq \ sum _ {n = 0} ^ {\ infty} c_ {n} T_ {n} (x)}

di cui teniamo solo i primi N termini della serie, che dà un polinomio di grado N prossimo alla funzione f .

La raison pour laquelle ce polynôme est presque optimal est que, pour des fonctions admettant un développement en série entière, dont la série a une convergence rapide, l'erreur commise sur le développement au bout de N termes est approximativement égale au terme suivant immédiatement la sezionamento. Cioè, il primo termine subito dopo il taglio domina la somma di tutti i termini successivi chiamati il ​​resto della serie. Questo risultato rimane se l'espansione viene eseguita con i polinomi di Chebyshev. Se un'espansione di Chebyshev viene interrotta dopo T N , l'errore sarà vicino al termine in T N + 1 . I polinomi di Chebyshev hanno la proprietà di avere una curva rappresentativa “a livello”, oscillante tra +1 e −1 nell'intervallo [−1, 1]. T n + 1 a n + 2 estremi . Ciò significa che l'errore tra f e la sua approssimazione di Chebyshev a un termine in T n è una funzione avente n + 2 estremi, i cui massimi (rispettivamente minimi) sono uguali, ed è quindi prossima al polinomio ottimo di grado n .

Negli esempi grafici sopra, possiamo vedere che la funzione di errore mostrata in blu a volte è migliore (quando rimane sotto) rispetto alla funzione mostrata in rosso, ma peggiore su alcuni intervalli, il che significa che questo non è proprio il polinomio ottimale. Questa differenza è relativamente meno importante per la funzione esponenziale , la cui intera serie converge molto rapidamente, che per la funzione logaritmo .

Sistemi Chebyshev

Questa parte e la seguente si basano principalmente sui lavori di Cheney e Powell.

È possibile generalizzare la caratterizzazione della “migliore approssimazione” con spazi di funzioni di approssimazione che non sono polinomi ma funzioni standard. Tuttavia, tali famiglie di funzioni devono avere alcune buone proprietà dei polinomi. Si parla quindi di “polinomi generalizzati”. Questi "polinomi" avranno funzioni di base (che consideriamo piacevoli) come monomi che soddisfano le condizioni di Haar.

Condizioni di Haar

Una famiglia di funzioni di un intervallo in soddisfa le condizioni di Haar se e solo se {g1,...,gnon}{\ displaystyle \ {g_ {1}, \ dots, g_ {n} \}}[a,b]{\ displaystyle [a, b]}R{\ displaystyle \ mathbb {R}}

1. Tutte le funzioni sono continue.gio{\ displaystyle g_ {i}}
2. Le funzioni soddisfano le seguenti condizioni equivalenti: g1,...,gnon{\ displaystyle g_ {1}, \ dots, g_ {n}}
   1. Per tutti distintiX1,...,Xnon∈[a,b]{\ displaystyle x_ {1}, \ dots, x_ {n} \ in [a, b]}|g1(X1)⋯gnon(X1)⋮⋮g1(Xnon)⋯gnon(Xnon)|≠0{\ displaystyle \ left | {\ begin {matrix} g_ {1} (x_ {1}) & \ cdots & g_ {n} (x_ {1}) \\\ vdots && \ vdots \\ g_ {1} ( x_ {n}) & \ cdots & g_ {n} (x_ {n}) \ end {matrix}} \ right | \ neq 0}
   2. Per tutti distinti, per tutti , esiste un'unica tupla tale che la funzione soddisfiX1,...,Xnon∈[a,b]{\ displaystyle x_ {1}, \ dots, x_ {n} \ in [a, b]}y1,...,ynon{\ displaystyle y_ {1}, \ dots, y_ {n}}(α1,...,αnon){\ displaystyle (\ alpha _ {1}, \ dots, \ alpha _ {n})}f=∑io=1nonαiogio{\ Displaystyle f = \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}∀io∈{1,...,non}f(Xio)=yio{\ displaystyle \ forall i \ in \ {1, \ dots, n \} \ quad f (x_ {i}) = y_ {i}}
   3. Le funzioni sono linearmente indipendenti ed è l'unica funzione della forma che ha strettamente più radicig1,...,gnon{\ displaystyle g_ {1}, \ dots, g_ {n}}X↦0{\ displaystyle x \ mapsto 0}X↦∑io=1nonαiogio(X){\ Displaystyle x \ mapsto \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i} (x)}non-1{\ displaystyle n-1}[a,b]{\ displaystyle [a, b]}

Una famiglia finita di funzioni che soddisfano le condizioni di Haar è chiamata sistema di Chebyshev. Ovviamente i monomi di grado scalati formano un sistema di Chebyshev: i polinomi sono continui, la condizione 2.1 è il determinante di Vandermonde , la condizione 2.2 è la caratterizzazione del polinomio di interpolazione e la condizione 2.3 è il fatto che un polinomio di grado fisso non può avere più radice della sua grado. g1,...,gnon∈VS([a,b]){\ displaystyle g_ {1}, \ dots, g_ {n} \ in {\ mathcal {C}} ([a, b])}{1,X,...Xnon-1}{\ displaystyle \ {1, X, \ dots X ^ {n-1} \}}

Possiamo anche dire che un sottospazio di dimensione soddisfa le condizioni Haar se e solo se le sue fondamenta sono i sistemi di Chebyshev. E{\ displaystyle E}VS([a,b]){\ displaystyle {\ mathcal {C}} ([a, b])}non{\ displaystyle n}

Equivalenza delle caratterizzazioni

La prova dell'equivalenza dei punti 2.1, 2.2 e 2.3 avverrà per implicazioni circolari.

2.1 ⇒ 2.2 Considera distinti e . Per l'ipotesi 2.1, notiamo in particolare che la matrice X1,...,Xnon∈[a,b]{\ displaystyle x_ {1}, \ dots, x_ {n} \ in [a, b]}y1,...,ynon∈R{\ displaystyle y_ {1}, \ dots, y_ {n} \ in \ mathbb {R}}

M: =(g1(X1)⋯gnon(X1)⋮⋮g1(Xnon)⋯gnon(Xnon)){\ displaystyle M: ​​= \ left ({\ begin {matrix} g_ {1} (x_ {1}) & \ cdots & g_ {n} (x_ {1}) \\\ vdots && \ vdots \\ g_ {1} (x_ {n}) & \ cdots & g_ {n} (x_ {n}) \ end {matrix}} \ right)}7

è invertibile. Esiste quindi un'unica soluzione all'equazione O, quest'ultima equazione è equivalente a . Viene così l'esistenza e l'unicità di una tupla tale che l' interpolazione y i in x i . M⋅(a1,...,anon)T=(y1,...,ynon)T{\ displaystyle M \ cdot (a_ {1}, \ dots, a_ {n}) ^ {T} = (y_ {1}, \ dots, y_ {n}) ^ {T}}∀io∈{1,...,non}∑j=1nonajgj(Xio)=yio{\ displaystyle \ forall i \ in \ {1, \ dots, n \} \ quad \ sum _ {j = 1} ^ {n} a_ {j} g_ {j} (x_ {i}) = y_ {i }}(α1,...,αnon){\ displaystyle (\ alpha _ {1}, \ dots, \ alpha _ {n})}f=∑io=1nonαiogio{\ Displaystyle f = \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}

2.2 ⇒ 2.3 La funzione nulla ha chiaramente rigorosamente più di n - 1 radici tra una e B , perché ha un'infinità di loro. Lascia che ora abbia n radici distinte, notato . La funzione nulla ef coincidono in questi punti. Per la proprietà 2.2, abbiamo quindi f = 0 . Ciò implica inoltre che i g i sono linearmente indipendenti se non si avrebbe la duplicità della scrittura della funzione nulla, che è vietata dall'assunzione 2.2. X↦0{\ displaystyle x \ mapsto 0}f=∑io=1nonαiogio{\ Displaystyle f = \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}X1,...,Xnon{\ displaystyle x_ {1}, \ dots, x_ {n}}

2.3 ⇒ 2.1 Sia distinto. Supponiamo che la matrice non sia invertibile. Quindi le sue colonne sono linearmente dipendenti e quindi esiste in modo tale . Allora sono radici di cui è quindi zero per proprietà 2.3. Sempre da questa proprietà, segue dall'indipendenza del g i che ciò che è assurdo. La matrice è quindi invertibile e la sua determinante è quindi diversa da zero. X1,...,Xnon∈[a,b]{\ displaystyle x_ {1}, \ dots, x_ {n} \ in [a, b]}M: =(g1(X1)⋯gnon(X1)⋮⋮g1(Xnon)⋯gnon(Xnon)){\ displaystyle M: ​​= \ left ({\ begin {matrix} g_ {1} (x_ {1}) & \ cdots & g_ {n} (x_ {1}) \\\ vdots && \ vdots \\ g_ {1} (x_ {n}) & \ cdots & g_ {n} (x_ {n}) \ end {matrix}} \ right)}α1,...,αnon{\ displaystyle \ alpha _ {1}, \ dots, \ alpha _ {n}}∀j∈{1,...,non}∑io=1nonαiogio(Xj)=0{\ displaystyle \ forall j \ in \ {1, \ dots, n \} \ quad \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i} (x_ {j}) = 0 }X1,...,Xnon{\ displaystyle x_ {1}, \ dots, x_ {n}}∑io=1nonαiogio{\ Displaystyle \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}∀io∈{1,...,non}αio=0{\ displaystyle \ forall i \ in \ {1, \ dots, n \} \ quad \ alpha _ {i} = 0}

Esempi

Possiamo citare due esempi di sistemi Chebyshev:

• Se sono distinti due per due, forma un sistema Chebyshev per qualsiasi intervallo compatto di .λ1,...,λnon{\ displaystyle \ lambda _ {1}, \ dots, \ lambda _ {n}}{eλ1X,...,eλnonX}{\ displaystyle \ {\ mathrm {e} ^ {\ lambda _ {1} x}, \ dots, \ mathrm {e} ^ {\ lambda _ {n} x} \}}R{\ displaystyle \ mathbb {R}}
• Se sono due per due distinti e positivi, forma un sistema Chebyshev per un intervallo compatto di .λ1,...,λnon{\ displaystyle \ lambda _ {1}, \ dots, \ lambda _ {n}}{Xλ1,...,Xλnon}{\ displaystyle \ {x ^ {\ lambda _ {1}}, \ dots, x ^ {\ lambda _ {n}} \}}R{\ displaystyle \ mathbb {R}}

Teorema dell'alternanza

I sistemi di Chebyshev consentono di caratterizzare le migliori approssimazioni di funzioni continue essendo polinomi generalizzati costruiti dalle funzioni di detto sistema.

stati

Considera un sistema Chebyshev. Sia una funzione continua. Sia un polinomio generalizzato sul sistema di Chebyshev e l'errore di approssimazione. Allora è una migliore approssimazione uniforme di , cioè , se e solo esiste tale che e{g1,...,gnon}⊆VS([a,b]){\ displaystyle \ {g_ {1}, \ dots, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}f∈VS([a,b]){\ Displaystyle f \ in {\ mathcal {C}} ([a, b])}p∗=∑io=1nonαio∗gio{\ displaystyle p ^ {*} = \ sum _ {i = 1} ^ {n} \ alpha _ {i} ^ {*} g_ {i}}r∗=f-p∗{\ displaystyle r ^ {*} = fp ^ {*}}p∗{\ displaystyle p ^ {*}}f{\ displaystyle f}‖r∗‖∞=minp∈Vect(g1,...,gnon)‖f-p‖∞{\ displaystyle \ | r ^ {*} \ | _ {\ infty} = \ min _ {p \ in {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n})} {\ | fp \ | _ {\ infty}}}a≤X0<⋯<Xnon≤b{\ displaystyle a \ leq x_ {0} <\ cdots <x_ {n} \ leq b}r(Xio)=(-1)ior(X0){\ displaystyle r (x_ {i}) = (- 1) ^ {i} r (x_ {0})}r(X0)=±‖r‖∞{\ displaystyle r (x_ {0}) = \ pm \ | r \ | _ {\ infty}}

Nota

È interessante notare che se il sistema di Chebyshev considerato è la base canonica di allora questa affermazione è esattamente quella del teorema nel caso dei polinomi. Rnon-1[X]{\ displaystyle \ mathbb {R} _ {n-1} [X]}

Dimostrazione del teorema dell'alternanza

Teorema di caratterizzazione

La prima cosa da fare è caratterizzare le migliori approssimazioni mediante polinomi generalizzati. Possiamo iniziare mostrando che è sufficiente che l'origine dello spazio sia in un certo inviluppo convesso. Per un sistema Chebyshev, notiamo . {g1,...,gnon}{\ displaystyle \ {g_ {1}, \ dots, g_ {n} \}}X^=(g1(X),...,gnon(X))T{\ displaystyle {\ hat {x}} = (g_ {1} (x), \ dots, g_ {n} (x)) ^ {T}}

Considera un sistema Chebyshev. Sia una funzione continua. Sia un polinomio generalizzato sul sistema di Chebyshev e l'errore di approssimazione. Allora r è di norma minima se e solo se 0 è nello scafo convesso di .{g1,...,gnon}⊆VS([a,b]){\ displaystyle \ {g_ {1}, \ dots, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}f∈VS([a,b]){\ Displaystyle f \ in {\ mathcal {C}} ([a, b])}p=∑io=1nonαio∗gio{\ Displaystyle p = \ sum _ {i = 1} ^ {n} \ alpha _ {i} ^ {*} g_ {i}}r=f-p{\ displaystyle r = fp}{r(X)X^ | r(X)=‖r‖∞}{\ displaystyle \ {r (x) {\ hat {x}} \ | \ r (x) = \ | r \ | _ {\ infty} \}}

Dimostrazione Condizione sufficiente

Procediamo per contrapposizione e supponiamo che non sia minimo. Allora è possibile trovare un polinomio generalizzato che soddisfi un migliore errore di approssimazione. In altre parole, ci sono come . ‖r‖∞{\ displaystyle \ | r \ | _ {\ infty}}d=(d1,...,dnon){\ displaystyle d = (d_ {1}, \ dots, d_ {n})}‖∑io=1non(αio∗-dio)gio‖∞<‖r‖∞{\ displaystyle \ left \ | \ sum _ {i = 1} ^ {n} (\ alpha _ {i} ^ {*} - d_ {i}) g_ {i} \ right \ | _ {\ infty} < \ | r \ | _ {\ infty}}

Mettiamoci in posa . Quindi per tutto ciò che abbiamo X={X∈[a,b] | |r(X)|=‖r‖∞}{\ displaystyle X = \ {x \ in [a, b] \ | \ | r (x) | = \ | r \ | _ {\ infty} \}}X∈X{\ displaystyle x \ in X}

|r(X)-∑io=1nondiogio(X)|≤‖r-∑io=1nondiogio‖∞=‖∑io=1non(αio∗-dio)gio‖∞<‖r‖∞=|r(X)|{\ Displaystyle \ left | r (x) - \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | \ leq \ left \ | r- \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} \ right \ | _ {\ infty} = \ left \ | \ sum _ {i = 1} ^ {n} (\ alpha _ {i} ^ { *} - d_ {i}) g_ {i} \ right \ | _ {\ infty} <\ | r \ | _ {\ infty} = | r (x) |}

Quadrando i membri della disuguaglianza,

(r(X)-∑io=1nondiogio(X))2<r(X)2{\ Displaystyle \ left (r (x) - \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right) ^ {2} <r (x) ^ {2} }

Quindi, per sviluppo

2r(X)∑io=1nondiogio(X)>(∑io=1nondiogio(X))2{\ displaystyle 2r (x) \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x)> \ left (\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right) ^ {2}}

e

⟨d,r(X)X^⟩=r(X)∑io=1nondiogio(X)>0{\ Displaystyle \ langle d, r (x) {\ hat {x}} \ rangle = r (x) \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x)> 0 }

Si tratta quindi ora di mostrare che 0 non è nell'inviluppo convesso di , che è un sottoinsieme di , e avremo quindi dimostrato il contrapposto. Supponiamo quindi il contrario. Esiste e tale che e . Allora {r(X)X^ | X∈X}{\ displaystyle \ {r (x) {\ hat {x}} \ | \ x \ in X \}}Rnon{\ displaystyle \ mathbb {R} ^ {n}}X1,...,Xnon∈X{\ displaystyle x_ {1}, \ dots, x_ {n} \ in X}a1,...anon∈[0,1]{\ displaystyle a_ {1}, \ dots a_ {n} \ in [0,1]}∑io=1nonaior(Xio)Xio^=0{\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} r (x_ {i}) {\ hat {x_ {i}}} = 0}∑io=1nonaio=1{\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} = 1}

0=⟨d,0⟩=⟨d,∑io=1nonaior(Xio)Xio^⟩=∑io=1nonaio⟨d,r(Xio)Xio^⟩>0{\ Displaystyle 0 = \ left \ langle {d, 0} \ right \ rangle = \ left \ langle {d, \ sum _ {i = 1} ^ {n} a_ {i} r (x_ {i}) { \ hat {x_ {i}}}} \ right \ rangle = \ sum _ {i = 1} ^ {n} a_ {i} \ langle {d, r (x_ {i}) {\ hat {x_ {i }}}} \ rangle> 0}

Questo è ovviamente assurdo, CQFD.

Condizione richiesta

Procediamo anche per contrapposizione. Supponiamo quindi che 0 non sia nell'inviluppo convesso C dell'insieme . C è chiuso perché è un involucro convesso. È limitato perche 'lo è. Infatti r e g i sono continui e X è contenuto in un intervallo limitato. C è quindi chiuso delimitato in dimensione finita (contenuto in ), è quindi compatto. Raggiunge quindi un minimo su C , diciamo in . In particolare . O arbitrario e nessuno dei due . Per convessità . Poi {r(X)X^ | r(X)=‖r‖∞}={r(X)X^ | X∈X}{\ displaystyle \ {r (x) {\ hat {x}} \ | \ r (x) = \ | r \ | _ {\ infty} \} = \ {r (x) {\ hat {x}} \ | \ x \ in X \}}{r(X)X^ | r(X)=‖r‖∞}{\ displaystyle \ {r (x) {\ hat {x}} \ | \ r (x) = \ | r \ | _ {\ infty} \}}Rnon{\ displaystyle \ mathbb {R} ^ {n}}‖⋅‖2{\ displaystyle \ | \ cdot \ | _ {2}}d∈VS{\ displaystyle d \ in C}d≠0{\ displaystyle d \ neq 0}u∈VS{\ displaystyle u \ in C}λ∈[0,1]{\ displaystyle \ lambda \ in [0,1]}λu+(1-λ)d∈VS{\ displaystyle \ lambda u + (1- \ lambda) d \ in C}

‖λu+(1-λ)d‖22≥‖d‖22‖λu+(1-λ)d‖22-‖d‖22≥0λ2‖u-d‖22+2λ⟨u-d,d⟩≥0{\ displaystyle {\ begin {align} \ | {\ lambda u + (1- \ lambda) d} \ | _ {2} ^ {2} & \ geq & \ | {d} \ | _ {2} ^ {2} \\\ | {\ lambda u + (1- \ lambda) d} \ | _ {2} ^ {2} - \ | {d} \ | _ {2} ^ {2} & \ geq & 0 \\ \ lambda ^ {2} \ | {ud} \ | _ {2} ^ {2} +2 \ lambda \ langle {ud, d} \ rangle & \ geq & 0 \ end {align}}}

Per un numero abbastanza piccolo, questa disuguaglianza viene violata . Quindi . Così per tutti , . X è un chiuso contenuto in C , quindi è anche compatto. Per la continuità di r e g i , ammette un minimo . Per quello che dobbiamo fare . Nota . Cercheremo quindi come , che concluderà. Mettiamoci in posa adesso . Per definizione . Per quanto riguarda gli altri, Y è ancora compatto. Sia quindi R il massimo di | r | su Y . In caso contrario, allora abbiamo il massimo , il che è assurdo. Quindi, se , λ{\ displaystyle \ lambda}⟨u-d,d⟩<0{\ displaystyle \ langle {ud, d} \ rangle <0}⟨u-d,d⟩≥0{\ displaystyle \ langle {ud, d} \ rangle \ geq 0}u∈VS{\ displaystyle u \ in C}⟨u,d⟩=⟨u-d,d⟩+‖d‖22≥‖d‖22>0{\ displaystyle \ langle {u, d} \ rangle = \ langle {ud, d} \ rangle + \ | {d} \ | _ {2} ^ {2} \ geq \ | {d} \ | _ {2 } ^ {2}> 0}{⟨d,r(X)X^⟩ | X∈X}{\ displaystyle \ {\ langle {d, r (x) {\ hat {x}}} \ rangle \ | \ x \ in X \}}ϵ{\ displaystyle \ epsilon}ϵ>0{\ displaystyle \ epsilon> 0}d=(d1,...,dnon)T{\ displaystyle d = (d_ {1}, \ dots, d_ {n}) ^ {T}}μ>0{\ displaystyle \ mu> 0}‖r-μ∑io=1nondiogio‖∞<‖r‖∞{\ displaystyle \ left \ | {r- \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ right \ | _ {\ infty} <\ | {r} \ | _ {\ infty}}Y={X∈[a,b]] | ⟨d,r(X)X^⟩≤ϵ2}{\ Displaystyle Y = \ left \ {x \ in [a, b]] \ | \ \ langle {d, r (x) {\ hat {x}}} \ rangle \ leq {\ frac {\ epsilon} { 2}} \ right \}}Y∩X=∅{\ displaystyle Y \ cap X = \ emptyset}R<‖r‖∞{\ displaystyle R <\ | {r} \ | _ {\ infty}}y∈Y{\ displaystyle y \ in Y}y∈X{\ displaystyle y \ in X}X∈Y{\ displaystyle x \ in Y}

∀X∈Y,|r(X)-μ∑io=1nondiogio(X)|≤|r(X)|+μ|∑io=1nondiogio(X)|≤R+μ‖∑io=1nondiogio‖∞{\ displaystyle \ forall x \ in Y, \, \ left | r (x) - \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | \ leq | r (x) | + \ mu \ left | \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | \ leq R + \ mu \ left \ | {\ somma _ {i = 1} ^ {n} d_ {i} g_ {i}} \ right \ | _ {\ infty}}

Se ora allora X∉Y{\ displaystyle x \ notin Y}

|r(X)-μ∑io=1nondiogio(X)|2=r(X)2-2μ∑io=1nondior(X)gio(X)+μ2(∑io=1nondiogio(X))2≤‖r‖∞2-2μ⟨d,r(X)X^⟩+μ2(∑io=1nondiogio(X))2≤‖r‖∞2-2μϵ2+μ2(∑io=1nondiogio(X))2perché X∉Y≤‖r‖∞2+μ(-ϵ+μ‖∑io=1nondiogio‖∞2){\ displaystyle {\ begin {align} \ left | r (x) - \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | ^ {2} & = & r (x) ^ {2} -2 \ mu \ sum _ {i = 1} ^ {n} d_ {i} r (x) g_ {i} (x) + \ mu ^ {2} \ sinistra (\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right) ^ {2} \\ & \ leq & \ | {r} \ | _ {\ infty} ^ {2} -2 \ mu \ langle {d, r (x) {\ hat {x}}} \ rangle + \ mu ^ {2} \ left (\ sum _ {i = 1} ^ {n} d_ { i} g_ {i} (x) \ right) ^ {2} \\ & \ leq & \ | {r} \ | _ {\ infty} ^ {2} -2 \ mu {\ frac {\ epsilon} { 2}} + \ mu ^ {2} \ sinistra (\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ destra) ^ {2} & {\ textrm {auto} } \ x \ notin Y \\ & \ leq & \ | {r} \ | _ {\ infty} ^ {2} + \ mu \ left (- \ epsilon + \ mu \ left \ | {\ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ right \ | _ {\ infty} ^ {2} \ right) \ end {allineato}}}

Quindi per , abbiamo 0<μ<min(‖r‖∞-R2‖∑io=1nondiogio‖∞,ϵ2‖∑io=1nondiogio‖∞2){\ displaystyle 0 <\ mu <\ min \ sinistra ({\ frac {\ | {r} \ | _ {\ infty} -R} {2 \ | {\ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ | _ {\ infty}}}, {\ frac {\ epsilon} {2 \ | {\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} } \ | _ {\ infty} ^ {2}}} \ right)}

|r(X)-μ∑io=1nondiogio(X)|<‖r‖∞+R2per X∈Y|r(X)-μ∑io=1nondiogio(X)|2<‖r‖∞2-μϵ2per X∉Y{\ displaystyle {\ begin {align} \ left | r (x) - \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | & <& {\ frac {\ | {r} \ | _ {\ infty} + R} {2}} & \ quad {\ textrm {pour}} \ x \ in Y \\\ sinistra | r (x) - \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right | ^ {2} & <& \ | {r} \ | _ {\ infty} ^ {2} - {\ frac {\ mu \ epsilon} {2}} & \ quad {\ textrm {pour}} \ x \ notin Y \ end {allineato}}}

Così ,, e quindi non è minimo. ‖r-μ∑io=1nondiogio‖∞<‖r‖∞{\ displaystyle \ left \ | {r- \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ right \ | _ {\ infty} <\ | {r} \ | _ {\ infty}}r{\ displaystyle r}

Lemma di alternanza

Esiste un collegamento tra il fatto che 0 si trova in un inviluppo convesso e che ci sia alternanza di segni.

Considera un sistema Chebyshev. Lasciate e non siano costanti . Allora 0 è nello scafo convesso di se e solo se per abbiamo .{g1,...,gnon}⊆VS([a,b]){\ displaystyle \ {g_ {1}, \ dots, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}a≤X0<⋯<Xnon≤b{\ displaystyle a \ leq x_ {0} <\ cdots <x_ {n} \ leq b}λ0,...,λnon∈R∗{\ displaystyle \ lambda _ {0}, \ dots, \ lambda _ {n} \ in \ mathbb {R} ^ {*}}{λioXio^ | io∈{1,...,non}}{\ displaystyle \ {\ lambda _ {i} {\ hat {x_ {i}}} \ | \ i \ in \ {1, \ dots, n \} \}}io∈{1,...,non}{\ displaystyle i \ in \ {1, \ dots, n \}}λioλio-1<0{\ displaystyle \ lambda _ {i} \ lambda _ {i-1} <0}

Prova del lemma

Cominciamo dal determinante X1<⋯<Xnon{\ displaystyle x_ {1} <\ cdots <x_ {n}}

D(X1,...,Xnon)=|g1(X1)⋯gnon(X1)⋮⋮g1(Xnon)⋯gnon(Xnon)|{\ displaystyle D (x_ {1}, \ dots, x_ {n}) = \ left | {\ begin {matrix} g_ {1} (x_ {1}) & \ cdots & g_ {n} (x_ {1 }) \\\ vdots && \ vdots \\ g_ {1} (x_ {n}) & \ cdots & g_ {n} (x_ {n}) \ end {matrix}} \ right |}.

Mostreremo che questi determinanti sono tutti strettamente positivi o tutti strettamente negativi. Per cominciare, sono diversi da zero perché il sistema soddisfa le condizioni di Haar. Supponiamo che sia per e abbiamo {g1,...,gnon}{\ displaystyle \ {g_ {1}, \ dots, g_ {n} \}}X1<⋯<Xnon{\ displaystyle x_ {1} <\ cdots <x_ {n}}y1<⋅<ynon{\ displaystyle y_ {1} <\ cdot <y_ {n}}

D(X1,...,Xnon)<0<D(y1,...,ynon){\ displaystyle D (x_ {1}, \ dots, x_ {n}) <0 <D (y_ {1}, \ dots, y_ {n})}. Quindi per il teorema dei valori intermedi applicato , abbiamo l'esistenza di tale ciò , che è impossibile per le condizioni di Haar. Quindi, tutti questi determinanti hanno lo stesso segno.λ↦D(λX1+(1-λ)y1,...,λXnon+(1-λ)ynon){\ displaystyle \ lambda \ mapsto D (\ lambda x_ {1} + (1- \ lambda) y_ {1}, \ dots, \ lambda x_ {n} + (1- \ lambda) y_ {n})}λ∈[0,1]{\ displaystyle \ lambda \ in [0,1]}D(λX1+(1-λ)y1,...,λXnon+(1-λ)ynon)=0{\ displaystyle D (\ lambda x_ {1} + (1- \ lambda) y_ {1}, \ dots, \ lambda x_ {n} + (1- \ lambda) y_ {n}) = 0}

Pertanto, 0 è nell'inviluppo convesso di se e solo se esiste tale che e . Se è così . Tuttavia, per le condizioni di Haar, formano una base dello spazio e quindi sono tutti zero, il che non è perché la loro somma è uguale a 1. Quindi . Allo stesso modo, per ogni i , . In particolare ,. Risolvendo questo sistema lineare secondo le regole di Cramer, abbiamo λioXio^{\ displaystyle \ lambda _ {i} {\ hat {x_ {i}}}}α0,...,αnon∈[0,1]{\ Displaystyle \ alpha _ {0}, \ dots, \ alpha _ {n} \ in [0,1]}0=∑io=0nonαioλioXio^{\ displaystyle 0 = \ sum _ {i = 0} ^ {n} \ alpha _ {i} \ lambda _ {i} {\ hat {x_ {i}}}}∑io=0nonαio=1{\ displaystyle \ sum _ {i = 0} ^ {n} \ alpha _ {i} = 1}α0=0{\ displaystyle \ alpha _ {0} = 0}∑io=1nonαioλioXio^=0{\ displaystyle \ sum _ {i = 1} ^ {n} \ alpha _ {i} \ lambda _ {i} {\ hat {x_ {i}}} = 0}λioXio^{\ displaystyle \ lambda _ {i} {\ hat {x_ {i}}}}Rnon{\ displaystyle \ mathbb {R} ^ {n}}αio{\ displaystyle \ alpha _ {i}}α0≠0{\ displaystyle \ alpha _ {0} \ neq 0}αio≠0{\ displaystyle \ alpha _ {i} \ neq 0}X0^=∑io=1non-λioαioλ0α0Xio^{\ displaystyle {\ hat {x_ {0}}} = \ sum _ {i = 1} ^ {n} {\ frac {- \ lambda _ {i} \ alpha _ {i}} {\ lambda _ {0 } \ alpha _ {0}}} {\ hat {x_ {i}}}}

-λioαioλ0α0=D(X1,...,Xio-1,X0,Xio+1,...,Xnon)D(X1,...,Xnon)=(-1)io-1D(X0,...,Xio-1,Xio+1,...,Xnon)D(X1,...,Xnon){\ displaystyle {\ frac {- \ lambda _ {i} \ alpha _ {i}} {\ lambda _ {0} \ alpha _ {0}}} = {\ frac {D (x_ {1}, \ dots , x_ {i-1}, x_ {0}, x_ {i + 1}, \ dots, x_ {n})} {D (x_ {1}, \ dots, x_ {n})}} = {\ frac {(-1) ^ {i-1} D (x_ {0}, \ dots, x_ {i-1}, x_ {i + 1}, \ dots, x_ {n})} {D (x_ { 1}, \ dots, x_ {n})}}}

Poi,

λioλ0=(-1)ioD(X0,...,Xio-1,Xio+1,...,Xnon)α0D(X1,...,Xnon)αio{\ displaystyle {\ frac {\ lambda _ {i}} {\ lambda _ {0}}} = {\ frac {(-1) ^ {i} D (x_ {0}, \ dots, x_ {i- 1}, x_ {i + 1}, \ dots, x_ {n}) \ alpha _ {0}} {D (x_ {1}, \ dots, x_ {n}) \ alpha _ {i}}}}

Le determinanti sono tutte dello stesso segno, sono strettamente positive. Quindi , vale a dire che si alternano di segno, o anche quello per tutto , (perché non sono zero). αio{\ displaystyle \ alpha _ {i}}sgnλio=(-1)iosgnλ0{\ displaystyle {\ textrm {sgn}} \ lambda _ {i} = (- 1) ^ {i} {\ textrm {sgn}} \ lambda _ {0}}λio{\ displaystyle \ lambda _ {i}}io∈{1,...,non}{\ displaystyle i \ in \ {1, \ dots, n \}}λioλio-1<0{\ displaystyle \ lambda _ {i} \ lambda _ {i-1} <0}

Dimostrazione del teorema dell'alternanza

Useremo ora il teorema e il lemma precedentemente dimostrato per dimostrare il teorema dell'alternanza. Prendiamo le annotazioni della dichiarazione.

Abbiamo che p * è la migliore approssimazione di f per la norma uniforme se e solo se r * è di norma uniforme minima. Per il teorema di caratterizzazione, questo è vero se e solo se 0 è nello scafo convesso di . Quindi esiste e con tale che , questo viola le condizioni di Haar se k < n . Quindi abbiamo . Anche se significa reindicizzare, li prendiamo in ordine crescente . Per le condizioni di Haar, come nel lemma, sono tutti diversi da zero. Applichiamo quindi il lemma e l'alternanza dei segni. Poiché sono positivi, sono i segni che si alternano. Questo quindi conclude la dimostrazione. {r(X)X^ | X∈X}{\ displaystyle \ {r (x) {\ hat {x}} \ | \ x \ in X \}}X0,...,XK∈X{\ displaystyle x_ {0}, \ dots, x_ {k} \ in X}α0,...αK∈[0,1]{\ Displaystyle \ alpha _ {0}, \ dots \ alpha _ {k} \ in [0,1]}K≤non{\ displaystyle k \ leq n}0=∑io=1Kαior(Xio)Xio^{\ displaystyle 0 = \ sum _ {i = 1} ^ {k} \ alpha _ {i} r (x_ {i}) {\ hat {x_ {i}}}}K=non{\ displaystyle k = n}Xio{\ displaystyle x_ {i}}a≤X0<⋯<Xnon≤b{\ displaystyle a \ leq x_ {0} <\ cdots <x_ {n} \ leq b}αior(Xio){\ displaystyle \ alpha _ {i} r (x_ {i})}αio{\ displaystyle \ alpha _ {i}}r(Xio){\ displaystyle r (x_ {i})}

Unicità della migliore approssimazione

Finora abbiamo definito cos'è una migliore approssimazione. Mostreremo ora che la migliore approssimazione esiste ed è unica.

stati

Considera un sistema Chebyshev. Sia una funzione continua. Poi c'è una migliore approssimazione unica di in . {g1,...,gnon}⊆VS([a,b]){\ displaystyle \ {g_ {1}, \ dots, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}f∈VS([a,b]){\ Displaystyle f \ in {\ mathcal {C}} ([a, b])}f{\ displaystyle f}Vect(g1,...,gnon){\ displaystyle {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n})}

Dimostrazione

Cominciamo con l'unicità. Quindi supponiamo che e siano le migliori approssimazioni per . Quindi abbiamo quello e questo standard è minimo. L'oro poi abbiamo . Quindi è ancora una migliore approssimazione. Sia dato dal teorema dell'alternanza per . Supponiamo che . Quindi almeno uno dei due non vale , diciamo anche se significa rinominare , e così via . Abbiamo p{\ displaystyle p}q{\ displaystyle q}f{\ displaystyle f}‖f-p‖∞=‖f-q‖∞{\ displaystyle \ | {fp} \ | _ {\ infty} = \ | {fq} \ | _ {\ infty}}‖f-p+q2‖∞≤‖f-p‖∞{\ displaystyle \ sinistra \ | {f - {\ frac {p + q} {2}}} \ right \ | _ {\ infty} \ leq \ | {fp} \ | _ {\ infty}}r=p+q2{\ displaystyle r = {\ frac {p + q} {2}}}X0<⋯<Xnon{\ displaystyle x_ {0} <\ cdots <x_ {n}}r{\ displaystyle r}p(Xio)≠q(Xio){\ displaystyle p (x_ {i}) \ neq q (x_ {i})}r(Xio){\ displaystyle r (x_ {i})}q(Xio){\ displaystyle q (x_ {i})}|f(Xio)-q(Xio)|<‖f-r‖∞{\ displaystyle | f (x_ {i}) - q (x_ {i}) | <\ | {fr} \ | _ {\ infty}}

‖f-r‖∞=|f(Xio)-r(Xio)|≤12|f(Xio)-p(Xio)|+12|f(Xio)-q(Xio)|<‖f-r‖∞{\ displaystyle \ | {en} \ | _ {\ infty} = | f (x_ {i}) - r (x_ {i}) | \ leq {\ frac {1} {2}} | f (x_ { i}) - p (x_ {i}) | + {\ frac {1} {2}} | f (x_ {i}) - q (x_ {i}) | <\ | {fr} \ | _ { \ infty}}. Questo non ha senso. Quindi . Quindi con zeri distinti. Quindi dalle condizioni di Haar, otteniamo che sia identicamente zero e quindi quello . Quindi abbiamo l'unicità. r(Xio)=p(Xio)=q(Xio){\ displaystyle r (x_ {i}) = p (x_ {i}) = q (x_ {i})}p-q{\ displaystyle pq}non+1{\ displaystyle n + 1}p=q{\ displaystyle p = q}

Passiamo ora alla dimostrazione dell'esistenza. Considera . Questo set è chiaramente chiuso e limitato. Non è vuoto poiché la funzione nulla è in ed è di dimensione finita. Quindi è compatto. Quindi essendo continuo , raggiunge un minimo lì, diciamo in . Ora, if è la migliore approssimazione di allora per disuguaglianza triangolare. Quindi . Quindi è un'approssimazione molto migliore per . F={p∈Vect(g1,...,gnon) | ‖p‖∞≤2‖f‖∞}{\ displaystyle F = \ {p \ in {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n}) \ | \ \ | {p} \ | _ {\ infty} \ leq 2 \ | {f} \ | _ {\ infty} \}}F{\ displaystyle F}Vect(g1,...,gnon){\ displaystyle {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n})}F{\ displaystyle F}p↦‖f-p‖∞{\ displaystyle p \ mapsto \ | {fp} \ | _ {\ infty}}F{\ displaystyle F}p∗{\ displaystyle p ^ {*}}p{\ displaystyle p}f{\ displaystyle f}‖p‖∞-‖f‖∞≤‖f-p‖∞≤‖f‖∞{\ displaystyle \ | {p} \ | _ {\ infty} - \ | {f} \ | _ {\ infty} \ leq \ | {fp} \ | _ {\ infty} \ leq \ | {f} \ | _ {\ infty}}p∈F{\ displaystyle p \ in F}p∗{\ displaystyle p ^ {*}}f{\ displaystyle f}

Vedi anche

• Sviluppo limitato
• L'algoritmo di Remez
• Unequal Jackson  (en)
• Serie di Fourier generalizzata

• Questo articolo è parzialmente o interamente tratto dall'articolo intitolato “  Teoria dell'approssimazione / Dimostrazioni  ” (vedi l'elenco degli autori ) .

Fonti

1. (in) CHENEY EW, Introduzione alla teoria dell'approssimazione ,1966
2. (in) POWEL MJD, teoria e metodi di approssimazione , Univetrsity Cambridge Press,diciannove ottantuno

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">