Teoria aproximării

În matematică , teoria aproximării se referă la modul în care funcțiile pot fi aproximate prin funcții mai simple , oferind o caracterizare cantitativă a erorilor introduse de aceste aproximări.

Problematic

Problema aproximării a apărut foarte devreme în geometrie, pentru funcții trigonometrice  : acestea sunt funcții ale căror proprietăți le cunoaștem (paritate, derivabilitate, valori la anumite puncte), dar care nu sunt exprimate din operații d ' care pot fi efectuate manual. (cele patru operații ). Acest lucru a dus la noțiunea de dezvoltare serială . Am putut astfel să constituim tabele trigonometrice , apoi, cu o abordare similară, tabele logaritmice și, în general, tabele pentru funcțiile utilizate în mod obișnuit în știință, cum ar fi rădăcina pătrată .

O problemă deosebit de interesantă este aceea a aproximării funcțiilor de către altele definite numai din operațiile de bază de computer , cum ar fi adunarea și multiplicarea, pentru a crea biblioteci de funcții matematice care la rândul lor execută produc valori cât mai apropiate de valorile teoretice . Aceasta se numește aproximare polinomială sau rațională (adică prin funcții raționale ).

Scopul este de a oferi o aproximare cât mai precisă a unei funcții reale date, astfel încât să ofere cele mai exacte valori posibile, până la precizia apropiată de aritmetica în virgulă mobilă a unui computer . Acest obiectiv este atins prin utilizarea unui polinom de grad înalt și / sau prin micșorarea domeniului peste care polinomul trebuie să aproximeze funcția. Reducerea domeniului poate fi adesea efectuată, deși acest lucru necesită compunerea funcției care trebuie aproximată prin alte funcții afine . Bibliotecile matematice moderne reduc adesea domeniul împărțindu-l în mai multe segmente mici și utilizează un polinom de grad scăzut pe fiecare segment.

Odată ce domeniul și gradul polinomului au fost alese, polinomul în sine este ales astfel încât să minimizeze eroarea în cel mai rău caz. Cu alte cuvinte, dacă f este funcția reală și P polinomul care trebuie să se apropie de f , trebuie să minimalizăm limita superioară a funcției de pe domeniu. Pentru o funcție „adecvată”, un polinom optim de grad N este caracterizat printr-o curbă de eroare a cărei valoare oscilează între + ε și - ε și care schimbă semnul N + 1 ori, dând o eroare în cele mai grave cazuri de ε . Este posibil să construim funcții f pentru care această proprietate nu deține, dar în practică este în general adevărată. |P-f|{\ displaystyle | Pf |}

• Eroare între polinomul optim de gradul 4 și logaritmul natural ln (în roșu) și între aproximarea lui Chebyshev a ln (în albastru) pe intervalul [2, 4]. Pasul vertical este de 10 -5 . Eroarea maximă pentru polinomul optim este 6,07 × 10 −5 .

• Eroare între polinomul optim de gradul 4 și e exponențială (în roșu) și între aproximarea Chebyshev și exp (în albastru) pe intervalul [−1, 1]. Pasul vertical este de 10 −4 . Eroarea maximă pentru polinomul optim este 5,47 × 10 −4 .

În fiecare caz, numărul de extreme este N + 2 adică 6. Două dintre extreme sunt capetele segmentului. Curbele în roșu, pentru polinomul optim, sunt de „nivel”, adică oscilează exact între + ε și - ε . Dacă un polinom de grad N conduce la o funcție de eroare care oscilează între extrema N + 2 ori, atunci acest polinom este optim.

Aproximarea prin polinoame

State

Să f să fie o funcție continuă pe un interval real , închis [ a , b ] . Fie P un polinom de grad n .

Observăm eroarea de aproximare între P și f . ε=P-f{\ displaystyle \ varepsilon = Pf}

Dacă există și așa încât la≤X0<X1<⋯<Xnu+1≤b{\ displaystyle a \ leq x_ {0} <x_ {1} <\ cdots <x_ {n + 1} \ leq b}s∈{-1,1}{\ displaystyle s \ in \ {- 1, \; 1 \}}

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

atunci P este un polinom de aproximare optim al lui f printre polinoame de grad mai mic sau egal cu n în sensul normei sup de pe [ a , b ]  :

P=arg⁡minÎ∈Rnu[X]‖f-S‖∞,[la,b]{\ displaystyle P = \ operatorname {arg} \ min _ {Q \ in \ mathbb {R} _ {n} [X]} \ | fS \ | _ {\ infty, [a, b]}} Demonstrație

Să începem prin a-l arăta pe un grafic. Să pozăm . Să presupunem că acesta este un polinom de grad care posedă proprietățile de mai sus, în sensul că oscilează între extreme de semne alternative, de la până la . NU=4{\ displaystyle N = 4}P{\ displaystyle P}nu{\ displaystyle n}P-f{\ displaystyle Pf}nu+2{\ displaystyle n + 2}+ε{\ displaystyle + \ varepsilon}-ε{\ displaystyle - \ varepsilon}

Funcția de eroare ar putea arăta ca graficul roșu:P-f{\ displaystyle Pf}

P-f{\ displaystyle Pf}a ajuns la extrema (dintre care două sunt la extremități), care au aceeași magnitudine în valoare absolută situată în 6 intervale pe graficul de mai sus. nu+2{\ displaystyle n + 2}

Fie acum un polinom de aproximare de grad optim. Aceasta înseamnă că extrema funcției sale de eroare trebuie să aibă toate o valoare absolută strict mai mică decât , astfel încât să fie situate strict în interiorul graficului de eroare pentru . Î{\ displaystyle Q}nu{\ displaystyle n}ε{\ displaystyle \ varepsilon}P{\ displaystyle P}

Funcția de eroare pentru ar putea avea o reprezentare grafică asemănătoare graficului albastru de mai sus. Aceasta înseamnă că trebuie să oscileze între numere care nu sunt zero strict pozitive și strict negative de un număr total de ori. Dar este egal cu care este un polinom de grad . Trebuie să aibă cel puțin rădăcinile situate între diferite puncte în care funcția polinomială ia valori diferite de zero. Cu toate acestea, într-un inel integral, un polinom diferit de zero nu poate avea mai multe rădăcini. Deci este identic zero, adică asta . Î{\ displaystyle Q}(P-f)-(Î-f){\ displaystyle (Pf) - (Qf)}NU+2{\ displaystyle N + 2}(P-f)-(Î-f){\ displaystyle (Pf) - (Qf)}P-Î{\ displaystyle PQ}nu{\ displaystyle n}nu+1{\ displaystyle n + 1}nu{\ displaystyle n}nu{\ displaystyle n}P-Î{\ displaystyle PQ}P=Î{\ displaystyle P = Q}

Aproximare Chebyshev

Este posibil să se obțină polinoame foarte apropiate de un polinom optim prin extinderea unei funcții date cu polinoame Chebyshev și apoi tăierea expansiunii într-un anumit grad. Acest proces este similar cu extinderea seriei Fourier a unei funcții în analiza Fourier , dar folosind polinoame Chebyshev în locul funcțiilor trigonometrice obișnuite.

Calculăm coeficienții în expansiunea Chebyshev a unei funcții f  :

f(X)≃∑nu=0∞vs.nuTnu(X){\ displaystyle f (x) \ simeq \ sum _ {n = 0} ^ {\ infty} c_ {n} T_ {n} (x)}

dintre care păstrăm doar primii N termeni ai seriei, ceea ce dă un polinom de grad N care se apropie de funcția f .

Motivul pentru care acest polinom este aproape optim este că, pentru funcțiile care admit o expansiune în serie întreagă, a cărei serie are o convergență rapidă, eroarea făcută la expansiunea după N termeni este aproximativ egală cu termenul imediat după tăiere. Adică primul termen imediat după tăiere domină suma tuturor termenilor ulteriori numiți restul seriei. Acest rezultat rămâne dacă extinderea se face cu polinoame Chebyshev. Dacă o expansiune Chebyshev este întreruptă după T N , atunci eroarea va fi aproape de termenul din T N + 1 . Polinoamele Chebyshev au proprietatea de a avea o curbă reprezentativă „la nivel”, oscilând între +1 și −1 în intervalul [−1, 1]. T n + 1 a n + 2 extrema . Aceasta înseamnă că eroarea dintre f și aproximarea lui Chebyshev la un termen din T n este o funcție care are n + 2 extreme, ale căror maxime (respectiv minime) sunt egale și, prin urmare, este apropiată de polinomul optim de grad n .

În exemplele grafice de mai sus, putem vedea că funcția de eroare afișată în albastru este uneori mai bună (când rămâne sub) decât funcția afișată în roșu, dar mai gravă la anumite intervale, ceea ce înseamnă că acesta nu este chiar polinomul optim. Această diferență este relativ mai puțin importantă pentru funcția exponențială , a cărei serie întreagă converge foarte repede decât pentru funcția logaritmică .

Sisteme Chebyshev

Această parte și următoarele se bazează în principal pe lucrările lui Cheney și Powell.

Este posibil să se generalizeze caracterizarea „cea mai bună aproximare” cu spații de funcții de aproximare care nu sunt polinoame ci funcții standard. Cu toate acestea, astfel de familii de funcții trebuie să aibă anumite proprietăți bune pe care le au polinoamele. Vorbim apoi de „polinoame generalizate”. Aceste „polinoame” vor avea funcții de bază (pe care le considerăm plăcute) ca monomii care îndeplinesc condițiile lui Haar.

Condiții Haar

O familie de funcții ale unui interval în îndeplinește condițiile Haar dacă și numai dacă {g1,...,gnu}{\ displaystyle \ {g_ {1}, \ dots, g_ {n} \}}[la,b]{\ displaystyle [a, b]}R{\ displaystyle \ mathbb {R}}

1. Toate funcțiile sunt continue.geu{\ displaystyle g_ {i}}
2. Funcțiile îndeplinesc următoarele condiții echivalente: g1,...,gnu{\ displaystyle g_ {1}, \ dots, g_ {n}}
   1. Pentru toate distincteX1,...,Xnu∈[la,b]{\ displaystyle x_ {1}, \ dots, x_ {n} \ în [a, b]}|g1(X1)⋯gnu(X1)⋮⋮g1(Xnu)⋯gnu(Xnu)|≠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. Pentru toți diferiți, pentru toți , există un tuplu unic astfel încât funcția să fie satisfăcutăX1,...,Xnu∈[la,b]{\ displaystyle x_ {1}, \ dots, x_ {n} \ în [a, b]}y1,...,ynu{\ displaystyle y_ {1}, \ dots, y_ {n}}(α1,...,αnu){\ displaystyle (\ alpha _ {1}, \ dots, \ alpha _ {n})}f=∑eu=1nuαeugeu{\ displaystyle f = \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}∀eu∈{1,...,nu}f(Xeu)=yeu{\ displaystyle \ forall i \ in \ {1, \ dots, n \} \ quad f (x_ {i}) = y_ {i}}
   3. Funcțiile sunt liniar independente și este funcția unică a formei având strict mai multe rădăcinig1,...,gnu{\ displaystyle g_ {1}, \ dots, g_ {n}}X↦0{\ displaystyle x \ mapsto 0}X↦∑eu=1nuαeugeu(X){\ displaystyle x \ mapsto \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i} (x)}nu-1{\ displaystyle n-1}[la,b]{\ displaystyle [a, b]}

O familie finită de funcții care îndeplinește condițiile lui Haar se numește sistem Chebyshev. Evident, monomiile cu grad scalat formează un sistem Chebyshev: polinoamele sunt continue, condiția 2.1 este determinantul Vandermonde , condiția 2.2 este caracterizarea polinomului de interpolare și condiția 2.3 este faptul că un polinom cu grad fix nu poate avea mai multă rădăcină decât grad. g1,...,gnu∈VS([la,b]){\ displaystyle g_ {1}, \ dots, g_ {n} \ in {\ mathcal {C}} ([a, b])}{1,X,...Xnu-1}{\ displaystyle \ {1, X, \ dots X ^ {n-1} \}}

Putem spune, de asemenea, că un sub spațiu de dimensiune îndeplinește condițiile Haar dacă și numai dacă fundamentele sale sunt sisteme Chebyshev. E{\ displaystyle E}VS([la,b]){\ displaystyle {\ mathcal {C}} ([a, b])}nu{\ displaystyle n}

Echivalența caracterizărilor

Dovada echivalenței punctelor 2.1, 2.2 și 2.3 se va face prin implicații circulare.

2.1 ⇒ 2.2 Se consideră distinct și . Prin ipoteza 2.1, observăm în special că matricea X1,...,Xnu∈[la,b]{\ displaystyle x_ {1}, \ dots, x_ {n} \ în [a, b]}y1,...,ynu∈R{\ displaystyle y_ {1}, \ dots, y_ {n} \ in \ mathbb {R}}

M: =(g1(X1)⋯gnu(X1)⋮⋮g1(Xnu)⋯gnu(Xnu)){\ 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

este inversabil. Există deci o soluție unică la ecuația Or, această ultimă ecuație este echivalentă cu . Astfel vine existența și unicitatea unui tuplu astfel încât interpola y i în x i . M⋅(la1,...,lanu)T=(y1,...,ynu)T{\ displaystyle M \ cdot (a_ {1}, \ dots, a_ {n}) ^ {T} = (y_ {1}, \ dots, y_ {n}) ^ {T}}∀eu∈{1,...,nu}∑j=1nulajgj(Xeu)=yeu{\ displaystyle \ forall i \ in \ {1, \ dots, n \} \ quad \ sum _ {j = 1} ^ {n} a_ {j} g_ {j} (x_ {i}) = y_ {i }}(α1,...,αnu){\ displaystyle (\ alpha _ {1}, \ dots, \ alpha _ {n})}f=∑eu=1nuαeugeu{\ displaystyle f = \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}

2.2 ⇒ 2.3 Funcția nulă are clar mai mult de n - 1 rădăcini între a și b , deoarece are o infinitate de ele. Să avem acum n rădăcini distincte, notat . Funcția nulă și f coincid în aceste puncte. Prin proprietatea 2.2, avem deci f = 0 . Asta implică în plus că g i sunt liniar independenți dacă nu ar exista o duplicitate a scrierii funcției nule, ceea ce este interzis de ipoteza 2.2. X↦0{\ displaystyle x \ mapsto 0}f=∑eu=1nuαeugeu{\ displaystyle f = \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}X1,...,Xnu{\ displaystyle x_ {1}, \ dots, x_ {n}}

2.3 ⇒ 2.1 Să fie distinct. Să presupunem că matricea nu este inversabilă. Apoi coloanele sale sunt liniar dependente și, prin urmare, există astfel încât . Atunci sunt rădăcini ale căror valori sunt deci zero prin proprietatea 2.3. Întotdeauna prin această proprietate, urmează prin independența g i ceea ce este absurd. Prin urmare, matricea este inversabilă și determinantul său este, prin urmare, diferit de zero. X1,...,Xnu∈[la,b]{\ displaystyle x_ {1}, \ dots, x_ {n} \ în [a, b]}M: =(g1(X1)⋯gnu(X1)⋮⋮g1(Xnu)⋯gnu(Xnu)){\ 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,...,αnu{\ displaystyle \ alpha _ {1}, \ dots, \ alpha _ {n}}∀j∈{1,...,nu}∑eu=1nuαeugeu(Xj)=0{\ displaystyle \ forall j \ in \ {1, \ dots, n \} \ quad \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i} (x_ {j}) = 0 }X1,...,Xnu{\ displaystyle x_ {1}, \ dots, x_ {n}}∑eu=1nuαeugeu{\ displaystyle \ sum _ {i = 1} ^ {n} \ alpha _ {i} g_ {i}}∀eu∈{1,...,nu}αeu=0{\ displaystyle \ forall i \ in \ {1, \ dots, n \} \ quad \ alpha _ {i} = 0}

Exemple

Putem cita două exemple de sisteme Chebyshev:

• Dacă sunt două câte două distincte, atunci formează un sistem Chebyshev pornit pentru orice interval compact de .λ1,...,λnu{\ displaystyle \ lambda _ {1}, \ dots, \ lambda _ {n}}{eλ1X,...,eλnuX}{\ displaystyle \ {\ mathrm {e} ^ {\ lambda _ {1} x}, \ dots, \ mathrm {e} ^ {\ lambda _ {n} x} \}}R{\ displaystyle \ mathbb {R}}
• Dacă sunt doi-la-doi distincti și pozitivi, atunci formați un sistem Chebyshev pornit pentru un interval compact de .λ1,...,λnu{\ displaystyle \ lambda _ {1}, \ dots, \ lambda _ {n}}{Xλ1,...,Xλnu}{\ displaystyle \ {x ^ {\ lambda _ {1}}, \ dots, x ^ {\ lambda _ {n}} \}}R{\ displaystyle \ mathbb {R}}

Teorema alternanței

Sistemele Chebyshev permit caracterizarea celor mai bune aproximări ale funcțiilor continue fiind polinoame generalizate construite din funcțiile sistemului menționat.

State

Luați în considerare un sistem Chebyshev. Fie o funcție continuă. Fie un polinom generalizat peste sistemul Chebyshev și eroarea de aproximare. Atunci este cea mai bună aproximare uniformă a , adică , dacă există astfel încât și{g1,...,gnu}⊆VS([la,b]){\ displaystyle \ {g_ {1}, \ dots, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}f∈VS([la,b]){\ displaystyle f \ in {\ mathcal {C}} ([a, b])}p∗=∑eu=1nuαeu∗geu{\ 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,...,gnu)‖f-p‖∞{\ displaystyle \ | r ^ {*} \ | _ {\ infty} = \ min _ {p \ in {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n})} {\ | fp \ | _ {\ infty}}}la≤X0<⋯<Xnu≤b{\ displaystyle a \ leq x_ {0} <\ cdots <x_ {n} \ leq b}r(Xeu)=(-1)eur(X0){\ displaystyle r (x_ {i}) = (- 1) ^ {i} r (x_ {0})}r(X0)=±‖r‖∞{\ displaystyle r (x_ {0}) = \ pm \ | r \ | _ {\ infty}}

Notă

Este interesant de remarcat faptul că, dacă sistemul considerat Chebyshev este baza canonică, atunci această afirmație este exact cea a teoremei în cazul polinoamelor. Rnu-1[X]{\ displaystyle \ mathbb {R} _ {n-1} [X]}

Dovada teoremei alternanței

Teorema caracterizării

Primul lucru de făcut este să caracterizați cele mai bune aproximări prin polinoame generalizate. Putem începe prin a arăta că este suficient ca originea spațiului să se afle într-un anumit plic convex. Pentru un sistem Chebyshev, observăm . {g1,...,gnu}{\ displaystyle \ {g_ {1}, \ dots, g_ {n} \}}X^=(g1(X),...,gnu(X))T{\ displaystyle {\ hat {x}} = (g_ {1} (x), \ dots, g_ {n} (x)) ^ {T}}

Luați în considerare un sistem Chebyshev. Fie o funcție continuă. Fie un polinom generalizat peste sistemul Chebyshev și eroarea de aproximare. Atunci r este de normă minimă dacă și numai dacă 0 este în carena convexă a .{g1,...,gnu}⊆VS([la,b]){\ displaystyle \ {g_ {1}, \ dots, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}f∈VS([la,b]){\ displaystyle f \ in {\ mathcal {C}} ([a, b])}p=∑eu=1nuαeu∗geu{\ 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} \}}

Demonstrație Stare suficientă

Să continuăm prin contrapunere și să presupunem că nu este minim. Atunci este posibil să se găsească un polinom generalizat care să satisfacă o eroare de aproximare mai bună. Cu alte cuvinte, există asemenea . ‖r‖∞{\ displaystyle \ | r \ | _ {\ infty}}d=(d1,...,dnu){\ displaystyle d = (d_ {1}, \ dots, d_ {n})}‖∑eu=1nu(αeu∗-deu)geu‖∞<‖r‖∞{\ displaystyle \ left \ | \ sum _ {i = 1} ^ {n} (\ alpha _ {i} ^ {*} - d_ {i}) g_ {i} \ right \ | _ {\ infty} < \ | r \ | _ {\ infty}}

Să pozăm . Deci pentru tot ce avem X={X∈[la,b] | |r(X)|=‖r‖∞}{\ displaystyle X = \ {x \ in [a, b] \ | \ | r (x) | = \ | r \ | _ {\ infty} \}}X∈X{\ displaystyle x \ în X}

|r(X)-∑eu=1nudeugeu(X)|≤‖r-∑eu=1nudeugeu‖∞=‖∑eu=1nu(αeu∗-deu)geu‖∞<‖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) |}

Prin pătrarea membrilor inegalității,

(r(X)-∑eu=1nudeugeu(X))2<r(X)2{\ displaystyle \ left (r (x) - \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right) ^ {2} <r (x) ^ {2} }

Apoi, prin dezvoltare

2r(X)∑eu=1nudeugeu(X)>(∑eu=1nudeugeu(X))2{\ displaystyle 2r (x) \ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x)> \ left (\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ dreapta) ^ {2}}

și

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

Prin urmare, acum este o chestiune de a arăta că 0 nu se află în învelișul convex al lui , care este un subset de , și atunci vom fi demonstrat contrapusul. Să presupunem deci contrariul. Există și astfel încât și . Asa de {r(X)X^ | X∈X}{\ displaystyle \ {r (x) {\ hat {x}} \ | \ x \ în X \}}Rnu{\ displaystyle \ mathbb {R} ^ {n}}X1,...,Xnu∈X{\ displaystyle x_ {1}, \ dots, x_ {n} \ în X}la1,...lanu∈[0,1]{\ displaystyle a_ {1}, \ dots a_ {n} \ în [0,1]}∑eu=1nulaeur(Xeu)Xeu^=0{\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} r (x_ {i}) {\ hat {x_ {i}}} = 0}∑eu=1nulaeu=1{\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i} = 1}

0=⟨d,0⟩=⟨d,∑eu=1nulaeur(Xeu)Xeu^⟩=∑eu=1nulaeu⟨d,r(Xeu)Xeu^⟩>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}

Desigur, acest lucru este absurd, CQFD.

Condiție necesară

De asemenea, procedăm prin contrapunere. Să presupunem, așadar, că 0 nu se află în plicul convex C al mulțimii . C este închis deoarece este un plic convex. El este limitat pentru că „este. Într-adevăr, r și g i sunt continue și X este conținut într-un interval mărginit. C este deci închis mărginit în dimensiune finită (conținută în ), prin urmare este compact. Astfel, atinge un minim pe C , să zicem în . În special . Fie arbitrar, fie . Prin convexitate . Atunci {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 \ în X \}}{r(X)X^ | r(X)=‖r‖∞}{\ displaystyle \ {r (x) {\ hat {x}} \ | \ r (x) = \ | r \ | _ {\ infty} \}}Rnu{\ displaystyle \ mathbb {R} ^ {n}}‖⋅‖2{\ displaystyle \ | \ cdot \ | _ {2}}d∈VS{\ displaystyle d \ în C}d≠0{\ displaystyle d \ neq 0}tu∈VS{\ displaystyle u \ în C}λ∈[0,1]{\ displaystyle \ lambda \ in [0,1]}λtu+(1-λ)d∈VS{\ displaystyle \ lambda u + (1- \ lambda) d \ în C}

‖λtu+(1-λ)d‖22≥‖d‖22‖λtu+(1-λ)d‖22-‖d‖22≥0λ2‖tu-d‖22+2λ⟨tu-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}}}

Pentru suficient de mic, această inegalitate este însă încălcată . Deci . Deci , pentru toți , . X este un conținut închis în C , deci este și compact. Pentru continuitatea lui r și g i , se admite un minim . Pentru ceea ce trebuie să facem . Notă . Vom căuta apoi, cum ar fi , care va încheia. Să pozăm acum . Prin definiție . În ceea ce privește celelalte, Y este încă compact. Fie R, prin urmare , maximul de | r | pe Y . Dacă nu, atunci avem maximul atunci satisfăcut , ceea ce este absurd. Deci dacă , λ{\ displaystyle \ lambda}⟨tu-d,d⟩<0{\ displaystyle \ langle {ud, d} \ rangle <0}⟨tu-d,d⟩≥0{\ displaystyle \ langle {ud, d} \ rangle \ geq 0}tu∈VS{\ displaystyle u \ în C}⟨tu,d⟩=⟨tu-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 \ în X \}}ϵ{\ displaystyle \ epsilon}ϵ>0{\ displaystyle \ epsilon> 0}d=(d1,...,dnu)T{\ displaystyle d = (d_ {1}, \ dots, d_ {n}) ^ {T}}μ>0{\ displaystyle \ mu> 0}‖r-μ∑eu=1nudeugeu‖∞<‖r‖∞{\ displaystyle \ left \ | {r- \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ right \ | _ {\ infty} <\ | {r} \ | _ {\ infty}}Da={X∈[la,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 \}}Da∩X=∅{\ displaystyle Y \ cap X = \ emptyset}R<‖r‖∞{\ displaystyle R <\ | {r} \ | _ {\ infty}}y∈Da{\ displaystyle y \ in Y}y∈X{\ displaystyle y \ în X}X∈Da{\ displaystyle x \ în Y}

∀X∈Da,|r(X)-μ∑eu=1nudeugeu(X)|≤|r(X)|+μ|∑eu=1nudeugeu(X)|≤R+μ‖∑eu=1nudeugeu‖∞{\ displaystyle \ forall x \ în 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 \ | {\ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ right \ | _ {\ infty}}

Dacă acum atunci X∉Da{\ displaystyle x \ notin Y}

|r(X)-μ∑eu=1nudeugeu(X)|2=r(X)2-2μ∑eu=1nudeur(X)geu(X)+μ2(∑eu=1nudeugeu(X))2≤‖r‖∞2-2μ⟨d,r(X)X^⟩+μ2(∑eu=1nudeugeu(X))2≤‖r‖∞2-2μϵ2+μ2(∑eu=1nudeugeu(X))2deoarece X∉Da≤‖r‖∞2+μ(-ϵ+μ‖∑eu=1nudeugeu‖∞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} \ left (\ 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} \ left (\ sum _ {i = 1} ^ {n} d_ {i} g_ {i} (x) \ right) ^ {2} & {\ textrm {car} } \ 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 {align}}}

Deci pentru , avem 0<μ<min(‖r‖∞-R2‖∑eu=1nudeugeu‖∞,ϵ2‖∑eu=1nudeugeu‖∞2){\ displaystyle 0 <\ mu <\ min \ left ({\ 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)-μ∑eu=1nudeugeu(X)|<‖r‖∞+R2pentru X∈Da|r(X)-μ∑eu=1nudeugeu(X)|2<‖r‖∞2-μϵ2pentru X∉Da{\ 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 \ în Y \\\ left | 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 {align}}}

Astfel, și, prin urmare, nu este minim. ‖r-μ∑eu=1nudeugeu‖∞<‖r‖∞{\ displaystyle \ left \ | {r- \ mu \ sum _ {i = 1} ^ {n} d_ {i} g_ {i}} \ right \ | _ {\ infty} <\ | {r} \ | _ {\ infty}}r{\ displaystyle r}

Lemă alternativă

Există o legătură între faptul că 0 este într-un plic convex și că există alternanță de semne.

Luați în considerare un sistem Chebyshev. Să nu fie constante . Atunci 0 este în corpul convex al dacă și numai dacă pentru avem .{g1,...,gnu}⊆VS([la,b]){\ displaystyle \ {g_ {1}, \ dots, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}la≤X0<⋯<Xnu≤b{\ displaystyle a \ leq x_ {0} <\ cdots <x_ {n} \ leq b}λ0,...,λnu∈R∗{\ displaystyle \ lambda _ {0}, \ dots, \ lambda _ {n} \ in \ mathbb {R} ^ {*}}{λeuXeu^ | eu∈{1,...,nu}}{\ displaystyle \ {\ lambda _ {i} {\ hat {x_ {i}}} \ | \ i \ in \ {1, \ dots, n \} \}}eu∈{1,...,nu}{\ displaystyle i \ in \ {1, \ dots, n \}}λeuλeu-1<0{\ displaystyle \ lambda _ {i} \ lambda _ {i-1} <0}

Dovadă a lemei

Să începem pentru determinant X1<⋯<Xnu{\ displaystyle x_ {1} <\ cdots <x_ {n}}

D(X1,...,Xnu)=|g1(X1)⋯gnu(X1)⋮⋮g1(Xnu)⋯gnu(Xnu)|{\ 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 |}.

Vom arăta că acești determinanți sunt toți strict pozitivi sau toți strict negativi. Pentru început, acestea sunt diferite de zero, deoarece sistemul îndeplinește condițiile lui Haar. Să presupunem că suntem pentru și avem {g1,...,gnu}{\ displaystyle \ {g_ {1}, \ dots, g_ {n} \}}X1<⋯<Xnu{\ displaystyle x_ {1} <\ cdots <x_ {n}}y1<⋅<ynu{\ displaystyle y_ {1} <\ cdot <y_ {n}}

D(X1,...,Xnu)<0<D(y1,...,ynu){\ displaystyle D (x_ {1}, \ dots, x_ {n}) <0 <D (y_ {1}, \ dots, y_ {n})}. Apoi, prin teorema valorilor intermediare aplicate , avem existența unui astfel de lucru , ceea ce este imposibil în condițiile lui Haar. Astfel, toți acești determinanți au același semn.λ↦D(λX1+(1-λ)y1,...,λXnu+(1-λ)ynu){\ 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,...,λXnu+(1-λ)ynu)=0{\ displaystyle D (\ lambda x_ {1} + (1- \ lambda) y_ {1}, \ dots, \ lambda x_ {n} + (1- \ lambda) y_ {n}) = 0}

Prin urmare, 0 se află în plicul convex al dacă și numai dacă există astfel încât și . Dacă da . Cu toate acestea, în condițiile lui Haar, ele formează o bază a spațiului și, prin urmare, toate sunt zero, ceea ce nu se datorează faptului că suma lor este egală cu 1. Prin urmare . În mod similar, pentru fiecare i , . În special ,. Rezolvând acest sistem liniar după regulile lui Cramer, avem λeuXeu^{\ displaystyle \ lambda _ {i} {\ hat {x_ {i}}}}α0,...,αnu∈[0,1]{\ displaystyle \ alpha _ {0}, \ dots, \ alpha _ {n} \ în [0,1]}0=∑eu=0nuαeuλeuXeu^{\ displaystyle 0 = \ sum _ {i = 0} ^ {n} \ alpha _ {i} \ lambda _ {i} {\ hat {x_ {i}}}}∑eu=0nuαeu=1{\ displaystyle \ sum _ {i = 0} ^ {n} \ alpha _ {i} = 1}α0=0{\ displaystyle \ alpha _ {0} = 0}∑eu=1nuαeuλeuXeu^=0{\ displaystyle \ sum _ {i = 1} ^ {n} \ alpha _ {i} \ lambda _ {i} {\ hat {x_ {i}}} = 0}λeuXeu^{\ displaystyle \ lambda _ {i} {\ hat {x_ {i}}}}Rnu{\ displaystyle \ mathbb {R} ^ {n}}αeu{\ displaystyle \ alpha _ {i}}α0≠0{\ displaystyle \ alpha _ {0} \ neq 0}αeu≠0{\ displaystyle \ alpha _ {i} \ neq 0}X0^=∑eu=1nu-λeuαeuλ0α0Xeu^{\ displaystyle {\ hat {x_ {0}}} = \ sum _ {i = 1} ^ {n} {\ frac {- \ lambda _ {i} \ alpha _ {i}} {\ lambda _ {0 } \ alpha _ {0}}} {\ hat {x_ {i}}}}

-λeuαeuλ0α0=D(X1,...,Xeu-1,X0,Xeu+1,...,Xnu)D(X1,...,Xnu)=(-1)eu-1D(X0,...,Xeu-1,Xeu+1,...,Xnu)D(X1,...,Xnu){\ 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})}}}

Atunci,

λeuλ0=(-1)euD(X0,...,Xeu-1,Xeu+1,...,Xnu)α0D(X1,...,Xnu)αeu{\ 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}}}}

Determinanții sunt toți de același semn, sunt strict pozitivi. Deci , asta înseamnă că alternează în semn, sau chiar asta pentru orice , (pentru că nu sunt zero). αeu{\ displaystyle \ alpha _ {i}}sgnλeu=(-1)eusgnλ0{\ displaystyle {\ textrm {sgn}} \ lambda _ {i} = (- 1) ^ {i} {\ textrm {sgn}} \ lambda _ {0}}λeu{\ displaystyle \ lambda _ {i}}eu∈{1,...,nu}{\ displaystyle i \ in \ {1, \ dots, n \}}λeuλeu-1<0{\ displaystyle \ lambda _ {i} \ lambda _ {i-1} <0}

Dovada teoremei alternanței

Vom folosi acum teorema și lema dovedită anterior pentru a demonstra teorema alternanței. Luăm notațiile declarației.

Avem că p * este cea mai bună aproximare a lui f pentru norma uniformă dacă și numai dacă r * este de norma minimă uniformă. Prin teorema caracterizării, acest lucru este adevărat dacă și numai dacă 0 este în corpul convex al lui . Deci , există și cu astfel încât , acest lucru încalcă condițiile Haar în cazul în care k < n . Deci avem . Chiar dacă înseamnă reindexare, le luăm în ordine crescătoare . În condițiile lui Haar, ca și în lemă, toate sunt diferite de zero. Prin urmare, aplicăm lema și alternanța semnelor. Deoarece sunt pozitive, semnele alternează. Prin urmare, aceasta încheie dovada. {r(X)X^ | X∈X}{\ displaystyle \ {r (x) {\ hat {x}} \ | \ x \ în X \}}X0,...,Xk∈X{\ displaystyle x_ {0}, \ dots, x_ {k} \ în X}α0,...αk∈[0,1]{\ displaystyle \ alpha _ {0}, \ dots \ alpha _ {k} \ în [0,1]}k≤nu{\ displaystyle k \ leq n}0=∑eu=1kαeur(Xeu)Xeu^{\ displaystyle 0 = \ sum _ {i = 1} ^ {k} \ alpha _ {i} r (x_ {i}) {\ hat {x_ {i}}}}k=nu{\ displaystyle k = n}Xeu{\ displaystyle x_ {i}}la≤X0<⋯<Xnu≤b{\ displaystyle a \ leq x_ {0} <\ cdots <x_ {n} \ leq b}αeur(Xeu){\ displaystyle \ alpha _ {i} r (x_ {i})}αeu{\ displaystyle \ alpha _ {i}}r(Xeu){\ displaystyle r (x_ {i})}

Unicitatea celei mai bune aproximări

Până acum am caracterizat ce este cea mai bună aproximare. Vom arăta acum că cea mai bună aproximare există și este unică.

State

Luați în considerare un sistem Chebyshev. Fie o funcție continuă. Apoi, există o cea mai bună aproximare unică a in . {g1,...,gnu}⊆VS([la,b]){\ displaystyle \ {g_ {1}, \ dots, g_ {n} \} \ subseteq {\ mathcal {C}} ([a, b])}f∈VS([la,b]){\ displaystyle f \ in {\ mathcal {C}} ([a, b])}f{\ displaystyle f}Vect(g1,...,gnu){\ displaystyle {\ textrm {Vect}} (g_ {1}, \ dots, g_ {n})}

Demonstrație

Să începem cu unicitatea. Deci, să presupunem că și sunt cele mai bune aproximări pentru . Deci, avem acest lucru și acest standard este minim. Aur, atunci avem . Deci, este încă o aproximare mai bună. Fie dat de teorema alternanței pentru . Să presupunem că . Deci cel puțin unul dintre cele două nu merită , să spunem chiar dacă înseamnă redenumire , și așa . Avem p{\ displaystyle p}q{\ displaystyle q}f{\ displaystyle f}‖f-p‖∞=‖f-q‖∞{\ displaystyle \ | {fp} \ | _ {\ infty} = \ | {fq} \ | _ {\ infty}}‖f-p+q2‖∞≤‖f-p‖∞{\ displaystyle \ left \ | {f - {\ frac {p + q} {2}}} \ right \ | _ {\ infty} \ leq \ | {fp} \ | _ {\ infty}}r=p+q2{\ displaystyle r = {\ frac {p + q} {2}}}X0<⋯<Xnu{\ displaystyle x_ {0} <\ cdots <x_ {n}}r{\ displaystyle r}p(Xeu)≠q(Xeu){\ displaystyle p (x_ {i}) \ neq q (x_ {i})}r(Xeu){\ displaystyle r (x_ {i})}q(Xeu){\ displaystyle q (x_ {i})}|f(Xeu)-q(Xeu)|<‖f-r‖∞{\ displaystyle | f (x_ {i}) - q (x_ {i}) | <\ | {fr} \ | _ {\ infty}}

‖f-r‖∞=|f(Xeu)-r(Xeu)|≤12|f(Xeu)-p(Xeu)|+12|f(Xeu)-q(Xeu)|<‖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}}. Aceasta este o prostie. Deci . Deci, cu zerouri distincte. Deci, prin condițiile lui Haar, obținem că este identic zero și, prin urmare, asta . Deci avem unicitate. r(Xeu)=p(Xeu)=q(Xeu){\ displaystyle r (x_ {i}) = p (x_ {i}) = q (x_ {i})}p-q{\ displaystyle pq}nu+1{\ displaystyle n + 1}p=q{\ displaystyle p = q}

Să trecem acum la demonstrația existenței. Luați în considerare . Acest set este clar închis și limitat. Nu este vid, deoarece funcția nulă este în și este de dimensiune finită. La fel este compact. Astfel, fiind continuu , atinge un minim acolo, să zicem în . Acum, dacă este cea mai bună aproximare a atunci prin inegalitate triunghiulară. Deci . Deci este o aproximare mult mai bună pentru . F={p∈Vect(g1,...,gnu) | ‖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,...,gnu){\ 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 \ în F}p∗{\ displaystyle p ^ {*}}f{\ displaystyle f}

Vezi și tu

• Dezvoltare limitată
• Algoritmul lui Remez
• Jackson inegal  (ro)
• Seria Fourier generalizată

• Acest articol este preluat parțial sau în totalitate din articolul intitulat „  Teoria aproximării / demonstrații  ” (vezi lista autorilor ) .

Surse

1. (în) CHENEY EW, Introducere în teoria aproximării ,1966
2. (în) POWEL MJD, teoria și metodele de aproximare , Univetrsity Cambridge Press,nouăsprezece optzeci și unu

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