Brzina konvergencije

Prijava

HrvatskihrEnglishen

Pristupačnost

Veličina slova:A A

Izgled stranice Uobičajen izgled Jednostavni izgled stranice

Kontrast stranice: Normalno Visoki kontrast Inverzni visoki kontrast

Očisti sve

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.)

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