Brzina konvergencije sljedova i funkcija, oznake veliki \(O\) i mali \(o\)

Konvergentni sljedovi

Kada pišemo da je \(\lim_{n\to\infty}a_n=a\), prirodno je pitati se kojemo brzinom slijed (ili niz) realnih brojeva \((a_n)_{n\ge1}\) konvergira prema \(a\).

To je isto što i pitati se kojom brzinom razlika \(|a_n-a|\) teži k nuli kada \(n\to\infty\). Na primjer, da li početni slijed  \((a_n)_{n\ge1}\) teži k broju \(a\)

  • brzinom \(1/\log n\) (tj. iznimno sporo - logaritamskom brzinom), tj. \(|a_n-a|\le C/\log n\)
  • brzinom \(1/n\) (tj. vrlo sporo - linearnom brzinom),  tj. \(|a_n-a|\le C/n\)
  • brzinom \(1/n^2\) (kvadratnom brzinom),  tj. \(|a_n-a|\le C/n^2\)
  • brzinom  \(1/2^n\) (eksponencijalnom brzinom s bazom 2),  tj. \(|a_n-a|\le C/2^n\)
  • brzinom \(1/10^n\) (eksponencijalnom brzinom s bazom 10),  tj. \(|a_n-a|\le C/10^n\)
  • brzinom \(10^n/n!\) (skoro faktorijelnom brzinom), tj. \(|a_n-a|\le C\cdot 10^n/n!\)
  • brzinom \(1/n!\) (faktorijelnom brzinom),  tj. \(|a_n-a|\le C/n!\).

Točnije, trebali bismo govoriti o brzini barem naznačenog iznosa. Kada bismo na primjer imali i dolnje međe, na pr.  \(B/n^2\le |a_n-a|\le C/n^2\) za neke pozitivne brojeve \(A\) i \(B\), onda bi \(a_n\) konvergirao prema \(a\) (kad \(n\to\infty\)) točno kvadratnom brzinom (a ne samo barem kvadratnom brzinom).

Želimo li  neki zadani slijed \((b_n)\) usporediti s nekim drugim, po mogućnosti jednostavnijim slijedom \((a_n)\) pozitivnih realnih brojeva, onda pišemo

  • \(b_n=O(a_n)\) kada \(n\to\infty\), ako postoji pozitivna konstanta \(C\) takva da je \(|b_n|\le Ca_n\). Drugim riječima, kvocijent  \(|b_n|/a_n\) je omeđen u ovisnosti \(n\). Slijed \(b_n\) je ne neki način "dominiran" s \(a_n\).To će biti slučaj ako na primjer postoji \(\lim_{n\to\infty}|b_n|/a_n\). Oznaku \(O(a_n)\) čitamo "veliki \(O \) od \(a_n\)".
  • \(b_n=o(a_n)\) kada \(n\to\infty\) ako vrijedi \(\lim_{n\to\infty}|b_n|/a_n=0\). Oznaku \(o(a_n)\) čitamo "mali \(o\) od \(a_n\)". Drugim riječima, za svaki pozitivan realan broj \(\varepsilon\) postoji prirodan broj \(n_0\ge1\) tako da za sve \(n\ge n_0\) vrijedi \(b_n=\varepsilon a_n\) .

 

Na primjer,

  • \(\frac{n^2+10}{n^3+n^2+3}=O(1/n)\) kada \(n\to\infty\).
  • \(\frac{\sin(1/n)}n=o(1/n)\) kada \(n\to\infty\). Štoviše,  vrijedi
  • \(\frac{\sin(1/n)}n=O(1/n^2)\) kada \(n\to\infty\).
  • \(n^{-1}+n^{-1/2}=O(n^{-1/2})\)  kada \(n\to\infty\).
  • \(n^{-1/2}+n^{-1/3}=O(n^{-1/3})\)  kada \(n\to\infty\).

 

Što znači oznaka \(a_n=O(1)\) kada \(n\to\infty\)? U ovom slučaju slijed \(a_n\) uspoređujemo sa slijedom koji je za sve \(n\) jednak \(1\). Dakle \(|a_n|\le C\cdot1=C\), a to znači da je slijed \(a_n\) omeđen.

Što znači oznaka \(a_n=o(1)\) kada \(n\to\infty\)? U ovom slučaju slijed \(a_n\) opet uspoređujemo sa slijedom koji je za sve \(n\) jednak \(1\). Dakle \(\lim_{n\to\infty}|a_n|/1=0\), tj. \(\lim_{n\to\infty}a_n=0\).

 

Sljedeći primjer je puno interesantniji. Znamo da je \(\lim_{n\to\infty}\Big(1+\frac1n\Big)^n=\mathrm e\). Kojom brzinom slijed \(\Big(1+\frac1n\Big)^n\) konvergira prema broju \(\mathrm e\approx 2.718\)? Pokazuje se da je ta brzina iznenađujuće spora, samo reda \(1/n\), tj.

$$\mathrm e-\Big(1+\frac1n\Big)^n=O(1/n)\quad\mbox{kada \(n\to\infty\).}$$

Drugim riječima,

$$\Big(1+\frac1n\Big)^n=e-O(1/n)\quad\mbox{kada \(n\to\infty\).}$$

Još točnije, dvostrukom primjenom l'Hospitalova pravila dobiva se da je

$$\lim_{n\to\infty}\frac{\mathrm e-\Big(1+\frac1n\Big)^n}{\frac1n}=\frac{\mathrm e}2.$$

Dokaz ove tvrdnje možete vidjeti u Poglavlju 9 (Dodatak na str. 29) iz Matan 1, ili opširnije u članku Željka Hanjša i D.Ž.

 

Broj \(\mathrm e\) se može puno bolje aproksimirati ovakvim slijedom racionalnih brojeva:

$$s_n=\sum_{k=0}^n\frac{1}{k!}=1+1+\frac1{2!}+\dots+\frac1{n!}.$$

Putem McLaurinove formule, pokazuje se da je

$$0<\mathrm e-s_n\le\frac3{(n+1)!},$$

tj. \(s_n=\mathrm e-O(1/(n+1)!)\) kada kada \(n\to\infty\),.

Zaključujemo da je

$$\sum_{k=0}^n\frac{1}{k!}=\mathrm e-O\Big(\frac1{(n+1)!}\Big)\quad\mbox{kada \(n\to\infty\),}$$

jer u Lagrangeovom \(n\)-tom ostatku \(R_n(x)=\frac{f^{n+1}(c)}{(n+1)!}x^{n+1}\) za MacLaurinov razvoj funkcije \(f(x)=\mathrm e^x\) imamo \(f^{n+1}(c)=e^c\le e\le3\), gdje je \(c\in(0,1)\). Ovdje stavljamo naravno \(x=1\).

Oznake veliki \(O\) i mali \(o\) uveo je Edmund Landau (1877.-1936.).

Znamo da za bilo koju pozitivnu bazu \(a\) slijed \(\frac{a^{n}}{n!}\) konvergira prema nuli kad \(n\to\infty\), ali pitamo se - kojom brzinom?

Pokazat ćemo da je ta brzina skoro faktorijelna. Točnije, za svaki, koliko god mali pozitivan realan broj \(\varepsilon\) postoji pozitivna realna konstanta \(C=C(\varepsilon,a)\) (ovisna o \(\varepsilon\) i \(a\)), takva da za sve prirodne brojeve \(n\) vrijedi

$$\frac{a^n}{n!}\le\frac{C}{(n!)^{1-\varepsilon}}.$$

To se vidi ovako:

$$\frac{a^n}{n!}=\frac{a^n}{(n!)^\varepsilon}\cdot\frac1{(n!)^{1-\varepsilon}}\le C\frac1{(n!)^{1-\varepsilon}}$$

Zadnja nejednakost se dobiva iz činjenice što je slijed \(\frac{a^n}{(n!)^\varepsilon}\) omeđen. Točnije, do nekog broja \(n_0=n_0(\varepsilon)\) on je rastući, a počevši od njega padajuć (a onda nije teško vidjeti da konvergira prema nuli). Ovakva vrsta monotonosti se lako vidi kada podijelimo \((n+1)\)-vi član tog slijeda s \(n\)-tim.

Na sličan način pokazuje se da za bilo koju bazu \(a>1\) vrijedi da za svaki, koliko god mali pozitivan realan broj \(\varepsilon\) postoji konstanta \(C=C(\varepsilon,a)\) (ovisna o \(\varepsilon\) i o \(a\)) takva da za sve prirodne brojeve \(n\) vrijedi

$$\frac{a^n}{n!}\le \frac{C}{(n!)^{1-\varepsilon}},$$

tj. $$\frac{a^n}{n!}=O\Big(\frac1{(n!)^{1-\varepsilon}}\Big)\quad\mbox{kada \(n\to\infty\).}$$

Iz tog razloga kažemo da slijed \(\frac{a^n}{n!}\) konvergira prema nuli skoro faktorijelnom brzinom, kad  \(n\to\infty\).

A što je u slučaju kada je \(0<a<1\)? Zbog \(\frac{a^n}{n!}=a^n\cdot\frac{1}{n!}\), slijed \(\frac{a^n}{n!}\) konvergira prema nuli još brže nego faktorijelnom brzinom, jer u tom slučaju \(a^n\to0\) kad \(n\to\infty\).

 

Sljedovi koji teže u \(+\infty\)

Oznake \(|b_n|=O(a_n)\) i \(|b_n|=o(a_n)\) kada \(n\to\infty\) koristim potpuno analogno i u situaciji kada sljedovi \(|b_n|\) i \(a_n\) divergiraju u \(+\infty\) (umjesto da konvergiraju u nulu). 

Radi jednostavnosti, gledamo samo sljedove pozitivnih brojeva. Na primjer, slijed  \((a_n)_{n\ge1}\) teži prema \(+\infty\) najviše

  • brzinom \(\log n\) (tj. iznimno sporo - logaritamskom brzinom), tj. \(a_n\le C\cdot\log n\)
  • brzinom \(n\) (tj. vrlo sporo - linearnom brzinom),  tj. \(a_n\le C\cdot n\)
  • brzinom \(n^2\) (kvadratnom brzinom),  tj. \(a_n\le C\cdot n^2\)
  • brzinom  \(2^n\) (eksponencijalnom brzinom s bazom 2),  tj. \(a_n\le C\cdot 2^n\)
  • brzinom \(10^n\) (eksponencijalnom brzinom s bazom 10),  tj. \(a_n\le C\cdot 10^n\)
  • brzinom \(n!/10^n\) (skoro faktorijelnom brzinom), tj. \(a_n\le C\cdot n!/10^n\)
  • brzinom \(n!\) (faktorijelnom brzinom),  tj. \(a_n\le C\cdot n!\).

Kada bismo imali i dolnje međe, na pr.  \(B\cdot n^2\le a_n\le C\cdot n^2\) za neke pozitivne brojeve \(A\) i \(B\), onda bi \(a_n\) konvergirao prema \(+\infty\) (kad \(n\to\infty\)) točno kvadratnom brzinom (a ne samo barem kvadratnom brzinom).

Ako su \(a_n\) i \(a_n\) sljedovi s pozitivnim članovima takvi da je \(b_n=O(a_n)\) i \(a_n=O(b_n)\), onda pišemo da \(a_n\simeq b_n\) (tj. oba slijeda imaju isto asimptotsko ponšanje). U uporabi je i oznaka \(a_n\asymp b_n\).

Na primjer, 

  • \(n^5+n^4 +5=O(n^5)\) kada \(n\to\infty\), štoviše, \(n^5+n^4 +5\simeq n^5\).
  • \(\frac{n^5+n^4 +5}{n^3+4}=O(n^2)\)  kada \(n\to\infty\), tj. početni slijed kvocijenata divergira u \(+\infty\) kvadratnom brzinom. Štoviše, \(\frac{n^5+n^4 +5}{n^3+4}\simeq n^2\).
  • \(n+\sqrt n=O(n)\)  kada \(n\to\infty\). Štoviše, \(n+\sqrt n\simeq n\).
  • \(\sqrt n+\sqrt[3] n=O(\sqrt n)\)  kada \(n\to\infty\). Štoviše, \(\sqrt n+\sqrt[3] n\simeq\sqrt n\).

Pokazuje se da slijed čiji je \(n\)-ti član jednak \(1+\frac12+\dots+\frac1n\) (tj. \(n\)-ta parcijalna suma harmonijskog reda) konvergira u \(+\infty\) vrlo sporo kada \(n\to\infty\), samo logaritamskom brzinom:

$$1+\frac12+\dots+\frac1n=O(\ln n)\quad\mbox{kada \(n\to\infty\).}$$

Još bolji je rezultat da 

$$\Big(1+\frac12+\dots+\frac1n\Big)-\ln n\to\gamma\quad\mbox{kada \(n\to\infty\).}$$

Konstanta \(\gamma\) prema kojoj ove razlike konvergiraju zove se Euler-Mascheronijeva konstanta, ili samo Eulerova konstanta. (Njena vrijednost je \(\gamma\approx0.57\). Ne zna se je li broj \(\gamma\) racionalan ili iracionalan.)

Prema tome, \(\big(1+\frac12+\dots+\frac1n\big)-\ln n-\gamma\to0\) kada \(n\to\infty\). Štoviše, može se pokazati da je brzina konvergencije jednaka \(O(1/n)\), tj.

$$\Big(1+\frac12+\dots+\frac1n\Big)-\ln n-\gamma=O(1/n)\quad\mbox{kada \(n\to\infty\).}$$

Drugim riječima,

$$1+\frac12+\dots+\frac1n=\ln n+\gamma+O(1/n)\quad\mbox{kada \(n\to\infty\),}$$

što predstavlja profinjenje činjenice da harmonijski brojevi \(1+\frac12+\dots+\frac1n\) teže u \(+\infty\) logaritamskom brzinom, kada \(n\to\infty\).

 

Oznake veliko \(O\) i mali \(o\) kod konvergencije funkcija

 

Neka je zadana realna funkcija realne varijable \(y=f(x)\), definirana na nekom otvorenom intervalu. Kada pišemo da je \(\lim_{x\to x_0}f(x)=a\), prirodno je pitati se kojomo brzinom funkcija \((y=f(x))\) konvergira prema \(a\) kada \(x\to x_0\).

To je isto što i pitati se kojom brzinom razlika \(|f(x)-a|\) teži k nuli kada \(x\to x_0\). To će svojstvo biti izraženo u ovom obliku: \(|f(x)-a|\) dovoljno mali za sve \(x\in(x_0-\delta,x_0+\delta)\). Na primjer, da zadana funkcija \(y=f(x)\) teži k \(a\), kad  \(x\to x_0\),

  • brzinom \(1/\log \frac1{x-x_0}\) (tj. iznimno sporo - logaritamskom brzinom), tj. \(|f(x)-a|\le C/\log \frac1{x-x_0}\)
  • brzinom \(|x-x_0|\) (tj. vrlo sporo - linearnom brzinom),  tj. \(|f(x)-a|\le C|x-x_0|\)
  • brzinom \((x-x_0)^2\) (kvadratnom brzinom),  tj. \(|f(x)-a|\le C(x-x_0)^2\)
  • brzinom  \(2^{-1/|x-x_0|}\) (eksponencijalnom brzinom s bazom 2),  tj. \(|f(x)-a|\le C\cdot 2^{-1/|x-x_0|}\)
  • brzinom \(10^{-1/|x-x_0|}\) (eksponencijalnom brzinom s bazom 10),  tj. \(|f(x)-a|\le C\cdot 10^{-1/|x-x_0|}\)

Točnije, trebali bismo govoriti o brzini barem naznačenog iznosa. Kada bismo na primjer imali i dolnje međe, na pr.   \(B(x-x_0)^2\le|f(x)-a|\le C(x-x_0)^2\) za neke pozitivne brojeve \(A\) i \(B\), onda bi funkcija \(f(x)\) konvergirala prema \(a\) (kad \(x\to x_0\)) točno kvadratnom brzinom (a ne samo barem kvadratnom brzinom).

Ovdje ne govorimo o eksponencijalnoj brzini konvergenciji funkcije \(y=f(x)\) prema broju \(a\) kada \(x\to x_0\), jer za to je potrebna takozvana gama funkcija \(\Gamma(x)\).

Želimo li  neku funkciju \(y=f(x)\), koja konvergira k nuli kad \(x\to x_0\), usporediti s nekom drugom poznatom pozitivnom realnom funkcijom \((g(x))\) koja također konvergira u nulu kada \(x\to x_0\), onda pišemo

  • \(f(x)=O(g(x))\) kada \(x\to x_0\), ako postoje pozitivne konstante \(C\) i \(\delta\) takva da je \(|f(x)|\le Cg(x)\) za sve \(x\) iz \(\delta\)-okolliša točke \(x_0\). Drugim riječima, kvocijent  \(|f(x)|/g(x)\) je omeđen u ovisnosti o \(x\) iz \(\delta\)-okoliša. Drugim riječima, funkcija \(y=f(x)\) je "dominirana" s \(g(x)\).To će biti slučaj ako na primjer postoji \(\lim_{x\to x_0}|f(x)|/g(x)\). Oznaku \(O(g(x))\) čitamo "veliki \(O\) od \(g(x)\)".
  • \(f(x)=o(g(x))\) kada \(x\to x_0\) ako vrijedi \(\lim_{n\to\infty}|f(x)|/g(x)=0\). Oznaku \(o(g(x))\) čitamo "mali \(o\) od \(g(x)\)". Drugim riječima, za svaki pozitivan realan broj \(\varepsilon\) postoji pozitivan broj \(\delta\) tako da za sve \(x\) iz \(\delta\)-okoliša od \(x_0\) vrijedi \(f(x)=\varepsilon\cdot g(x)\) .

 

Na primjer,

  • \(\frac{x^{-2}+10}{x^{-3}+x^{-2}+3}=O(x)\) kada \(x\to0\).
  • \(x\sin x=o(x)\) kada \(x\to0\). Štoviše,  vrijedi
  • \(x\cdot\sin x=O(x^2)\) kada \(x\to0\).
  • \(x+x^{1/2}=O(x^{1/2})\)  kada \(x\to0^{+}\).
  • \(x^{1/2}+x^{1/3}=O(x^{1/3})\)  kada \(x\to0^{+}\).

 

Što znači oznaka \(f(x)=O(1)\) kada \(x\to a\)? U ovom slučaju funkciju\(f(x)\) uspoređujemo s funkcijom koji je za sve \(x\) iz nekog \(\delta\)-okoliša od \(a\) jednaka \(1\): \(|f(x)\le C\cdot 1=C\), a to znači da je funkcija \(f\) omeđena u nekom \(\delta\)-okolišu od \(a\).

Što znači oznaka \(f(x)=o(1)\) kada \(x\to a\)? U ovom slučaju slijed \(f(x)\) opet uspoređujemo s funkcijom koja je za sve \(x\) iz nekog \(\delta\)-okoliša od \(a\) jednaka \(1\): \(\lim_{x\to a}|f(x)|/1=0\), tj. \(\lim_{x\to a}f(x)=0\).

Sljedeći primjer je puno interesantniji. Znamo da je \(\lim_{x\to0}\Big(1+x\Big)^{1/x}=\mathrm e\). Kojom brzinom funkcija \(\Big(1+x\Big)^{1/x}\) konvergira prema broju \(\mathrm e\approx 2.718\) kada \(x\to0\)? Pokazuje se da je ta brzina iznenađujuće spora, samo reda \(x\), tj.

$$\mathrm e-\Big(1+x\Big)^{1/x}=O(x),\quad\mbox{kada \(x\to0\).}$$

Još točnije, dvostrukom primjenom l'Hospitalova pravila dobiva se da je

$$\lim_{x\to0}\frac{\mathrm e-\Big(1+x\Big)^{1/x}}{x}=\frac{\mathrm e}2.$$

Dokaz ove tvrdnje možete vidjeti u Poglavlju 9 (Dodatak na str. 29) iz Matan 1, ili opširnije u članku Željka Hanjša i D.Ž.

Na sličan način se tretira i slučaj kada \(x\to\infty\).

Na primjer,

  • \(\sqrt x=o(x)\) kada \(x\to+\infty\), ali \(x=o(\sqrt x)\) kada \(x\to0^+\). Nacrtajte grafove funkcija \(y=x\) i \(y=\sqrt x\) i pogledajte gdje je \(x\le\sqrt x\), a gdje \(\sqrt x\le x\).
  • Stavljajući \(x_n=n\) dobivamo da je \(\sqrt n=o(n)\) kada \(n\to\infty\), a za \(x_n=1/n\) dobivamo \(1/n=o(1/\sqrt n)\).
  • \(\frac{x^{2}+10}{x^{3}+x^{2}+3}=O(1/x)\) kada \(x\to\infty\).
  • \(\frac{\sin (1/x)}x=o(x^{-1})\) kada \(x\to\infty\). Štoviše,  vrijedi
  • \(\frac{\sin (1/x)}x=O(x^{-2})\) kada \(x\to\infty\).
  • \(x+x^{1/2}=O(x)\)  kada \(x\to+\infty\).
  • \(x^{1/2}+x^{1/3}=O(x^{1/2})\)  kada \(x\to+\infty\).

Na temelju MacLaurinove formule znamo da za bilo koji prirodan broj vrijedi

$$e^x=1+x+\frac{x^2}{2!}+\dots+\frac{x^n}{n!}+\frac1{(n+1)!}O(x^{n+1})$$

za \(x\)-ove iz bilo kojeg omeđenog intervala \([-a,a]\). Zadnji član predstavlja ostatak, a konstanta \(C\) koja se pojavljuje u definiciji od \(O(x^{n+1})\) ovisi samo o \(a\).

 

Znamo da za svaki prirodan broj \(n\) vrijedi \(x^n=o(e^x)\) kada \(x\to+\infty\), jer je \(\lim_{x\to+\infty}\frac{x^n}{e^x}=0\).

Na temelju toga nije teško vidjeti da za svaki prirodan broj \(n\) vrijedi

$$\lim_{x\to0^+}\frac{e^{-1/x}}{x^n}=\lim_{x\to0^+}\frac{(1/x)^n}{e^{1/x}}=\lim_{t\to+\infty}\frac{t^n}{e^t}=0,$$

Gdje se zadnja jednakost dobiva \(n\)-strukom primjenom l'Hospitalova pravila. Dakle,  za svaki prirodan broj \(n\) vrijedi

$$e^{-1/x}=o(x^n)\quad\mbox{kada}\quad x\to0^+.$$

Iz ovoga se može zaključiti da funkcija \(f:\mathbb R\to\mathbb R\) definirana sa \(f(x)=0\) za \(x\le0\) i \(f(x)=e^{-1/x}\) za \(x>0\) trne (tj. teži k nuli) jako brzo kada \(x\to0^+\). Izravnim računom se dobiva da \(f\)  ima sve derivacije, a sve te derivacije izračunate u nuli jednake su nula, tj. imaju  svojstvo da je \(f^{(n)}(0)=0\) za sve \(n\). Ovaj primjer pokazuje da na funkciju \(f\) nije primijenjiva MacLaurinova formula, tj. za nju ne vrijedi razvoj \(f(x)=\sum_{k=0}^{\infty}\frac{f^{k}(0)}{k!}x^k\)  (desna strana jednakosti jednaka je identički nula, a lijeva strana nije).

Funkcije sa svojstvom da sve njene derivacije izračunate u nekoj točki iščezavaju, zovemo plosnatim funkcijama. (Engleski termin je flat function.)