Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28581

Re: Liczby Fibonacciego rzędu N

Cross-posted to 2 groups.

Show all headers | View raw

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_Fibonacci_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

Back to pl.comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-13 17:46 +0200
  Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-13 17:52 +0200
    Re: Liczby Fibonacciego rzędu N Roman W <bloody_rabbitREMOVETHIS@gazeta.pl> - 2016-05-14 10:10 +0100
      Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-14 16:51 +0200
      Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 03:55 +0200
        Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 04:23 +0200
          Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 04:29 +0200
            Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 04:40 +0200
              Re: Liczby Fibonacciego rzędu N peter <ToJestTo@nic.nie.wiem> - 2016-05-15 11:37 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-15 18:55 +0200
                Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-16 09:00 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-16 14:42 +0200
                Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-16 09:16 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-16 14:35 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-16 16:57 +0200
          Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-15 14:26 +0200

csiph-web