Differential-algebraic equations
Definition of DAEs
A differential-algebraic equation (DAE) is an equation involving an unknown function and its derivatives.
A first order DAE is a system of equations of the form
F (t, x, x˙) = 0, (1.1) where t ∈ R is the independent variable (generally referred to as the
” time” variable), x(t) ∈ R n is the unknown function, and x˙ (t) = dx (t) The function
F : R × R n × R n → R n is assumed to be differentiable.
The system described in (1.1) represents a broad class of Differential Algebraic Equations (DAEs) This thesis focuses specifically on initial value problems, which involve the system (1.1) along with the initial condition x(t₀) = x₀, where t₀ is an initial time in the real numbers and x₀ is a value in Rⁿ.
• In general, if the Jacobian matrix
∂ x˙ is non-singular (invertible) then the system F (t, x, x˙ ) = 0 can be transformed into an ordinary differ- ential equation (ODE) of the form x˙ = f (t, x) Numerical methods for
ODE models have been already well discussed Therefore, the most interesting case is when ∂F is singular.
The approach to solving a Differential Algebraic Equation (DAE) is influenced by its specific structure A notable category of DAEs is the semi-explicit DAE, which can also be viewed as an ordinary differential equation (ODE) with constraints, represented by the equation y˙ = f(t, y, z).
0 = g(t, y, z), which appear frequently in applications. d t
Example 1.1.1 The system x 1 − x˙1 + 2 = 0, x˙1 x 2 + 2 = 0 is a DAE To see this, determine the Jacobian ∂F of
Hence, the Jacobian is a singular matrix irrespective of the values of x 2. Furthermore, we observe that in this example the derivative x˙2 does not appear.
Index of a DAE
The various index concepts aim to classify differential-algebraic equations (DAEs) based on their difficulty in both analytical and numerical solutions Key definitions include the Kronecker index for linear constant coefficient DAEs, the differentiation index introduced by Brenan et al in 1996, the perturbation index by Hairer et al in 1996, the tractability index from Griepentrog et al in 1986, the geometric index proposed by Rabier et al in 2002, and the strangeness index developed by Kunkel et al in 2006 This thesis specifically focuses on the differentiation index.
DAEs are usually very complex and hard to be solved analytically There- fore, DAEs are commonly solved by using numerical methods.
Question: Is it possible to use numerical methods of ODEs for the solution of DAEs?
Idea: Attempt to transform the DAE into an ODE This can be achieved through repeated derivations of the system with respect to time t.
Definition 1.1.1 The minimum number of differentiation steps required to transform a DAE into an ODE is known as the (differentiation) index of the DAE.
• Index measures the distance from a DAE to its related ODE.It reveals the mathematical structure and potentialcomplications in the analysis and the numerical solution ofthe DAE.
• The higher the index of a DAE is, the more difficulties for itsnumerical solutions appear.
Example 1.1.2 Let q(t) be a given smooth function in R n
The scalar equation y = q(t) is a (trivial) index-1 DAE ( with a differentiation, you obtain an ODE for y).
One differentiates the first equation to get y 2 y˙1 q˙(t) = y 2 and then y˙2 = y¨1 = q¨(t) This is an index-2 DAE (constraint differentiated twice to get
Classification of DAEs
Frequently, DAEs posses mathematical structure that are specific to a given application area As a result we have nonlinearDAEs, linear DAEs, etc.
In the DAE F (t, x, x˙) = 0 if the function F is nonlinear with respect to any one of t, x or x˙ , then it is said to be a nonlinear DAE.Linear DAEs:
A(t)x˙(t) + B(t)x(t) = c(t), where A(t) and B(t) are n× n matrices, is linear If A(t) ≡ A and
B(t) ≡ B, then we have time-invariant linear DAE.
A DAE system given in the form x J = f (t, x, z), (1.2)
• Note that the derivative of the variable z does not appear in the DAE.
• Such a variable z is called an algebraic variable; while x is called a differential variable.
• The equation 0 = g(t, x, z) called algebraic equation ora con- straint.
Example 1.1.3 (Simple pendulum) Consider a simple pendulum de- scribed in the figure leads to equation
We have a semi-explicit DAE system: x˙1 = x 3 , x˙2 = x 4 ,
A DAE system of the form:
Example 1.1.4 The system x 1 − x˙1 + 1 = 0 (1.4) x˙1 x 2 + 2 = 0 (1.5) is a fully-implicit DAE.
• Any fully-implicit DAE can be always transformed into semi-explicit DAEs with index increased by one as follows:
For F (t, y, y˙) = 0, let y˙ = z Then, we have y˙ = z,
• Semi-explicit form is nice because differential and algebraic variables are decoupled.
Special DAE Forms
The general differential-algebraic equation (DAE) F(t, y, y˙) = 0 may encompass mathematically ill-defined problems and those that fail with direct discretization methods without reformulation However, many higher-index problems commonly faced can be reformulated as a combination of more constrained ordinary differential equations (ODEs) alongside constraints By appropriately identifying and handling differential and algebraic variables, the algebraic variables can be eliminated through an equivalent number of differentiations.
Hessenberg index-1 DAEs have the form x J = f (t, x, z),
Also called semi-explicit index-1 DAE This is very closely related to implicit
ODEs because we can solve (in principle) for z in terms of x, t
Hessenberg index-2 DAEs have the form x J = f (t, x, z),
Note that g is independent of z It is also called pure index-2 DAE (algebraic variables are index-2 only, not a mixture of index 1 and 2).
It is also possible to take a semi-explicit index-2 DAE x˙ = f (t, x, z),
0 = g(t, x) to a fully implicit, index-1 form: Let w˙ = z Then, x˙ = f (t, x, w˙ ),
These problem classes are equivalent!
Runge-Kutta methods
Formulation of Runge-Kutta methods
In carrying out a step we evaluate s stage values
Y 1 , Y 2 , , Y s and s stage derivatives k 1 , k 2 , , k s , using the formula k i = f (Y i ).
Each Y i is defined as a linear combination of the k j added on to y 0 s
Y i = y 0 + h a ij k j , i = 1, 2, , s, j=0 and the approximation at x 1 = x 0 + h is found from s y 1 = y 0 + h b i k i j=0 Σ Σ cA b T c1 a 11 ã ã ã a 1s
Definition 1.2.1 Let b 1 , , b s , a ij (i, j = 1, , s) be real numbers Let c i = Σ j a ij The method s k i = f (x 0 + c i h, y 0 + h a ij k j ) s j=1 y 1 = y 0 + h b i k i i=1 is called an s − stage Runge-Kutta method.
There are many different Runge-Kutta methods; individual ones are usu- ally described by presenting their Butcher Array.
Butcher tableau: where the c i are the row-sums of the matrix.
Runge-Kutta methods are categorized into two primary types based on the structure of the matrix A When the A matrix is strictly lower triangular, the method is referred to as "explicit." Conversely, if the A matrix is not strictly lower triangular, the method is known as "implicit."
Classes of Runge-Kutta methods
For explicit methods, the Butcher array is strictly lower triangular Thus it is common to omit the upper-diagonal terms when writing the Butcher array: where c 2 = a 21 , c 3 = a 31 + a 32 , , c s = a s1 + ã ã ã + a s,s−1.
1-stage Explicit Euler method 2-stage Runge-Kutta method 3-stage Runge-Kutta 4-stage Runge-Kutta Formula
Implicit Runge-Kutta (IRK) methods are more complicated The diagonal and supra-diagonal elements of the Butcher array may be nonzero.
1-stage Implicit Midpoint 2-stage Implicit Trapezoidal Rule
Implicit Runge-Kutta methods are ideal for addressing stiff problems due to their extensive regions of absolute stability In contrast, explicit Runge-Kutta methods are inadequate for stiff problems as they are limited by a restricted region of absolute stability.
Simplifying assumptions
The following are properties that an RK method usually has For historic reasons these properties are known as the simplifying assumptions For the method description we have to introduce: i j k j=1 s k
Condition B(p) indicates that a quadrature formula with weights b₁, , bₛ and nodes c₁, , cₛ accurately integrates polynomials of degree up to p − 1 over the interval [0, 1] Meanwhile, condition C(q) asserts that polynomials of degree at least q − 1 are precisely integrated over the interval [0, cᵢ] for each i, using the quadrature formula with weights aᵢ₁, , aᵢₛ.
An RK method is said to have stage order q if C(q) is satisfied. s
Implicit RK methods and half-explicit RK methods for semi- explicit DAEs of index 2
This chapter explores the application of implicit Runge-Kutta (IRK) and half-explicit Runge-Kutta (HERK) methods specifically for solving index 2 differential-algebraic equations (DAEs) in Hessenberg form It emphasizes the importance of leveraging the structure of DAEs, such as their index and semi-explicit nature, to ensure robust and numerically stable solutions By focusing on Runge-Kutta coefficients, we aim to enhance the numerical methods available for addressing systems of semi-explicit index 2 DAEs.
These methods combine efficient s-stage Runge-Kutta method from ODE- theory for differential part with a method to handle the algebraic part [2].
Introduction
We consider the following class of semi-explicit differential- algebraic equa- tions (DAEs) of index 2 given in autonomous and
In this context, we consider differential variables \( y \in \mathbb{R}^n \) and algebraic variables \( z \in \mathbb{R}^m \), with functions \( f: \mathbb{R}^n \times \mathbb{R}^m \to \mathbb{R}^n \) and \( g: \mathbb{R}^n \to \mathbb{R}^m \) assumed to be sufficiently differentiable It is important that the product \( g_y(y)f_z(y, z) \) is invertible Additionally, the initial values \( y_0 \) and \( z_0 \) at time \( t_0 \) must be consistent, meaning they satisfy the condition \( g(y_0) = 0 \) and \( g_y(y_0)f(y_0, z_0) = 0 \).
The latter is called the hidden constraint, which is obtained by differentiating the algebraic equation.
The system of DAEs (2.1) is thus of index 2 [3, 7].
The system described by equation (2.1) can be integrated by differentiating the constraint, leading to the index 1 Differential Algebraic Equation (DAE) represented as \(\dot{y} = f(y, z)\) and \(0 = g_y(y)f(y, z)\) (2.4) This approach focuses on one-step methods that directly integrate the problem outlined in (2.1), bypassing the algebraic constraints presented in (2.3).
Implicit Runge-Kutta methods are the primary first-step approaches for directly integrating the system described in (2.1), as highlighted in the literature [3, 7] and further explored in [5] Additionally, half-explicit Runge-Kutta methods, introduced in [3] and refined in [4], provide a more efficient solution for specific problems of the form (2.1) that emerge in the simulation of multi-body systems represented in index 2 descriptor form.
Implicit Runge-Kutta methods
Formula of implicit Runge-Kutta methods
The s-stage Runge-Kutta method for semi-explicit index 2 differential-algebraic equations (DAEs) is defined for a single step with a stepsize \( h \), starting from \( y_n \) at \( t_n \) The numerical approximations for the solutions \( y_{n+1} \) and \( z_{n+1} \) at \( t_{n+1} = t_n + h \) are given by the equations \( y_{n+1} = y_n + h \sum_{i=1}^{s} b_i f(Y_{ni}, Z_{ni}) \) and \( z_{n+1} = z_n + \sum_{i=1}^{s} b_i \sum_{j=1}^{s} w_{ij} (Z_{nj} - z_n) \) Here, the internal stages \( Y_{ni} \) and \( Z_{ni} \) (for \( i = 1, \ldots, s \)) are the solutions to a system of nonlinear equations.
Here W := (w ij ) s denotes the inverse of the RK matrix A, i.e., W : A −1 , assuming that A is invertible.
1 From the above standard application of implicit RKmethods it is im- portant to notice that from (2.7b) allinternal stages g(y) = 0, whereas the numerical solution does not However, for stiffly accurate RK methods, i.e.,for methods satisfying ayfor such methods since from (2.7b) for g(Yhas been demonstrated [3, 5, 7] n+1 ns = Y) = 0 Superconvergence of stiffly accurate methods ns Therefore Y ni (i g(y= 1, , s) satisfy the constraint n+1 si = b) = 0 is automatically satisfied i for i = 1, , s we havei y= n+1 s generallywe have
2 Y 1 , Y 2 , , Y s and Z 1 , Z 2 , , Z s are obtained by solving (m + n) × s nonlinear equations at the same time Therefore, it can be very computationally expensive.
Convergence of implicit Rung-Kutta methods
Existence and uniqueness of the system of nonlinear equations arising with implicit Runge-Kutta methods are shown in the following theorem.
(2.8) and suppose that (2.2) holds in an h-independent neighbourhood of (η, ξ) If the Runge-Kutta matrix A = (a ij ) is invertible, then the nonlinear system s
0 = g(Y i ) (2.9b) possesses a solution for h ≤ hsatisfies 0 The solution is locally unique and
Definition 2.2.1 The difference between the numerical solution (y 1 , z 1) and the exact solution at x + h: δy h (x) = y 1 − y(x + h), δz h (x) = y 1 − z(x + h) is called the local error.
Lemma 2.2.1 Suppose that the Runge-Kutta method satisfies with p ≥ q + 1 and q ≥ 1 the conditions s
Then the local error is of magnitude δy h (x) = O(h q+1 ), P (x)δy h (x) O(h q+2 ) δz h (x) = O(h q ).
Here P (x) is a projection given by
P (x) = I − Q(x),Q(x) = (f z (g y f z ) −1 g y )(y(x), z(x)) (2.12) The limit of the stability function at infinity plays a decisive role for differential algebraic equations For invertible A it is given by
The convergence of the y-component solution, represented as y(x) and z(x), is established under consistent initial values According to Theorem 2.2.2, if the estimate (2.2) is valid within a neighborhood and the Runge-Kutta matrix A is invertible, the results will hold true.
|R(∞)| < 1 and the local error satisfies δy h (x) = O(h r ), P (x)δy h (x) = O(h r+1 ) (2.14) with P (x) given in (2.12), then the method (2.5) is convergent of order r, i.e., y n − y(x n ) = O(h r ) for x n = nh ≤ Const.
If in addition δy h (x) = O(h r+1 ), then we have g(y n ) = O(h r+1 ).
The proof of this theorem is given in [4, Theorem VII.4.5] and
[10, Theo- rem 4.4]; it is therefore omitted.Convergence for the z -component
Theorem 2.2.3 establishes that the global error for the z-component is approximately equal to its local error when |R(∞)| < 1, assuming the initial values are consistent In a neighborhood where the estimate (2.2) is valid, and given that the Runge-Kutta matrix A is invertible, if the global error of the y-component is O(h^k) and g(y_n) is O(h^(k+1)), it follows that the global error for the z-component satisfies z_n - z(x_n) = O(h^k) for x_n = nh ≤ Const.
Order conditions
The objective is to derive a local error estimate for the differential variable y1 in relation to the exact solution y(t) at t0 + h, utilizing consistent initial values (y0, z0) at t0 This thesis will not reiterate the complete tree theory for semi-explicit index 2 differential-algebraic equations (DAEs), as detailed in previous studies.
7] Definitions of tree t ∈ T y and related quantities p(t), γ(t),etc., are as in [3, Section 5] and [7, Section VII.5] We only mention the main idea, algorithm and results.
To establish the conditions on the method coefficients that guarantee a specific order of local error, we analyze the Taylor expansions of both the exact and numerical solutions.
Taylor expansions of the exact solution
Theorem 2.2.4 For the exact solution of (2.1) we have: y (k) (0) t∈T y ,ρ(t)=k z (k) (0) = Σ α(t)F (t)(y 0 , z 0), α(u)F (u)(y 0 , z 0), u∈T x ,ρ(u)=k where α(t), α(u) are integer coefficients.
Taylor expansions of the numerical solution
Theorem 2.2.5 For the numerical solution of (2.7) we have:
Z (k) (0) = Σ α(u)γ(u)Φ i (u)F (u)(y 0 , z 0), u∈T x ,ρ(u)=k where α(t), α(u) are the same integer coefficients as in
Again (w ij ) denotes the inverse of the Runge-Kutta matrix (a ij ) The order conditions are now given as follows:
Theorem 2.2.6 The local error y h (x 0) = y 1 − y(x 0 + h) satisfies y h (x 0) = O(h r ), P (x 0)δy h (x 0) = O(h r+1 ) (2.15) with P (x 0) = I − (f z (g y f z ) −1 g y )(y 0 , z 0), if the conditions Σ s b Φ (t) 1
0 hold for all trees t ∈ T y of order ρ(t) ≤ r − 1 and those of order ρ(t) r which are not of the form [u] y with u ∈ T z
Forming the order condition for a given tree.
The order conditions can be directly interpreted from the trees by assigning letters such as i, j, k, l, and so on, to each vertex in the tree T y The left-hand side of equation (2.16) is derived by summing over these letters, where the summand consists of the product of b i when the letter i is linked to the root, a lm when vertex l is succeeded by a meagre vertex m, and w np when vertex n is followed by a fat vertex p.
Figure 2.1: Order conditions for order r.
1 By the convergence result of Theorem (2.2.5order condi- tions imply that the global error of the y-component is O(h r ) ) the above
2 For the local error of theTheorem2.2.5and formula (2.6) that zif the conditions s z-component we find from 1 − z(x 0 + h) = O(h k ), i Σ ,j=1 b i w ij Φ j
Numerical experiment
To illustrate the superconvergence results, we have applied the stiffly accu- rate Radau II method with constant stepsize h to the following semi-explicit system of index 2 DAEs:
0 = y 1 y 2 − 1 For the initial conditions y 1(0) = 1, y 2(0) = 1 at t 0 = 0 the exact solution to this test problem is given by y 1(t) = e t , y 2(t) = e −t , z 1(t) = e t
The value of numerical order are displayed in Table 2.1
Table 2.1: The approximation of order of convergence for Radau IIA methods
Remark 2.2.3 The numerical results clearly show the order of convergence p = 3 which confirm the theoretical results in
Figure 2.2: The error results for Radau IIA in the test problem on interval [0, 1] with h = 0.1.
Half-explicit Rung-Kutta methods
Discussion of the convergence
The convergence analysis given here is based on the results for general implicit Runge-Kutta methods. Σ Σ
Lemma 2.3.1 (Existence of numerical solution) Let (2.2) and (2.3) be sat-isfied and assume that for the coefficients of the Runge-Kutta scheme a i,i−1 ƒ= 0 for i = 2, , s and b s
Then, for sufficiently small h, the numerical solution of (2.19) exists and is
The local error of method (2.19) is defined by δy h (x) = y 1 − y(x + h), (2.21) where y 1 is the numerical solution of (2.19) with initial value y 0 = y(x).
Theorem 2.3.1 (Convergence) Suppose that (2.2) holds in a neighbourhood of the solution (y(x), z(x)) of (2.1) and that the initial values are consistent If the coefficients of the half-explicit
Runge-Kutta method satisfy (2.20) and if the local error satisfies δy h (x) = O(h p+1 ), (2.22) then the method is convergent of order p, i.e., y n − y(x n ) = O(h p ) for x n − x 0 = nh ≤ Const.
In the proposed method, it is suggested to set c s = 1 and use z 1 = Z s as an approximation for z(x 0 + h) The convergence is maintained under the condition that Y s − y(x 0 + s − z(x 0 + h) = O(h r+1) if h = O(h r+1) Importantly, since the formula for z 1 is applied locally, the value of r does not affect the convergence behavior of the method.
Order conditions
This section focuses on verifying equation (2.22) by expanding both the exact solution y(x₀ + h) and the numerical solution y₁ as Taylor series By comparing the coefficients of h^q for q ≤ p, we can achieve this verification The process, which involves complex notations such as trees and elementary differentials, is detailed in references [3] and [7] The findings are summarized in Table [insert table number].
2.2 There, the coefficients w ij are the entries of the matrix
, a s1 a s2 ã ã ã a s,s−1 b 1 b 2 ã ã ã b s−1 b s which exists by (2.20) We further use the standard notation i−1 a ij = c i , c 1 = 0, (2.24) j=1 and we also write a s+1,i = b i , i = 1, , s, c s+1 = 1.
In our analysis, we find that a method of order 1 requires one condition, while a method of order 2 necessitates two conditions For order 3, six conditions are essential, and a method of order 4 demands a total of 20 conditions These order conditions are intricately linked to the corresponding trees in the algorithm.
To establish the order condition for a specific tree structure, assign a summation index to each vertex, denoted as i, j, etc The left side of the order condition is represented by a summation that includes products of factors: b_i when "i" is the index of the root vertex, a_ij when the meagre vertex "j" is directly above the meagre vertex "i," and a_(i+1),j when the meagre vertex "j" is positioned directly above the fat vertex "i."
If the fat vertex "j" is positioned directly above the meagre vertex "i," the order condition's right-hand side represents a rational number This number is derived from the product of all indices associated with the factor.
1/r if the vertex ”i” is meagre; r + 1 if the vertex ”i” is fat.
Figure 2.3: Order conditions up to order 4.
3 with s = 3 stages Its coefficients are given in Table 2.1:
Proposition 2.3.1 There exists a unique half-explicit method
It is easy to check that these coefficients satisfy the order conditions.
Proposition 2.3.2 There is no half-explicit method (2.19) of order 4 with s = 4 stages.
To apply method (2.19), it is sufficient to know the initial value y0, which allows for the approximation y1 at y(x0 + h) If an approximation for the z-component is also desired, there are various options to consider.
The computation of z₁ from the non-linear equation g(y₁)f(y₁, z₁) = 0 is highly accurate, as indicated in equation (2.26) By applying the implicit function theorem in conjunction with equation (2.2), we achieve the same level of accuracy for z₁ as we do for y₁.
The proposal in [6] suggests setting c s = 1 and using z 1 = Z s as an approximation for z(x 0 + h) The order conditions for this approximation can be derived from the findings in [1] It is established that Z s - z(x 0 + h) = O(h r+1) if and only if Y s - y(x 0 + h) = O(h r+1), provided that the conditions illustrated in Figure 2.2 are met up to order r Furthermore, since z 1 is applied locally, the convergence behavior of the method remains unaffected by the value of r.
Figure 2.4: Order condition for z-component.
1 Half-explicit Runge-Kutta methods suffer from orderreduction: for traditional higher order explicit Runge-Kuttamethods the order usu- ally drops down to 2 As mentionedabove, there exists uniquely the method of order 3 with 3stages and no method of order 4 with 4 stages.
2 Most of order conditions for half-explicit Runge-Kutta methodcoin- cide with classical order condition for underlyingexplicit Runge-Kutta method.
Numerical experiment
To illustrate the order reduction of HERK, we have applied the3-stage HERK method with constant stepsize h to the semi-explicit system of index 2 DAEs (2.18):
Figure 2.5: The error results for 3-stage HERK in the test problem on interval [0, 1] with h = 0.1.
The values of numerical orders are displayed in Table 2.2
Table 2.2: The approximation of order of convergence for HERK methods
Remark 2.3.3 The numerical results clearly show the order of convergence h1/h2 p y1 p y2 p z1
2.739 2.693 1.543 p = 2 which confirms the theoretical results in Proposition 2.3.1.
Discussion
Half-explicit Runge-Kutta methods, as introduced by Hairer et al., offer a unique approach to solving differential equations by calculating the solution components y in a manner similar to explicit Runge-Kutta methods for ordinary differential equations (ODEs) The algebraic solution components z are designed to ensure that all stage values Y ni remain within the specified manifold defined by the algebraic constraints Unlike implicit Runge-Kutta methods that necessitate solving complex systems of nonlinear equations, half-explicit methods simplify this process, typically reducing the order of the equations to q = 2 While they are straightforward to implement and do not require special initial conditions, a significant drawback is their order reduction, which can lead to decreased efficiency in integrating certain systems Nonetheless, these methods retain some advantages over traditional implicit Runge-Kutta methods, particularly in handling the algebraic components separately.
Partitioned HERK methods for semi- explicit DAEs of index 2
This chapter focuses on the numerical solution of non-stiff semi-explicit differential algebraic equations (DAEs) of index two, utilizing the partitioned half-explicit Runge-Kutta method (PHERK) This approach avoids order reduction in the differential components, contingent on a sufficiently accurate approximation of the algebraic components PHERK demonstrates significant advantages when applied to constrained mechanical systems, as proposed in [1].
This article presents a comprehensive theoretical analysis of partitioned half-explicit Runge-Kutta methods that precisely adhere to the algebraic constraints of differential-algebraic equation (DAE) systems Additionally, numerical tests demonstrate the effectiveness and efficiency of these methods.
Introduction
We consider a semi-explicit system of differential-algebraic equations of index 2 given in (2.1) Half-explicit methods are for
DAE systems the counterpart of explicit methods for ODEs: They are efficient, robust, and easy to implement Half-explicit Runge-
Kutta methods for (2.1) were introduced in previous chapter They compute the differential solution components y similar to explicit
Runge- Kutta methods for ODEs However, a drawback of these half-explicit Runge- Kutta methods is severe order reduction.
To address the limitations of traditional methods, partitioned half-explicit Runge-Kutta methods can be utilized, which closely resemble half-explicit Runge-Kutta techniques These methods involve simple modifications to achieve super-convergence The key concept is to introduce an explicit stage defined by Y1 = y0 and Z1 = z0, along with additional internal stages to effectively manage index 2 constraints.
DAEs In [10], a general class of methods to solve the system of
DAEs (2.1), the partitioned Runge-Kutta methods (PRK) is presented: i = 1, , s, s
The existence and uniqueness of the numerical solution provided by equation (3.1) is not always assured This article examines two specific subclasses of PRK methods, demonstrating that for sufficiently small values of h, the scheme (3.1) yields a unique solution.
• Type 1: PRK methods (3.1) such that
The invertibility of the matrix A¯ ensures that standard implicit Runge-Kutta methods can effectively address systems represented by (2.1) These methods are a specific instance of PRK methods (3.1) of the first type, where A is equivalent to A¯ Additionally, half-explicit Runge-Kutta methods have been examined in this context.
[4, 10, 12] are also particular cases of PRK methods (3.1) of type 1, with A corresponding to an explicit Runge-Kutta method (i.e., is strictly lower triangular), and
• Type 2: PRK methods (3.1) such that the first row of A¯ is null, andA˜ is invertible, where A˜ denotes the matrix obtained from
The A¯ method modifies its (1,1) entry to 1, resulting in the numerical approximation y 1 being influenced by both z 0 and y 0, unlike type 1 methods where Z 1 is not determined The Lobatto IIIA methods discussed in reference [6] are included in this category, along with the half-explicit methods introduced in references [1] and [10].
PRK methods involve a strictly lower triangular matrix A and a lower triangular matrix A¯, where the sth row of A and the (s − 1)th row of A¯ are equal to the vector b The approaches discussed in the referenced study are designed so that for every i ≥ 2, the ith row of A coincides with the (i + 1)th row of A¯.
These methods maintain their effectiveness without experiencing order reduction in the differential components, as long as the approximation of the algebraic components is sufficiently accurate In the following section, we will provide a detailed description of these innovative methods.
This article introduces partitioned half-explicit Runge-Kutta methods specifically designed for non-stiff index-2 differential-algebraic equations (DAEs) in Hessenberg form It thoroughly analyzes the existence, uniqueness, local error, and global convergence of the numerical solutions associated with these methods Additionally, the article presents a numerical experiment in the final section to demonstrate the super-convergence results achieved.
Partitioned half-explicit Runge-Kutta methods
Definition of partitioned half-explicit RK method 34
Definition 3.2.1 A step (y 0 , z 0) → (y 1 , z 1) of a s-stage partitioned half- explicit Runge-Kutta (PHERK) method is defined by
= 0, j=1 y 1 = Y¯ s−1 , z 1 = Z s , where it is assumed that a si = a¯ s−1,i for all i(a ss 0).
1 The numerical approximation yconstraint of (2.1) 1 = Y s satisfies the algebraic
2 Although the PHERK method (3.2partitioned Runge-Kutta method (3.1) of type 2, itseffective number stages is s − 1, as s − 1 equations haveto be solved and s − 1 new f (Y i , Z ) i ) areis formally an s-stage Σ Σ computed at each step Here we have put Y s = y 1 , Z s z 1 so that the value f (Y 1 , Z 1) can be reused as f (y 0 , z 0) for the next step.
3.A significant difference compared to the half-explicit RKmethod is that the numerical solution (yboth initial values y 0 , z 0 1 , z 1) depends on
4 In contrast to the HERK methods of [4] we do not requireg(Yadditional parameters aorder of convergence Because of these two reasons PHERKmethods do not suffer from the order reductionphenomenon mentioned in Chapter 2.1) = 0 in (3.2) Furthermore, the PHERK methods have ij that may be chosen to get a high
5 Similar to the half-explicit Runge-Kutta methods thestage vector Ystage, and results when replacing in Y i Note that the Jacobian with respect to ZZ i is obtained by solving the equation that i in (3.2) is computed explicitly at the ithg(Y i ) = 0 the expression for i of such an algebraic equation is ha¯ ii g y (Y¯ i )f z (Y i , Z i ) Thus, we will always assume that a¯ ii ƒ= 0 for i ≥ 2 This condition guarantees the existence of the numerical solution as stated in Lemma3.2.1 below.
6 An interesting particular case of PHERK methods (3.2) isthat of methods satisfying a¯ ij = a i+1,j , 2 ≤ i ≤ s − 1, 1 ≤ j ≤ i, (3.3) so that
Y¯ i = Y i+1 for 2 ≤ i ≤ s − 1 This simplification reduces the numerical work per step.
Existence and influence of perturbations
In the more general case, the repeated application of more than one step of the PHERK method leads to the application of the
PHERK methods with inconsistent (y 0 , z 0) The following result on the existence of the numerical solution of these methods is a particular case of the Lemma3.2.2 below.
Lemma 3.2.1 (Existence of numerical solution) Let us consider the system (2.1 ) and (y 0 , z 0) such that (2.2 ) is satisfied, and assume that g y (y)f z (y, z) is invertible in a neighborhood of (y 0 , z 0).
Consider a PHERK scheme (3.2) wit h a¯ ii ƒ= 0 for i ≥ 2 If ||g y (y 0)f (y 0 , z 0)|| is sufficiently small, the method
(3.2) has for h ≤ h 0 a locally unique solution, which smoothly depends on h and (y 0 , z 0).
Our aim now is to study the influence of perturbations of the
Given (yˆ0 , zˆ0) such that g(yˆ0) = θ 1, we consider the following scheme
In our analysis, we gather perturbations into two vectors, r = (r1, , rs) and θ = (θ1, , θs) It is important to note that the existence and local uniqueness of the solution for yˆ0 and θ in h-independent neighborhoods is not assured To address this, we formally define δi as θi − θ1 h g(Yˆ¯g(yˆhi) − 0).
(by definition, δ 1 = 0). Σ Σ i 0 j= i j j j j i i ues (y 0 , z 0) such that (2.2) is satisfied, and a PHERK method
Lemma 3.2.2 states that for the system defined in equation 2.1 with consistent initial values a¯ ii ƒ= 0 for i ≥ 2, the perturbed scheme described in equation 3.4 has a locally unique solution (yˆ1, zˆ1, Yˆ 2, , Yˆ s, Zˆ 2, , Zˆ s) in a neighborhood U of (y 0, z 0, 0, 0, 0) when (yˆ0, zˆ0, h, r, δ) are appropriately defined This solution depends smoothly on the parameters (yˆ0, zˆ0, h, r, δ) Specifically, the perturbed numerical solutions can be expressed as yˆ1 = yˆ0 + hΦ(yˆ0, zˆ0, h, r, δ) and zˆ1 = ϕ(yˆ0, zˆ0, h, r, δ), where Φ and ϕ are smooth functions defined within the neighborhood U.
Proof Proceeding in a similar way to the proof of Theorem VII.4.1 of [7] when studying the existence of Runge-Kutta methods with invertible A matrix, the equations g(Yˆ¯ i )
= θ i in (3.4) can be replaced by
Then we have H i = 0 and G i = 0 for i = 2, , s Defining H (H 2 , , H s ) T ,
Therefore, replacing Yˆ¯ i by their explicit expressions, (3.4) can be expressed in the form
The equation F(Uˆ, h, yˆ0, zˆ0, r, δ) = 0 represents a smooth function where Uˆ consists of variables Yˆ 2, , Y s, and Z 2, , Z s We aim to demonstrate the applicability of the implicit function theorem to this nonlinear system Specifically, we will prove that for values (yˆ0, zˆ0) that are sufficiently close to consistent initial values (y 0, z 0), along with sufficiently small parameters r and δ, the equation (3.4) will yield a solution Σ for h values less than or equal to h 0.
− δ i locally unique solution: First, we see that F (U 0 , 0, y 0 , z 0 , 0, 0) = 0, where
U 0 = (y 0 , , y 0 , z 0 , , z 0) Second, the Jacobian of F with respect to Uˆ at
, where Aˆ is the matrix obtained from A¯ suppressing its first column and row.
This matrix is invertible provided that (2.2) is satisfied and the matrix
A¯ is invertible It follows from the implicit function theorem that there exists a locally unique solution
This implies that there exist smooth functions Φ and ϕ defined in a neighbor- hood of (y 0 , z 0 , 0, 0, 0) such that the solution (yˆ1 , zˆ1) of the perturbed scheme (3.4) satisfies yˆ1 = yˆ0 + hΦ(yˆ0 , zˆ0 , h, r, δ),z 1 = ϕ(yˆ0 , zˆ0 , h, r, δ).
1 Lemma3.2.2is an more general result than Lemma3.2.1Therefore, the proof of Lemma3.2.1can be obtainedconsidering Lemma3.2.2 with r i = 0; and θ i = 0 .
2 In [10] (Subsection 5.4) we show that, for arbitrary under certain conditions on the parameters of the method,the following statement holds k > 1, Φ z (y 0 , z 0 , 0, 0, 0) = O(h k ) for consistent initial values(y 0 , z 0),
Lemma 3.2.3 Under the conditions of Lemma3.2.2 , given k ≥ 1 such that(3.7) is satisfied, then
Proof By Lemma3.2.2and using Taylor expansion, we have
With the results of computing the partial derivatives with respect to variables, this implies the proof of lemma.
Convergence of partitioned half-explicit Runge- Kutta methods
This section examines the convergence of PHERK methods, ensuring that their numerical solutions adhere to the algebraic constraints outlined in equation (2.1) According to Lemma 3.2.2, the numerical approximations for the system (2.1) at time \( t_n = t_{n-1} + h_n \) are derived from the solutions \( y(t_{n-1}) \) obtained through the scheme represented in equation (3.2) This can be reformulated as \( y_{n+1} = y_n + h_n \Phi(y_n, z_n, h_n) \) and \( z_{n+1} = \phi(y_n, z_n, h_n) \), where \( \Phi(y, z, h) \) and \( \phi(y, z, h) \) are defined with specific parameters Given initial conditions \( (y_0, z_0) \) that satisfy the consistency equations (2.2)-(2.3), the local error of the method is characterized by \( \delta_y(y_0, z_0, h) = y(t_0 + h) - y_0 - h\Phi(y_0, z_0, h) \) and \( \delta_z(y_0, z_0, h) = z(t_0 + h) - z_0 - \phi(y_0, z_0, h) \).
(3.10) where (y(t), z(t)) is the exact solution of (2.1) with initial values y(t 0) = y 0 , z(t 0) = z 0.
The PHERK method, rewritten as (3.8), utilizes initial values (y₀, z₀) that comply with Theorem 3.2.1 We analyze the system presented in (2.1) and apply the conditions specified in (2.3) alongside g_y(y₀)f(y₀, z₀) = O(h^l) Let h be defined as the maximum of hᵢ Furthermore, if the condition |w₁| < 1 is met, along with (3.7) and the constraints δ_y(y, z, h) = O(h^(p+1)) and δ_z(y, z, h) = O(h^m) in the vicinity of the solution, then for nh < Constant, the errors are expressed as y_n - y(t_n) = O(h^(min(p, m+k, 2m, m+l, l+k+1, 2l+1))) and z_n - z(t_n) = O(h^(min(p, m, l))).
The following result, generalization of Lemma 3.9 of [7], will be used in the proof of next theorem:
Lemma 3.2.4 Let u n and v n be two sequences of non-negative numbers such that u n+1 hM, v ≤ (1 + O(h))uO(h))v n+1 ≤ O(1)u n + hN, n + O(s)v n + (α + n + with α, M, N ≥ 0, then, the following estimates hold for sufficiently small h, s ≤ ch, nh ≤ Const : u n ≤ C(u 0 + sv 0 + M + sN ), v n ≤ C(u 0 + (s + (α ∗ ) n )v 0 + M + hN ), if α ∗ = |α +
Proof It can be proven in a very similar way to Lemma 3.9 of [7], and it is based on the decomposition
O(1) 1 a PHERK method given by (3.2), with initial values (y 0 , z 0) satisfying (2.3) Theorem 3.2.2 Let us consider the system (2.1), and the application of and g y (y 0)f (y 0 , z 0) = O(h l ) Let us denote h = max h i If |α| < 1, and
(3.11) and (3.7) are satisfied in a neighborhood of the solution, then, for nh ≤ Constant, y n − y(t n ) = O(h min(p,m+k,2m,m+l,l+k+1,2l+1)), z n − z(t n ) = O(h min(p,m,l) ).
Proof The statement of this theorem can be proven comparing the numerical solution (y n , z n ) of (3.2) with the exact solution (y(t n ), z(t n )) of (2.1) with initial values (y 0 , z 0 ), where z 0 is the solution of g y (y 0)f (y 0 , z 0 ) = 0 which is
0 0 0 closest to z 0 Let us denote ∆y n = y n − y(t n ) and ∆z n = z n − z(t n ) The hypothesis of the theorem together with Lemma3.2.3implies that
First, assuming that the errors ||∆z n || are sufficiently small so that α ∗ = | α +
O(h)+ max ||∆z n ||| < 1, Lemma3.2.4can be applied with u n = ||
∆y n ||, v n ||∆z n ||, s = h, α replaced by α ∗ , M = O(h p ), and N = O(h m−1 ), which implies that ∆z n = O(h min(p,m,l) ).
Second, we again apply Lemma3.2.4with u n = ||∆y n ||, v n = ||∆z n ||, s h min(p,m,l,k)+1 , M = O(h p ), and M = O(h m−1 ), which gives the estimate for
1 Lemma3.2.2guarantees that (3.7) is fulfilled at least for k =1 In Subsection 5.4 of [8], we develop a procedure to obtainin a systematic way sufficient conditions on the coefficientsof the methods for (3.7) to be satisfied for k > 1.
2 The application with consistent initial values of a PHERKmethod such that |α| < 1 is of order p for the differentialvariables if (3.11) and (3.7) are satisfied with k Moreover, if m > p − k, the leading term of ynot influenced by the local error of the algebraiccomponent m ≥ k, p n − y(t n ) is−
3 In the case of of the proof of the Theorem, it can be proven that|α| = 1, using the similar arguments to those y n − y(t n ) = O(h min(p,m+k,l+k+1,2m−1,2l+1,m+l)), z n − z(t n )(3.15)
Construction of partitioned half-explicit Runge-Kutta 39 methods42
Methods of order up to 4
Theorem 3.3.1 Let us consider a s-stage PHERK method (3.2) such that the underlying (s − 1)-stage explicit Runge-Kutta method is of order 3 for
ODEs If its coefficients satisfy C¯(2), and |w s1 | < 1, then (3.11) holds with p = 3 and m = 1 If in addition s
Using this result, we have constructed a 4-stage PHERK method (3 effec- tive stages) of order 3 (both y and z) based on the below third order method, determining the remaining parameters so that
1 w si c¯ 3 = 3 hold, and choosing the free parameters w 41 ƒ= 0 and c¯2 , c¯4 in such a way that the local error coefficients and |w 41 | are reasonably small
Construction of the 3th order PHERK method divide in two steps: First, choose a standard 3 order 3-stage IRK as follows
Hence, we determines the coefficients a ij = 0 for j ≥ i, a 21 = 1, a 31
It is then straightforward to see that a 4-stage PHERK method have the coefficients satisfy a¯31 = a¯32 = 1 (= b 1 = b 2), a¯33 = b 3 = 2
Secondly, we will determine the remaining parameters so that
1 w 3i a¯ 3 = 3 hold, and choose free parameters w 41 ƒ= 0 and w 41 ∈ (−1, 1); c¯2 , c¯4 in such way that local error coefficients are reasonably small. Σ i
Then we need to find a¯21 , a¯22 , a¯41 , a¯42 , a¯43 , a¯44 satisfy the system of equations
Solving this systems (with c¯1 = 0, c¯2 = 1 , c¯3 = 1, c¯4 = 2 ) we get
Its coefficients are displayed in Table 3.1
Table 3.1: PHERK method of order 3.
Note that: Construction of the pth order PHERK method divide in two steps:
1 First, choose a standard method This determines the coefficients amethod pth order explicit Runge- Kutta ij of the PHERK
2 And second, determine the coefficients in order that thecorresponding PHERK method is of the required order whenapplied to systems of the form (2.1).
It is well known that the construction of explicit Runge- Kutta methods of or- der higher than 3 is best accomplished if the standard simplifying assumption D(1) is made. s−1
Let us now consider s-stage PHERK methods such that
C¯(2) and D(1) are satisfied, and the underlying explicit method is of order 4 We have the following result
Theorem 3.3.2 Given a s-stage PHERK method (3.2) such that
D(1) is satisfied and the underlying explicit Runge-Kutta method is of order 4 for
C¯(3) is satisfied, then (3.11) holds with p = 4 and m = 2 If in addition, condition w si i
(3.16) holds, then (3.11) is fulfilled with p = 4 and m = 3.
Using this result, we have constructed a 5-stage PHERK method
(4 ef- fective stages) of order 4 (both y and z) based on the classical 3/8-rule, determining the remaining parameters so that
C¯(3) and (3.16) hold, and choosing the free parameters (w s1 ƒ= 0 and c¯3) in such a way that the local error coefficients and |w s1 | are reasonably small Its coefficients are displayed in Table 3.2.
Table 3.2: PHERK method of order 4. Σ Σ Σc¯ 4, w c i a ij c¯ i a¯ ij
Methods of order 5 and 6
The construction of higher order explicit Runge-Kutta methods for ODEs usually relies the simplifying assumption D(1) and
In the development of higher-order PHERK methods, it is important to focus on those that satisfy specific conditions for k ≤ 2 This approach minimizes the impact of errors in the z-components on the overall error in the y-components, allowing for higher accuracy in differential variables while maintaining a more modest convergence rate for algebraic variables Our current focus is on PHERK methods that meet these criteria specifically for k = 2.
Given a s-stage PHERK method, we assume that there exist real numbers ¯b 1 , , ¯b s−1 such that
, 2 ≤ l ≤ p. the underlying (s − 1)-stage explicit Runge-Kutta method satisfies
D(1) and Theorem 3.3.3 Let us consider a s-stage PHERK method (3.2) such that i l− Σ s− 1 j= j l i= i i l
C ∗ (2) and it is of order 5 for ODEs If C¯(3), D¯ (1), and B¯(5) are fulfilled, and s−1¯b i c¯ i a¯ i2 = 0, (3.17) holds, then (3.11) and (3.7) are satisfied with p = 5, m = 3, k = i=2
2, so that, if |w s1 | < 1, the method is of order 5 for differential variables and of order 3 for the algebraic variables If in addition
When condition (3.16) is met, the method achieves fourth-order accuracy for the algebraic variables, and the local error in the z-component does not influence the dominant term of the global error in the y-component.
Numerical experiment
To illustrate the superconvergence results, we have applied the 4-stage PHERK method and 5-stage PHERK method with constant stepsize h to the semi-explicit system of index 2 DAEs (2.18):
To evaluate the convergence of method (3.2), we performed an integration of the problem over the interval from t = 0 to t = 1, utilizing a constant step size of h = 1/n for various n values We defined err y and err z as the errors in the y-component and z-component, respectively, after n steps of length h = 1/n The relationship between the errors and the step size indicates that err y ≈ Ch^p and err z ≈ Ch^p for h1 ≥ h2, leading to the conclusion that the numerical order can be expressed as log(err y) = p * log(h).
1 log errz ( h z 1 2 ) is taken as an approximation for p Similarly p z log( h 2 ) is an approx- h 1 imation for p The results are displayed in Figure 3.1 and Figure 3.2.
Remark 3.4.1 The numerical results clearly show the order of convergence Σ
Figure 3.1: The error results for 4-stage PHERK in the test problem on interval [0, 1] with h = 0.1. h1/h2 p y1 p y2 p z1
Table 3.1: The approximation of order of convergence for 4-stage
PHERK method p = 3 which confirm the theoretical results in Theorem 3.3.1 and the coeffi- cients that we have just found it above
Remark 3.4.2 The numerical results clearly show the order of convergence p = 4 which confirm the theoretical results in Theorem 3.3.2 and Table
Figure 3.2: The error results for 5-stage PHERK in the test problem on interval [0, 1] with h = 0.1. h1/h2 p y1 p y2 p z1
Table 3.2: The approximation of order of convergence for 5-stage PHERK method
Discussion
We introduced a novel class of half-explicit methods for differential-algebraic systems of index 2, building on the half-explicit Runge-Kutta methods developed by Hairer et al These methods replace the first stage with explicit Runge-Kutta stages and include additional parameters that enhance convergence order This modification allows for the extension of well-established high-order explicit Runge-Kutta methods for ordinary differential equations (ODEs) to half-explicit forms for differential-algebraic systems without any loss in order Moreover, constructing high-order methods is streamlined, as most order conditions align with the classical order conditions of the underlying explicit Runge-Kutta methods.
The PHERK methods, similar to half-explicit Runge-Kutta methods, compute the stage vector \( Y_i \) explicitly at each stage, while \( Z_i \) is derived by solving the equation \( g(Y_i) = 0 \) with the expression for \( Y_i \) These methods effectively have \( s - 1 \) stages, allowing for the resolution of \( s - 1 \) separate nonlinear systems of size \( m \times m \) Consequently, PHERK methods are simpler compared to implicit methods, which require solving \( (m + n) \times s \) nonlinear equations simultaneously.
Non-stiff differential-algebraic equations (DAEs) can be effectively addressed using partitioned half-explicit Runge-Kutta methods and half-explicit Runge-Kutta methods In contrast, implicit methods are preferred for solving stiff problems due to their larger regions of absolute stability and higher-order accuracy.
Recent advancements in half-explicit methods highlight the advantages of PHERK methods in constrained mechanical systems These methods achieve convergence at the same rate as the underlying explicit Runge-Kutta methods, provided that the local discretization error in the algebraic components is minimal and stability conditions are met Additionally, the methods can be enhanced with extra stages for better approximation of algebraic components However, a significant drawback is that for index 2 DAEs, this approach necessitates the use of additional internal stages, leading to the need for more coefficients \( \bar{a}_{ij} \).
This thesis is devoted to the numerical solution of semi-explicit differential- algebraic equations of index 2 by Runge-Kutta methods
We have presented implicit Runge-Kutta and half-explicit Runge-Kutta methods and also dis- cussed their advantages and disadvantages.
The thesis presents partitioned half-explicit Runge-Kutta (PHERK) methods, highlighting their advantages over implicit and half-explicit Runge-Kutta methods It thoroughly discusses the convergence, order conditions, and implementation of PHERK Additionally, a numerical experiment demonstrates the superconvergence results achieved by PHERK methods.
This thesis explores the advantages and disadvantages of various classes of Runge-Kutta methods, supported by numerical experiments that demonstrate the theoretical findings.
M Arnold has contributed significantly to the field of differential-algebraic systems, particularly with his work on Half-Explicit Runge-Kutta Methods for index 2 systems, as detailed in his 1995 submission to BIT In collaboration with A Murua, he explored non-stiff integrators for these systems in a 1998 publication in Numerical Algorithms Additionally, Arnold, along with K Strehmel and R Weiner, presented methods for numerically solving differential-algebraic systems using Runge-Kutta techniques in Lecture Notes in Mathematics, Vol 1409 The study of half-explicit methods for semi-explicit differential-algebraic equations was further advanced by V Brasey and E Hairer in their 1993 paper in SIAM Journal on Numerical Analysis K E Brenan and L R Petzold also contributed to this area by developing implicit Runge-Kutta methods for higher index differential-algebraic equations, as published in SIAM Journal on Numerical Analysis in 1989 E Hairer, along with S P Nørsett and G Wanner, authored a comprehensive guide on solving ordinary differential equations, addressing non-stiff problems in their 1993 book, followed by a second volume in 1996 that focused on stiff and differential-algebraic problems.