View source for Differential-algebraic system of equations

{{Differential equations}}
In [[Mathematics|mathematics]], a '''differential-algebraic system of equations''' ('''DAE''') is a [[System of equations|system of equations]] that either contains [[Differential equation|differential equation]]s and [[Algebraic equation|algebraic equation]]s, or is equivalent to such a system.

The set of the solutions of such a system is a ''differential algebraic variety'', and corresponds to an [[Ideal (ring theory)|ideal]] in a [[Differential algebra|differential algebra]] of differential polynomials.

In the [[Univariate|univariate]] case, a DAE in the  variable ''t'' can be written as a single equation of the form
:<math>F(x'(t), x(t),t)=0,</math>
where <math>x(t)</math> is a vector of unknown functions.

They are distinct from [[Ordinary differential equation|ordinary differential equation]] (ODE) in that a DAE is not completely solvable for the derivatives of all components of the function ''x'' because these may not all appear (i.e. some equations are algebraic); technically the distinction between an implicit ODE system [that may be rendered explicit] and a DAE system is that the Jacobian matrix <math>\frac{\partial F(u, v, t)}{\partial u}</math> is a [[Singular matrix|singular matrix]] for a DAE system.<ref name="AscherPetzold1998">{{cite book|author1=Uri M. Ascher|author2=Linda R. Petzold|title=Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations|year=1998|publisher=SIAM|isbn=978-1-61197-139-2|page=12}}</ref> This distinction between ODEs and DAEs is made because DAEs have different characteristics and are generally more difficult to solve.<ref name="IlchmannReis2014">{{cite book|author1=Achim Ilchmann|author2=Timo Reis|title=Surveys in Differential-Algebraic Equations II|year=2014|publisher=Springer|isbn=978-3-319-11050-9|pages=104–105}}</ref>

In practical terms, the distinction between DAEs and ODEs is often that the solution of a DAE system depends on the derivatives of the input signal and not just the signal itself as in the case of ODEs;<ref name="MerkerSchwarz2001">{{cite book |editor=Renate Merker |editor2=Wolfgang Schwarz|title=System Design Automation: Fundamentals, Principles, Methods, Examples|url=https://archive.org/details/systemdesignauto00teic |url-access=limited |year=2001|publisher=Springer Science & Business Media|isbn=978-0-7923-7313-1|page=[https://archive.org/details/systemdesignauto00teic/page/n221 221]}}</ref> this issue is commonly encountered in [[Nonlinear system|nonlinear system]]s with [[Hysteresis|hysteresis]],<ref name="BrenanCampbell1996">{{cite book|author1=K. E. Brenan|author2=S. L. Campbell|author3=L. R. Petzold|title=Numerical Solution of Initial-value Problems in Differential-algebraic Equations|year=1996|publisher=SIAM|isbn=978-1-61197-122-4|pages=173–177}}</ref> such as the [[Physics:Schmitt trigger|Schmitt trigger]].<ref>{{Cite book | doi = 10.1016/S1570-8659(04)13006-8| chapter = Modelling and Discretization of Circuit Problems| title = Numerical Methods in Electromagnetics| volume = 13| pages = 523| series = Handbook of Numerical Analysis| year = 2005| last1 = Günther | first1 = M. | last2 = Feldmann | first2 = U. | last3 = Ter Maten | first3 = J. | isbn = 978-0-444-51375-5| url = https://research.tue.nl/nl/publications/7e8db823-0664-4b2d-b03d-7c5bd5edb0b5}}, pp. 529-531</ref>

This difference is more clearly visible if the system may be rewritten so that instead of ''x'' we consider a pair <math>(x,y)</math> of vectors of dependent variables and the DAE has the form
::<math>\begin{align}\dot x(t)&=f(x(t),y(t),t),\\0&=g(x(t),y(t),t).\end{align}</math>
:where <math>x(t)\in\R^n</math>, <math>y(t)\in\R^m</math>, <math>f:\R^{n+m+1}\to\R^n</math> and <math>g:\R^{n+m+1}\to\R^m.</math>

A DAE system of this form is called ''semi-explicit''.<ref name="AscherPetzold1998" /> Every solution of the second half ''g'' of the equation defines a unique direction for ''x'' via the first half ''f'' of the equations, while the direction for ''y'' is arbitrary. But not every point ''(x,y,t)'' is a solution of ''g''. The variables in ''x'' and the first half ''f'' of the equations get the attribute ''differential''. The components of ''y'' and the second half ''g'' of the equations are called the ''algebraic'' variables or equations of the system. [The term ''algebraic'' in the context of DAEs only means ''free of derivatives'' and is not related to (abstract) algebra.]

The solution of a DAE consists of two parts, first the search for consistent initial values and second the computation of a trajectory. To find consistent initial values it is often necessary to consider the derivatives of some of the component functions of the DAE. The highest order of a derivative that is necessary for this process is called the ''differentiation index''. The equations derived in computing the index and consistent initial values may also be of use in the computation of the trajectory. A semi-explicit DAE system can be converted to an implicit one by decreasing the differentiation index by one, and vice versa.<ref>Ascher and Petzold, p. 234</ref>

== Other forms of DAEs ==
The distinction of DAEs to ODEs becomes apparent if some of the dependent variables occur without their derivatives. The vector of dependent variables may then be written as pair <math>(x,y)</math> and the system of differential equations of the DAE appears in the form
::<math> F\left(\dot x, x, y, t\right) = 0 </math>
where
* <math>x</math>, a vector in <math>\R^n</math>, are dependent variables for which derivatives are present (''differential variables''),
* <math>y</math>, a vector in <math>\R^m</math>, are dependent variables for which no derivatives are present (''algebraic variables''),
* <math>t</math>, a scalar (usually time) is an independent variable.
* <math>F</math> is a vector of <math>n+m</math> functions that involve subsets of these <math>n+m+1</math> variables and <math>n</math> derivatives.

As a whole, the set of DAEs is a function
::<math> F: \R^{(2n+m+1)} \to \R^{(n+m)}. </math>

Initial conditions must be a solution of the system of equations of the form
::<math> F\left(\dot x(t_0),\, x(t_0), y(t_0), t_0 \right) = 0. </math>

== Examples ==
The behaviour of a [[Physics:Pendulum|pendulum]] of length ''L'' with center in (0,0) in Cartesian coordinates (''x'',''y'') is described by the [[Euler–Lagrange equation]]s
::<math>\begin{align}
\dot x&=u,&\dot y&=v,\\
\dot u&=\lambda x,&\dot v&=\lambda y-g,\\
x^2+y^2&=L^2,
\end{align}</math>
where <math>\lambda</math> is a [[Lagrange multiplier]]. The momentum variables ''u'' and ''v'' should be constrained by the law of conservation of energy and their direction should point along the circle. Neither condition is explicit in those equations. Differentiation of the last equation leads to
::<math>\begin{align}
&&\dot x\,x+\dot y\,y&=0\\
\Rightarrow&& u\,x+v\,y&=0,
\end{align}</math>
restricting the direction of motion to the tangent of the circle. The next derivative of this equation implies
::<math>\begin{align}
&&\dot u\,x+\dot v\,y+u\,\dot x+v\,\dot y&=0,\\
\Rightarrow&& \lambda(x^2+y^2)-gy+u^2+v^2&=0,\\
\Rightarrow&& L^2\,\lambda-gy+u^2+v^2&=0,
\end{align}</math>
and the derivative of that last identity simplifies to <math>L^2\dot\lambda-3gv=0</math> which implies the conservation of energy since after integration the constant <math>E=\tfrac32gy-\tfrac12L^2\lambda=\frac12(u^2+v^2)+gy</math> is the sum of kinetic and potential energy.

To obtain unique derivative values for all dependent variables the last equation was three times differentiated. This gives a differentiation index of 3, which is typical for constrained mechanical systems.

If initial values <math>(x_0,u_0)</math> and a sign for ''y'' are given, the other variables are determined via <math>y=\pm\sqrt{L^2-x^2}</math>, and if <math>y\ne0</math> then <math>v=-ux/y</math> and <math>\lambda=(gy-u^2-v^2)/L^2</math>. To proceed to the next point it is sufficient to get the derivatives of ''x'' and ''u'', that is, the system to solve is now

:: <math>\begin{align}

\dot x&=u,\\
\dot u&=\lambda x,\\[0.3em]
0&=x^2+y^2-L^2,\\
0&=ux+vy,\\
0&=u^2-gy+v^2+L^2\,\lambda.
\end{align}</math>
This is a semi-explicit DAE of index 1. Another set of similar equations may be obtained starting from <math>(y_0,v_0)</math> and a sign for ''x''.

DAEs also naturally occur in the modelling of circuits with non-linear devices. [[Engineering:Modified nodal analysis|Modified nodal analysis]] employing DAEs is used for example in the ubiquitous [[Software:SPICE|SPICE]] family of numeric circuit simulators.<ref name="IlchmannReis2013">{{cite book|editor=Achim Ilchmann |editor2=Timo Reis|title=Surveys in Differential-Algebraic Equations I|year=2013|publisher=Springer Science & Business Media|isbn=978-3-642-34928-7|author=Ricardo Riaza|chapter=DAEs in Circuit Modelling: A Survey}}</ref> Similarly, [[Organization:Fraunhofer Society|Fraunhofer's]] Analog Insydes [[Software:Mathematica|Mathematica]] package can be used to derive DAEs from a [[Engineering:Netlist|netlist]] and then simplify or even solve the equations symbolically in some cases.<ref>{{Cite book | doi = 10.1007/978-1-4020-6149-3_4| chapter = Improving Efficiency and Robustness of Analog Behavioral Models| title = Advances in Design and Specification Languages for Embedded Systems| pages = 53| year = 2007| last1 = Platte | first1 = D. | last2 = Jing | first2 = S. | last3 = Sommer | first3 = R. | last4 = Barke | first4 = E. | isbn = 978-1-4020-6147-9}}</ref><ref>{{Cite book | doi = 10.1007/978-3-642-23568-9_17| chapter = Fast and Robust Symbolic Model Order Reduction with Analog Insydes| title = Computer Algebra in Scientific Computing| volume = 6885| pages = 215| series = Lecture Notes in Computer Science| year = 2011| last1 = Hauser | first1 = M. | last2 = Salzig | first2 = C. | last3 = Dreyer | first3 = A. | isbn = 978-3-642-23567-2}}</ref> It is worth noting that the index of a DAE (of a circuit) can be made arbitrarily high by cascading/coupling via capacitors operational amplifiers with [[Positive feedback|positive feedback]].<ref name="BrenanCampbell1996" />

== Semi-explicit DAE of index 1 ==
DAE of the form
::<math>\begin{align}\dot x&=f(x,y,t),\\0&=g(x,y,t).\end{align}</math>
are called semi-explicit. The index-1 property requires that ''g'' is [[Implicit function theorem|solvable]] for ''y''. In other words, the differentiation index is 1 if by differentiation of the algebraic equations for ''t'' an implicit ODE system results,
::<math>\begin{align}
\dot x&=f(x,y,t)\\
0&=\partial_x g(x,y,t)\dot x+\partial_y g(x,y,t)\dot y+\partial_t g(x,y,t),
\end{align}</math>
which is solvable for <math>(\dot x,\,\dot y)</math> if <math>\det\left(\partial_y g(x,y,t)\right)\ne 0.</math>

Every sufficiently smooth DAE is almost everywhere reducible to this semi-explicit index-1 form.

== Numerical treatment of DAE and applications ==

Two major problems in solving DAEs are ''index reduction'' and ''consistent initial conditions''. Most numerical solvers require ordinary differential equations and algebraic equations of the form

::<math>\begin{align}\frac{dx}{dt}&=f\left(x,y,t\right),\\0&=g\left(x,y,t\right).\end{align}</math>

It is a non-trivial task to convert arbitrary DAE systems into ODEs for solution by pure ODE solvers. Techniques which can be employed include ''[[Pantelides algorithm]]'' and ''dummy derivative index reduction method''. Alternatively, a direct solution of high-index DAEs with inconsistent initial conditions is also possible. This solution approach involves a transformation of the derivative elements through ''orthogonal collocation on finite elements'' or ''direct transcription'' into algebraic expressions. This allows DAEs of any index to be solved without rearrangement in the open equation form

::<math>\begin{align}0&=f\left(\frac{dx}{dt},x,y,t\right),\\0&=g\left(x,y,t\right).\end{align}</math>

Once the model has been converted to algebraic equation form, it is solvable by large-scale nonlinear programming solvers (see [[Software:APMonitor|APMonitor]]).

=== Tractability ===
Several measures of DAEs tractability in terms of numerical methods have developed, such as ''differentiation index'', ''perturbation index'', ''tractability index'', ''geometric index'', and the ''Kronecker index''.<ref name="Riaza2008">{{cite book|author=Ricardo Riaza|title=Differential-algebraic Systems: Analytical Aspects and Circuit Applications|url=https://archive.org/details/differentialalge00riaz|url-access=limited|year=2008|publisher=World Scientific|isbn=978-981-279-181-8|pages=[https://archive.org/details/differentialalge00riaz/page/n19 5]–8}}</ref><ref>{{cite journal |last1=Takamatsu |first1=Mizuyo |last2=Iwata |first2=Satoru |title=Index characterization of differential-algebraic equations in hybrid analysis for circuit simulation |journal=International Journal of Circuit Theory and Applications |date=2008 |pages=n/a |doi=10.1002/cta.577 |s2cid=3875504 |url=http://www.ise.chuo-u.ac.jp/ise-labs/takamatsu-lab/takamatsu/metr/METR08-10.pdf |access-date=9 November 2022 |language=en |url-status=dead |archive-url=https://web.archive.org/web/20141216161815/http://www.ise.chuo-u.ac.jp/ise-labs/takamatsu-lab/takamatsu/metr/METR08-10.pdf |archive-date=16 December 2014}}</ref>

== Structural analysis for DAEs ==
We use the <math>\Sigma</math>-method to analyze a DAE. We construct for the DAE a signature matrix <math>\Sigma=(\sigma_{i,j})</math>, where each row corresponds to each equation <math>f_i</math> and each column corresponds to each variable <math>x_j</math>. The entry in position <math>(i,j)</math> is <math>\sigma_{i,j}</math>, which denotes the highest order of derivative to which <math>x_j</math> occurs in <math>f_i</math>, or <math>-\infty</math> if <math>x_j</math> does not occur in <math>f_i</math>.

For the pendulum DAE above, the variables are <math>(x_1,x_2,x_3,x_4,x_5)=(x,y,u,v,\lambda)</math>. The corresponding signature matrix is
:<math>\Sigma =
\begin{bmatrix}
1 & - & 0^\bullet & - & - \\
- & 1^\bullet & - & 0 & - \\
0 & - & 1 & - & 0^\bullet \\
- & 0 & - & 1^\bullet & 0 \\
0^\bullet & 0 & - & - & -
\end{bmatrix}
</math>

== See also ==
* [[Algebraic differential equation]], a different concept despite the similar name
* [[Delay differential equation]]
* [[Partial differential algebraic equation]]
* [[Modelica]] Language

== References ==
{{reflist}}

== Further reading ==
{{div col|colwidth=30em}}

=== Books ===
* {{cite book
|last1 = Hairer
|first1 = E.
|last2 = Wanner
|first2 = G.
|title = Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems
|publisher = Springer-Verlag
|location = Berlin
|edition = 2nd revised
|year = 1996
}}
* {{cite book
|first1 = Uri M.
|last1 = Ascher
|first2 = Linda R.
|title = Computer Methods for Ordinary Differential equations and Differential-Algebraic equations
|publisher = SIAM
|location = Philadelphia
|year = 1998
|isbn = 978-0-89871-412-8
}}
* {{cite book
|url = https://books.google.com/books?id=iRZPqCwkI_IC
|title = Differential-algebraic equations: analysis and numerical solution
|first1=Peter
|last1=Kunkel
|first2=Volker Ludwig
|last2=Mehrmann
|publisher = European Mathematical Society
|location=Zürich, Switzerland
|year=2006
|isbn=978-3-03719-017-3
}}
* {{cite book|author=Kazuo Murota|title=Matrices and Matroids for Systems Analysis|year=2009|publisher=Springer Science & Business Media|isbn=978-3-642-03994-2}} (Covers the structural approach to computing the DAE index.)
* {{cite book|author=Matthias Gerdts|title=Optimal Control of ODEs and DAEs|year=2012|publisher=Walter de Gruyter|isbn=978-3-11-024999-6}}
* {{cite book
|first1 = René
|last1 = Lamour
|first2 = Roswitha
|first3 = Caren
|last3 = Tischendorf
|title = Differential-Algebraic equations: a Projector based analysis
|publisher = Springer
|location = Heidelberg
|year = 2013
|isbn = 978-3-642-27554-8
}}

=== Various papers ===
* {{cite journal
 |url         = http://se.wtb.tue.nl/~vanbeek/pub/mcmds01.pdf
 |title       = Index Reduction and Discontinuity Handling using Substitute Equations
 |author1     = G. Fábián
 |author2     = D.A. van Beek
 |author3     = J.E. Rooda
 |journal     = Mathematical and Computer Modelling of Dynamical Systems
 |volume      = 7
 |number      = 2
 |year        = 2001
 |pages       = 173–187
 |doi         = 10.1076/mcmd.7.2.173.3646
 |url-status     = dead
 |archive-url  = https://web.archive.org/web/20050426090003/http://se.wtb.tue.nl/~vanbeek/pub/mcmds01.pdf
 |archive-date = 2005-04-26
|citeseerx       = 10.1.1.8.5859
 |s2cid = 14450374
 }}
* {{cite journal
|first1 = Silvana
|last1 = Ilie
|first2 = Robert M.
|last2 = Corless
|first3 = Greg
|last3 = Reid
|title = Numerical Solutions of Differential Algebraic Equations of Index −1 Can Be Computed in Polynomial Time
|journal = Numerical Algorithms
|volume = 41
|number = 2
|year = 2006
|pages = 161–171
|doi=10.1007/s11075-005-9007-1
|citeseerx = 10.1.1.71.7366
|s2cid = 14684538
}}
* {{cite journal
|url = http://www.cas.mcmaster.ca/~nedialk/PAPERS/DAEs/taylcoeff_I/taylorcoeffsdae.pdf
|first1 = Ned S.
|last1 = Nedialkov
|first2 = John D.
|last2 = Pryce
|title = Solving Differential-Algebraic Equations by Taylor Series (I): Computing Taylor Coefficients
|journal = BIT
|year = 2005
|doi=10.1007/s10543-005-0019-y
|volume=45
|issue = 3
|pages=561–591
|s2cid = 16451180
}}
* {{cite journal
|url = http://www.cas.mcmaster.ca/~nedialk/PAPERS/DAEs/taylcoeff_II/sysjac.pdf
|first1 = Ned S.
|last1 = Nedialkov
|first2 = John D.
|last2 = Pryce
|title = Solving Differential-Algebraic Equations by Taylor Series (II): Computing the System Jacobian
|journal = BIT
|year = 2005
|doi=10.1007/s10543-006-0106-8
|volume=47
|pages=121–135
|citeseerx = 10.1.1.455.6965
|s2cid = 16666782
}}
* {{cite journal
|url = http://www.cas.mcmaster.ca/~nedialk/PAPERS/DAEs/daets/daets_color.pdf
|first1 = Ned S.
|last1 = Nedialkov
|first2 = John D.
|last2 = Pryce
|title = Solving Differential-Algebraic Equations by Taylor Series (III): the DAETS Code
|journal = Journal of Numerical Analysis, Industrial and Applied Mathematics (JNAIAM)
|volume = 1
|number = 1
|year = 2007
|issn = 1790-8140
|pages = 1–30
}}
* {{cite journal
|url = http://www.cas.mcmaster.ca/~nedialk/PAPERS/DAEs/daesa_software/daesaSoftware.pdf
|first1 = Ned S.
|last1 = Nedialkov
|first2 = John D.
|last2 = Pryce
|first3 = Guangning
|last3 = Tan
|title = DAESA — a Matlab Tool for Structural Analysis of Differential-Algebraic Equations: Software
|journal = ACM Transactions on Mathematical Software
|volume =41
|issue = 2
|year = 2014
|doi =10.1145/2700586
|pages =1–14
|s2cid = 16655498
}}
* {{cite journal
|url = http://www.cas.mcmaster.ca/~nedialk/PAPERS/DAEs/daesa_theory/daesaTheory.pdf
|first1 = John D.
|last1 = Pryce
|first2 = Ned S.
|last2 = Nedialkov
|first3 = Guangning
|last3 = Tan
|title = DAESA — a Matlab Tool for Structural Analysis of Differential-Algebraic Equations: Algorithm
|journal = ACM Transactions on Mathematical Software
|volume =41
|issue = 2
|year = 2014
|doi = 10.1145/2689664
|pages =1–20
|s2cid = 311443
}}
* {{cite journal
|first1 = T.
|last1 = Roubíček
|first2 = M.
|last2 = Valášek
|title = Optimal control of causal differential algebraic systems
|journal  = J. Math. Anal. Appl.
|volume = 269 |issue = 2
|year = 2002 |pages = 616–641
 |doi=10.1016/s0022-247x(02)00040-9
|doi-access = free
}}
{{div col end}}

== External links ==
* http://www.scholarpedia.org/article/Differential-algebraic_equations

{{Differential equations topics}}

[[Category:Differential equations]]
[[Category:Numerical analysis]]
[[Category:Differential calculus]]

{{Sourceattribution|Differential-algebraic system of equations}}