Estimarea asimptotică

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Atunci când două succesiuni sunt ambele infinitesimale sau ambele sunt utile pentru a putea stabili o comparație între ele pentru a înțelege care dintre cele două corturi mai repede la 0 sau infinit. Acest articol se referă la studiul estimărilor asimptotice pentru succesiune. Operații similare se pot face pentru funcții reale ale unei variabile , unde în loc de infinit poate fi orice punct de acumulare comun ambelor funcții.

Ordinele infinitului

O functie Spune infinit în dacă limita lui este infinită la tensiune la . În simboluri, dacă

De exemplu este infinit în Și este infinit în .

O secvență (care poate fi considerată ca o funcție definită pe numere naturale) se numește infinită dacă limita sa este infinită la tensiune la nesfârșit. În simboluri: dacă este o succesiune de numere reale, . Cu toate acestea, nu tot infinitul este identic unul cu celălalt: există de fapt într-o ordine a infinitului, care depinde de tipul de performanță a funcției până la infinit. Iată câteva tipuri de infinit plasate în ordine crescătoare: , Și sunt orice numere mai mari decât 1, în timp ce este indicele succesiunii.

Notă: Semnul Ar trebui înțeles în sensul „ sau mic” .

Alte exemple

Iată câteva exemple de ordine ale infinitului referitoare la funcții, unde indică ordinea variabilei care are tendința de :

Ordine de infinitesimal

O functie se spune la infinitesimal dacă limita sa este a tinde spre la . În simboluri, dacă . De exemplu și sunt infinitezimale în (primul, de asemenea, în ).

O succesiune se spune infinitesimal atunci când limita sa este zero pentru a căuta la nesfârșit:

.

Ca și în cazul infinitivelor, există secvențe care tind să zero mai repede decât altele; luând reciprocul secvenței inegalităților de mai sus și schimbând în aveți tabelul corespunzător

Notă: ordinea infinitesimalului Este mai mare decât cea a , De vreme ce acesta din urmă tinde la zero mai încet.

Alte tipuri de limite

Iată câteva exemple de ordine de funcții infinitezimale:

Secvențe asimptotice

Dă două secvențe Și Se spune că sunt asimptotice sau echivalente asimptotic și se notează prin notație de sine

(Evident, trebuie presupus că există un astfel încât ).

În acest caz, este posibil să se creeze lanțuri de relații asimptotice:

O expresie constând din produs sau coeficient din mai mulți factori poate fi estimată factor cu factor:

Relația este o relație de echivalență , deoarece aplică proprietăți reflexive , simetrice și tranzitive relației operatorului.

Reguli de operare

Comparații între infinite și infinitesimale

Lasa-i sa fie Și două secvențe infinite. Pentru limita raportului că dacă noi Este egal cu:

  • :
este o infinitate de ordine mai mică decât
  • :
Și sunt infinite de același ordin
  • :
este o infinitate de ordin superior decât
  • nu exista:
Și nu sunt comparabile.

Implicațiile inverse mai dețin: dacă domină atunci limita este infinită și așa mai departe.

Același raționament poate fi repetat și pentru infinitesimale. Lasa-i sa fie Și două secvențe infinitesimale. Pentru limita raportului că dacă noi Este egal cu:

  • :
este un infinitesimal de ordin superior decât
  • :
Și sunt infinitezimale de aceeași ordine
  • :
este un infinitesimal de ordine mai mic decât
  • nu exista:
Și nu sunt comparabile.

Principiul substituirii infinitelor

Lasa-i sa fie Și doi infinitivi. La calcularea limitei raportului pot fi adăugate sau eliminate în numărător și numitorul infinitului care sunt de ordin inferior, conform a ceea ce am văzut în paragraful anterior.

De fapt, de exemplu:

Principiul de substituție a infinitesimalelor

Lasa-i sa fie , două secvențe infinitesimale. În calcularea limitei raportului puteți fi adăugat sau eliminat, într-o sumă de infinitesimal, al cărui numărător și numitorul sunt infinitesimali de ordin superior, în conformitate cu ceea ce am văzut în paragraful anterior.

Se obține astfel următoarea ecuație, utilă pentru rezolvarea problemelor cu limite nedeterminate:

De exemplu:

Principiul de substituție a echivalenților infinitesimali

Lasa-i sa fie , două funcții infinitesimale. Pentru limita relației merita

dacă se dovedește Și , adică dacă numeratorii și numitorii sunt funcții echivalente asimptotic.

De exemplu, a fi :

Expresii asimptotice

În evaluarea comportamentului asimptotic al unui algoritm suntem introduși în relațiile dintre secvențele numerice care au devenit uzuale. Aceste notații pot fi folosite și pentru funcții reale, cu specificarea valorii domeniului către care tinde variabila, care poate să nu fie .

Schema generală

Definițiile pe care le vom introduce mai jos sunt multe și la prima vedere pot părea confuze sau poate fi obositor să le amintim pe toate împreună și să le comparăm între ele. Din acest motiv, adică pentru a oferi o imagine de ansamblu care este și de ajutor mnemonic, înainte de a trece la definițiile riguroase și specifice, vom ilustra într-un mod discursiv schema generală pe care se bazează toate aceste concepte.

Aproape toate definițiile pe care urmează să le introducem au următoarea structură:

Să spunem succesiunea e o a succesiunii , iar noi scriem

dacă și numai dacă:

În paranteze pătrate am specificat părțile definiției care variază din când în când. În loc de [cuantificator] putem obține cele două cuantificatoare și , in timp ce este o relație de ordine și poate fi sau . Prin urmare, avem doi parametri, fiecare dintre aceștia putând asuma două valori diferite, astfel încât definițiile posibile vor fi patru:

Pentru a distinge aceste patru cazuri, simbolul trebuie, de asemenea care definește relația dintre Și poate presupune patru valori diferite, definite într-un fel de doi parametri: unul care definește cuantificatorul și celălalt care definește relația de ordine.

Aceste simboluri sunt după cum urmează:

  • („O grozavă”) / („sau mic”),
  • („omega mare”) / („omega mic”).

După cum puteți vedea, acestea sunt de fapt patru simboluri definite de doi parametri:

  • Greacă latină
  • micul Mare

Dintre acești doi parametri, primul, adică „latină / greacă”, este utilizat pentru a specifica relația de ordine, conform următoarei asocieri:

  • Latin:
  • Greacă:

în timp ce al doilea, care este „mic / mare”, este utilizat pentru a specifica cuantificatorul, în conformitate cu următoarea asociere:

  • mic:
  • Grozav:

Aceste asociații pot părea decisiv contraintuitive. De exemplu, ar părea mai util să asociați „mic / mare” la relațiile de ordine, astfel încât „mic” să însemne „mai mic” (adică ) și „mare” înseamnă „mai mare (adică ). În schimb, pentru a reda relația de ordine folosim parametrul ciudat pe care l-am definit „latină / greacă”.

Toate aceste ciudățenii aparente sunt rezolvate imediat de îndată ce se face un pic de muncă "filologică". În special, este important să reținem că inițial ceea ce acum numim „o” era de fapt un „omicron”, adică o altă literă greacă. De fapt, în alfabetul grecesc există două litere corespunzătoare „o” noastre:

  • „o-micron”, care înseamnă „sau mic”
  • „o-mega”, care înseamnă „sau mare”.

Prin urmare, inițial notația indica exact ceea ce intenționăm să indicăm: „micul o” („omicron”) a reprezentat iar „marele o” („omega”) a reprezentat .

În ceea ce privește parametrul pe care până acum l-am indicat cu „mare / mic”, știm bine că acesta este doar un mod colocvial de a face referire la literele „majuscule / mici”.

Deci, dacă ne întoarcem la utilizarea inițială a tuturor acestor simboluri, avem următoarele asociații:

  • „micron” („mic”):
  • „mega” („mare”):
  • „minusculă”:
  • "majuscule":

Întărit de această schemă generală, care poate fi utilă și ca regulă mnemonică, să încercăm să scriem, de exemplu, definiția următoarei expresii:

Trebuie să spunem că este un „o-micron” capital al . Ne amintim că:

  • „micron” înseamnă „mai mic”, adică ;
  • „majusculă” înseamnă: (Cel puțin unul) astfel încât...

Iată definiția căutată:

Să spunem asta dacă și numai dacă:

În cele din urmă, suntem interesați să cunoaștem implicațiile dintre toate aceste relații. Aceste implicații pot fi extrase imediat din următoarele considerații:

1) Amintindu-mi că, în general:

asa de este un "omicron" (adică "mai mic") decât dacă și numai dacă este un "omega" (adică "mai mare") decât :

2) Dacă o relație este adevărată apoi în special un anumit asta te mulțumește. Deci, dacă o succesiune este o „minusculă” a secvenței atunci este și „capital” al acestuia:

Acest lucru poate fi exprimat și spunând că setul „minuscule” al unei anumite funcții este conținut în setul „majuscule” al acelei funcții și acest lucru se aplică și ca regulă mnemonică pentru parametrul „majusculă / minusculă”.

Sau mare

Pictogramă lupă mgx2.svg Același subiect în detaliu: Big-O .

Lasa-i sa fie Și două funcții definite pe la valori în .

Se spune că sau este o mare , în simboluri

de sine .

Se mai spune că are un ordin de mărime mai mic sau egal cu cel al , aceasta este funcția domină .

Dacă succesiunea are valori cu siguranță diferite de zero, o condiție echivalentă, care exploatează limita superioară , este că ambele .

Exemple

Sau mici

Se spune că Este o o mică , în simboluri

de sine

Omega mare

Se spune că Omega este un minunat , în simboluri

de sine .

Se mai spune că are un ordin de mărime mai mare sau egal cu cel al , sau asta este dominat de .

Folosind notația limitei inferioare , o condiție echivalentă este aceea că ambele

Omega mic

Se spune că Omega este un mic , în simboluri

de sine

Theta

Și se spune că au același ordin de mărime, în simboluri

de sine .

Folosind limitele superioare și inferioare, această condiție poate fi declarată ca ->

Proprietățile expresiilor asimptotice

Următoarele proprietăți se aplică expresiilor asimptotice:

Proprietăți de bază

  1. .
  2. .
  3. .
  4. .

Implicații

  1. .
    acesta este: .
  2. .

Sume de funcții

  1. .
  2. .
  3. .
    acesta este .
  4. .
  5. .

Produse

  1. acesta este .
  2. .
  3. .

În plus față de acestea, în cadrul fiecăreia dintre notațiile care merită proprietatea tranzitivă , adică, de exemplu, dacă Și asa de .

Reflexivitatea și tranzitivitatea Acestea implică faptul că este o precomandă , a cărei relație de echivalență este exact asociată . De fapt din definiția , este exact .

De asemenea, dacă este o constantă, este cu siguranță dacă și numai dacă și în mod similar este cu siguranță dacă și numai dacă .

Probleme de notare

Afirmația este o o mare de se scrie de obicei ca . Aceasta este o ușoară utilizare greșită a notației, deoarece egalitatea celor două funcții nu este afirmată. În plus, proprietatea nu este simetrică:

.

Din acest motiv, unii autori preferă notația setului și scriu , gindind despre în ceea ce privește clasa tuturor funcțiilor dominate de Sau utilizați o notație introdusă de Hardy , care este următoarea:

Și .

Grafice

Exemplu de notare big-O: f (x) = O (g (x)), există c> 0 și o valoare x 0 astfel încât în ​​dreapta lui x 0 avem f (x) <cg (x)
Notare exemplu Ω-mare: f (x) = Ω (g (x)), există c> 0 și o valoare x 0 astfel încât în ​​dreapta lui x 0 avem f (x)> cg (x)

Elemente conexe

Matematica Portale Matematica : accedi alle voci di Wikipedia che trattano di matematica