Quantized state systems method: Difference between revisions

Revision as of 19:57, 7 July 2015

Latest revision as of 18:56, 27 May 2025

(19 intermediate revisions by 17 users not shown)

Line 1:

The '''quantized state systems''' ('''QSS''') '''methods''' are a family of numerical integration solvers based on the idea of state quantization, [[dual (mathematics)|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 [[Quantization (signal processing)|quantize]] the system's state, instead solving for the ''time'' at which the state deviates from its quantized value by a ''quantum''.

They can also have many advantages compared to classical algorithms.<ref>{{cite journal |authorsauthor1=Migoni, Gustavo, |author2=Ernesto Kofman, and |author3=François Cellier |title=Quantization-based new integration methods for stiff ordinary differential equations|year=2011 |journal = Simulation |volume=88 |issue=4 |pages=387&ndash;407 |doi=10.1177/0037549711403645 |url=http://sim.sagepub.com/content/88/4/387 |url-access=subscription }}</ref>

They inherently allow for modeling discontinuities in the system due to their discrete-event nature and asynchronous nature. They also allow for explicit root-finding and detection of zero-crossing using ''explicit'' algorithms, avoiding the need for iteration---a fact which is is especially important in the case of stiff systems, where traditional time-stepping methods require a heavy computational penalty due to the requirement to implicitly solve for the next system state. Finally, QSS methods satisfy remarkable global stability and error bounds, described below, which are not satisfied by classical solution techniques.

By their nature, 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 have therefore been implemented in [[PowerDEVS#References|[PowerDEVS]]], a simulation engine for such discrete-event systems.

Line 9:

==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 | issue=2 |pages=76&ndash;89 |url doi=http:10.1177//sim0037549702078002206 | citeseerx=10.sagepub1.com/content/78/2/761.short640.1903 | s2cid=20959777 }}</ref> a remarkable property of the quantized-state system simulation method: namely, that when the technique is used to solve a [[Exponential stability|stable]] [[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 stable multidimensional LTI system with the [[state-transition matrix]] <math>A</math> and [[State-space representation#Linear systems|input matrix]] <math>B</math>, it was shown in [CK06] that the absolute error vector <math>\vec{e}(t)</math> is bounded above by

:<math>

:<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>

\left| \vec{e}(t) \right| \leq

:<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> +

\left| V \right|\ \left| \Re\left(\Lambda\right)^{-1} V^{-1} B \right|\ \Delta\vec{u}</math>

where <math>\Delta\vec{Q}</math> is the vector of state quanta, <math>A\Delta\vec{u}</math> =is the vector with quanta adopted in the input signals, <math>V \Lambda V^{-1} = A</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 spectacularremarkable 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 thatbecause, 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 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 discrete time simulation algorithms.

==First-order QSS method – QSS1==

Line 44 ⟶ 47:

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, <math>t</math>, cannot (in general) be [[Explicit and implicit methods|explicitly solved]] for [[algebraic solution|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.

==Backward QSS method – BQSS==

{{Empty section|date=May 2013}}

==Linearly implicit QSS method – LIQSS==

{{Empty section|date=May 2013}}

==Software implementation==

Line 61 ⟶ 56:

== References ==

{{Reflist}}

* [CK06] {{cite book|author author1= Francois E. Cellier and |author2=Ernesto Kofman |name-list-style=amp | year = 2006| title = Continuous System Simulation| publisher = Springer| isbn = 978-0-387-26102-7 |edition=first}}

* [BK11] {{cite news|author author1= Bergero, Federico and |author2=Kofman, Ernesto |name-list-style=amp | year = 2011| title = PowerDEVS: a tool for hybrid system modeling and real-time simulation| publisher = Society for Computer Simulation International, San Diego | id = |edition=first}}

* [BK11] {{cite news|author = Bergero, Federico and Kofman, Ernesto | year = 2011| title = PowerDEVS: a tool for hybrid system modeling and real-time simulation| publisher = Society for Computer Simulation International,San Diego | id = |edition=first}}

==External links==