A reference request for linear iterations with "rounding"

Question

Given a vector $x$, define $[x]$ to be the vector obtained by rounding each entry of $x$ to the nearest integer. For definiteness, lets assume that midpoints round up, e.g., $2.5$ rounds to $3$.

I would appreciate pointers to any literature which analyzes dynamical systems of the form

$$ x(t+1) = A x(t) + B [x(t)].$$

Here $A,B$ are fixed matrices.

I would like to find out what is known about such systems. Unfortunately, I don't even know what keywords to search for. Pointers to even tangentially related literature would be very welcome!

Answer 1

The dynamical system you have presented is in the class of discrete-time piecewise-affine (PWA) dynamical systems, and they are notoriously hard to analyze. The general form of a discrete-time PWA system is:

$x^+ = A_i x + B_i u + c_i$, for $x \in \Omega_i \subset \mathbb{R}^n$

where $x \in \mathbb{R}^n$ is the state vector, $u \in \mathbb{R}^m$ is the input vector, $c_i$ is a constant vector, and $\Omega_i$ is a region of the state-space. Note that $x^+$ is the updated state vector. Essentially, we have different affine dynamical systems on different "patches" of the state-space $\mathbb{R}^n$. This has been studied quite a bit in the past couple of decades by the control theory community. A good paper for you to start would be:

• Analysis of discrete-time piecewise affine and hybrid systems (2002)

Another way of looking at the dynamical system you presented is to think of it as a linear dynamical system with quantized feedback. The following paper by Brockett might interest you too:

• Quantized Feedback Stabilization of Linear Systems (2000)

However, your dynamical system is PWA over an infinite number of patches, and I do believe that the PWA systems literature considers only dynamical systems over a finite number of patches.

Answer 2

I would suggest searching for round-off error, floating-point representation and floating-point precision and numerical simulation of dynamical systems.

This is equivalent to doing numerical simulation computations using integers for all of the variables. Integers, short and long, signed and unsigned, are represented using a fixed number of bits in computational systems. Floating point numbers are also represented with a fixed number of bits, with a certain number allocation to the mantissa, and the remainder of bits allocated to the exponent in base $2$, representing what the mantissa is multiplied by

This is also equivalent to what must happen in fixed-digit or limited precision representation of floating point digits in any computerized simulation of any dynamical systems. The numerical simulation is only correct up to a certain number of digits, and the imprecision can build up rather quickly depending upon the variance of the elements of the matrix. Rounding occurs in every floating-point representation using a fixed number of bits; it just occurs at smaller magnitudes with larger number of bits used for the mantissa.

There are two points to consider:

• fixed point errors in the numerical simulation (or round-off error), due to limited precision representation of floating point numbers or fixed-number-of-bits representation of integers

• the dynamics of the system itself. The dynamics may be such that the sequence is diverging, and that the series will quicly go beyond the limit of what the numerical representation system is capable of dealing with: effectively hitting infinity (for the representation system) and not being able to go further. Even if the dynamics are such that the system is oscillatory or chaotic around an attractor, the round-off error in the numerical simulation may begin to dominate after a set number of iterations.

You will find a lot of literature about this from the 1950's and 1960's about matrix representations and matrix manipulations with computers, and a lot about this if you research floating-point representation standards.

Answer 3

A simple example which leads to open questions (afaik) is $(x,y)->[(\frac{x}{2}-y,x)]$. Without the rounding, the orbit of a given point belongs to an ellipse $x^2-\frac{xy}2+y^2=k$. This rounded version is a bijection on $\mathbb{Z} \times \mathbb{Z}$. It seems likely that all orbits are finite, but afaik this is not known to be true. A relevant reference seems to be The arithmetic of discretized rotations .

Notes:

1. This is not exactly in the form you request but it is equivalent since $A$ is the $0$ matrix.
2. I recall a problem like this floating around Ohio State University in the late 80's although it may not have been exactly this.