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

Groups > pl.comp.programming > #28589

Re: Liczby Fibonacciego rzędu N

Cross-posted to 2 groups.

Show all headers | View raw

On 16.05.2016 09:00, Borneq wrote:
> W dniu 15.05.2016 o 18:55, bartekltg pisze:
>>         x=2;
>>         while ( (x-2)* mpfr::pow(x,k) + 1 > pow(10,-precyzja) )
>>             x= (x *(2 + k *(-2 + x) - mpfr::pow(x,-k)))/(k* (-2 + x) +
>> x) ;
>
>
> A co to za wzór?
>

Ciało: Iteracna metodą Newtona. Warunek pętli: sprawdza wartośći
wielomianu w wyliczonym punkcie, ma być bliski 0.

Wszystko nie na orgunalnym wielomianie, ale na przemnożonym przez q-1,
bo ma łatwiejszą numerycznie postać.

Dopiero co było opisywane! Sztuczka z mnozeniem prze (q-1) wspominana 
była chyba w każdym moim pośćie;-)

Masz ctrtl C+V, bo przeciez jest tu tyle postów (poza Twoimi 5,
słownie - pięć:), że nie znajdziesz ;p

pzdr
bartekltg


From: bartekltg <bartekltg@gmail.com>
Newsgroups: pl.comp.programming,pl.sci.matematyka
Subject: =?UTF-8?Q?Re:_Liczby_Fibonacciego_rz=c4=99du_N?=
Date: Sun, 15 May 2016 14:26:51 +0200
Message-ID: <nh9puc$t8t$1@node1.news.atman.pl>
pl.sci.matematyka:18873


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?)



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