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

Groups > pl.comp.programming > #28566 > unrolled thread

Liczby Fibonacciego rzędu N

Back to article view | Back to pl.comp.programming

Contents

  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

#28566 — Liczby Fibonacciego rzędu N

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

[toc] | [next] | [standalone]

#28567

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

[toc] | [prev] | [next] | [standalone]

#28571

On Fri, 13 May 2016 17:52:46 +0200, Borneq 
<borneq@antyspam.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

[toc] | [prev] | [next] | [standalone]

#28572

On 14.05.2016 11:10, Roman W wrote:
> On Fri, 13 May 2016 17:52:46 +0200, Borneq <borneq@antyspam.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

[toc] | [prev] | [next] | [standalone]

#28573

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.

[toc] | [prev] | [next] | [standalone]

#28574

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

[toc] | [prev] | [next] | [standalone]

#28575

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

[toc] | [prev] | [next] | [standalone]

#28576

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.

[toc] | [prev] | [next] | [standalone]

#28579

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

[toc] | [prev] | [next] | [standalone]

#28582

On 15.05.2016 11:37, peter wrote:
> 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}}

Nie ma co się ograniczać;-)

2: 
1.618033988749894848204586834365638117720309179805762862135448622705260462818902449707207204189391137
3: 
1.839286755214161132551852564653286600424178746097592246778758639404203222081966425738435419428307014
4: 
1.927561975482925304261905861736622168698554255163384727146647038009666062297815559149818253461890653
5: 
1.965948236645485337189937375934401396151327177456861393236934508442252712871886881734818665554630472
6: 
1.983582843424326330385629293391425752730080865568821753216359065656702278014172402986575070226899797
7: 
1.991964196605035021097741754584374963479318960053157995244782153400951980309622183563141577022719017
8: 
1.996031179735414589815317901755839774489379680945221927634853627284595269945627520379784497496677719
9: 
1.99802947026228669866233146697141889422394811200720817635007606418347246216418323113493506302640167
10: 
1.999018632710101138663409239129152861854310076062220826532008328824786927236540933057020104301232375
11: 
1.999510401978285491440043956861529326661081254266614810779837519236615390078719789044140796520274345
12: 
1.999755500937317536697426762400382912383323386504556323062753939321611287661284370644702025866990915
13: 
1.999877832711545540039946899212990477872263216888867413202466954233036366079897025359931465066825935
14: 
1.999938938749594648497845059170961691634186447969185808282677452968010724453480158889012554038686369
15: 
1.999969475434503292360189201418153043006796608216820644909453656234921657658569086286226322162157151
16: 
1.999984739347944107289059690853180523398789865045347828924870915759038438904118573567103314365400392
17: 
1.999992370110654554581262086662690173744461423887555531876842475084516571192165982892311479262694294
18: 
1.999996185171760268010734733416410670883028695620770951598826851042717888337484473992487986041191113
19: 
1.999998092616805432968528027719761428200428348135841577975196837806368081561631463543584620578204458
20: 
1.999999046316588514457316408446048445016706257736798957683555662453016630707735356535989845294224046

Kod w c++ (mathematica drogawa) na dole.


bieganie tego pierwiastka do 2 łatwo zrozumieć znów patrząc na
wielomian.

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

Rozszerzemy go dla ułatwienia obliczeń o dodatkowy pierwiastek
mnożąc przez (q-1). NIe zmienia to pozostąłych pierwiastków.

w = w*(q-1) =  q^(k+1) - 2 q^k + 1

[Przy okazji, robiąc wykres pierwiastków widać, że układają sie
na okregu jednostkowym i dodatkowy pierwiastek siedzi w okolicy x=2.
Spodziewam się więc, że ten wielomian podobny jest do
(q^k -1) (q-2) =    q^(k+1) - 2 q^k - q -2 ]

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

(2-q)q^k = 1

(2-q)q^k ma pierwiastek w 0 i 2. W okolicy 2 bardzo szybko rośnie,
(bo praktycznie wygląda jak funkcja liniowa (2-q)*2^k) i trafia
w jedynkę. Skoro przyblizęnie q^k = 2^k wydaje się dobre i w okolicy 
rozwiązania
(2-q)q^k = 1
to je zastosujmy do rozwiązania:

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

{{15, 1.9999694824218750000},
  {16, 1.9999847412109375000},
  {17, 1.9999923706054687500},
  {18, 1.9999961853027343750},
  {19, 1.9999980926513671875},
  {20, 1.9999990463256835938}}

Bardzo ładnie współgra z dokładnymi wynikami.


pzdr
bartekltg



#include <iostream>
#include <mpreal.h>
#include <iomanip>
using namespace std;

// kompilować z biblotekami -lmpfr -lgmp

int main(){
     const int precyzja = 100;
     mpfr::mpreal::set_default_prec(precyzja*1.2*log(10)/log(2));
     mpfr::mpreal x ;

     for (int k=2; k<21;k++)  {
         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) ;
         cout <<setprecision(precyzja)<< k<<": "<<  x << endl;
     }
     return 0;
}

[toc] | [prev] | [next] | [standalone]

#28586

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?

[toc] | [prev] | [next] | [standalone]

#28589

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

[toc] | [prev] | [next] | [standalone]

#28587

W dniu 15.05.2016 o 18:55, bartekltg pisze:
> bieganie tego pierwiastka do 2 łatwo zrozumieć znów patrząc na
> wielomian.
>
> w0= q^k - q^(k-1) - q^2 - q - 1

Tak z grubsza w = 2-1/(2^k)

[toc] | [prev] | [next] | [standalone]

#28588

On 16.05.2016 09:16, Borneq wrote:
> W dniu 15.05.2016 o 18:55, bartekltg pisze:
>> bieganie tego pierwiastka do 2 łatwo zrozumieć znów patrząc na
>> wielomian.
>>
>> w0= q^k - q^(k-1) - q^2 - q - 1

Wyciąłeś za dużo cytatu:


>>
>> (2-q)q^k ma pierwiastek w 0 i 2. W okolicy 2 bardzo szybko rośnie,
>> (bo praktycznie wygląda jak funkcja liniowa (2-q)*2^k) i trafia
>> w jedynkę. Skoro przyblizęnie q^k = 2^k wydaje się dobre i w okolicy rozwiązania
>> (2-q)q^k = 1
>> to je zastosujmy do rozwiązania:
>>
>> (2-q) = 1/2^k.
********************
>> q = 2 - 2^-k
********************
>>
>> {{15, 1.9999694824218750000},
>>  {16, 1.9999847412109375000},
>>  {17, 1.9999923706054687500},
>>  {18, 1.9999961853027343750},
>>  {19, 1.9999980926513671875},
>>  {20, 1.9999990463256835938}}
>>
>> Bardzo ładnie współgra z dokładnymi wynikami.


> Tak z grubsza w = 2-1/(2^k)


No brawo chłopie.

Skoro odpowiadasz, bądź łąskaw przeczytać posta;p


pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28590

On 16.05.2016 14:35, bartekltg wrote:
> On 16.05.2016 09:16, Borneq wrote:
>> W dniu 15.05.2016 o 18:55, bartekltg pisze:
>>> bieganie tego pierwiastka do 2 łatwo zrozumieć znów patrząc na
>>> wielomian.
>>>
>>> w0= q^k - q^(k-1) - q^2 - q - 1
>
> Wyciąłeś za dużo cytatu:
>
>
>>>
>>> (2-q)q^k ma pierwiastek w 0 i 2. W okolicy 2 bardzo szybko rośnie,
>>> (bo praktycznie wygląda jak funkcja liniowa (2-q)*2^k) i trafia
>>> w jedynkę. Skoro przyblizęnie q^k = 2^k wydaje się dobre i w okolicy
>>> rozwiązania
>>> (2-q)q^k = 1
>>> to je zastosujmy do rozwiązania:
>>>
>>> (2-q) = 1/2^k.
> ********************
>>> q = 2 - 2^-k
> ********************
>>>
>>> {{15, 1.9999694824218750000},
>>>  {16, 1.9999847412109375000},
>>>  {17, 1.9999923706054687500},
>>>  {18, 1.9999961853027343750},
>>>  {19, 1.9999980926513671875},
>>>  {20, 1.9999990463256835938}}
>>>
>>> Bardzo ładnie współgra z dokładnymi wynikami.
>
>
>> Tak z grubsza w = 2-1/(2^k)

Można też to ciut porawić.


q^k (2 - q) == 1

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

// y = 2-q

y = 1/(2-y)^k = 1/2^k 1/(1-y/2)^k =~=  1/2^k (1+y k/2)

y = 1/2^k / (1-k/2^(k+1) )

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


k, err_pierwszy wzor, err_drugi wzor
  {2, 0.1, 0.05},
  {3, 0.04, 0.007},
  {4, 0.01, 0.001},
  {5, 0.003, 0.0002},
  {6, 0.0008, 0.00002},
  {7, 0.0002, 4.*10^-6},
  {8, 0.00006, 6.*10^-7},
  {9, 0.00002, 9.*10^-8},
  {10, 5.*10^-6, 1.*10^-8},
  {11, 1.*10^-6, 2.*10^-9},
  {12, 4.*10^-7, 3.*10^-10},
  {13, 1.*10^-7, 4.*10^-11},
  {14, 3.*10^-8, 6.*10^-12},
  {15, 7.*10^-9, 9.*10^-13},
  {16, 2.*10^-9, 1.*10^-13},
  {17, 5.*10^-10, 2.*10^-14},
  {18, 1.*10^-10, 2.*10^-15},
  {19, 3.*10^-11, 3.*10^-16},
  {20, 9.*10^-12, 5.*10^-17}


I to liniowa aproksymacja, i to liniowa aproksymacja, a parę cyfr
znaczacych się pojawia ;-)

BTW,
q <- 2 - 1/q^k

Jest (w okolicy q=2) przekształceniem zwężającym. Iterując je
w granicy dostaniemy  oczekiwany wynik. W dodatku ma bardzo dobrą
stałą (~ 2^-k).
Jednak jest to zbieżność liniowa, więc matoda Newtona, mimo większej
komplikacji, jest lepsza. Obie wymagają jednokrotnego
policzenia q^k, co jest najbardziej kosztowną operacją.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28581

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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web