Strona główna » Poradniki » Maxima » Równania Rekurencyjne

Równania Rekurencyjne

Wstęp

Równanie rekurencyjne to takie równanie, które definiuje ciąg w sposób rekurencyjny. Zazwyczaj określona ona zależność pomiędzy dwoma kolejnymi wyrazami np. an + 1 = 2an, gdzie a1 = 2. W tym przypadku można łatwo wyprowadzić, że an = 2n. Czasem zdarzają się jednak bardziej skomplikowane przypadki takie jak np. ciąg Fibonacciego. Tym razem znalezienie wzoru ogólnego nie jest oczywiste.

Rozwiązywanie

Biblioteka

Do rozwiązywania równań rekurencyjnych potrzebna jest funkcja solve_rec(), która jest dostępna w bibliotece o tej samej nazwie solve_rec. Bibliotekę należy dołączyć przed dalszymi obliczeniami:

(%i1)load(solve_rec);
(%o1)C:\maxima-5.37.3\share\maxima\solve_rec\solve_rec.mac

Prosty układ

Na początek rozpatrzmy przypadek podany we wstępie: an + 1 = 2an. Dodatkowo został podany warunek a1 = 2. Jednak tego typu równanie można rozwiązać bez warunku początkowego tj.:

(%i3)r1: a[n + 1] = 2*a[n];
roz: solve_rec(r1, a[n]);
(roz)an = %k12n

W odpowiedzi otrzymaliśmy, że an = %k12n, gdzie %k1 jest to pewna wartość początkowa. Dla dowolnej wartości otrzymamy ciąg spełniający ustaloną na początku zależność.

Jednak jeśli pierwszy wyraz szukanego ciągu jest znany to wystarczy dopisać go do rozwiązywanego układu w następujący sposób:

(%i3)r1: a[n + 1] = 2*a[n];
roz: solve_rec(r1, a[n], a[1] = 2);
(roz)an = 2n

W przypadku gdyby warunków początkowych byłoby więcej należałoby je dopisywać jako kolejne argumenty. Zostało to przedstawione w następnym przykładzie.

Ciąg Fibonacciego

Analogicznie do poprzednich przykładów można rozwiązać równanie rekurencyjne ciągu Fibonacciego. Jest on określany równaniem an + 2 = an + 1 + an dla każdego n > 2 z dwoma warunkami początkowymi a1 = 1 i a2 = 1.

W celu rozwiązania tego układu należy wpisać:

(%i7)r1: a[n + 2] = a[n + 1] + a[n];
roz: solve_rec(r1, a[n], a[2] = 1, a[1] = 1);
(roz)an =

Wyliczanie konkretnego wyrazu

W celu wyliczenia n-tego wyrazu ciągu na podstawie obliczonego rozwiązania roz można skorzystać z funkcji ev, która przyjmuje dwa argumenty. Jako pierwsze należy podać rozwiązanie zwrócone przez funkcję solve_rec(). Drugim arguementem musi być zmienna oraz jaka wartość ma zostać jej przypisana.

(%i10)r1: a[n + 1] = 2*a[n];
roz: solve_rec(r1, a[n], a[1] = 2);
a10: ev(roz, n = 10);
(a10)a10 = 1024

Zadania

Zadanie 1

Rozwiąż przy pomocy funkcji solve_rec() poniższy układ:

an + 2 = 2an + 1 + 3an
a1 = 3
a2 = 2

Następnie oblicz 10 wyraz podanego układu.