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.61803398874989484820458683436563811772030917980576
2862135448622705260462818902449707207204189391137
3:
1.83928675521416113255185256465328660042417874609759
2246778758639404203222081966425738435419428307014
4:
1.92756197548292530426190586173662216869855425516338
4727146647038009666062297815559149818253461890653
5:
1.96594823664548533718993737593440139615132717745686
1393236934508442252712871886881734818665554630472
6:
1.98358284342432633038562929339142575273008086556882
1753216359065656702278014172402986575070226899797
7:
1.99196419660503502109774175458437496347931896005315
7995244782153400951980309622183563141577022719017
8:
1.99603117973541458981531790175583977448937968094522
1927634853627284595269945627520379784497496677719
9:
1.99802947026228669866233146697141889422394811200720
817635007606418347246216418323113493506302640167
10:
1.99901863271010113866340923912915286185431007606222
0826532008328824786927236540933057020104301232375
11:
1.99951040197828549144004395686152932666108125426661
4810779837519236615390078719789044140796520274345
12:
1.99975550093731753669742676240038291238332338650455
6323062753939321611287661284370644702025866990915
13:
1.99987783271154554003994689921299047787226321688886
7413202466954233036366079897025359931465066825935
14:
1.99993893874959464849784505917096169163418644796918
5808282677452968010724453480158889012554038686369
15:
1.99996947543450329236018920141815304300679660821682
0644909453656234921657658569086286226322162157151
16:
1.99998473934794410728905969085318052339878986504534
7828924870915759038438904118573567103314365400392
17:
1.99999237011065455458126208666269017374446142388755
5531876842475084516571192165982892311479262694294
18:
1.99999618517176026801073473341641067088302869562077
0951598826851042717888337484473992487986041191113
19:
1.99999809261680543296852802771976142820042834813584
1577975196837806368081561631463543584620578204458
20:
1.99999904631658851445731640844604844501670625773679
8957683555662453016630707735356535989845294224046

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;
}

do góry

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?

do góry

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)

do góry

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

do góry

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 <b...@g...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_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

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

do góry