Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
1  
Do you understand its behavior when $x$, $A$, and $B$ are all just real numbers, rather than vectors and matrices? Its behavior already seems quite complicated. –  Joseph O'Rourke Oct 28 '10 at 23:49
    
@Joseph O'Rourke - no, I don't. –  alex Oct 29 '10 at 0:00
    
I did not say this in the question, but I have a very specific system of this form which I want to analyze, and whose behavior I do understand when $x,A,B$ are in $R^3$. I'm looking for any related work out there. Its true that a complete classification of the behavior of such systems for all dimensions seems like too much to hope for. –  alex Oct 29 '10 at 0:04
    
What are the restrictions on $A, B,$ and $x(0)$ in the type of system which you do already understand? What physical system are you modeling? (My question is merely out of curiousity; sometimes, however, knowing the underlying system being modeled helps to constrain some of the equations and assumptions about the dynamical equations...) –  sleepless in beantown Oct 29 '10 at 0:43
    
One keyphrase that might be remotely related is iterative rounding, used in multiobjective optimization problems to obtain approximations. –  Joseph O'Rourke Oct 29 '10 at 0:57

3 Answers 3

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:

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:

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.

share|improve this answer
1  
Just to add to this: rounding is a bit of a tricky function to handle though. Although I suppose one could obtain rounding behavior (en.wikipedia.org/wiki/Floor_and_ceiling_functions#Rounding) through the use of integer variables (switch between floor/ceiling functions depending on sign), which leads to MLD (Mixed Logical Dynamical) systems, which has been shown to be equivalent to PWAs in W. Heemels, B. D. Schutter, and A. Bemporad, "Equivalence of hybrid dynamical models", Automatica, vol. 37, no. 7, pp. 1085-1091, July 2001 –  Gilead Nov 10 '10 at 6:14

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.

share|improve this answer

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.