11. Pozostałe informacje o ciągach

Treści kształcenia. Ciągi liczbowe: granice właściwe i niewłaściwe. Zbieżność i arytmetyka granic. Ciągi monotoniczne. Podciągi, punkty skupienia i tw. Bolzano-Weierstrassa. Warunek Cauchy’ego i zupełność. Pozostałe informacje o zbieżności ciągów. Symbole Landaua i obliczanie granic z nimi związanych.

Efekty kształcenia. Student potrafi wprawnie posługiwać się pojęciem granicy ciągu oraz sprawdzać wykonalność obliczeń na komputerze. Zna podstawowe metody obliczania granic.

Dowiedzieliśmy się już, co to jest granica ciągu i zobaczyliśmy, jak w niektórych sytuacjach można ją obliczyć. Teraz poznamy twierdzenia pozwalające stwierdzić, że dany ciąg jest zbieżny. Później (omawiając ciągi rekurencyjne) zobaczymy zastosowania poznanej teorii: na przykład potrafili będziemy napisać algorytmy pozwalające przybliżać wartości pierwiastka z dowolną dokładnością.

Twierdzenie o ciągu monotonicznym i ograniczonym¶

Twierdzenie

Niech $(a_n)$ będzie ciągiem monotonicznym i ograniczonym. Wtedy $(a_n)$ jest ciągiem zbieżnym.

Uwagi:

Wiadomo, że każdy ciąg zbieżny jest ciągiem ograniczonym. Nie musi być jednak ciągiem monotonicznym. Dla przykładu: ciąg $\left(\frac{(-1)^n}{n}\right)$ jest zbieżny, ale nie jest monotoniczny.

Niech $(a_n)$ będzie ciągiem monotonicznym i ograniczonym. Jeśli ciąg jest niemalejący, to jego granicą jest kres górny zbioru $\{a_n:n\in\mathbb{N}\}$ . Jeśli ciąg jest nierosnący, to jego granicą jest kres dolny zbioru $\{a_n:n\in\mathbb{N}\}$ . Obserwacja ta niestety nie daje efektywnego sposobu na obliczenie granicy ciągu.

Przykład 1.¶

Podczas omawiania ograniczoności i monotoniczności ciągów zobaczyliśmy, że ciąg $(a_n)$ określony rekurencyjnie:

a_1= \sqrt{2}, \quad a_{n+1}=\sqrt{2+a_{n}}.

jest ograniczony i rosnący. Zatem na mocy powyższego twierdzenia jest on zbieżny. Niech $g$ oznacza jego granicę. Aby poznać jej wartość, zauważmy, że równość

a_{n+1}=\sqrt{2+a_{n}}

jest prawdziwa dla wszystkich liczb naturalnych.

Ponieważ

\lim_{n\to\infty} a_{n+1}=g \text{ oraz } \lim_{n\to\infty}\sqrt{2+a_{n}}=\sqrt{2+g},

to

g=\sqrt{2+g}.

Stąd $g^2=2+g$ . Rozwiązaniami tego równania są liczby -1 oraz 2. Pierwszą z nich musimy odrzucić, bo wyrazy naszego ciągu są nieujemne. Zatem

\lim_{n\to\infty} a_{n}=2.

Uwaga: więcej tego typu przykładów zobaczymy przy okazji omawiania ciągów rekurencyjnych.

Przykład 2.¶

Niech $(s_n)$ będzie ciągiem danym wzorem

s_n=\sum_{k=1}^n\frac{1}{k^2}.

Oczywiście ciąg $(s_n)$ jest rosnący. Prosty dowód indukcyjny pokazuje, że dla każdego $n\in\mathbb{N}$ mamy

s_n\leq 2-\frac{1}{n}.

Stąd ciąg $(s_n)$ jest ograniczony. Na mocy powyższego twierdzenia otrzymujemy zatem, że jest to ciąg zbieżny.

Uwagi:

Pokazaliśmy tak naprawdę, że szereg $\displaystyle\sum_{k=1}^\infty\frac{1}{k^2}$ jest zbieżny. Co to oznacza, wyjaśni się na kursie z Analizy Matematycznej.

Można pokazać, że $\displaystyle\lim_{n\to\infty} s_n=\frac{\pi^2}{6}$ .

Przykład 1 do samodzielnego rozwiązania¶

Niech $(a_n)$ będzie ciągiem określonym następująco:

a_1=2, a_{n+1}=2-\frac{1}{a_n}.

Stosując indukcję, pokaż, że dla każdego $n\in\mathbb{N}$ mamy $1\leq a_n\leq 2$ .
Pokaż, że ciąg ten jest malejący.
Uzasadnij, że ciąg ten jest zbieżny i oblicz jego granicę.

a = 2
for i in range(1,1000):
    print(a)
    a = 2-1/a

Ciągi Cauchy’ego¶

Definicja¶

Ciąg $(a_n)$ nazywamy ciągiem Cauchy’ego, gdy dla każdego $\varepsilon > 0$ istnieje takie $N$ , że dla każdego $n,m\geq N$ mamy

|a_n-a_m| < \varepsilon.

Uwaga: używając symboli logicznych, można powyższą definicję wyrazić następująco: ciąg $a_n$ jest ciągiem Cauchy’ego, gdy

\forall_{\varepsilon > 0}\exists_{N}\forall_{n,m\geq N} | a_n-a_m | < \varepsilon.

Fakt

Każdy ciąg zbieżny jest ciągiem Cauchy’ego.

Dowód.

Niech $(a_n)$ będzie ciągiem zbieżnym do $g$ i niech $\varepsilon>0$ . Ponieważ $(a_n)$ jest zbieżny do $g$ , to istnieje takie $N$ , że dla $n\geq N$ mamy

|a_n-g| < \frac{\varepsilon}{2}.

Zatem dla każdego $n,m\geq N$ mamy

|a_n-a_m|=|a_n-g+g-a_m|\leq |a_n-g|+|g-a_m| < \frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon.

Czyli $(a_n)$ jest ciągiem Cauchy’ego.

Twierdzenie

Każdy ciąg Cauchy’ego jest ciągiem zbieżnym.

Uwagi:

powyższe twierdzenie mówi, że $\mathbb{R}$ jest przestrzenią metryczną zupełną.

twierdzenie i jego dowód nie podaje “recepty” pozwalającej obliczyć granicę ciągu, pozwala ono jedynie stwierdzić, że ciąg jest zbieżny.

Przykład ciągu, który nie jest ciągiem Cauchy’ego¶

Niech

a_n=(-1)^n.

Wtedy dla każdego $n\in\mathbb{N}$ mamy

|a_{n+1}-a_n|=1.

Zatem ciąg $(a_n)$ nie jest ciągiem Cauchy’ego. Nie jest zatem zbieżny.

Przykład ciągu, który nie jest ciągiem Cauchy’ego¶

Niech $(s_n)$ będzie ciągiem danym wzorem

s_n=\sum_{k=1}^n\frac{1}{k}.

Wtedy dla każdego $n\in\mathbb{N}$

s_{2n}-s_n=\sum_{k=n+1}^{2n}\frac{1}{k} \geq \frac{1}{2}.

Zatem ciąg $s_n$ nie jest ciągiem Cauchy’ego. Ponieważ jest on rosnący, to otrzymujemy, że

\lim_{n\to\infty} s_n=\infty.

Przykład ciągu Cauchy’ego¶

Niech $(s_n)$ będzie ciągiem danym wzorem

s_n=\sum_{k=1}^n\frac{1}{k^2}.

Pokażemy, że jest to ciąg Cauchy’ego.

W tym celu zauważmy, że dla $n > m$ mamy

|s_n-s_m|=\sum_{k=m+1}^{n}\frac{1}{k^2}<\sum_{k=m+1}^n\frac{1}{k(k-1)}= \sum_{k=m+1}^n\left(\frac{1}{k-1}-\frac{1}{k}\right)=\frac{1}{m}-\frac{1}{n} < \frac{1}{m}.

Zatem jeśli $N$ jest takie, że $N > \frac{1}{\varepsilon}$ , to dla $n,m\geq N$ mamy

|s_n-s_m| < \varepsilon.

Przykład 2 do samodzielnego rozwiązania¶

Podzielmy przedział $[a_1,b_1]=[0,1]$ na dwa równe przedziały i oznaczmy jeden z nich przez $[a_2,b_2]$ . Teraz podzielmy przedział $[a_2,b_2]$ na dwa równe przedziały i oznaczmy jeden z nich przez $[a_3,b_3]$ . Kontynuując ten proces, otrzymamy ciąg przedziałów $[a_n,b_n]$ . Uzasadnij, że ciągi $(a_n)$ i $(b_n)$ są zbieżne i pokaż, że ich granice są równe.

Hint:

pokaż, że ciągi $(a_n)$ i $(b_n)$ są ciągami Cauchy’ego. W tym celu oblicz długość przedziału $[a_n,b_n]$ .

Podciągi i punkty skupienia ciągu¶

Widzieliśmy już rozmaite przykłady ciągów. Niektóre z nich okazały się ciągami zbieżnymi. Do analizy tych ciągów, które nie są zbieżne, przydatne są pojęcia podciągu i punktu skupienia ciągu.

Definicja podciągu¶

Niech $(a_n)$ będzie ciągiem liczbowym i niech $(k_n)$ będzie rosnącym ciągiem liczb naturalnych. Ciąg $(a_{k_n})$ nazywamy podciągiem ciągu $(a_n)$ .

Uwaga:

Intuicyjnie rzecz ujmując, podciąg danego ciągu powstaje poprzez skreślenie pewnej (być może nieskończonej) liczby jego wyrazów.

Powinno być jasne, że każdy podciąg ciągu zbieżnego jest ciągiem zbieżnym.

Przykład: Podciągami ciągu $(a_n)$ danego wzorem

a_n=(-1)^n

są na przykład ciągi $a_{2n}$ i $a_{2n+1}$ . Pierwszy z nich przyjmuje stale wartość 1, drugi przyjmuje stale wartość -1.

Definicja punktu skupienia¶

Liczbę rzeczywistą $a$ nazywamy punktem skupienia ciągu $(a_n)$ , gdy istnieje podciąg ciągu $(a_n)$ zbieżny do $a$ .
Mówimy, że $+\infty$ jest punktem skupienia ciągu $(a_n)$ , gdy istnieje podciąg ciągu $(a_n)$ rozbieżny do $+\infty$ .
Mówimy, że $-\infty$ jest punktem skupienia ciągu $(a_n)$ , gdy istnieje podciąg ciągu $(a_n)$ rozbieżny do $-\infty$ .

Przykład

Jedynymi punktami skupienia ciągu $a_n=(-1)^n$ są liczby -1 i 1.

Przykład

Jedynymi punktami skupienia ciągu $a_n=(-1)^nn$ są $-\infty$ i $+\infty$ .

Przykład

Można pokazać, że punktami skupienia ciągu $(\sin n)$ są wszystkie elementy odcinka $[-1,1]$ .

Definicja granicy górnej i dolnej ciągu¶

Granicą górną ciągu $(a_n)$ nazywamy największy z jego punktów skupienia i oznaczamy symbolem $\displaystyle\limsup_{n\to\infty}a_n$ .
Granicą dolną ciągu $(a_n)$ nazywamy najmniejszy z jego punktów skupienia i oznaczamy symbolem $\displaystyle\liminf_{n\to\infty}a_n$ .

Uwagi:

Ciąg $a_n$ jest zbieżny do g wtedy i tylko wtedy, gdy $\displaystyle\liminf_{n\to\infty}a_n=g=\limsup_{n\to\infty}a_n$ .

Przykład

Niech $a_n=(-1)^n$ . Wtedy

\displaystyle\limsup_{n\to\infty}a_n=1

i

\displaystyle\liminf_{n\to\infty}a_n=-1.

Tw. Bolzano-Weierstrassa¶

Poniżej prezentujemy bardzo ważny dla Analizy Matematycznej wynik.

Twierdzenie

Z każdego ograniczonego ciągu liczb rzeczywistych można wyrwać podciąg zbieżny. Innymi słowy każdy ograniczony ciąg liczb rzeczywistych posiada przynajmniej jeden punkt skupienia.

Notacja Landaua¶

Nauczymy się teraz notacji używanej do określania złożoności obliczeniowej algorytmów. W całym tym rozdziale wszystkie pojawiające się funkcje będą funkcjami określonymi na zbiorze liczb naturalnych (a więc ciągami) i o wartościach w zbiorze liczb dodatnich.

Notacja ,,duże O’’¶

Definicja

Mówimy, że $f$ jest co najwyżej rzędu g, gdy istnieje $N > 0$ oraz $c > 0$ takie, że dla $n\geq N$ mamy

f(n)\leq c\cdot g(n).

Piszemy wtedy, że $f(n)\in O(g(n))$ .

Uwaga:

Jeśli $\displaystyle\lim_{n\to\infty} \frac{f(n)}{g(n)} < \infty$ , to $f(n)\in O(g(n))$ .

Notacja ,,małe o’’¶

Definicja

Mówimy, że $f$ jest niższego rzędu niż g, gdy dla każdego $c > 0$ istnieje $N>0$ takie, że dla $n\geq N$ mamy

f(n) < c\cdot g(n).

Piszemy wtedy, że $f(n)\in o(g(n))$ .

Uwaga:

Jeśli $\displaystyle\lim_{n\to\infty} \frac{f(n)}{g(n)}=0$ , to $f(n)\in o(g(n))$ .

Notacja ,, $\Theta$ ’’¶

Definicja

Mówimy, że $f$ jest dokładnie rzędu $g$ , gdy istnieje $N > 0$ oraz $c,d > 0$ takie, że dla $n\geq N$ mamy

c\cdot g(n)\leq f(n) \leq d\cdot g(n).

Piszemy wtedy, że $f(n)\in \Theta(g(n))$ .

Uwaga: Jeśli $\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)}=L$ , gdzie $0 < L < \infty$ , to $f(n)\in \Theta(g(n))$ .

Uwaga:

najczęściej pojawiającą się notacją w informatyce jest notacja ,,duże O’':

$O(\log(n))$ - złożoność logarytmiczna;
$O(n)$ - złożoność liniowa;
$O(n^2)$ - złożoność kwadratowa,
$O(n^k)$ - złożoność wielomianowa
$O(a^n)$ - złożoność wykładnicza

Twierdzenie o ciągu monotonicznym i ograniczonym¶

Przykład 1.¶

Przykład 2.¶

Przykład 1 do samodzielnego rozwiązania¶

Ciągi Cauchy’ego¶

Definicja¶

Przykład ciągu, który nie jest ciągiem Cauchy’ego¶

Przykład ciągu, który nie jest ciągiem Cauchy’ego¶

Przykład ciągu Cauchy’ego¶

Przykład 2 do samodzielnego rozwiązania¶

Podciągi i punkty skupienia ciągu¶

Definicja podciągu¶

Definicja punktu skupienia¶

Definicja granicy górnej i dolnej ciągu¶

Tw. Bolzano-Weierstrassa¶

Notacja Landaua¶

Notacja ,,duże O’’¶

Notacja ,,małe o’’¶

Notacja ,,Θ\ThetaΘ’’¶

Notacja ,, $\Theta$ ’’¶