Rekursives Gleichungssystem aufl

05/07/2009 - 13:31 von Martin | Report spam
Ich habe folgendes Problem, das sich am Rande meiner Diplomarbeit
ergeben hat. Ich interessiere mich für die Folge a(n), die ich mit
etwas Aufwand rekursiv definieren kann:

a(n) = 3 a(n-1) + 4 a(n-2) + 2 b(n)+ 2 b(n-1) + c(n) + 3 c(n-1) - ∑
{i=0, n-3} a(i)
b(n) = 2 a(n-2) + c(n-1) + b(n-1)
c(n) = a(n-2) + 2 b(n-1) + a(n-3) + c(n-2)

Startwerte:
a(-1) = b(0) = b(1) = c(0) = c(1) = 0
a(0) = 1

Gesucht ist jetzt eine explizite Darstellung (oder zumindest eine
Nàherung) für a(n), also eine Darstellung von p, die nur noch von der
Variablen n, nicht aber von den übrigen rekursiv definierten
Funktionen abhàngt.

Ist so etwas möglich und wenn ja, wie geht man es am besten an?

Gruß,
martin
 

Lesen sie die antworten

#1 Jakob Creutzig
05/07/2009 - 13:57 | Warnen spam
Martin writes:

Ich habe folgendes Problem, das sich am Rande meiner Diplomarbeit
ergeben hat. Ich interessiere mich für die Folge a(n), die ich mit
etwas Aufwand rekursiv definieren kann:

a(n) = 3 a(n-1) + 4 a(n-2) + 2 b(n)+ 2 b(n-1) + c(n) + 3 c(n-1) - ∑
{i=0, n-3} a(i)
b(n) = 2 a(n-2) + c(n-1) + b(n-1)
c(n) = a(n-2) + 2 b(n-1) + a(n-3) + c(n-2)

Startwerte:
a(-1) = b(0) = b(1) = c(0) = c(1) = 0
a(0) = 1
Gesucht ist jetzt eine explizite Darstellung (oder zumindest eine
Nàherung) für a(n), also eine Darstellung von p, die nur noch von der
Variablen n, nicht aber von den übrigen rekursiv definierten
Funktionen abhàngt.

Ist so etwas möglich und wenn ja, wie geht man es am besten an?



Grundsaetzlich geht das schon. Mangels einer gescheiten Idee
wuerd ich vielleicht brute force probieren: Ich wuerd erstmal
versuchen, eine direkte Formel fuer c(n) in a&b zu finden, also

c(n) = 2b(n-1) + a(n-2) + a(n-3) + c(n-2)
= 2b(n-1) + a(n-2) + a(n-3) + 2b(n-3) + a(n-4) + a(n-5) + c(n-4)
..
= 2 \sum_{i< n/2} b(n- (2*i + 1) ) + \sum_{i < n -2} a(i)

(ganz auf die Schnelle, ist sicher noch bisschen flasch).

Dann wuerd ich ganz tief seufzen, und eine Formel fuer b(n)
in a finden wollen. Und danach koennt man den Kladderatatsch
fuer b,c in die Formel fuer a einsetzen, hat eine rekursive
Definition (AFAICS linear, aber immer mit Rueckgriff auf alle
vorigen Elemente), und kann a(n) nach und nach "ausrechnen".

Und das fuehrt dann hoffentlich zu einer Formel, die man mit
vollstaendiger Induktion beweisen kann. (Man kann alternativ
auch von unten anfangen, a(1), a(2), a(3) usf. bestimmen, bis man
eine Idee hat, aber das ist meiner Erfahrung nach wesentlich
zielloser.)

Die Frage ist nur, wie viel eine explizite Darstellung bringt.
Hoechstwahrscheinlich laeuft das auf eine Summe von 1 bis n
hinaus, was die z.B. Berechnung per Rekursion eventuell
vergleichbar schnell und u.U. sogar numerisch guenstiger macht.
Fuer die analytische Einsicht koennen rekursive Definitionen,
so aehnlich wie DGLs, auch sinnvoller sein.

Wofuer waer das denn gedacht?

Best,
Jakob

Ähnliche fragen