Spatial Systems Laboratory
March 11,2004
Snacks Today: Carl
Notes Today: Paul
Snacks Tuesday: Paul
Notes Tuesday: Brendan
Carl explains how the Moebius transform applies to what we have thus far for
Newton's Method on a generalized quadratic. After applying the transform, we
have P(n) = [a^(2^n-1)/(r1-r2)] * sum{k=0..2^n}
(-1)^(2^n-k)*(x^k)*binomial(2^n,k)*[r1*r2^(2^n-k)-r2*r1^(2^n-k)]
and Q(n) = [a^(2^n-1)/(r1-r2)] * sum{k=0..2^n}
(-1)^(2^n-k)*(x^k)*binomial(2^n,k)*[r2^(2^n-k)-r1^(2^n-k)],
where if ax^2 + bx + c is the generalized quadratic r1 = [-b+sqrt(b^2-4ac)]/2a
and r2 = [-b-sqrt(b^2-4ac)]/2a, so that a=a, b=-a*(r1+r2), c=a*r1*r2.
Sam explains how the Moebius transform got us to that conclusion.
x---->N(x)
| ^
| | M(-1).. that is, M inverse
| |
v |
M(x)-->[M(x)]^2
where N(x) is Newton's method applied to x, so [N(x)]^n will give P(n)/Q(n).
We take M(r1)=0 and M(r2)=infinity
Then define M(x) = y = (x-r1)/(x-r2).
So solving for x and plugging in y = (x-r1)/(x-r2) gives us x =
[r2*(x-r1)-r1*(x-r2)]/[(x-r1)-(x-r2)].
Now we can iterate this process to see that [N(x)]^n = M(-1)([M(x)]^(2^n)]).
Doing this gives the two formulas that Carl gave earlier.
One question and one comment arose during this explanation.
Firstly, no one was really sure why this transform should have the squaring
function in it. It seems like the general consensus is that it was just a
good guess, but might need to be further justified.
Secondly, the function M(-1)([M(x)]^(2^n)]), even though it is equal to
[N(x)]^n might not give P(n) and Q(n) even though it gives the same ratio
of P(n)/Q(n) since there might be some common factors in one of the forms
that aren't in the other.
Emilie explains where she and Paul are at in working with the new quadratic
recurrences.
Conjecture: b(n)b(n-k) = b(n-1)b(n-k+1) + b(n-(k-1)/2) + b(n-(k+1)/2) starting
b(i)=1 for i