Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Appendix A

Systems of ordinary differential equations

Abstract

This appendix serves the purpose of a brief introduction to ordinary differential equations and systems thereof. A concise and nonexhaustive collection of methods and techniques used to find solutions to several types of differential equations, including first-order scalar equations, second order linear equations, and systems of linear equations, is included. In most cases, the reader is directed to more thorough and complete treatises, while this appendix offers a brief idea of the background material required for better understanding the mathematical models and methodologies employed in the analysis of malware diffusion in computer and communications networks, especially those based on epidemics models.

Derivatives; Ordinary differential equations; Linear systems; Initial value problems; Existence; Uniqueness; Epidemics

A.1. Initial Definitions

A differential equation is an equation that contains one or more derivatives of an unknown function. Differential equations are extensively used in mathematical modeling of many systems. When the independent variable is time, then the differential equation describes the temporal dynamics of a monolithic quantity, e.g. population, capital investment, chemical compound, decayed radioactive material, and so on. Other independent random variables such as the spatial coordinates can give more detailed description of a spatiotemporal quantity with spatiotemporal dynamics, e.g. diffusion of heat and fluids. In the rest of this appendix, we assume that the independent variable is time and denote it by

t

$t$

. Any other interpretation of

t

$t$

is valid too.

A differential equation that only contains ordinary derivatives is called an ODE. If, on the other hand, one or more partial derivatives are involved as well, it is referred to as a partial differential equations (PDEs) [81]. Each of these two broad categories is further classified based on the highest order of derivative that appears in them. In this appendix, we only consider ODEs.

Depending on the number of unknown functions that are involved, a classification to single ODE and system of ODEs is obtained. If there is a single function to be determined, then one equation is sufficient. However, if there are two or more unknown functions, then a system of equations is required.

Let

x

$x$

in a space

X \subset ℝ^{m}

$X \subset ℝ^{m}$

(for some proper dimension

m

$m$

of the space) be a function of a single-dimensional real-valued variable

t

$t$

. Furthermore, for any positive integer

i

$i$

, let

x^{(i)} (τ)

$x^{(i)} (τ)$

represent the

i

$i$

th order derivative of

x

$x$

with respect to

t

$t$

evaluated at

τ

$τ$

, i.e.

x^{(i)} (τ) : = d^{i} (x (t)) ∕ d t^{i}

$x^{(i)} (τ) : = d^{i} (x (t)) ∕ d t^{i}$

evaluated at

t = τ

$t = τ$

. Then, we have the following.

Definition A.1

A differential equation that can be put in the form of

$F (t, x (t), x^{(1)} (t), \dots, x^{(n - 1)} (t), x^{(n)} (t)) = 0$ $F (t, x (t), x^{(1)} (t), \dots, x^{(n - 1)} (t), x^{(n)} (t)) = 0$

(A.1)

for a given

F : D \subseteq ℝ \times X^{n + 1} \to X

$F : D \subseteq ℝ \times X^{n + 1} \to X$

constitutes an ODE of order

n

$n$

In the rest of this appendix, whenever not ambiguous, we will suppress the explicit dependence on

t

$t$

for simplicity of notation. Note that the first and second order derivatives are also often denoted by

x^{'}

$x^{'}$

and

x^{″}

$x^{″}$

, and specially when the independent variable is time, also by

\dot{x}

$\dot{x}$

and

\ddot{x}

$\ddot{x}$

as well.

ODE (A.1) is said to be linear if

F

$F$

is a linear function of the variables

x (t), x^{(1)} (t), \dots, x^{(n - 1)} (t), x^{(n)} (t)

$x (t), x^{(1)} (t), \dots, x^{(n - 1)} (t), x^{(n)} (t)$

. A similar definition applies to PDEs. An equation not in linear form is called nonlinear ODE or PDE, respectively.

An important class of first-order equations are those in which the independent variable does not appear explicitly. Such equations are called autonomous and have the form

x^{'} = f (x)

$x^{'} = f (x)$

Definition A.2

A solution of ODE(A.1)over an interval

t \in I \subseteq ℝ

$t \in I \subseteq ℝ$

is a function

φ (t)

$φ (t)$

that identically satisfies(A.1)over the interval of

I

$I$

. That is (1) the first

n

$n$

-derivatives of

x

$x$

exist for any point in the interval of

I

$I$

; (2) for every

t \in I

$t \in I$

F

$F$

is defined, i.e.

(t, φ, φ^{'}, \dots, φ^{(n})

$(t, φ, φ^{'}, \dots, φ^{(n})$

is in the domain of

F

$F$

; and (3)

F (t, φ, φ^{'}, \dots, φ^{n}) = 0, \forall t \in I

$F (t, φ, φ^{'}, \dots, φ^{n}) = 0, \forall t \in I$

This definition describes an exact solution of the ODE, as opposed to an approximate one. When a solution of the ODE needs to satisfy the initial condition of

φ (t_{0}) = x_{0}

$φ (t_{0}) = x_{0}$

for a given

(t_{0}, x_{0}) \in D

$(t_{0}, x_{0}) \in D$

, we refer to the problem as an initial value problem (IVP). Some very important questions about a solution of an ODE (PDE) or an IVP is the existence, uniqueness, and stability of solution or solutions.

A.2. First-order Differential Equations

By Eq. (A.1) and when

F

$F$

is invertible with respect to

x^{(n)} (t)

$x^{(n)} (t)$

, a first-order ODE may also be expressed in the following form:

$x^{'} = f (t, x),$ $x^{'} = f (t, x),$

(A.2)

for a function

f : D \subseteq ℝ \times X \to X

$f : D \subseteq ℝ \times X \to X$

. For linear first-order ODEs, the integrating factor solution approach can be used to obtain the desired result. Details on the application of such techniques can be found in [40, Section 2.1].

In cases where

x

$x$

is a single-valued function of

t

$t$

, this is just a single ODE. If, on the other hand,

x

$x$

is a multivalued function of

t

$t$

, i.e.

X = X_{1} \times X_{2} \times \dots X_{m}

$X = X_{1} \times X_{2} \times \dots X_{m}$

for a positive integer

m

$m$

, then the ODE can be decomposed and expressed in terms of each element of the vector function

x

$x$

. For such a case, the

f

$f$

function is also multivalued, i.e.

f = (f_{1}, \dots, f_{m})

$f = (f_{1}, \dots, f_{m})$

such that each

f_{i} : D \subseteq ℝ \times X \to X_{i}

$f_{i} : D \subseteq ℝ \times X \to X_{i}$

. This leads to the following system of

m

$m$

differential equations:

$x_{i}^{'} = f_{i} (t, x_{1}, \dots, x_{m}), i = 1, \dots, m$ $x_{i}^{'} = f_{i} (t, x_{1}, \dots, x_{m}), i = 1, \dots, m$

(A.3)

that need to be simultaneously satisfied over the interval of solution. The converse direction yields another interpretation of the above system of first-order ODEs. According to this if there are

m

$m$

unknown functions

x_{1}, \dots x_{m}

$x_{1}, \dots x_{m}$

that need to simultaneously satisfy

m

$m$

first-order differential equations, then by introducing an

m

$m$

-dimensional vector-valued function one may obtain a single vectorized differential equation.

The form of first-order ODE presented in (A.2) can also model higher order ODEs through introduction of auxiliary dependent variables. Specifically, consider an

n

$n$

-th order ODE of the form

x^{(n)} = F_{0} (t, x, x^{'}, \dots, x^{(n - 1)})

$x^{(n)} = F_{0} (t, x, x^{'}, \dots, x^{(n - 1)})$

. Now consider the auxiliary functions

y_{1}, \dots, y_{n}

$y_{1}, \dots, y_{n}$

such that

y_{1} = x

$y_{1} = x$

y_{2} = x^{'}

$y_{2} = x^{'}$

y_{3} = x^{″}

$y_{3} = x^{″}$

, and so on till

y_{n} = x^{(n - 1)}

$y_{n} = x^{(n - 1)}$

. Then, we have

y_{1}^{'} = x^{'} = y_{2}

$y_{1}^{'} = x^{'} = y_{2}$

y_{2}^{'} = x^{″} = y_{3}, \dots, y_{n - 1}^{'} = x^{(n - 1)} = y_{n}

$y_{2}^{'} = x^{″} = y_{3}, \dots, y_{n - 1}^{'} = x^{(n - 1)} = y_{n}$

. Moreover,

y_{n}^{'} = x^{(n)}

$y_{n}^{'} = x^{(n)}$

, which must be equal to

F_{0} (t, x, x^{'}, \dots, x^{(n - 1)})

$F_{0} (t, x, x^{'}, \dots, x^{(n - 1)})$

, hence

y_{n}^{'} = F_{0} (t, x, x^{'}, \dots, x^{(n - 1)}) = F_{0} (t, y_{1}, y_{2}, \dots, y_{n})

$y_{n}^{'} = F_{0} (t, x, x^{'}, \dots, x^{(n - 1)}) = F_{0} (t, y_{1}, y_{2}, \dots, y_{n})$

. Hence, the

n

$n$

th order ODE

x^{(n)} = F_{0} (t, x, x^{'}, \dots, x^{(n - 1)})

$x^{(n)} = F_{0} (t, x, x^{'}, \dots, x^{(n - 1)})$

is equivalent to the following system of ODEs:

$y_{i}^{'} = y_{i + 1} (i = 1, \dots, (n - 1)),$ $y_{i}^{'} = y_{i + 1} (i = 1, \dots, (n - 1)),$

$y_{n}^{'} = F_{0} (t, y_{1}, y_{2}, \dots, y_{n}) .$ $y_{n}^{'} = F_{0} (t, y_{1}, y_{2}, \dots, y_{n}) .$

In (A.3), if

f_{i}

$f_{i}$

functions are linear functions in

x

$x$

, specifically,

$x_{i}^{'} = \sum_{j = 1}^{m} a_{i j} (t) x_{j} + b_{i} (t) i = 1, \dots, m,$ $x_{i}^{'} = \sum_{j = 1}^{m} a_{i j} (t) x_{j} + b_{i} (t) i = 1, \dots, m,$

(A.4)

where

a_{i j}

$a_{i j}$

b_{i}

$b_{i}$

are real-valued continuous functions of

t

$t$

over the interval

I

$I$

, then we have a first-order system of linear ODEs. Using the technique of introducing auxiliary functions for higher order derivatives of the unknown function

x

$x$

, we can convert the

n

$n$

-th order linear ODE of

x^{(n)} = a_{1} (t) x^{(n - 1)} + a_{2} (t) x^{(n - 2)} + \dots + a_{n} (t) x + b (t)

$x^{(n)} = a_{1} (t) x^{(n - 1)} + a_{2} (t) x^{(n - 2)} + \dots + a_{n} (t) x + b (t)$

into a first-order system of linear ODEs too [40]. The analysis and properties of (systems of) linear ODEs are well-developed, and consequently, whenever meaningful, nonlinear ODE systems are analyzed by approximating them through “linearization” (around an operation point) [40].

Some first-order ODEs of the form

\frac{d x}{d n} = f (x, n)

$\frac{d x}{d n} = f (x, n)$

can be transformed as

M (x, n) + N (x, n) \frac{d x}{d n} = 0

$M (x, n) + N (x, n) \frac{d x}{d n} = 0$

and cast in the form

M (n) d n + N (x) d x = 0

$M (n) d n + N (x) d x = 0$

when

M

$M$

is a function of

n

$n$

and

N

$N$

a function of

x

$x$

. Such equations are called separable. The solution to such equation can be easily obtained. More on separable ODEs and their solution methodology can be found in [40].

A.3. Existence and Uniqueness of a Solution

Existence of a solution to any ODE of the form

x^{'} = f (x, t)

$x^{'} = f (x, t)$

with initial condition

x (0) = x_{0}

$x (0) = x_{0}$

is guaranteed for any continuous finite dimensional function

f

$f$

. More formally, we have the following.

Theorem A.1

[Solution Existence[73, 2.4.4]] Let

X

$X$

(the

ℝ^{m}

$ℝ^{m}$

space for the values of the unknown function

x

$x$

) be finite dimensional, let

D

$D$

be an open set in

ℝ \times X

$ℝ \times X$

, let

(t_{0}, x_{0}) \in D

$(t_{0}, x_{0}) \in D$

and let

f : D \to X

$f : D \to X$

be continuous (for

t \geq t_{0}

$t \geq t_{0}$

). Then there exists at least one solution

φ

$φ$

of the ODE

x^{'} = f (t, x)

$x^{'} = f (t, x)$

satisfying the initial condition of

φ (t_{0}) = x_{0}

$φ (t_{0}) = x_{0}$

and reaching the boundary of

D

$D$

on the right.

In (A.2), we say function

f : D \to X

$f : D \to X$

satisfies a

K

$K$

-Lipschitz condition in

x

$x$

over

D

$D$

, where

D \subseteq ℝ \times X

$D \subseteq ℝ \times X$

, if there exists a

K > 0

$K > 0$

, such that

$for all (t, x), (t, y) \in D, ∥ f (t, x) - f (t, y) ∥ \leq K ∥ x - y ∥ .$ $for all (t, x), (t, y) \in D, ∥ f (t, x) - f (t, y) ∥ \leq K ∥ x - y ∥ .$

Note that in the above Lipschitz condition, the right hand side does not have any explicit appearance of

t

$t$

, and the

t

$t$

in the two terms of the left hand side are the same. For ODEs

x^{'} = f (t, x)

$x^{'} = f (t, x)$

, where

f

$f$

satisfies the Lipschitz condition, there is a result stronger than Theorem A.1, which guarantees not only existence but also uniqueness of the solution.

Theorem A.2

[Solution Existence and Uniqueness[73, 2.7.4]] Let

I

$I$

be an interval in

ℝ

$ℝ$

and assume

(t_{0}, x_{0}) \in I \times X

$(t_{0}, x_{0}) \in I \times X$

. Consider

f : I \times X \to X

$f : I \times X \to X$

to be a continuous function that is

K

$K$

-Lipschitz in

x

$x$

over

J \times X

$J \times X$

, where

J

$J$

is any compact subinterval of

I

$I$

(

K

$K$

may depend on

J

$J$

). Then, the IVP of

x^{'} = f (t, x)

$x^{'} = f (t, x)$

and

x (0) = x_{0}

$x (0) = x_{0}$

has one and only one solution over

I

$I$

The continuity requirement of this theorem for

f

$f$

can be relaxed as long as discontinuities constitute a null-measure set [72]. A measure is a function that assigns a non-negative real number or

\infty

$\infty$

to (certain) subsets of a set

X

$X$

[210,226]. It must assign zero to the empty set and be (countably) additive: the measure of a “large” subset that can be decomposed into a finite (or countable) number of “smaller” disjoint subsets is the sum of the measures of the “smaller” subsets. Thus, a measure on a set is a systematic way to assign a number to each suitable subset of that set, intuitively interpreted as its size [210,226]. Any set of measure zero is called a null-set (or simply a null-measure set).

A.4. Linear Ordinary Differential Equations

In this section, we review some elements of the theory of systems of linear ODEs. These can be helpful in the understanding of the content of Chapters 3, 6 and 7, where systems of ODEs emerge.

Consider the first-order system of linear ODEs as in (A.4). Using a matrix representation, we can rewrite (A.4) in the form

$x^{'} = A (t) x + b (t),$ $x^{'} = A (t) x + b (t),$

where

x

$x$

and

b

$b$

are

m

$m$

-dimensional vectors of continuous functions from

I \subseteq ℝ \to X

$I \subseteq ℝ \to X$

, and for finite dimensional

X

$X$

A (t)

$A (t)$

is the

m \times m

$m \times m$

matrix

[a_{i j} (t)]

$[a_{i j} (t)]$

where

a_{i j}

$a_{i j}$

are all real-valued and continuous. Consider the initial condition of

x (0) = (x_{10}, \dots, x_{m 0})

$x (0) = (x_{10}, \dots, x_{m 0})$

. The existence and uniqueness of the solution to this IVP follows from Theorem A.2. Since the functions are linear, they automatically satisfy the Lipschitz condition, with

K

$K$

associated with the supremum/maximum of

A (t)

$A (t)$

’s norm over the compact interval mentioned in the statement of Theorem A.2.

When

b (t)

$b (t)$

is identically zero, the resulting linear ODE,

x^{'} = A (t) x

$x^{'} = A (t) x$

, is called homogeneous linear ODE . Then,

x (t) = \vec{0}

$x (t) = \vec{0}$

is the unique solution of the homogeneous linear ODE with the initial state of

x_{0} = \vec{0}

$x_{0} = \vec{0}$

. Clearly, addition of a solution of a linear ODE with any solution of its associated homogeneous linear ODE leads to a new solution of that linear ODE. Moreover, subtraction of two solutions of a linear ODE results in a solution of its associated homogeneous counterpart. The solution space of the homogeneous linear ODE forms a vector space. Let

φ_{1}, \dots, φ_{p}

$φ_{1}, \dots, φ_{p}$

p

$p$

solutions of the homogeneous linear ODE

x^{'} = A (t) x

$x^{'} = A (t) x$

. Then

φ_{1} (t), \dots, φ_{p} (t)

$φ_{1} (t), \dots, φ_{p} (t)$

are linearly independent at each

t \in I

$t \in I$

if and only if they are linearly independent at some point

t_{0} \in I

$t_{0} \in I$

. The proof of this key result can be found in [73, 2.8.2]. Therefore, if

X

$X$

has finite dimension

m

$m$

and

φ_{1}, \dots, φ_{m}

$φ_{1}, \dots, φ_{m}$

are

m

$m$

linearly independent solutions of the homogeneous linear ODE, then every other solution of it can be written as a unique linear combination of

φ_{1}, \dots, φ_{m}

$φ_{1}, \dots, φ_{m}$

, which is known as the general solution of the homogeneous linear ODE. Hence, if

ν

$ν$

is a solution of the nonhomogeneous linear ODE (called a particular solution ), then every solution of the nonhomogeneous problem

ψ

$ψ$

is the sum of the general solution of the associated homogeneous problem and a particular solution, i.e.

ψ = \sum_{j = 1}^{m} α_{j} φ_{j} + ν

$ψ = \sum_{j = 1}^{m} α_{j} φ_{j} + ν$

for a unique set of scalars

α_{1}, \dots, α_{m}

$α_{1}, \dots, α_{m}$

The solution of the IVP

x^{'} = A (t) x + b (t)

$x^{'} = A (t) x + b (t)$

x (0) = x_{0}

$x (0) = x_{0}$

, can be expressed as the following:

$x = Λ (t) (Λ {(t_{0})}^{- 1} x_{0}) + Λ (t) \int_{t_{0}}^{t} Λ {(τ)}^{- 1} b (τ) d τ,$ $x = Λ (t) (Λ {(t_{0})}^{- 1} x_{0}) + Λ (t) \int_{t_{0}}^{t} Λ {(τ)}^{- 1} b (τ) d τ,$

where

Λ (t)

$Λ (t)$

is a fundamental kernel¹ of the linear transformation associated with

A (t)

$A (t)$

. When

X

$X$

has a finite dimension equal to

m

$m$

Λ (t)

$Λ (t)$

is a matrix whose columns are the coordinates of

m

$m$

linearly independent solutions of the homogeneous linear ODE

x^{'} = A (t) x

$x^{'} = A (t) x$

. Additionally, when the coefficients of the linear ODE are constant, i.e. we have an autonomous linear ODE , the basis-forming solutions of the homogeneous ODE

x^{'} = A x

$x^{'} = A x$

are of the form

e^{λ_{l} t} ϕ_{l p} (t)

$e^{λ_{l} t} ϕ_{l p} (t)$

for

l = 1, \dots, L

$l = 1, \dots, L$

and

p = 1, \dots, P_{l}

$p = 1, \dots, P_{l}$

for polynomials

ϕ_{l p}

$ϕ_{l p}$

of degree of at most

P_{l} - 1

$P_{l} - 1$

, where

λ_{1}, \dots, λ_{L}

$λ_{1}, \dots, λ_{L}$

are the distinct eigenvalues of matrix

A

$A$

, and

P_{1}, \dots, P_{L}

$P_{1}, \dots, P_{L}$

are their respective multiplicity.

A.5. Stability

Consider the autonomous ODE of

x^{'} = f (x)

$x^{'} = f (x)$

(where there is no explicit dependence of

f

$f$

t

$t$

) with the solution of

φ (x_{0}, t)

$φ (x_{0}, t)$

for the initial value of

x (0) = x_{0}

$x (0) = x_{0}$

. Then a point

\hat{x} \in X

$\hat{x} \in X$

is an equilibrium (also known as a steady state, fixed point, or critical state) if the constant function

ϕ (t) = \hat{x}, \forall t

$ϕ (t) = \hat{x}, \forall t$

, is a solution of the ODE with the initial condition

x (0) = \hat{x}

$x (0) = \hat{x}$

, i.e. the solution remains at

\hat{x}

$\hat{x}$

if it starts there as the initial state. We say an equilibrium

\hat{x}

$\hat{x}$

is stable if any solution of the IVP

x^{'} = f (x)

$x^{'} = f (x)$

x (0) = x_{0}

$x (0) = x_{0}$

with

x_{0}

$x_{0}$

close to

\hat{x}

$\hat{x}$

remains in a small neighborhood of

\hat{x}

$\hat{x}$

for all

t \geq 0

$t \geq 0$

. It is further called asymptotically stable if it is stable and there is a small neighborhood of

\hat{x}

$\hat{x}$

such that if the initial value

x_{0}

$x_{0}$

is in that neighborhood we have

{lim}_{t \to \infty} φ (x_{0}, t) = \hat{x}

${lim}_{t \to \infty} φ (x_{0}, t) = \hat{x}$

The following result governs the stability of equilibrium points derived from

f (x) = 0

$f (x) = 0$

Theorem A.3

[[73]] Let

\hat{x}

$\hat{x}$

be an equilibrium of the ODE

x^{'} = f (x)

$x^{'} = f (x)$

. If for every eigenvalue

ξ

$ξ$

of the Jacobian matrix of

f

$f$

\hat{x}

$\hat{x}$

we have

R e (ξ) < 0

$R e (ξ) < 0$

, then

\hat{x}

$\hat{x}$

is asymptotic stable. If there exists an

ξ

$ξ$

with

R e (ξ) > 0

$R e (ξ) > 0$

, then

\hat{x}

$\hat{x}$

is unstable.

It should be noted that a finite dimensional space is assumed. In vector calculus, the Jacobian matrix is the matrix of all first-order partial derivatives of a vector-valued function. Specifically, suppose

f : ℝ^{n} \to ℝ^{m}

$f : ℝ^{n} \to ℝ^{m}$

is a function which takes as input the vector

x \to ℝ^{n}

$x \to ℝ^{n}$

and produces as output the vector

f (x) \to ℝ^{m}

$f (x) \to ℝ^{m}$

. Then, the Jacobian matrix

J

$J$

f

$f$

is an

m \times n

$m \times n$

matrix, usually defined and arranged as follows:

$J = \frac{d f}{d x} = [\begin{matrix} \frac{\partial f}{\partial x_{1}} & \dots & \frac{\partial f}{\partial x_{n}} \end{matrix}] = [\begin{matrix} \frac{\partial f_{1}}{\partial x_{1}} & \dots & \frac{\partial f_{1}}{\partial x_{n}} \\ ⋮ & ⋱ & ⋮ \\ \frac{\partial f_{m}}{\partial x_{1}} & \dots & \frac{\partial f_{m}}{\partial x_{n}} \end{matrix}] .$ $J = \frac{d f}{d x} = [\begin{matrix} \frac{\partial f}{\partial x_{1}} & \dots & \frac{\partial f}{\partial x_{n}} \end{matrix}] = [\begin{matrix} \frac{\partial f_{1}}{\partial x_{1}} & \dots & \frac{\partial f_{1}}{\partial x_{n}} \\ ⋮ & ⋱ & ⋮ \\ \frac{\partial f_{m}}{\partial x_{1}} & \dots & \frac{\partial f_{m}}{\partial x_{n}} \end{matrix}] .$