Simple Namessuche fuer ein Verfahren

20.03.2006, 16:07

Crock

Simple Namessuche fuer ein Verfahren

Hossa,

ich hab letzten von einem Kollegen (Informatikstudent) von einem Verfahren geheort,
mit der man aus der Bildungsregel einer rekusriven Folge die Formel ausrechnen kann, um sie nicht-rekursiv (iterativ?) darstellen kann.
So soll man zum Beispiel aus der Bildungsregel fuer die Fibonacci-Zahlen
$\begin{eqnarray*} a_1 = 1 \end{eqnarray*}$
$\begin{eqnarray*} a_2 = 1 \end{eqnarray*}$
$\begin{eqnarray*} a_i = a_{i-2} + a_{i-1} \end{eqnarray*}$
eine simple Formel errechnen koennen.
Leider kannte mein Kollege den Namen des Verfahrens, geschweige denn den richtigen Ansatz bzw. die richtige Durchfuehrung.

Ist jemanden so ein Verfahren bekannt? Wenn ja, wie heisst es? (Wenn es kein Eintrag bei Wikipedia gibt, waer ein Link super).

MfG Alexander "Crock" Surma

20.03.2006, 16:48

Auf diesen Beitrag antworten »

So simpel ist die Formel gar nicht...

Für diese "Umwandlung der rekursiven in eine explizite Folgendarstellung" ist mir kein griffiger kurzer Name geläufig. Was nicht bedeuten soll, dass es den nicht gibt - ich hab's nicht so mit Bezeichnungen für alles und jedes... Augenzwinkern

Das Verfahren an sich für solche rekursiv definierten Folgen

$\begin{eqnarray*} a_n = \sum\limits_{k=1}^m b_ka_{n-k} \end{eqnarray*}$

mit bekannten Koeffizienten $\begin{eqnarray*} b_1,\ldots,b_m \end{eqnarray*}$ ist bekannt und ähnelt dem Vefahren zur Bestimmung der Lösung einer linearen homogenen Dgl m-ter Ordnung mit konstanten Koeffizienten.

20.03.2006, 18:45

Crock

Auf diesen Beitrag antworten »

Hi,
das ist nicht so ganz was ich meinte.
Ich dachte an ein Verfahren,
dass aus einer rekursiven Formel
eine nicht-rekursive Formel macht, (dass heisst eine Formel, die
nicht auf andere Elemente der Reihe zurueckgreif) und somit nur den
gegebenen Index zur Berechnung des Gliedwertes nutzt.

20.03.2006, 18:50

papahuhn

Auf diesen Beitrag antworten »

Da gibts zwei Varianten.
Einmal über formale Potenzreihen und einmal über lineare Differenzengleichungen. Die Rechnung über Potenzreihen kann ziemlich lang werden, vor allem die explizite Darstellung der Koeffizienten eines Reihenprodukts ist knifflig; lineare Differenzengleichungen sind da einfacher, funktionieren halt nur bei "linearen Rekursionen".

Ps: Mich deucht, Arthur meint die Differenzengleichungen.

20.03.2006, 19:13

Auf diesen Beitrag antworten »

Zitat:

Original von Crock
das ist nicht so ganz was ich meinte.
Ich dachte an ein Verfahren,
dass aus einer rekursiven Formel
eine nicht-rekursive Formel macht

"nicht-rekursiv" nennt man auch "explizit". Und genau darum ging es in meinem Beitrag!

Neue Frage »

Antworten »

Simple Namessuche fuer ein Verfahren

Verwandte Themen