11. Pozostałe informacje o ciągach#

Tresci 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 poznane teorii: na przykład potrafili będziemy napisać algorytmy pozwalące przybliżać wartości pierwiatka 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 nierosnacy, 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}. \]

Rozwiązaniami tego równanania są liczby \(-1\) oraz \(2\). Pierwsza 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 indukcjyjny 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 nastepują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ą definicje wyrazić nastepują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}^{2n}\frac{1}{k} > \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 niech przez \([a_2,b_2]\). Teraz podzielmy przedział \([a_2,b_2]\) na dwa równe przedziały i oznaczmy jeden z niech 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ą wszyskie elementy odcinka \([0,1]\).

Definicja granica 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 Matematyczny wynik.

Twierdzenie

  • Z każdego ograniczonego ciągu liczb rzeczywstych można wyrwać podciąg zbieżny. Innymi słowy każdy ograniczony ciąg liczb rzeczywstych posiada przynjamniej 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 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)}=g > 0\), to \(f(n)\in \Theta(g(n))\).

Uwaga:

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

  • \(O(\log(n))\) - zlożoność logarytmiczna;

  • \(O(n)\) - zlożoność liniowa;

  • \(O(n^2)\) - zlożoność kwadratowa,

  • \(O(n^k)\) - zlożoność wielomianowa

  • \(O(a^n)\) - zlożoność wykładnicza