Matematické Fórum

SweetNelli · 16. 11. 2009 12:37

Našla jsem postup, jak by se dali řešit Fibonnaciho čísla velmi efektivně a to pomocí umocňování matic.. řekla bych, že ten postup je daleko výhodnější než ten rekurentní.

Proto mě ale napadla mě otázka, jestli někdo z vás by nedokázal zobecnit postup pro libovolnou rekurentní posloupnost?

Oxyd · 16. 11. 2009 13:14 — Editoval Oxyd (16. 11. 2009 13:15)

De to i bez násobení matic:

$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{ 1 + \sqrt{5} }{ 2 } \right)^n - \left( \frac{ 1 - \sqrt{5} }{ 2 } \right)^n \right]$

kde F_n je n-té Fibonacciho číslo.

K tomuhle výsledku -- a nejen k němu, ale i k jiným rekurencím -- se dá dojít pomocí vytvořujících funkcí. Na netu je volně ke stažení knížka ohledně vytvořujících funkcí s příšerným názvem Generatingfunctionology -- ovšem anglicky. Kromě toho si můžeš sehnat Kapitoly z diskrétní matematiky, kde je též kapitola o vytvořujících funkcích (i včetně odvození explicitního vzorce pro Fibonacciho čísla).

SweetNelli · 16. 11. 2009 13:17

↑ Oxyd:

děkuju, ale zajímalo by mě jestli vytvořující funkce se používají i pro obecné rekurence?

Kondr · 16. 11. 2009 16:45

↑ SweetNelli:Dokonce obecnější, než násobení matic. Fakt doporučuju tu odkazovanou knížku pročíst.

Matematické Fórum

#1 16. 11. 2009 12:37

Rekurentní posloupnost - těžká úloha

#2 16. 11. 2009 13:14 — Editoval Oxyd (16. 11. 2009 13:15)

Re: Rekurentní posloupnost - těžká úloha

#3 16. 11. 2009 13:17

Re: Rekurentní posloupnost - těžká úloha

#4 16. 11. 2009 16:45

Re: Rekurentní posloupnost - těžká úloha

Zápatí