Quantized state systems method: Difference between revisions

Revision as of 10:12, 6 July 2015

Revision as of 11:22, 6 July 2015

Line 1:

{{Multiple issues|{{no footnotes|date=July 2013}}{{technical|date=July 2013}}}}

The '''quantized state systems (QSS) methods''' [[PowerDEVS#References|[CK06]]] are a family of numerical integration solvers based on the idea of state quantization, which are [[dual]] to the traditional idea of time discretization.

Unlike traditional [[numerical methods for ordinary differential equations|numerical solution methods]], which approach the problem by [[Discretization|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 simulation|discrete-event]] [[model of computation]], in contrast with traditional methods, which form [[Discrete time and continuous time#Discrete_time|discrete-time]] models of the [[Discrete time and continuous time#Continuous_time|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#References|[PowerDEVS]]], a simulation engine for such discrete-event systems.

==First-order QSS method – QSS1==

Line 43 ⟶ 44:

==Theoretical properties==

In 2001, Ernesto Kofman proved<ref>{{cite journal | last=Kofman | first=Ernesto |title=A second-order approximation for DEVS simulation of continuous systems|year=2002 |journal = Simulation |volume=78 |pages=76&ndash;89 |url=http://sim.sagepub.com/content/78/2/76.short }}</ref> a remarkable property of the quantized-state system simulation method: namely, that when the technique is used to solve a [[LTI system theory|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 [[Exponential stability|stable]] LTI system with the [[state-transition matrix]] <math>A</math>, it was shown that the absolute error vector <math>\vec{e}(t)</math> is bounded above by

{{Empty section|date=May 2013}}

:<math>\left| \vec{e}(t) \right| \leq \left| V \right|\ \left| \Re\left(\Lambda\right)^{-1} \Lambda \right|\ \left| V^{-1} \right|\ \Delta \vec{Q}</math>

where <math>\Delta\vec{Q}</math> is the vector of state quanta, <math>A = V \Lambda V^{-1}</math> is the [[Eigendecomposition#Eigendecomposition_of_a_matrix|eigendecomposition]] or [[Jordan canonical form]] of <math>A</math>, and <math>\left|\,\cdot\,\right|</math> denotes the element-wise [[absolute-value]] operator (not to be confused with the [[determinant]] or [[Norm (mathematics)|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 dynamically lowering the quantum in a manner analogous to [[adaptive stepsize methods]] in traditional simulation algorithms.

==Software implementation==

Line 49 ⟶ 56:

QSS methods constitute the main numerical solver for [[PowerDEVS]][[PowerDEVS#References|[BK011]]] software.

They have also been implemented in as a stand alone version.

== References ==