Co to są liczby Fibonacciego - wiadomo, ale co to są liczby Fibonacciego
któregoś rzędu?

do góry

W dniu 13.05.2016 o 17:46, Borneq pisze:
> Co to są liczby Fibonacciego - wiadomo, ale co to są liczby Fibonacciego
> któregoś rzędu?

Już wiem, normalne inicjowane są dwiema jedynkami , inne większą liczbą
jedynek, i tak dla trzech:
1+1+1=3 1+1+3=5 1+3+5=9
co nam daje 1 1 1 3 5 9 17 31 57

do góry

On Fri, 13 May 2016 17:52:46 +0200, Borneq
<b...@a...hidden.pl> wrote:
> W dniu 13.05.2016 o 17:46, Borneq pisze:
> > Co to są liczby Fibonacciego - wiadomo, ale co to są liczby
Fibonacciego
> > któregoś rzędu?
> Już wiem, normalne inicjowane są dwiema jedynkami , inne większą
liczbą
> jedynek, i tak dla trzech:
> 1+1+1=3 1+1+3=5 1+3+5=9
> co nam daje 1 1 1 3 5 9 17 31 57

Czy istnieje rozwiązanie analityczne dla rzędu N > 4?

RW

do góry

On 14.05.2016 11:10, Roman W wrote:
> On Fri, 13 May 2016 17:52:46 +0200, Borneq <b...@a...hidden.pl>
> wrote:
>> W dniu 13.05.2016 o 17:46, Borneq pisze:
>> > Co to są liczby Fibonacciego - wiadomo, ale co to są liczby
> Fibonacciego
>> > któregoś rzędu?
>> Już wiem, normalne inicjowane są dwiema jedynkami , inne większą
>> liczbą

Pomijasz najistotniejsze. Element ciągu jest sumą nie dwóch,
ale k poprzednich elementów.
Niby oczywiste, ale można przeoczyć.

>> jedynek, i tak dla trzech:
>> 1+1+1=3 1+1+3=5 1+3+5=9
>> co nam daje 1 1 1 3 5 9 17 31 57
>
> Czy istnieje rozwiązanie analityczne dla rzędu N > 4?

Rozwiązanie liniowej rekurencji sprowadza się do znalezienia
pierwiastków wielomianu. To dla n>4 bywa upierdliwe;-)


Wiemy, że rozwiązaniami podstawowymi są ciagi geometryczne.
q^k

(rozwiążaniem jest kombinacja liniowa takich rozwiązań podstawowych
spałniająca warunki początkowe)

które spełniają rekurencję:

a[n]+a[n+1]+..a[k-1] = a[k]

czyli
1 + q + q^2.. + q^(k-1) = q^k

q^k - q^(k-1) - q^2 - q - 1 = 0 (1)


(q^k-1)/(q-1) = q^k

q^k -1 = q^(k+1) - q^k

0 = q^(k+1) - 2 q^k + 1

Dla k=2

(q^2-q-1)

pierwiastkami są fi i bar{fi}

Zgadza się.


Do rzeczy... wielomian (1) wygląda ładnie, ale
pierwiasków oczywistych nie widać. Mathematica ich też nie widzi
dla k>4:(

Do ataku nemerycznego można użyć równoważnego

-(q^k-1)/(q-1) + q^k

lub ładniejszego ale z dodatkowym sztucznym pierwiastkiem równym 1

q^(k+1) - 2 q^k + 1

Patrząc na te wykresy widać, że pierwiastki są
jeden w okolicy liczby 2
k-1 w okolicach (zespolonych) pierwiastków z jedynki (z pominięciem
samej jedynki).



To daje nam jakościowe oszacowanie, jak szybko ten ciąg rośnie,
ale pewnie chceilibyśmy go policzyć.
Dokładnie policzyć element nr 3535436743678357 ;-) Modulo
10^18 niech dla ulatwienia bedzie.
Jechanie rekurencją odpada, a wspołczynniki wzoru 'analitycznego'
znamy być możę nie dostatecznie dokładnie, aby wyzanczyć liczbę
jednosci.

Tu przydatna jest pewna sztuczka, używana już przy Fibonaccim.

Weźmy macierz
A =
[1 1 1 1 1 1 1 1]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 1 0]

Opisuje ona iterację stanu z naszego ciągu. Jeśli wsadzimy w nią wektor
an, an-1... dostaniemy wektor an+1,an...

Jeśli zaczniemy od wektora jednostkowego v=[1;1;1;1;1;1;1]

Pierwszym elementem wektora (A^n)v
będzie n+k ty element ciągu Fib.

A^n obliczami potęgowaniem binarnym, log(n) mnożęj, każde
po k^3 dzialań, łączny koszt O(log(n) k^3)


pzdr
bartekltg

do góry

W dniu 14.05.2016 o 11:10, Roman W pisze:
> Czy istnieje rozwiązanie analityczne dla rzędu N > 4?

Właśnie potrzebuję znaleźć granicę x_{i+1}/x_i przy i dążącym do
nieskończoności. (jak jest rząd tych ciągów po angielsku?)
Dla rzędu 2 jest to (sqrt(1)+1)/2
A jak jest z wyższymi rzędami? Dokładne wzory zdają się nie istnieć, a
może można to rozwiązać za pomocą metody Newtona?
Czy są tablice tych wielkości do 20 ?
To, o co mi chodzi, to nie same ciągi Fibonacciego a ciągi pochodne,
zawierające liczby bliższe sobie:
dla rzędu 2 będą to te same ciągi co Fibonacciego.

Ale dla rzędu trzy będą to ciągi:

x_0,x_1,x_2, gdzie największy x_0 i najmniejszy x2 to kolejne elementy
ciągu Fibonacciego, ale różnica x1-x2 to wcześniejszy, mniejszy element
a różnica x0-x1 to jeszcze wcześniejszy.
Przykład: 57,48,31
inny: 31,26,17
będą miały procentowo do całości: 42%,35%,23%
Właśnie interesują mnie te procenty dla granicy ciągów i dla różnych
rzędów. Jeśli znam granicę między dwiema sąsiednimi liczbami
Fibonacciego a moimi skrajnymi liczbami ciągu, to chyba pozostałe liczby
procentowo mojego ciągu mogę obliczyć.
Do czego potrzebne: sortowanie zewnętrzne (plikowe) polifazowe. Serie
rozdzielam nie równomiernie ale tak 42%,35%,23% i ostatni plik pusty.

do góry

W dniu 15.05.2016 o 03:55, Borneq pisze:
> Właśnie potrzebuję znaleźć granicę x_{i+1}/x_i przy i dążącym do
> nieskończoności. (jak jest rząd tych ciągów po angielsku?)

https://en.wikipedia.org/wiki/Generalizations_of_Fib
onacci_numbers
tutaj Tribonacci,Tetranacci itd to nie całkiem te o które mi chodzi, bo
są inicjowane zerami zamiast jedynkami.
Ale Tribonacci są różne: https://oeis.org/A000213 - te o które chodzi
https://oeis.org/A000213
https://oeis.org/A000288

Jakie wzory uogólnionych ciągów inicjowanych jedynkami?

do góry

W dniu 15.05.2016 o 04:23, Borneq pisze:
> Jakie wzory uogólnionych ciągów inicjowanych jedynkami?

To znaczy wzór nie na same ciągi, ale równanie dla x_{i+1}/x_i przy i
dążącym do nieskończoności.
Na przykład dla Fibonacciego : fib^2 = fib+1

do góry

W dniu 15.05.2016 o 04:29, Borneq pisze:
> W dniu 15.05.2016 o 04:23, Borneq pisze:
>> Jakie wzory uogólnionych ciągów inicjowanych jedynkami?
>
> To znaczy wzór nie na same ciągi, ale równanie dla x_{i+1}/x_i przy i
> dążącym do nieskończoności.
> Na przykład dla Fibonacciego : fib^2 = fib+1

Chyba wiem:
dla Fibonacciego: a_n = a_{n-1}+a_{n-2}
jeśli przez r oznaczymy golden ratio, to
r^2 = r+1
dla innych będzie analogicznie:
r^3 = r^2+r+1
r^4 = r^3+r^2+r+1
r^5 = r^4+r^3+r^2+r+1
...
Wystarczy teraz do tablicy Hornera i szukać metodą Newtona około punktu x=2.

do góry

Borneq pisze:
> W dniu 15.05.2016 o 04:29, Borneq pisze:
>> W dniu 15.05.2016 o 04:23, Borneq pisze:
>>> Jakie wzory uogólnionych ciągów inicjowanych jedynkami?
>>
>> To znaczy wzór nie na same ciągi, ale równanie dla x_{i+1}/x_i przy i
>> dążącym do nieskończoności.
>> Na przykład dla Fibonacciego : fib^2 = fib+1
>
> Chyba wiem:
> dla Fibonacciego: a_n = a_{n-1}+a_{n-2}
> jeśli przez r oznaczymy golden ratio, to
> r^2 = r+1
> dla innych będzie analogicznie:
> r^3 = r^2+r+1

OK. Tylko to nie jest już golden ratio

r = 1/3 ( 1+(19-3sqrt[33])^(1/3) + (19+3sqrt[33])^(1/3) )
r = 1.839286755

> r^4 = r^3+r^2+r+1
> r^5 = r^4+r^3+r^2+r+1
> ...
> Wystarczy teraz do tablicy Hornera i szukać metodą Newtona około punktu x=2.
>
A to masz już gotowe
{{2, 1.618033989}, {3, 1.839286755}, {4, 1.927561975}, {5,
1.965948237}, {6, 1.983582843}, {7, 1.991964197}, {8,
1.996031180}, {9, 1.998029470}, {10, 1.999018633}, {11,
1.999510402}, {12, 1.999755501}, {13, 1.999877833}, {14,
1.999938939}, {15, 1.999969475}, {16, 1.999984739}, {17,
1.999992370}, {18, 1.999996185}, {19, 1.999998093}, {20,
1.999999046}}

--
peter

do góry

On 15.05.2016 04:23, Borneq wrote:
> W dniu 15.05.2016 o 03:55, Borneq pisze:
>> Właśnie potrzebuję znaleźć granicę x_{i+1}/x_i przy i dążącym do
>> nieskończoności. (jak jest rząd tych ciągów po angielsku?)


Przegapiłęś mojego wczorajszego posta, a tam już były odpowiedzi
na Twoje pytania;-)


Wielomianem charkterystycznym tej rekurencji jest

q^k - q^(k-1) - q^2 - q - 1 = 0

Interesuje Cię największy pierwiastek tego równania
(dlaczego, widać we wspomnianym poście, rozwiązanie
to x[j] a_k q_k^j, gdzie q_j to pierwiastki wielomianu,
dla dużych j istotny jest tylko największy)..


Co lepsze, wielomian ten co najwyzęj dwa pierwiastki rzeczywiste,
interesujacy Cię znajduje się w przedziale [fi,2].

Użyj Newtona zaczynając od puinktu startowego q_0= 2.
(pomiedzy pierwiastkiem a dwójką wykres jest wylukłu,
podchodząc od góry mamy onotoniczną zbieżność metody).


Również sztuczka z wczoraj: dla dużych wartośći k być może
wygodniej jest rozwiazać ten wielomian *(q-1), co daje
zwartą formę:

q^(k+1) - 2 q^k + 1 ==0

Pierwiastki są te same, tylko dołożyliśmy dodatkowo pierwiastek
w jedynce. Numerycznie, np do metody Newtona, powinno nadawać się
lepiej, mniej liczenia.

Iteracja Newtona x <- x -f/f'

(q (2 + k (-2 + q) - q^-k))/(k (-2 + q) + q)

Bardzo ładny wzorek do iterowania, zbiega też elegancko.


Oryginał k=2:

In[107]:= RecurrenceTable[{a[n + 1] == (
a[n] (2 - 2 k + k a[n] - a[n]^-k))/(-2 k + (1 + k) a[n]) /.
k -> 2, a[0] == 2}, a[n], {n, 0, 10}, WorkingPrecision -> 30]

Out[107]= {2.00000000000000000000000000000, \
1.75000000000000000000000000000, 1.64285714285714285714285714286, \
1.61920688007644529383659818442, 1.61803681847513501855590525011, \
1.61803398876643183749199913556, 1.61803398874989484820515162178, \
1.61803398874989484820458683437, 1.61803398874989484820458683437, \
1.61803398874989484820458683437, 1.61803398874989484820458683437}

k=4:

In[108]:= RecurrenceTable[{a[n + 1] == (
a[n] (2 - 2 k + k a[n] - a[n]^-k))/(-2 k + (1 + k) a[n]) /.
k -> 4, a[0] == 2}, a[n], {n, 0, 10}, WorkingPrecision -> 30]

Out[108]= {2.00000000000000000000000000000, \
1.93750000000000000000000000000, 1.92778299933984536716905553131, \
1.92756208799223947008945657261, 1.92756197548295447685033895311, \
1.92756197548292530426190586370, 1.92756197548292530426190586174, \
1.92756197548292530426190586174, 1.92756197548292530426190586174, \
1.92756197548292530426190586174, 1.92756197548292530426190586174}

k=10:

In[109]:= RecurrenceTable[{a[n + 1] == (
a[n] (2 - 2 k + k a[n] - a[n]^-k))/(-2 k + (1 + k) a[n]) /.
k -> 10, a[0] == 2}, a[n], {n, 0, 10}, WorkingPrecision -> 30]

Out[109]= {2.00000000000000000000000000000, \
1.99902343750000000000000000000, 1.99901863282589812378374126107, \
1.99901863271010113873066887060, 1.99901863271010113866340923913, \
1.99901863271010113866340923913, 1.99901863271010113866340923913, \
1.99901863271010113866340923913, 1.99901863271010113866340923913, \
1.99901863271010113866340923913, 1.99901863271010113866340923913}

k=50

In[112]:= RecurrenceTable[{a[n + 1] == (
a[n] (2 - 2 k + k a[n] - a[n]^-k))/(-2 k + (1 + k) a[n]) /.
k -> 50, a[0] == 2}, a[n], {n, 0, 10}, WorkingPrecision -> 30]

Out[112]= {2.00000000000000000000000000000, \
1.99999999999999911182158029987, 1.99999999999999911182158029986, \
1.99999999999999911182158029986, 1.99999999999999911182158029986, \
1.99999999999999911182158029986, 1.99999999999999911182158029986, \
1.99999999999999911182158029986, 1.99999999999999911182158029986, \
1.99999999999999911182158029986, 1.99999999999999911182158029986}



> https://en.wikipedia.org/wiki/Generalizations_of_Fib
onacci_numbers
> tutaj Tribonacci,Tetranacci itd to nie całkiem te o które mi chodzi, bo
> są inicjowane zerami zamiast jedynkami.
> Ale Tribonacci są różne: https://oeis.org/A000213 - te o które chodzi
> https://oeis.org/A000213
> https://oeis.org/A000288
>
> Jakie wzory uogólnionych ciągów inicjowanych jedynkami?

Nie ma problemu, co też możan wywnioskować z postaci
ogolnego rozwiązania.

Warunki początkowe nie ma ją praktycznie znaczenia.
Równnie rekurencyjne jest to samo, więc rozwiązania
podstawowe są takie same.
Granica iloczynu x_{n+1}/x_n będzie taka sama (no, chyba,
że warunki początkowy dały a_k =0 dla największego pierwiastka
q_k).

pzdr
bartekltg

do góry