Applying repeated doubling to an update Matrix

Question

Given a rule to obtain a new $x,y$ positions from an initial $x_0,y_0$

The rule is $ \binom{x'}{y'} = \begin{pmatrix} v_x & -v_y \\ v_y & v_x \end{pmatrix} \binom{x}{y}$

$x' = v_x x - v_y y$

$y' = v_y x + v_x y$

$f(x,y) = (v_x x - v_y y, v_y x + v_x y)$

Now let's say I wanted to use this rule to update a position $x_0,y_0$

How can I use repeated doubling to calculate the position after updating it $n$ times without having to manually update the position $n$ times

For instance lets say we started at position $(-10, 0) $ and we wanted to update this position 5 times and our given value for $(u_x,u_y) = (\frac{1}{2},\frac{1}{2})$

after the first update(n=1) the position would be $(-5,-5)$ and then the 5th update(n=5) the position would be $( \frac{5}{4}, \frac{5}{4}) $

How could I calculate the position for $( \frac{5}{4}, \frac{5}{4}) $ without having to calculate n = 2 or n= 3 or n= 4 or simply just using the concept of repeated doubling

Answer 1

Assuming that $v_x$ and $v_y$ are constants, note that the update rule is equivalent to

$$x'+iy' = (v_x + iv_y)(x + iy) $$

where $i$ is the imaginary unit. So, if we write $v_x+iv_y$ in the polar form $re^{i\theta}$, then after $n$ updates, the result will be

\begin{align*} (v_x+iv_y)^n(x+iy) &= r^n(\cos(n\theta)+i\sin(n\theta))(x+iy) \\ &= r^n(x\cos(n\theta)-y\sin(n\theta)) + ir^n(x\sin(n\theta)+y\cos(n\theta)). \end{align*}

Reading out its real and imaginary part will yield the desired coordinates. In doing so, all you need to know is

$$r = \lvert v_x+iv_y\rvert = \sqrt{v_x^2+v_y^2}$$

and

$$\theta = \arg(v_x + iv_y) = \operatorname{arctan2}(v_y, v_x), $$

where $\operatorname{arctan2}$ is the 2-argument arctangent function.

The following is a Python code for this:

import math

# arguments
(x, y) = (-10, 0);
(v_x, v_y) = (1/2, 1/2);
n = 5;

# computation
r = math.sqrt(v_x**2 + v_y**2);
th = math.atan2(v_y, v_x);
x_n = (r**n)*(x*math.cos(n*th) - y*math.sin(n*th));
y_n = (r**n)*(x*math.sin(n*th) + y*math.cos(n*th));

# print the result
print(x_n, y_n);

The outcome will be

1.2500000000000009 1.2500000000000004

which is $(5/4, 5/4)$ ignoring the numerical errors due to rounding.