Rekurrenzgleichungs-Löser

Rekurrenzgleichungs-Löser

Der Rekurrenzgleichungs-Löser berechnet die geschlossene Lösung jeder linearen homogenen Rekurrenz mit konstanten Koeffizienten durch Lösen der zugehörigen charakteristischen Gleichung, Darstellung der Wurzeln in der komplexen Ebene und Generierung der ersten N Terme der Folge. Geben Sie die Rekurrenz entweder als geordnete Koeffizientenliste oder als natürlichen mathematischen Ausdruck wie a(n) = 3·a(n−1) − 2·a(n−2) ein; das Tool verarbeitet automatisch verschiedene reelle Wurzeln, mehrfache Wurzeln und komplex konjugierte Paare.

Was ist eine lineare Rekurrenzgleichung?

Eine lineare homogene Rekurrenzgleichung mit konstanten Koeffizienten der Ordnung k hat die Form:

wobei c₁, c₂, …, c_k feste reelle Zahlen sind und k die Ordnung ist. Zusammen mit k Anfangswerten a(0), a(1), …, a(k−1) definiert die Rekurrenz jeden nachfolgenden Term eindeutig. Klassische Beispiele sind:

• Fibonacci: a(n) = a(n−1) + a(n−2), Anfangswerte 0, 1 → 0, 1, 1, 2, 3, 5, 8, 13, …
• Lucas: a(n) = a(n−1) + a(n−2), Anfangswerte 2, 1 → 2, 1, 3, 4, 7, 11, 18, 29, …
• Pell-Zahlen: a(n) = 2·a(n−1) + a(n−2), Anfangswerte 0, 1 → 0, 1, 2, 5, 12, 29, 70, …
• Tribonacci: a(n) = a(n−1) + a(n−2) + a(n−3), Anfangswerte 0, 0, 1 → 0, 0, 1, 1, 2, 4, 7, 13, 24, …

Die Methode der charakteristischen Gleichung

Um eine geschlossene Formel für a(n) zu finden, suchen wir nach Lösungen der Form a(n) = rⁿ. Einsetzen in die Rekurrenz und Division durch r^n−k ergibt:

Dies ist die charakteristische Gleichung — ein Polynom vom Grad k in r. Nach dem Fundamentalsatz der Algebra hat sie genau k komplexe Wurzeln (unter Berücksichtigung der Vielfachheit). Die allgemeine Lösung der Rekurrenz hängt von der Struktur dieser Wurzeln ab:

Fall 1: Verschiedene reelle Wurzeln r₁, …, r_k

Die Konstanten A₁, …, A_k werden bestimmt, indem man n = 0, 1, …, k−1 einsetzt und ein lineares Gleichungssystem gegen die Anfangswerte löst.

Fall 2: Eine Wurzel r mit Vielfachheit m

Jede mehrfache Wurzel trägt m linear unabhängige Basissequenzen rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ bei.

Fall 3: Komplex konjugierte Wurzeln r = ρ·e^iθ, r̄ = ρ·e^−iθ

Wenn die Rekurrenz reelle Koeffizienten hat, treten komplexe Wurzeln immer paarweise konjugiert auf. Jedes Paar kombiniert sich zu einem reellen oszillierenden Term mit geometrischer Hüllkurve ρⁿ und Frequenz θ.

Wachstumsklassifizierung durch die dominante Wurzel

Sei ρ = max|r_i| die Magnitude der größten Wurzel (der Spektralradius). Das Langzeitverhalten von a(n) wird bestimmt durch:

Fibonacci — Ein durchgerechnetes Beispiel

Betrachten wir die Fibonacci-Rekurrenz a(n) = a(n−1) + a(n−2) mit a(0) = 0 und a(1) = 1.

1. Charakteristische Gleichung: r² − r − 1 = 0
2. Wurzeln (quadratische Formel): r = (1 ± √5) / 2, also φ ≈ 1.6180 und ψ ≈ −0.6180
3. Allgemeine Form: a(n) = A·φⁿ + B·ψⁿ
4. Anfangsbedingungen anwenden: A + B = 0 und A·φ + B·ψ = 1, was A = 1/√5 und B = −1/√5 ergibt.
5. Binet-Formel: a(n) = (φⁿ − ψⁿ) / √5

Da |ψ| < 1, verschwindet der zweite Term für n → ∞, sodass a(n) annähernd φⁿ / √5 entspricht — das ist der Grund, warum Fibonacci-Zahlen pro Schritt um etwa den Faktor φ wachsen.

So verwenden Sie diesen Löser

1. Wählen Sie einen Eingabemodus: 'Geführt' ermöglicht die Auswahl der Ordnung und Eingabe von kommagetrennten Koeffizienten; 'Freiform-Ausdruck' akzeptiert vollständige Rekurrenzen wie a(n) = a(n-1) + 6*a(n-2) - 8*a(n-3).
2. Geben Sie die Koeffizienten oder den Ausdruck ein. Dezimalzahlen (0.5) und Brüche (1/2) sind zulässig.
3. Geben Sie die Anfangswerte an. Sie müssen genau k Werte passend zur Ordnung angeben: a(0), a(1), …, a(k−1).
4. Wählen Sie, wie viele Terme angezeigt werden sollen (bis zu 60).
5. Klicken Sie auf Lösen. Die Ergebnisseite zeigt die charakteristische Gleichung, die Positionen der Wurzeln in der komplexen Ebene, die geschlossene Formel und ein animiertes Balkendiagramm der Folge.

Unterstützte Fälle & Einschränkungen

• Ordnung: 1 bis 6 (das charakteristische Polynom wird für Ordnung ≥ 3 numerisch über die Durand–Kerner-Iteration gelöst).
• Reelle konstante Koeffizienten: Komplexe Koeffizienten werden nicht unterstützt; die c_i müssen reell sein.
• Nur homogen: Dieses Tool löst homogene Rekurrenzen (ohne Störterm wie + n oder + 2ⁿ). Für eine inhomogene Rekurrenz lösen Sie hier den homogenen Teil und addieren separat eine partikuläre Lösung.
• Numerische Präzision: Die Ergebnisse werden in IEEE-754 doppelter Genauigkeit berechnet; bei sehr schlecht konditionierten Rekurrenzen (große Spreizung der Wurzelmagnituden) weist der Verifizierungs-Banner auf Abweichungen zwischen geschlossener Form und iterativen Werten hin.

Anwendungen

• Algorithmenanalyse: Laufzeiten von Divide-and-Conquer-Algorithmen erfüllen oft lineare Rekurrenzen (Master-Theorem).
• Kombinatorik: Abzählfolgen — Catalan-Zahlen, Derangements, Pflasterungen — sind häufig durch Rekurrenzen gegeben.
• Signalverarbeitung: Zeitdiskrete LTI-Systeme mit Rückkopplung sind lineare Rekurrenzen; ihre Stabilität wird durch die Wurzelpositionen bestimmt (innerhalb des Einheitskreises ⇔ stabil).
• Populationsdynamik & Finanzen: Zinseszins, altersstrukturierte Populationsmodelle, autoregressive AR(p) Zeitreihen.
• Physik: Eindimensionale Gittermodelle, Tight-Binding-Hamiltonians und Transfer-Matrix-Methoden.

Häufig gestellte Fragen

Was ist eine lineare Rekurrenzgleichung mit konstanten Koeffizienten?

Eine lineare Rekurrenzgleichung mit konstanten Koeffizienten ist eine Gleichung der Form a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k), wobei c₁, c₂, …, c_k feste reelle Zahlen sind und k die Ordnung ist. Jeder Term in der Folge ist eine Linearkombination der vorherigen k Terme. Bekannte Beispiele sind die Fibonacci-Folge a(n) = a(n−1) + a(n−2) und die Lucas-Folge mit anderen Anfangswerten.

Was ist die charakteristische Gleichung einer Rekurrenz?

Gegeben sei die Rekurrenz a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k). Die charakteristische Gleichung lautet r^k − c₁·r^k−1 − c₂·r^k−2 − … − c_k = 0. Diese Polynomgleichung hat genau k komplexe Wurzeln (unter Berücksichtigung der Vielfachheit), und jede Lösung der Rekurrenz ist eine Linearkombination von Folgen der Form n^j·rⁿ, wobei r eine Wurzel ist und j bis zu ihrer Vielfachheit minus 1 läuft.

Wie erhalte ich eine geschlossene Formel für a(n)?

Lösen Sie die charakteristische Gleichung, um ihre Wurzeln r₁, r₂, …, r_k zu finden. Wenn alle Wurzeln verschieden sind, lautet die geschlossene Form a(n) = A₁·r₁ⁿ + A₂·r₂ⁿ + … + A_k·r_kⁿ, wobei die Konstanten A_i durch Einsetzen der Anfangswerte und Lösen eines linearen Systems bestimmt werden. Wenn eine Wurzel r die Vielfachheit m hat, trägt sie m Basisterme bei: rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ. Dieser Rechner erledigt den gesamten Vorgang automatisch.

Was bedeuten komplexe Wurzeln für die Folge?

Wenn die Rekurrenz reelle Koeffizienten hat, treten komplexe Wurzeln immer in konjugierten Paaren r = ρ·e^iθ und r̄ = ρ·e^−iθ auf. Ein solches Paar erzeugt Oszillationen: Die geschlossene Form enthält einen Term 2·ρⁿ·[α·cos(nθ) − β·sin(nθ)]. Bei ρ = 1 oszilliert die Folge mit konstanter Amplitude; bei ρ < 1 klingt die Oszillation ab; bei ρ > 1 wächst die Amplitude geometrisch.

Warum sagt mir die dominante Wurzel, wie die Folge wächst?

Mit steigendem n dominiert der Term mit dem größten |r| alle anderen, da sein Betrag am schnellsten wächst. Gilt ρ = max|r_i|, dann ist |a(n)| asymptotisch proportional zu ρⁿ (mit einem zusätzlichen Polynomfaktor bei mehrfachen dominanten Wurzeln). Der Löser klassifiziert Folgen danach: konvergent gegen Null bei ρ < 1, beschränkt bei ρ = 1, geometrisches Wachstum bei ρ > 1.

Kann dieses Tool die Fibonacci-Folge lösen?

Ja. Geben Sie die Rekurrenz a(n) = a(n−1) + a(n−2) mit den Anfangswerten 0, 1 ein. Der Rechner leitet die charakteristische Gleichung r² − r − 1 = 0 mit den Wurzeln φ = (1 + √5)/2 und ψ = (1 − √5)/2 ab und gibt die Binet-Formel a(n) = (φⁿ − ψⁿ) / √5 aus. Klicken Sie auf das Fibonacci-Schnellbeispiel, um die Lösung zu sehen.

Unterstützt das Tool inhomogene Rekurrenzen wie a(n) = a(n−1) + n?

Nein — dieses Tool löst ausschließlich homogene Rekurrenzen (ohne Störterm). Für inhomogene Fälle zerlegt man die Lösung in den homogenen Teil (hier lösbar) plus eine partikuläre Lösung passend zum Störterm. Typische Ansätze für partikuläre Lösungen sind: ein Polynom gleichen Grades bei polynomiellem Störterm, C·rⁿ bei exponentiellem Störterm oder A·cos(nθ) + B·sin(nθ) bei trigonometrischem Störterm.

Weiterführende Literatur

• Rekursion — Wikipedia
• Lineare Differenzengleichung — Wikipedia
• Charakteristisches Polynom — Wikipedia
• Fibonacci-Folge — Wikipedia
• Durand–Kerner-Verfahren — Wikipedia (Englisch)

Andere verwandte Tools:

Sequenztools:

• Arithmetische Folge Rechner hohe Präzision
• quadratzahlen-liste
• Die ersten n Primzahlen
• Geometrische Folge Rechner
• Liste von Fibonacci-Zahlen
• Primzahlenliste Empfohlen
• Quadratzahlenliste
• Collatz-Vermutung-Rechner Empfohlen
• Glückliche-Zahlen-Rechner
• Magisches Quadrat Generator Empfohlen
• Catalan-Zahlen-Generator
• Sigma-Notation-Rechner Summierung Neu
• Produktnotation Rechner (Pi Notation) Neu
• Pascalsches Dreieck Generator Neu
• Primzahlzwillinge-Finder Neu
• Partitionsfunktions-Rechner Neu
• Rekurrenzgleichungs-Löser Neu