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