Numerikus sorozatok/Rekurzív sorozatok

A Wikikönyvekből, a szabad elektronikus könyvtárból.

Rekurzív módon megadott sorozatok[szerkesztés]

Rekurzív módon adunk meg egy (a_n) sorozatot, ha az n-edik tagja az a_1,a_2, ..., a_{n-1} elemek segítségével számítható ki. Ezzel szemben a sorozat explicit módon van megadva, ha ismert az a mód, ahogyan az n szám és más műveletek segítségével kiszámítható az a_n általános tag.

Példák[szerkesztés]

  1. Az  a_n=\left\{
\begin{matrix}
1, & \mbox{ha} & n=1\\
\sqrt{3-a_{n-1}}, & \mbox{ha} & n>1
\end{matrix}\right.
    hozzárendeléssel megadott sorozat rekurzív módon van adva, mert az n-edik tagot a közvetlenül megelőzőből kell kiszámítani, feltéve, hogy az a tag egyáltalán létezik (a definíció 1-et ad a_1-re)
  2. (b_n)=\left(\sqrt{n+1}\right)
    az index függvényében, azaz explicit módon megadott sorozat
  3. (p_n)=(2,3,5,7,11, ...)\,
    a prímszámok sorozata a prímszámok halmazának sorbarendezésével megadott sorozat, mely esetén a megadás módja nem jellemezhető egyértelműen
  4.  c_n=\left\{
\begin{matrix}
1, & \mbox{ha} & n=1\\
n\cdot a_{n-1}, & \mbox{ha} & n>1
\end{matrix}\right.
    maga a faktoriális sorozat: (n!), mely általános tagja az előző tag és az index függvényében van megadva.

Megjegyzések[szerkesztés]

A matematikai analízisben egy sorozatot elegendő adottnak vennünk, egyáltalán nem kell mellékelnünk azt a módot ahogyan az elemeket kiszámíthatjuk. Ezzel szemben a rekurzív matematikában használatos sorozatokat nem tekinthetjük adottnak, amíg egy rekurzív eljárást nem mutatunk fel, mellyel kiszámíthatjuk a sorozat tetszőleges tagját.

A rekurzív definíció tétele[szerkesztés]

A rekurzív megadási módnál ellenőriznünk kell, hogy egyáltalán létezik-e az adott módon adott sorozat, sőt sok esetben (de nem mindig) azt is elvárjuk, hogy egyértelműen létezzen a kívánt rekurzív tulajdonságú sorozat. Ezt biztosítja a rekurziótétel.

TételA rekurzív definíció tétele – Legyen S a következő függvényhalmaz:

S=\{f\mid f:\{1,...,n-1\}\to \mathbf{R}, \;n\in \mathbf{Z}^+\}

és legyen

g:S\to \mathbf{R}

függvény. Ekkor létezik egyetlen olyan (a_n):Z+ \to R sorozat, mely rendelkezik a következő tulajdonsággal:

a_n=g((a_n)|_{\{1,...,n-1\}})\, minden nZ+-re.

Magyarázat. A g függvény szerepe az, hogy a sorozat előző tagjaiból, például az (a_1,a_2, ..., a_{n-1}) véges sorozatból, mely az (a_n) sorozat {1,...,n – 1} halmazra vett \scriptstyle{(a_n)|_{\{1,...,n-1\}}}-vel jelölt leszűkítése, kiszámítsa az n-edik tag értékét. Speciálisan az n = 1 esetben az előbb említett sorozat az üres halmazra vett leszűkítés, azaz \scriptstyle{a_1=g(\emptyset)}, mely a kezdő elem értékét definiálja.

Világos, hogy a tételben az R halmaz szerepeltetésének nincs különleges indoka, állhat R helyett bármely halmaz.

Bizonyítás.

(1) egzisztencia

(a) Először belátjuk, hogy tetszőleges nZ+-re létezik egyetlen olyan s:{1,...,n – 1} \to R véges sorozat, hogy minden 0 < k < n-ra

s_k=g(s|_{\{1,...,k-1\}})\,

n=1-re nyilvánvalóan létezik egyetlen ilyen sorozat, hiszen ekkor \scriptstyle{s_1=g(\emptyset)}.

n > 1 tetszőleges esetén tegyük fel, hogy az állítás az n-nél kisebb számokra már áll. Vegyük t:{1,...,n – 2} \to R -t ilyen tulajdonsággal. Ekkor

s(m) = t(m) (m < n), s(n) = g(t)

alkalmasan definiált sorozat, mert t-re már igaz a szóban forgó tulajdonság, s-re pedig a definícióbójából adódik. Az egyértelműség az n-edik elem sorozattól független megadásából következik.

(b) Jól definiált tehát minden n-re az az (an) sorozat, melyet a következő definícióval kapunk:

an = s(n)

ahol s az előző pontban az n + 1 -hez egyértelműen megadható véges sorozat, s(n) pedig ennek n-edik eleme.

(2) unicitás

Teljes indukcióval igazolható, hogy ha lenne két ilyen tulajdonságú (an) sorozat, akkor ezek pontról pontra megegyeznek.

Példák[szerkesztés]

1. számtani sorozat, iterációk

Ha

a_1=a\,
a_n=a_{n-1}+d\, minden n > 1

akkor

g:\quad (s:\{1,...,n-1\}\to \mathbf{R})\quad \mapsto \quad s_{n-1} + d\,

és g(\scriptstyle{\emptyset}) = a

Általában, ha a g függvény

g:\quad (s:\{1,...,n-1\}\to \mathbf{R})\quad \mapsto \quad f(s_{n-1})\,

alakú, ahol f egyváltozós függvény, akkor iterációról beszélünk.

2. faktoriális sorozat, egyszerű rekurziók

Ha

a_1=1\,
a_n=n\cdot a_{n-1}\, minden n > 1

akkor

g:\quad (s:\{1,...,n-1\}\to \mathbf{R})\quad \mapsto \quad n\cdot s_{n-1}\,

Általában, ha a g függvény

g:\quad (s:\{1,...,n-1\}\to \mathbf{R})\quad \mapsto \quad f(n,s_{n-1})\,

alakú, ahol f kétváltozós függvény, akkor egyszerű rekurzióról beszélünk (mely nem összetévesztendő a primitív rekurzióval).

3. Fibonacci-sorozat, általános rekurziók

Ha

a_1=0\,
a_2=1\,
a_n=a_{n-2}+a_{n-1}\, minden n > 2

akkor

g:\quad (s:\{1,...,n-1\}\to \mathbf{R})\quad \mapsto \quad s_{n-2}+\cdot s_{n-1}\,

mely egy teljesen általános rekurzióval megadott sorozat.

Ilyen általános rekurzióra még egy példa:

a_1=a\,
a_2=b\,
a_3=c\,
a_n=n\cdot a_{n-3}+(n^2+1)a_{n-2}-(n^3-1)\cdot (a_{n-1})^{2008}\, minden n > 3

akkor

g:\quad (s:\{1,...,n-1\}\to \mathbf{R})\quad \mapsto \quad n\cdot s_{n-3}+(n^2+1)s_{n-2}-(n^3-1)\cdot (s_{n-1})^{2008}\,

Kiválasztással kombinált rekurzió[szerkesztés]

Az analízis bizonyításai során számos esetben nem kell megadnunk rekurzív módon sorozatokat, elegendő valamely rekurzív tulajdonságnak eleget tévő sorozat létezését igazolni (például monoton növekvő, vagy egy ponttól egyenletesen távolodó, vagy ahhoz közeledő sorozat létezését igazolni).


TételA kiválasztási axiómával segített rekurzió tétele – Legyen \scriptstyle{(F_n)_{n\in \mathbf{Z}^+}} olyan függvényrendszer, hogy minden n természetes számra Fn elemei az {1,...,n-1}-en értelmezett, R-be képező függvények (R helyett tetszőleges halmazt is vehetünk). Legyen továbbá \scriptstyle{e=(e_i)_{i=1}^M\in F_M} „kezdő sorozat”. Ha

minden n természetes számra és minden f ∈ Fn-re létezik f* ∈ Fn+1, hogy f*|{1,...,n-1} = f,

akkor létezik olyan a sorozat, hogy

a|_{\{1,...,M\}}=e\, és minden n > M-re (a_1, ..., a_{n-1})\in F_n\,
Japan road sign 206-R.svg

Bizonyítás.

Először is a feltétel szerint minden n természetes számra a

\prod\limits_{f\in F_n}\{f\mbox{*}\in F_{n+1}\mid f\mbox{*}|_f\}

halmaz nem üres (ez tehát azon függvények halmaza, mely minden Fn -beli f-hez az f egy Fn+1-beli kiterjesztését rendeli). A kiválasztási axióma miatt ekkor nem üres az alábbi Descartes-szorzat:

\prod\limits_{n\in\mathbf{Z}^+}\prod\limits_{f\in F_n}\{f\mbox{*}\in F_{n+1}\mid f\mbox{*}|_f\}

Ennek egy eleme olyan

(g_1,g_2, ..., g_n, ...)\,

függvényrendszer, melynek n-edik eleme az összes Fn -beli f-hez az f egy Fn+1-beli kiterjesztését rendeli. Iterációval definiálunk ezek után egy sorozatot, mely rendelkezni fog a kívánt tulajdonsággal. Legyen ugyanis

a_1=e\, és
a_{n+1}=g_{n}(a_n)\,

Világos, hogy ez jól definiált függvény és teljes indukcióval az is belátható, hogy rendelkezik a fenti tulajdonsággal.


Példa. Ha (an) szigorúan monoton növekvő valós számsorozat, akkor van olyan csupa racionális számokból álló (bn) sorozat, melyre an < bn < an+1.

(1) Ilyen nyilvánvalóan létezik, hisz an és an+1 között mindig van racionális szám, ezeket kiválasztva nyerjük a sorozatot. Ez a megoldás lényeget érintően helyes, de formailag kifogásolható, hiszen a végtelen sok halmazból történő egyidejű kiválasztás esetén legalább azt igazolni kell, hogy ezen halmazok egyike sem üres.

(2) Igényesebb igazolása ennek a ténynek, a fenti tétel alkalmazása. a1 és a2 között választunk egy b1 racionális számot. Ezután legyen Fn+1 az összes olyan {1,...,n}-halmazon értelmezett függvény (n tagú véges sorozat), melyekre teljesül, hogy az n-edik tagja an és an+1 közé eső racionális szám. Ha f egy Fn-beli, akkor világos, hogy hozzávéve n+1-edik tagként egy an+1 és an+2 közé eső racionális számot Fn+1-beli sorozatot kapunk. Ezen a ponton hivatkozunk a tételre: eszerint van a b1 számmal induló, a fenti rekurzív tulajdonságnak eleget tévő sorozat.