matematikk.net

Hei.

Har akkurat støtt på en del oppgaver der man ganske aktivt bruker Big-Oh og Little-Oh notasjoner. Dette har jeg egentlig aldri vært borti før, men etter å ha søkt litt på nettet tror jeg at jeg har en noenlunde ok forståelse for dette. Men oppgavene i boken er som regel av såpass høyere vanskelighetsgrad enn de oppgavene jeg finner på nettet, at jeg fremdeles er litt usikker.

I et eksempel i teksteboken har man f.eks. skrevet følgende:

Vi har [tex]x = \eta \psi(\epsilon)[/tex]

[tex]y_{0}(\epsilon,x) = e^{\frac{1}{2}} e^{-\frac{1}{2} \psi(\epsilon)} = e^{\frac{1}{2}} + O(\psi)[/tex]

[tex]y_{1}(\epsilon, x) = A(1 - e^{-\frac{2 \eta \psi}{\epsilon}}) = A + o(1)[/tex]

Agreement is only possible if [tex]A = e^{\frac{1}{2}}[/tex] so finally:

[tex]y \approx y_{0}(\epsilon,x) = e^{\frac{1}{2}} e^{-\frac{x}{2}}[/tex] for [tex]x = O(1)[/tex]

[tex]y \approx y_{1}(\epsilon,x) = e^{\frac{1}{2}}(1 - e^{-\frac{2x}{\epsilon}})[/tex] for [tex]x = O(\epsilon)[/tex]

Jeg forstår egentlig godt fremgangsmåtene i oppgavene, bortsett fra at jeg er usikker på hvorfor man velger de verdiene man gjør for de ulike O-notasjonene. Hvorfor velger man f.eks. Little-Oh i den første y_1 approksimasjonen, og ikke i den andre, osv? Og hvorfor bruker man x = O(1) og x = O([tex]\epsilon[/tex]) i de to siste approksimasjonene? Dersom noen kort kan forklare meg hvorfor man velger akkurat det man velger over, så ville jeg vært meget takknemlig!

krje1980 wrote:
[tex] e^{\frac{1}{2}} e^{-\frac{1}{2} \psi(\epsilon)} = e^{\frac{1}{2}} + O(\psi)[/tex]

[tex]y_{1}(\epsilon, x) = A(1 - e^{-\frac{2 \eta \psi}{\epsilon}}) = A + o(1)[/tex]

Agreement is only possible if [tex]A = e^{\frac{1}{2}}[/tex] so finally:

[tex]y \approx y_{0}(\epsilon,x) = e^{\frac{1}{2}} e^{-\frac{x}{2}}[/tex] for [tex]x = O(1)[/tex]

[tex]y \approx y_{1}(\epsilon,x) = e^{\frac{1}{2}}(1 - e^{-\frac{2x}{\epsilon}})[/tex] for [tex]x = O(\epsilon)[/tex]

Du må se nærmere på definisjonene av stor og liten o.

At f(x)=O(g(x)) når x går mot en verdi a betyr at det fins positive konstanter M og d slik at når |x-a|<d er |f(x)|<M|g(x)|

At f(x)=o(g(x)) betyr at for alle positive konstanter M fins det en [tex]d_M[/tex] slik at når
[tex]|x-a|<d_M[/tex] er |f(x)|<M|g(x)|

Altså vil o(g(x)) implisere O(g(x)), men ikke nødvendigvis motsatt.

For å vise det du nevner kan du i mange tilfeller bruke Taylorrekker til eksponensialfunksjonen og deretter bruke definisjonene av stor og liten o. Det kommer litt an på oppgavene..

Eksempel:

[tex] e^{\frac{1}{2}} e^{-x} =e^{\frac{1}{2}}(1-x+\frac{1}{2!}x^2-\frac{1}{3!}x^3+...)=e^{\frac{1}{2}}+e^{\frac{1}{2}}(-x+\frac{1}{2!}x^2-\frac{1}{3!}x^3+...)[/tex]

Når [tex]|x|<1[/tex] ([tex]x\to 0[/tex]) er

[tex]|-x+\frac{1}{2!}x^2-\frac{1}{3!}x^3+...|<|x|+\frac{1}{2!}|x|+\frac{1}{3!}|x|+...=M|x|[/tex] der [tex]M=\sum_n \frac{1}{n!}[/tex].


Altså er [tex]e^{\frac12}e^{-x}=e^{0.5}+O(x)[/tex] (O(kg(x))=O(g(x) for konstanter k) når x går mot 0.

Takk så mye for hjelpen! Jeg skal se nærmere på dette

OK.

Enda et eksempel:

Å vise at

[tex]Ae^{-x}=o(1)[/tex] når [tex]x \to \infty[/tex] er rimelig åpenbart.

Det vi må vise er at for enhver positiv M fins en d slik at for

[tex]x>d[/tex] er [tex]|Ae^{-x}|<M[/tex].

Takk skal du ha!

Tror jeg begynner å skjønne dette nå, men jeg er fortsatt litt usikker på forskjellen mellom stor og liten O. Har du noen eksempler på uttrykk som er f.eks O(1) og o(1), der forskjellen mellom de to kommer frem? I det siste eksempelet du nenver, kunne vi ikke like greit ha skrevet O(1) heller enn o(1)?

Hva med funksjonen f(x)=1.

Vi har at [tex]f(x)=O(1)[/tex] når [tex]x\to\infty[/tex] (velg M=2 og d=0)


, men

[tex]f(x)\neq o(1)[/tex] når [tex]x\to\infty[/tex]. Velg M=0.5. Da fins det ingen d slik at når x>d er |f(x)|<0.5


Et annet eksempel:

[tex]g(x)=\frac{1}{x}[/tex].

[tex](x\to\infty)[/tex]
g(x)=O(1) (velg d=1 og M=1) og g(x)=o(1) (velg [tex]d=\frac{1}{M}[/tex])


Forskjellen på o(1) og O(1) er altså at o(1) er et strengere krav, men alle funksjoner som er o(1) er O(1). Over har vi et eksempel på en funksjon som er O(1), men som ikke er o(1). Vi kan jo også skrive det som [tex]o(1)\subset O(1)[/tex], som mengder.

Takk igjen! Det begynner å sitte bra nå, men av og til blir jeg forvirret når boken av og til tar utgangspunkt i at funksjoner er O-etellerannet, for så senere og si at x = O-etellerannet. Jeg tror jeg forstår dette helt fint i forhold til å evaluere funksjoner. Men for å ta et kort eksempel fra boken:


Consider

[tex]q(x,\epsilon) = y_{0} + y_{1} = e^{1-x} + e(1 - e^{-x/ \epsilon})[/tex]

If [tex]x = O(1)[/tex], then

[tex]q(x, \epsilon) = e^{1-x} + e + O(\epsilon)[/tex]


Hvofor må vi her påpeke at x = O(1)? Jeg har sittet med Big-Oh/Little-Oh greiene i lang tid nå, og selv om jeg føler at jeg forstår teorien bak det bra (blant annet basert på det du skrev), så synes jeg likevel det fort blir forvirrende og frustrerende. Særlig fordi jeg egentlig forstår alt det andre mht fremgangsmåten i oppgavene forøvrig. Det virker som boken forventer at leseren kan dette, og når jeg ikke har vært borti det før, så klarer jeg liksom ikke å forstå det fullt ut ettersom boken hopper over mellomregningene.

For å vise disse tingene må du gå veien via definisjonene. Skriv først opp eksplisitt hva du må vise.

Ah! Nå tror jeg det gikk et lys opp for meg her!

Dersom [tex]x = O(1)[/tex], så har vi at [tex]\frac{|x|}{1} < A[/tex]. Altså har vi: [tex]|x| < A[/tex], hvor [tex]A[/tex] er en konstant. Da vet vi at x ikke går mot uendelig, og av dette følger det at når [tex]\epsilon \to 0[/tex] så får vi den ønskede approksimasjonen. Hadde derimot x gått mot uendelig, så kunne vi ikke antatt dette. Har jeg forstått dette riktig nå?