Quantized state systems method

The quantized state systems (QSS) methods are a family of numerical integration solvers based on the idea of state quantization, dual to the traditional idea of time discretization. Unlike traditional numerical solution methods, which approach the problem by discretizing time and solving for the next (real-valued) state at each successive time step, QSS methods keep time as a continuous entity and instead quantize the system's state, instead solving for the time at which the state deviates from its quantized value by a quantum.

QSS methods are therefore neatly modeled by the DEVS formalism, a discrete-event model of computation, in contrast with traditional methods, which form discrete-time models of the continuous-time system. They satisfy strong stability and error bound properties not found in time-based discretization techniques, and they have been implemented in [PowerDEVS], a simulation engine for such discrete-event systems.

First-order QSS method – QSS1

Let an initial value problem be specified as follows.

${\dot {x}}(t)=f(x(t),t),\quad x(t_{0})=x_{0}.$

The first-order QSS method, known as QSS1, approximates the above system by

${\dot {x}}(t)=f(q(t),t),\quad q(t_{0})=x_{0}.$

where $x$ and $q$ are related by a hysteretic quantization function

$q(t)={\begin{cases}x(t)&&{\text{if }}\left|x(t)-q(t)\right|\geq \Delta Q\\q(t^{-})&&{\text{otherwise}}\end{cases}}$

where $\Delta Q$ is called a quantum. Notice that this quantization function is hysteretic because it has memory: not only is its output a function of the current state $x(t)$, but it also depends on its old value, $q(t^{-})$.

This formulation therefore approximates the state by a piecewise constant function, $q(t)$, that updates its value as soon as the state deviates from this approximation by one quantum.

The multidimensional formulation of this system is almost the same as the single-dimensional formulation above: the $k^{\text{th}}$ quantized state $q_{k}(t)$ is a function of its corresponding state, $x_{k}(t)$, and the state vector ${\vec {x}}(t)$ is a function of the entire quantized state vector, ${\vec {q}}(t)$:

${\vec {x}}(t)=f({\vec {q}}(t),t)$

High-order QSS methods – QSS2 and QSS3

The second-order QSS method, QSS2, follows the same principle as QSS1, except that it defines $q(t)$ as a piecewise linear approximation of the trajectory $x(t)$ that updates its trajectory as soon as the two differ from each other by one quantum. The pattern continues for higher-order approximations, which define the quantized state $q(t)$ as successively higher-order polynomial approximations of the system's state.

It is important to note that, while in principle a QSS method of arbitrary order can be used to model a continuous-time system, it is seldom desirable to use methods of order higher than four, as the Abel–Ruffini theorem implies that the time of the next quantization, $t$, cannot (in general) be explicitly solved for algebraically when the polynomial approximation is of degree greater than four, and hence must be approximated iteratively using a root-finding algorithm. In practice, QSS2 or QSS3 proves sufficient for many problems and the use of higher-order methods results in little, if any, additional benefit.

Theoretical properties

In 2001, Ernesto Kofman proved a remarkable property of the quantized-state system simulation method: namely, that when the technique is used to solve a stable linear time-invariant (LTI) system, the global error is bounded by a constant that is proportional to the quantum, but (crucially) independent of the duration of the simulation. More specifically, for a stable LTI system with the state-transition matrix $A$, for a multidimensional it was shown in [CK06] that the absolute error vector ${\vec {e}}(t)$ is bounded above by

$\left|{\vec {e}}(t)\right|\leq \left|V\right|\ \left|\Re \left(\Lambda \right)^{-1}\Lambda \right|\ \left|V^{-1}\right|\ \Delta {\vec {Q}}$

where $\Delta {\vec {Q}}$ is the vector of state quanta, $A=V\Lambda V^{-1}$ is the eigendecomposition or Jordan canonical form of $A$, and $\left|\,\cdot \,\right|$ denotes the element-wise absolute value operator (not to be confused with the determinant or norm).

It is worth noticing that this spectacular error bound comes at a price: the global error for a stable LTI system is also, in a sense, bounded below by a the quantum itself, at least for the first-order QSS1 method. This is due to the fact that, unless the approximation happens to coincide exactly with the correct value (an event which will almost surely not happen), it will simply continue oscillating around the equilibrium, as the state derivative is always (by definition) guaranteed to change by exactly one quantum outside of the equilibrium. Avoiding this condition would require finding a reliable technique for dynamically lowering the quantum in a manner analogous to adaptive stepsize methods in traditional simulation algorithms.

Software implementation

The QSS Methods can be implemented as a discrete event system and simulated in any DEVS simulator.

QSS methods constitute the main numerical solver for PowerDEVS[BK011] software. They have also been implemented in as a stand alone version.

References

• [CK06] Francois E. Cellier and Ernesto Kofman (2006). Continuous System Simulation (first ed.). Springer. ISBN 978-0-387-26102-7.

• [BK11] Bergero, Federico and Kofman, Ernesto (2011). "PowerDEVS: a tool for hybrid system modeling and real-time simulation" (first ed.). Society for Computer Simulation International,San Diego.{{cite news}}: CS1 maint: multiple names: authors list (link)

External links

• Stand-alone implementation of QSS Methods
• PowerDEVS at SourceForge