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 komputer w tym nie pomoże...) kwadrat jak największej liczby nie przekraczającej $a$ . To działa ‘‘w pamięci’’ np. dla $\sqrt{10}$ , znajdziemy $3^2 = 9 < 10$ , czyli $3 < \sqrt{10}$ 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 bok kwadratu o polu $a$ , 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 monotoniczność 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}$ . Algorytm 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!). Aby uniknąć rozważań co do porównania wielkości $x_n$ i $\frac{a}{x_n}$ w kolejnych krokach będziemy zawsze przyjmować za $x_{n}$ mniejszą z tych liczb (tj. obliczając powyższym wzorem $x_{n+1}$ wyznaczymy też $\frac{a}{x_{n+1}}$ i do dalszych obliczeń zakładać będziemy, że $x_{n+1}$ oznacza mniejszą z nich (czyli zawsze krótszy bok prostokąta)). Formalnie: $x_{n+1} = \min{ \{ \frac{1}{2}(x_n + \frac{a}{x_n}) , \frac{a}{\frac{1}{2}(x_n + \frac{a}{x_n}) }\} }$ . 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^{2^n} .

Ponieważ $|c_0| < 1$ , to $|c_n| = |c_0|^{2^n} \leq |c_0|^n$ , 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 (bo $1 - c_k = 1 - c_{k-1}^2 = (1 - c_{k-1}) \cdot (1 + c_{k-1})$ )

\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 ciągi 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} = \frac{x_n + y_n}{2} \quad gdy \quad f(x_n) \cdot f\left(\frac{x_n + y_n}{2}\right) < 0

y_{n+1} = y_n \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_2{x}$ (dla $x \in [1,2]$ )

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{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}

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

Uwaga: działanie nieskończone. Procedury z ciągami rekurencyjnymi - niekoniecznie liniowymi - będą napotykane w trudniejszych problemach, tu jeszcze za wcześnie na wszystkie przypadki. Warto zwró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{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}

Rekurencja liniowa II rzędu¶

Dotyczy to przypadku

a_{n+2} = k\cdot a_{n+1} + m\cdot a_n \ , \ a_0 = A \ , \ a_1 = B \ (n = 0,1,2...)

dla pewnych stałych $k, m$ . 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 ustalonych 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 = a_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 = a_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^n + w\cdot \bar{z}^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 + w\cdot \bar{z} .

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

a_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ń:

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} = 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 = \frac{1}{2} - \frac{i}{4\sqrt{7}} \quad , \quad w = \frac{1}{2} + \frac{i}{4\sqrt{7}} .

Ostatecznie

a_n = \left(\frac{1}{2} - \frac{i}{4\sqrt{7}}\right) \cdot \left( \frac{1-i\sqrt{7}}{2}\right)^n + \left(\frac{1}{2} + \frac{i}{4\sqrt{7}}\right) \cdot \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 wzoru de Moivre’a.

Mamy $\left|\frac{1-i\sqrt{7}}{2}\right| = \left|\frac{1+i\sqrt{7}}{2}\right| = \sqrt{2}$ . Postać trygonometryczna to $\frac{1-i\sqrt{7}}{2} = \sqrt{2} \cdot (\cos{ \phi} + i\sin{ \phi})$ oraz $\frac{1+i\sqrt{7}}{2} = \sqrt{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 = v \cdot \left( \frac{1-i\sqrt{7}}{2}\right)^n + w \cdot \left( \frac{1+i\sqrt{7}}{2}\right)^n = \left( \sqrt{2}\right)^n \cdot \left( \cos{ n \phi} + \frac{1}{2\sqrt{7}} \sin{ n \phi} \right) .

Zadania (wzory ogólne rekurencji)¶

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} = -2b_{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 sytuacji, 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 charakterystyczne 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 matematycznego 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:

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

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{array}{c} x_{n+2}=-5x_{n+1}+6x_n,\\ t^2+5t-6=(t-1)\,(t+6)=0. \end{array}

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ą

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

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

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.

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

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.

Ć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:

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

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:

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

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ągnię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 Cauchy’ego, 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}

Ciągi rekurencyjne a obliczanie funkcji pierwiastek a\sqrt{a}a​.¶

Zadanie¶

Inne algorytmy¶

Przykład (BIS)¶

Rekurencja - kolejne zadanie¶

Pytania¶

Rekurencja liniowa: od wzoru rekurencyjnego do ogólnego¶

Zadania (samodzielne)¶

Rekurencja liniowa II rzędu¶

Ćwiczenie (F)¶

Zadania (wzory ogólne rekurencji)¶

Układy równań liniowych rekurencyjnych¶

Ciągi rekurencyjne a obliczanie funkcji pierwiastek $\sqrt{a}$ .¶