14. Rekurencja 3. Zastosowania.#

Treści kształcenia. Ciągi zadane rekurencyjnie w informatyce. Granice ciągów, algorytmy obliczania granic (problem zbieżności). Interpretacja geometryczna (programy), obliczanie granic ciągów rekurencyjnych, postać rekurencyjna a ogólna.

Efekty kształcenia: Student potrafi operować ciągami rekurencyjnymi, badać ich zbieżność i granice. Potrafi określić podstawowe wady i zalety takich ciągów w zastosowaniach informatycznych.

Ciągi rekurencyjne a obliczanie funkcji pierwiastek \(\sqrt{a}\).#

Metoda naiwna (jak to było w szkole…) jest zła: mamy zgadnąć (a komuter w tym nie pomoże…) kwadrat jak największej liczby nie przekarczającej \(a\). To działa ‘’w pamięci’’ np. dla \(\sqrt{10}\), znajdziemy \(3^2 = 9 < 10\), czyli \(3 < \sqrt{3}\) itp. Ale już np. dla

\[\sqrt{125624726}\]

nie jest to dobry algorytm, nie mówiąc np. o obliczeniu tego pierwiastka:

\[\sqrt{1213,86428997}.\]

A na komputerze:

def sqrt5(m:float):
    i=float(0)
    while(i**2 <= m):
        i+=float(1/10)
    x1=i
    for j in range(10):
        x2=m
        x2/=x1
        x2+=x1
        x2/=2
        x1=x2
    return x2

[sqrt5(k) for k in range(1,10)]

[1.0,
 1.414213562373095,
 1.7320508075688772,
 2.0,
 2.23606797749979,
 2.449489742783178,
 2.6457513110645907,
 2.82842712474619,
 3.0]

Lepszym algorytmem było omawiane ujęcie poprzez twierdzenie Cauchy’ego o średnich. Ale to nadal dalekie od optymalności.

Kolejna metoda (rekurencyjna) będzie bazowała na poprzedniej, ale z wykorzystaniem tylko jednego ciągu. Metoda babilońska (Herona) (bazująca na geometrii - pierwiastek jako pole kwadratu o boku \(x\), rozpoczynamy od prostokąta i zmniejszamy różnicę pomiędzy długościami boków korzystając ze średniej arytmetycznej) \(a > 0\):

\[ x_{n+1} = \frac{1}{2} \left( x_n + \frac{a}{x_n} \right) \ , \ x_1 = \frac{a}{2} . \]

Jak widać: wyraz \(x_{n+1}\) jest tu średnią arytmetyczną liczb \(x_n\) oraz \(\frac{a}{x_n}\).

W pętli while:

def sqrt9(fg:float):
    n=fg/float(2)
    lstX=float(0)
    while n!=lstX:
        lstX = n
        n = (n + fg/n)/float(2)
    return n

[sqrt9(k) for k in range(1,10)]

[1.0,
 1.414213562373095,
 1.7320508075688772,
 2.0,
 2.23606797749979,
 2.449489742783178,
 2.6457513110645907,
 2.82842712474619,
 3.0]

Albo w pętli for:

def sqrt13(n:int):
    a = float(n)
    x=float(1)
    for i in range(n):
        x = float(1/2)*(x+a / x)
    return x

[sqrt13(k) for k in range(1,10)]

[1.0,
 1.4166666666666665,
 1.7321428571428572,
 2.0000000929222947,
 2.236067977499978,
 2.449489742783178,
 2.6457513110645907,
 2.82842712474619,
 3.0]

A to w Python (interaktywne):

def newtonsqrt(n):
    approx=0.5*n
    better=0.5*(approx+n/approx)
    while better!=approx:
        approx=better
        better=0.5*(approx+n/approx)
    return approx
print(newtonsqrt(193792))

440.218127750323

def newton_method(number, number_iters = 500):

    a = float(number) 

    for i in range(number_iters): 

        number = 0.5 * (number + a / number) 

    return number

a=int(input("Podaj pierwsza liczba:"))

b=int(input("Podaj druga liczba:"))

print("Pierwiastek z pierwszej liczby to:",newton_method(a))

print("Pierwiastek z drugiej liczby to:",newton_method(b))

Podaj pierwsza liczba: 154
Podaj druga liczba: 4579

Pierwiastek z pierwszej liczby to: 12.4096736459909
Pierwiastek z drugiej liczby to: 67.6683086828687

Dla porównania predefiniowana funkcja z modułu math Pythona (dla zainteresowanych - poszukać jakim algorytmem jest obliczana). Wartości do porównania…

import math
math.sqrt(4579)

67.66830868286867

Zadanie. Sprawdzić, że ten ciąg jest zbieżny do \(\sqrt{a}\). A jak być może pamiętamy: to (na ogół liczba niewymierna, a więc wymaga obliczeń na komputerze. A to czego jeszcze nie mówiliśmy: funkcja pierwiastkowa sprawi pewne problemy obliczeniowe i warto opracować specjalne algorytmy - zwłaszcza za pomocą ciągów rekurencyjnych!

Rozwiązanie. Zbadamy oczywiście ograniczoność i montoniczność tego ciągu. Zastanowimy się skąd ten algorytm. To proste: bierzemy prostokąt o polu \(a\) i bokach \(x_n\) oraz \(\frac{a}{x_n}\). Algorym zakłada dążenie do uzyskania kwadratu, a wówczas jego bok ma długość \(\sqrt{a}\).

…. rysunek - może być na tablicy ….

Mamy więc dwie liczby: \(x_n\) i \( \frac{a}{x_n}\), a (jak już przypominaliśmy) ich średnia arytmetyczna, czyli \(x_{n+1}\) jest ‘’pomiędzy nimi’’. Rozpatrzmy przypadek \(x_1 < \frac{a}{x_1}\) (odwrotny przypadek jest analogiczny - samodzielnie!). Wtedy

\[ x_1 \leq x_2 \leq x_3 \leq \ldots \leq \frac{a}{x_3} \leq \frac{a}{x_2} \leq \frac{a}{x_1} , \]

czyli ciąg \((x_n)\) jest rosnący i ograniczony z góry. Jest więc zbieżny (oznaczmy tę granicę przez \(x\)).

Tak jak we wcześniejszych przykładach przechodzimy do granicy z \(n \to \infty\) we wzorze rekurencyjnym i uzyskujemy

\[ x = \frac{1}{2} \left( x + \frac{a}{x} \right) \]

Rozwiązujemy równanie uzyskując

\[ x^2 = a \quad \Rightarrow \quad x = \sqrt{a} . \]

Wyjaśnienie źródeł pomysłu i komentarz do drugiego przypadku - pozostawionego do samodzielnego uzupełnienia:

\[ x_n\approx \sqrt{a} \;\Rightarrow \; \frac{a}{x_n}\approx \frac{a}{\sqrt{a}}=\sqrt{a}, \]
\[ x_n>\sqrt{a} \;\Rightarrow \; \frac{a}{x_n} < \frac{a}{\sqrt{a}}=\sqrt{a}, \]
\[ x_n<\sqrt{a} \;\Rightarrow \; \frac{a}{x_n} > \frac{a}{\sqrt{a}}=\sqrt{a}, \]

czyli w każdym przypadku

\[ \left|\frac{1}{2}\,\left(x_n+\frac{a}{x_n}\right) - \sqrt{a}\right| \]

jest mniejsze albo od \(\left|x_n - \sqrt{a}\right|\), albo od \(\left|\frac{a}{x_n} - \sqrt{a}\right|\).

Jeśli \(x_n\) leży blisko \(\sqrt{a}\), to \(\frac{a}{x_n}\) też leży blisko \(\sqrt{a}\); przy tym jeśli \(x_n\) leży po jednej stronie \(\sqrt{a}\), to \(\frac{a}{x_n}\) leży po drugiej stronie \(\sqrt{a}\). Jedna z liczb \(x_n\), \(\frac{a}{x_n}\) znajduje się bliżej \(\sqrt{a}\) niż druga, ale niezależnie od tego która, ich średnia \(\frac{1}{2}\,\left(x_n+\frac{a}{x_n}\right)\) znajdzie się bliżej \(\sqrt{a}\) od obu z nich.

Inne algorytmy. A jak programy obliczają wartości funkcji \(\sqrt{x}\)?

Czy jest ‘’najlepszy algorytm’’? Dla zainteresowanych przegląd algorytmów dla funkcji \(f(x) = \sqrt{x}\) można znaleźć tu: przegląd kilkunastu algorytmów

Może ograniczymy się do jednego algorytmu rekurencyjnego pozwalającego obliczać pierwiastki (tak naprawdę: ich przybliżone wartości) - ale co ważne - tylko za pomocą mnożenia i dodawania ({N. Wirth}):

\[ a_n = a_{n-1} \cdot \left( 1 + \frac{1}{2}c_{n-1} \right) \qquad , \qquad c_n - c_{n-1}^2 \cdot \frac{1}{4} \cdot (3 + c_{n-1} ) \ , \]

gdzie \(a_0 = x, c_0 = 1-x , x \in (0,2)\).

Pozostawimy zbadanie granicy w tym zadaniu do samodzielnego rozwiązania…

Wskazówka.

Można pokazać, że \(a_n = \sqrt{x \cdot (1 - c_n)}\) , \(|c_0| < 1\) i \(c_n \to 0\) gdy \(n \to \infty\) i dalej podobnie jak w przypadku \(\frac{1}{x}\).

A może rekurencja dla innych typowych operacji w informatyce? {N. Wirth}

Obliczanie odwrotności liczby \(\frac{1}{x}\) dla rzeczywistych liczb \(x \in (0,2)\) (jedynie poprzez mnożenie i dodawanie) i za pomocą rekurencji…

Dane: \(a_0 = 1\), \(c_0 = 1 - x\) (\(x \not= 0\)). Definiujemy dwa ciągi rekurencyjne:

\[ a_n = a_{n-1} \cdot (1 + c_{n-1}) \]
\[ c_n = c_{n-1} \cdot c_{n-1} \]

Wtedy (dlaczego?)

\[ \lim_{n \to \infty} a_n = \frac{1}{x} \]

Ale najpierw (!!) wypadałoby sprawdzić, że te ciągi są zbieżne. Proszę sprawdzić te fakty.

Rozwiązanie. Po pierwsze zauważmy, że \(|c_0| < 1\) oraz, że \(c_1 = c_0^2\), \(c_2 = c_1^2 = c_0^{4}\) i ogólnie

\[ c_n = c_0^{2n} = \left(c_0^2\right)^n . \]

Czyli jest to ciąg geometryczny o ilorazie \(c_0^2 < 1\), w szczególności \(\lim_{n \to \infty} c_n = 0\). Teraz zajmiemy się ciągem \((a_n)\):

\[ a_n = a_{n-1} \cdot (1 + c_{n-1}) = a_{n-2} \cdot (1 + c_{n-2}) \cdot (1 + c_{n-1}) = ... = (1 + c_{n-1}) \cdot (1 + c_{n-2}) \cdot ... \cdot (1 + c_{1}) \cdot (1 + c_{0}) . \]

Teraz zauważmy, że dla \(k = 1,2, \ldots , n\) mamy (z własności ciągu geometrycznego)

\[ \frac{1+ c_{k-1}}{1- c_k} = \frac{1}{1-c_{k-1}} . \]

Podstawiając do wzoru i pamiętając, że \(c_0 = 1-x\) uzyskujemy:

\[ a_n = \frac{1 - c_n}{x} . \]

A teraz można skorzystać z własności ciągów zbieżnych i przejść obustronnie do granicy (pamiętając, że zbieżność \((a_n)\) można też sprawdzić bezpośrednio):

\[ a = \frac{1}{x} . \]

Przykład (BIS): A teraz wrócimy do wspominanej wcześniej (zajęcia z liczb rzeczywistych) metody bisekcji rozwiązywania równań nieliniowych

\[ f(x) = 0 . \]

Tam była taka metoda ‘’wspomagana graficznie’’, ale chodzi nam o algorytm, którym posłuży się sam program, bez oceny przez jego twórcę. Definiujemy dwa ciagi rekurencyjne: \(x_1 = a\), \(y_1 = b\) oraz

\[ x_{n+1} = x_n \quad gdy \quad f(x_n) \cdot f\left(\frac{x_n + y_n}{2}\right) < 0 \]
\[ x_{n+1} = \frac{x_n + y_n}{2} \quad gdy \quad f(x_n) \cdot f\left(\frac{x_n + y_n}{2}\right) \geq 0 \]
\[ y_{n+1} = y_n \quad gdy \quad f(x_n) \cdot f\left(\frac{x_n + y_n}{2}\right) < 0 \]
\[ y_{n+1} = \frac{x_n + y_n}{2} \quad gdy \quad f(x_n) \cdot f\left(\frac{x_n + y_n}{2}\right) \geq 0 . \]

A teraz (najciekawsze (dla matematyka, a najważniejsze dla informatyka): to czy te ciągi są zbieżne i to do wspólnej granicy będącej miejscem zerowym funkcji \(f\) w przedziale \([a,b]\) zależy od własności funkcji \(f\). Czyli: konkretny algorytm metody ma swoje założenia - jak każde z twierdzeń…

Dokładniej da się to wprowadzić albo na metodach numerycznych, albo zajęciach z analizy matematycznej.

Rekurencja - kolejne zadanie. Dane są ciągi rekurencyjne \((a_n)\), \((b_n)\) i \((s_n)\):

\[ a_{n+1} = (a_n)^2 \ \mbox{ o ile } (a_{n})^2 < 2 \ \mbox{ oraz } \ a_{n+1} = \frac{1}{2}a_n^2 \ \mbox{ o ile } \ (a_n)^2 \geq 2 , \]
\[ b_{n+1} = \frac{b_n}{2} , \]
\[ \ s_{n+1} = s_n\ \mbox{ o ile } \ (a_{n})^2 < 2 \ \mbox{ oraz } \ s_{n+1} = s_n + b_{n+1} \ \mbox{ o ile } \ (a_n)^2 \geq 2 . \]

Pytania: czy istnieje i jaka jest granica ciągu \((s_n)\)?

Odp. zbieżne do \(\log{x}\)

Kiedy istnieje (dla jakich wartości początkowych: rozpocznij od \(a_0 = x > 0\), \(b_0 = 1\) i \(s_0 = 0\))? Jak zakończyć obliczenia typu ‘’while do’’ (warunek stopu)?

Kolejny ciąg określamy rekurencyjnie:

\[ c_1 = \frac{a}{2} \quad , \quad c_{n+1} = \frac{1}{2} \cdot ( a + c_n^2 ) , \]

przy czym \(0 < a < 1\). Wykazać, że \((c_n)\) jest ograniczony i \(c_n < 1 - \sqrt{1 - a}\) oraz, że jest zbieżny. Obliczyć jego granicę.

Czym różni się metoda jego rozwiązywania od tej z poprzedniego zadania?

Rekurencja liniowa: od wzoru rekurencyjnego do ogólnego.

Podamy jak sobie radzić w 2 najprostszych (ale typowych) przypadkach. Dotyczyć to będzie rekurencji liniowej I i II rzędu i wyjaśnimy też na czym polega trudność dla wyższych rzędów (dla przypadku ogólnego rekurencji liniowej). A dlaczego takie rekurencje? Z pewnością wszyscy poznają (lub poznali) algorytmy sortowania, złożoność czasowa takich algorytmów wyraża się w naturalny sposób rekurencjami liniowymi.

Zbadamy rekurencje o stałych współczynnikach.

Rekurencja liniowa I rzędu. Dotyczy to przypadku

\[ a_{n+1} = k\cdot a_n + s \ , a_1 = a \]

dla pewnych stałych \(k\) i \(s\). Zobaczmy pierwsze wyrazy

\[ a_1 = a \]
\[ a_2 = k \cdot a_1 + s = ka + s \]
\[ a_3 = k \cdot a_2 + s = k^2 a + ks + s \]
\[ a_4 = k \cdot a_3 + s = k^3 a + k^2 s + ks + s \]
\[ a_5 = k \cdot a_4 +s = k^4 a + k^3 s + k^2 s + ks + s \]
\[ \ldots \]

Wygląda to na zasadę

\[ a_n = k^{n-1} a + s \cdot (k^{n-2} + k^{n-3} + ... + k + 1) = k^{n-1} a + s \cdot \frac{k^{n-1} - 1}{k - 1} . \]

Warto powtórzyć zasadę indukcji zupełnej - dowód prawdziwości powyższego wzoru proszę przeprowadzić samodzielnie poprzez indukcję matematyczną… Udało się więc zamienić wzór rekurencyjny na ogólny.

Kolejny ważny przypadek (dwa ciągi rekurencyjne - już takie napotkaliśmy):

\[ x_{n+1} = k \cdot x_n + y_n \ . \]

Stosujemy ponownie rozumowanie krok po kroku

\[\begin{split} \begin{array}{l} x_1 = k \,x_0 + y_0,\\ x_2 = k \,x_1 + y_1 = k \cdot(k \,x_0+y_0) + y_1 = {k}^2\,x_0 + k \,y_0+y_1,\\ x_3 = k \,x_2 + y_2 = k \cdot(k^2\,x_0+k \,y_0+y_1) +y_2 = {k}^3\,x_0 + k^2\,y_0+k \,y_1+y_2,\\ ................................................... \\ x_n = k \,x_{n-1} + y_{n-1} = k \cdot \left(k^{n-1}\,x_0 + \sum\limits_{i=0}^{n-2} k^{n-2-i}\cdot y_i\right) + y_{n-1} = {k}^n\,x_0 + \sum\limits_{i=0}^{n-1} k^{n-1-i}\cdot y_i. \end{array} \end{split}\]

Oczywiście jako szczególny przypadek \(y_n = s\) mamy nasz pierwszy wzór.

Uwaga: działanie nieskończone. Procedury z ciagami rekurencyjnymi - niekoniecznie liniowymi - będą napotykane w trudniejszych problemach, tu jeszcze za wcześnie na wszystkie przypadki. Warto zwócić uwagę na:

(a) Ułamki łańcuchowe

\[ R_n = [a_0;a_1,a_2,\ldots,a_{n-2},a_{n-1},a_n] \]

\(n\)-ty redukt ułamka łańcuchowego

\[ [a_0; a_1, a_2, a_3, \ldots] = a_0 + \cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+{\ddots}}}}, \]

zakładamy przy tym \(a_n >0\). Wartością ułamka łańcuchowego nazywamy granicę

\[ \lim_{n\to\infty} R_n . \]

Ciekawy jest przypadek \([a_0; a_1, a_2, \ldots]\), gdy liczby \(a_n\) są całkowite. Liczby wymierne posiadają skończone rozwinięcie w taki ułamek łańcuchowy. Liczby niewymierne mogą mieć rozwinięcia okresowe.

Ułamek \(\frac{253}{48}\) zapisujemy w postaci ułamka łańcuchowego następująco:

\[ \frac{253}{48} = 5 + \cfrac{13}{48} = 5 + \cfrac{1}{\frac{48}{13}} = 5 + \cfrac{1}{3 + \cfrac{9}{13}} = 5 + \cfrac{1}{3 + \cfrac{1}{\frac{13}{9}}} = 5 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{4}{9}}} = 5 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{\frac{9}{4}}}} = 5 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{4}}}} \, . \]

Ćwiczenie. Rozwinąć w ułamek łańcuchowy liczbę \(\frac{11}{3}\).

(b) Nieskończone pierwiastki.

Wzór

\[ x_{n+1} = \sqrt{a+x_n}, \]

gdzie \(x_0=0 , a > 0\) - ustalona liczba, opisuje \(n\)-te przybliżenie pierwiastka nieskończonego

\[ \sqrt{a+\sqrt{a+\sqrt{a+\ldots}\,}\,} . \]

Analogicznie

\[ x_{n+1} = \sqrt[p]{a\cdot x_n}, \]

gdzie \(x_0=1 ,a > 0 , p>1\) - zadane liczby, opisuje \(n\)-te przybliżenie pierwiastka

\[ \sqrt[p]{a\cdot\sqrt[p]{a\cdot\sqrt[p]{a\cdot \ldots}\,}\,}. \]

Zadania (samodzielne).

(1) Znaleźć wzór ogólny dla ciągu rekurencyjnego

\[ a_1 = 3 \ , \ a_{n+1} = 3\cdot a_n - 1 \ . \]

Oczywiście: nie posługujemy się wzorem ogólnym, tylko ćwiczymy całą procedurę!

(2) Rozwiązać równania rekurencyjne:

\[\begin{split} \begin{array}{ll} % \mbox{(a)}\odst x_{n+1}=x_n + \frac{1}{(n+1)(n+2)},& \mbox{(a)}\ x_{n+1}=x_n + \frac{1}{5^{n+1}},& % \mbox{(c)}\odst x_{n+1}=x_n + 6^{n+1},\\ \mbox{(b)}\ x_{n+1}=x_n + 2n,\\ \mbox{(c)}\ x_{n+1}=x_n+(-1)^n,& \mbox{(d)}\ x_{n+1}=x_n + 2^{n+1}. % \mbox{(f)}\odst x_{n+1}=x_n+\frac{1}{(n+1)(n+2)(n+3)}.\\ \end{array} \end{split}\]

Rekurencja liniowa II rzędu.

Dotyczy to przypadku

\[ a_{n+2} = k\cdot a_{n+1} + m\cdot a_n \ , \ a_1 = a \ , \ a_2 = b \ (n = 0,1,2...) \]

dla pewnych stałych \(k, m, s\). Podamy tylko jedną z metod - zainteresowani znajdą inne. Teraz czeka nas zdecydowanie więcej pracy, ale za to mamy dobry algorytm. Będziemy szukali rozwiązań postaci \(a_n = x^n\) (nie będziemy tego uzasadniali - pozostawimy to zainteresowanym).

Rozpoczniemy (bez uzasadniania…) od poszukiwań \(a_n\) w postaci potęgi:

\[ a_n = q^n . \]

Przy przyjęciu usytalonych 2 wyrazów początkowych (a wiemy, że to istotne)

\[ a_0 = A \ , \ a_1 = B \]

i po podstawieniu do równania uzyskujemy

\[ q^2\cdot q^n = k \cdot q \cdot q^n + m \cdot q^n \ \Rightarrow \ q^2 = k \cdot q + m \]

i te ostatnie równanie nazwiemy równaniem charakterystycznym. To trójmian kwadratowy, więc ma 2 pierwiastki (niestety - być może zespolone, do czego wrócimy po wprowadzeniu liczb zespolonych) i rozpatrzymy te 3 przypadki:

a) 2 pierwiastki rzeczywiste,

b) 1 pierwiastek rzeczywisty podwójny,

c) dwa pierwiastki zespolone (sprzężone).

ad a) Skoro mamy 2 pierwiastki równania charakterystycznego \(\alpha\) i \(\beta\), to z liniowości wynika, że ich kombinacje liniowe

\[ a_n = v\cdot (\alpha)^n + w\cdot (\beta)^n \ , \ v,w \in {\mathbb{R}} \]

spełniają równanie. Pozostaje dobrać \(v\) i \(w\) tak, aby pierwsze wyrazy były uzyskane

\[ A = a_0 = v + w \quad , \quad B = c_1 = v \cdot \alpha + w \cdot \beta \]

i rozwiązujemy ten układ równań liniowych wyznaczając \(v\) i \(w\).

ad b) Teraz mamy tylko jeden pierwiastek (podwójny) \(\alpha\), a więc ciągi rozwiązań to \((\alpha)^n\) oraz \((n\cdot (\alpha)^n)\), czyli

\[ a_n = v\cdot (\alpha)^n + w\cdot n \cdot (\alpha)^n \ , \ v,w \in {\mathbb{R}} . \]

Także tu dobieramy \(v\) i \(w\) w celu uzgodnienia pierwszych wyrazów:

\[ A = a_0 = v \quad , \quad B = c_1 = v \cdot \alpha + w \cdot \alpha . \]

łatwo to rozwiązujemy…

ad c) Uwaga - jeśli nie znamy jeszcze liczb zespolonych - pominąć ten przypadek i dokończyć te zadanie po ich wprowadzeniu!

Teraz skorzystamy, że trójmian ma 2 pierwiastki zespolone sprzężone: \(z = z_1 + i z_2\) oraz \(\bar{z} = z_1 - i z_2\). Bierzemy ich kombinację liniową o współczynnikach zespolonych (!):

\[ a_n = v\cdot z_1^n + w\cdot z_2^n \ , \ v,w \in {\mathbb{C}} . \]

To nie zmienia dalszego rozumowania, ponownie szukamy \(v\) i \(w\) tak, aby dwa pierwsze wyrazy były zgodne z danymi wejściowymi:

\[ A = a_0 = v + w \ , B = a_1 = v\cdot z_1 + w\cdot z_2 . \]

Jak widać - rozwiązujemy układ równań zespolonych, mogą się przydać np. wzór Moivre’a… O tym - w jednym z kolejnych ćwiczeń.

Wersja a): Rozpatrzmy ciąg rekurencyjny

\[ a_0 = 5 \ , \ a_1 = 13 \ , \ a_{n+2} = 2\cdot a_{n+1} + 3 \cdot a_n . \]

Odpowiednie równanie charakterystyczne jest więc w postaci

\[ x^2 = 2x + 3 \ \Rightarrow \ x^2 - 2x - 3 = 0 . \]

Rozwiązujemy równanie: \(\Delta = 4 + 12 = 16\), czyli \(\sqrt{\Delta} = 4\), a więc

\[ x_1 = 3 \ , \ x_2 = -1 . \]

Rozwiązaniami są więc również funkcje postaci

\[ x_n = v \cdot 3^n + w \cdot (-1)^n . \]

Ponieważ \(a_0 = 5\), \(a_1 = 13\), to

\[ v + w = 5 \quad , \quad 3v - w = 13. \]

Rozwiązujemy prosty układ równa’n:

\[ v = \frac{9}{2} \quad , \quad w = \frac{1}{2} . \]

Ostatecznie

\[ a_n = \frac{9}{2} \cdot 3^n + \frac{1}{2} \cdot (-1)^n . \]

Ćwiczenie (F). A teraz - na koniec proszę taką właśnie metodą znaleźć wyraz ogólny ciągu Fibonacciego (z równaniem charakterystycznym \(x^2 = x +1\))!

Wersja b): Rozpatrzmy ciąg rekurencyjny

\[ a_0 = 1 \ , \ a_1 = 2 \ , \ a_{n+2} = 2\cdot a_{n+1} - a_n . \]

Odpowiednie równanie charakterystyczne jest więc w postaci

\[ x^2 - 2x + 1 = 0 \ \Rightarrow \ (x-1)^2 = 0 . \]

Rozwiązaniem jest

\[ x_1 = 1 . \]

Rozwiązaniami są więc również funkcje postaci

\[ a_n = v \cdot 1^n + w \cdot n \cdot 1^n = v + n\cdot w. \]

Ponieważ \(a_0 = 1\), \(a_1 = 2\), to

\[ v = 1 \quad , \quad v + w = 2 \ \Rightarrow \ w = 1. \]

Ostatecznie

\[ a_n = 1 + n . \]

Wersja c): Uwaga - jeśli nie było jeszcze liczb zespolonych - pominąć ten przypadek i dokończyć te zadanie po ich wprowadzeniu!

Rozpatrzmy ciąg rekurencyjny

\[ a_0 = 1 \ , \ a_1 = \frac{1}{4} \ , \ a_{n+2} = \cdot a_{n+1} - 2\cdot a_n . \]

Odpowiednie równanie charakterystyczne jest więc w postaci

\[ x^2 - x + 2 = 0 . \]

Rozwiązujemy równanie: \(\Delta = 1 - 8 = -7\), czyli \(\sqrt{\Delta} = i\cdot \sqrt{7}\), a więc

\[ x_1 = \frac{1-i\sqrt{7}}{2} \ , \ x_2 = \frac{1+i\sqrt{7}}{2} . \]

Rozwiązaniami są więc również funkcje postaci

\[ a_n = v \cdot \left( \frac{1-i\sqrt{7}}{2}\right)^n + w \cdot \left( \frac{1+i\sqrt{7}}{2}\right)^n . \]

Korzystamy ze znajomości pierwszych wyrazów ciągu:

\[ v + w = 1 \quad , \quad v \cdot \left( \frac{1-i\sqrt{7}}{2}\right) + w \cdot \left( \frac{1+i\sqrt{7}}{2}\right) = \frac{1}{4} , \]

czyli oczywiście

\[ v = w = 1. \]

Ostatecznie

\[ a_n = \left( \frac{1-i\sqrt{7}}{2}\right)^n + \left( \frac{1+i\sqrt{7}}{2}\right)^n . \]

Ale teraz mamy kolejne zadanie: nasz ciąg składa się z wartości rzeczywistych, a więc powinniśmy z powyższego ciągu wyeliminować liczby zespolone. Co będzie potrzebne? Ponieważ potęgujemy liczby zespolone, to skorzystamy ze wzoró de Moivre’a.

Mamy \(\left|\frac{1-i\sqrt{7}}{2}\right| = \left|\frac{1+i\sqrt{7}}{2}\right| = \frac{\sqrt{53}}{2}\). Postać trygonometryczna to \(\frac{1-i\sqrt{7}}{2} = \frac{\sqrt{53}}{2} \cdot (\cos{ \phi} + i\sin{ \phi})\) oraz \(\frac{1+i\sqrt{7}}{2} = \frac{\sqrt{53}}{2} \cdot (\cos{ \phi} - i\sin{ \phi})\) dla pewnego kąta \(\phi\), gdzie możemy go wyliczyć w danych funkcji trygonometrycznych, nie obliczamy, to ćwiczenie z algebry…) Czyli

\[ a_n = \left( \frac{1-i\sqrt{7}}{2}\right)^n + \left( \frac{1+i\sqrt{7}}{2}\right)^n = \left( \frac{\sqrt{53}}{2}\right)^n \cdot \left( \cos{ n \phi} \right) . \]

Zadania. Znajdź wzory ogólne ciągów rekurencyjnych:

a)

\[ a_0 = 5, a_1 = 7, \quad a_{n+2} = 5\cdot a_{n+1} - 6\cdot a_n , \]

b)

\[ b_0 = 0, b_1 = 2 , \quad b_{n+2} = -2n_{n+1} - 2b_n , \]

c)

\[ c_0 = 1, c_1 = -4 , \quad c_{n+2} = 4\cdot c_{n+1} - 4 \cdot c_n . \]

Przypadek ogólny.

To wskazuje, że w ogólnym przypadku \(a_{n+k} = F(a_1, ... , a_{n+k-1})\) uzyskamy

\[ a = F(a,a,...,a) , \]

a takich (dowolnych) równań nie potrafimy rozwiązywać…

Na ogół ograniczamy się do sytaucji, gdy \(F\) jest wielomianem.

A tu wprowadzenie do równań rekurencyjnych w terminologii ciągów geometrycznych (a nie funkcji tworzących) jak kto woli… - autor: prof. J. Matkowski. a symulacje… ponownie przypomnę o ‘’Geogebrze’’. Tym razem ładny skrypt o rekurencji liniowej i to niejednorodnej… I może kolejny materiał .

Układy równań liniowych rekurencyjnych.

Jak się okaże - nawet na tym wykładzie często zamiast ciągu zadanego rekurencyjnie mamy np. dwa ciągi (choćby przy obliczeniach \(\sqrt{x}\) na komputerze).

Metoda: sprowadzić do jednego równania poprzez redukcję zmiennej.

Przykład. \(a_0 = 2, b_0 = 3, a_{n+1} = 6a_n + 4 b_n , b_{n+1} = a_n + 3b_n\).

Weźmy pierwsze równanie \(a_{n+1} = 6a_n + 4 b_n\) i liczymy

\[ a_{n+2} = 6a_{n+1} + 4 b_{n+1} = 6a_{n+1} + 4\cdot (a_n + 3b_n ) = 6 a_{n+1} + 4 a_n + 12 b_n . \]

Ale z pierwszego równania \(a_{n+1} - 6a_n = 4 b_n\), czyli

\[ a_{n+2} = 6 a_{n+1} + 4 a_n + 12 b_n = 6 a_{n+1} + 4 a_n + 3\cdot ( a_{n+1} - 6a_n ) = 9 a_{n+1} - 14 a_n , \]

skąd

\[ a_{n+2} - 9 a_{n+1} + 14 a_n = 0 \]

i równanie charakterystyk jest postaci

\[ x^2 - 9x + 14 = 0 . \]

Z trójmianu

\[ x^2 - 9x + 14 = 0 . \]

uzyskujemy

\[ (x-2)\cdot (x-7) = 0 , \]

a więc \(a_n = c\cdot 7^n + d\cdot 2^n \). Wstawiając \(a_0\) i \(a_1\) uzyskamy układ równań:

\[ c + d = a_0 = 2 \qquad , \qquad 7c + 2d = a_1 = 24 . \]

Ostatecznie \(c = 4\) i \(d = -2\), czyli

\[ a_n = 4\cdot 7^n - 2^{n+1} \]

i dalej

\[ b_n = 7^n + 2^{n+1} . \]

Uwaga: można było inaczej, ale taka jest ogólna metoda…

Zauważmy, że metoda tu podawana ograniczyła się do przypadku rekurencji liniowych (o stałych współczynnikach). To ograniczenie pozwala na pominięcie całego aparatu matematyczny szeregów potęgowych (o tym: na analizie matematycznej)! Zamiast tego uzyskujemy wyłącznie wielomiany, a więc wystarczy badać ich pierwiastki. To i tak sprawia, że przydatne są liczby zespolone, albo musimy potrafić to zrobić wyłącznie dla wielomianów, dla których znajdziemy pierwiastki - a w ogólnym przypadku to nie jest możliwe!

Np. ciąg dany rekurencyjnie

\[ a_{n+6} - 5a_{n+5} - 15 a_{n+4} + 85 a_{n+3} + 10 a_{n+2} - 372 a_{n+1} + 360 a_n = 0 \]

prowadzi do równania charakterystycznego

\[ x^6 - 5x^5 -15x^4 +85 x^3 +10x^2 - 372 x + 360 = 0 , \]

ale to jest

\[ (x-2)^3 \cdot (x+3)^2 \cdot (x - 5) = 0 . \]

Tu się uda, ale…

Ćwiczenie. (dodatkowe) Rozwiązać układ równań rekurencyjnych niejednorodnych:

\[\begin{split} \left\{\begin{array}{l} x_{n+1} = 3\,x_n - 3\,y_n + (-8)^n\\ y_{n+1} = 6\,x_n - 8\,y_n - 1.\\ \end{array}\right. \end{split}\]

Rozwiązanie. Przekształćmy pierwsze z równań:

\[ y_n=x_n-\frac{1}{3}\,x_{n+1} + \frac{1}{3}\,(-8)^n \]

i wstawiamy do drugiego

\[ x_{n+2} = -5x_{n+1} + 6x_n +3. \]

Równanie charakterystyczne problemu jednorodnego

\[\begin{split} \begin{array}{c} x_{n+2}=-5x_{n+1}+6x_n,\\ t^2+5t-6=(t-1)\,(t+6)=0. \end{array} \end{split}\]

Rozwiązanie problemu niejednorodnego jest więc postaci

\[ x_n = (c_n+c) \,+\, (d_n+d)\cdot (-6)^n, \]

gdzie \(c,d\) – stałe dowolne, a ciągi \((c_n )\) i \( (d_n)\) spełniają

\[\begin{split} \left\{\begin{array}{l} \Delta c_n\cdot 1 + \Delta d_n\cdot (-6)^{n+1}=0,\\ \Delta c_n\cdot 1 + \Delta d_n\cdot (-6)^{n+2}=3.\\ \end{array}\right. \end{split}\]

Z pierwszego równania \(\Delta d_n\cdot (-6)^{n+1} = - \Delta c_n\) i wstawiamy do drugiego uzyskując:

\[ \Delta d_n = \frac{-\Delta c_n}{(-6)^{n+1}} \ , \ \Delta c_n = \frac{3}{7}. \]

Stąd

\[\begin{split} c_n= \frac{3}{7}\,n+c_0, \ \Delta d_n = -\frac{3}{7} \cdot \left(-\frac{1}{6}\right)^{n+1}\\ \Leftrightarrow d_n = \left(-\frac{3}{7}\right)\cdot \sum_{j=1}^{n} \left(-\frac{1}{6}\right)^{j} + d_0 = \frac{3}{49}\cdot\left(1-\left(-\frac{1}{6}\right)^{n}\right) +d_0. \end{split}\]

Jeśli np. ustalimy pierwszy wyarz \(c_0=\frac{3}{49} ,\) \(d_0=-\frac{3}{49}\), to dostajemy

\[\begin{split} x_n= \frac{3}{7}\,n \,+\, c+d\cdot (-6)^n,\\ y_n= \left(\frac{1}{3}\cdot (-8)^n + \frac{2}{7}\,n - \frac{1}{7}\right) \,+\, \frac{2}{3}\,c+ 3d\cdot (-6)^n. \end{split}\]

Ćwiczenie samodzielne. Na wzór tej metody można łatwo rozwiązać wiele zadań. Np. takie:

Wyrazy pewnego ciągu geometrycznego \((a_n)\) spełniają warunki:

\[\begin{split} \left\{\begin{array}{l} a_1+a_2+a_3=2 \\ a_4+a_5+a_6=-2\end{array}\right. \end{split}\]

Aby wyznaczyć iloraz \(q\) tego ciągu, postąpimy następująco:

(1) Zapisujemy drugie równanie jak przy rekurencjach liniowych: \(q^{3}(a_1+a_2+a_3)=-2\). 2. Korzystając z równania pierwszego uzyskamy \(a_1+a_2+a_3=2\) 3. Teraz mamy: \(q^{3}=-1\). 4. Obliczmy, że \(q=-1\).

A teraz - wyznaczyć iloraz \(q\) ciągu geometrycznego \((b_n)\),o wyrazach \(b_3,b_4,\ldots,b_8\) spełniających:

\[\begin{split} \left\{\begin{array}{l} b_3+b_4+b_5+b_6=2 \\ b_5+b_6+b_7+b_8=8\end{array}\right. \end{split}\]

Rekurencja - trudniejsze pytanie. Dane są ciągi:

\[ a_{n+1} = (a_n)^2 \ \mbox{ o ile } \ (a_{n})^2 < 2 \ \mbox{ oraz } \ a_{n+1} = \frac{1}{2}a_n^2 \ \mbox{ o ile } \ (a_n)^2 \geq 2 , \]
\[ b_{n+1} = \frac{b_n}{2} , \]
\[ \ s_{n+1} = s_n \ \mbox{ o ile } \ (a_{n})^2 < 2 \ \mbox{ oraz } \ s_{n+1} = s_n + b_{n+1} \ \mbox{ o ile } \ (a_n)^2 \geq 2 . \]

Pytania: czy istnieje i jaka jest granica ciągu \((s_n)\)? Kiedy istnieje (dla jakich wartości początkowych: rozpocznij od \(a_0 = x > 0\), \(b_0 = 1\) i \(s_0 = 0\))? Jak zakończyć obliczenia (warunek stopu)?

Rekurencja jest silnie związana z zastosowaniem pętli bez wskazania liczby przebiegów, a raczej ze sprawdzeniem osiągnęcia założonego celu, czyli pętli ‘’while… do’’. I tu problem: obliczając symulacje istnienia i wartości granicy mamy dwa problemy: pierwszy, to nie możemy zweryfikować, czy granica istnieje (o czym mówiliśmy), a drugi, to kiedy zakończyć obliczenia (problem ‘’stopu’’). W tym drugim przypadku możemy uzyskać fałszywą sugestię odnośnie wartości granicy, a na ogół chcemy znać tę wartość z zadaną precyzją \(\varepsilon > 0\). Nie znając granicy \(g\) nie możemy sprawdzać w pętli warunku z definicji \(|a_n - g| < \varepsilon\).

Powinniśmy badać warunek Cauchyego, bo on nie wymaga znajomości granicy, a jedynie wyrazów ciągu. Niestety - wszystkich od pewnego miejsca. Tego się nie da, więc często sprawdzamy różnice \(|a_n - a_{n-1}| < \varepsilon\).

To za mało: proszę zrobić symulację np. dla \(a_n = \sum_{k=3}^n \frac{1}{k \ln k \ln (\ln k)} \) lub po prostu dla \(a_n = \ln{n}\). Problem jest otwarty, a pewne istniejące rozwiązania podamy na analizie matematycznej…

Proszę być świadomym ograniczeń obliczeń komputerowych:

Diagonal arguments are used to prove many fundamental results about the limitations of computation, such as the undecidability of the Halting Problem for programs and the inherent, unavoidable inefficiency (exponential time or worse) of procedures for other computational problems. So computer scientists do need to study diagonal arguments in order to understand the logical limits of computation. A well-educated computer scientist will be comfortable dealing with countable sets, finite as well as infinite. {Mathematics for Computer Science, Eric Lehman, F Thomson Leighton, Albert R Meyer}