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

Groups > pl.comp.programming > #28590

Re: Liczby Fibonacciego rzędu N

Cross-posted to 2 groups.

Show all headers | View raw

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

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