HOME

TheInfoList



OR:

A matrix difference equation is a
difference equation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
in which the value of a
vector Vector most often refers to: * Euclidean vector, a quantity with a magnitude and a direction * Disease vector, an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematics a ...
(or sometimes, a matrix) of variables at one point in time is related to its own value at one or more previous points in time, using
matrices Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the ...
. The order of the equation is the maximum time gap between any two indicated values of the variable vector. For example, :\mathbf x_t = \mathbf_ + \mathbf_ is an example of a second-order matrix difference equation, in which is an vector of variables and and are matrices. This equation is homogeneous because there is no vector constant term added to the end of the equation. The same equation might also be written as :\mathbf x_ = \mathbf_ + \mathbf_ or as :\mathbf x_n = \mathbf_ + \mathbf_ The most commonly encountered matrix difference equations are first-order.


Nonhomogeneous first-order case and the steady state

An example of a nonhomogeneous first-order matrix difference equation is :\mathbf x_t = \mathbf_ + \mathbf with additive constant vector . The steady state of this system is a value of the vector which, if reached, would not be deviated from subsequently. is found by setting in the difference equation and solving for to obtain : \mathbf^* = mathbf-\mathbf\mathbf where is the
identity matrix In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. It has unique properties, for example when the identity matrix represents a geometric transformation, the obje ...
, and where it is assumed that is
invertible In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers. Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that ...
. Then the nonhomogeneous equation can be rewritten in homogeneous form in terms of deviations from the steady state: : \left mathbf_t - \mathbf^*\right= \mathbf\left mathbf_-\mathbf^*\right


Stability of the first-order case

The first-order matrix difference equation is
stable A stable is a building in which working animals are kept, especially horses or oxen. The building is usually divided into stalls, and may include storage for equipment and feed. Styles There are many different types of stables in use tod ...
—that is, converges asymptotically to the steady state —if and only if all
eigenvalue In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...
s of the transition matrix (whether real or complex) have an
absolute value In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if x is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), ...
which is less than 1.


Solution of the first-order case

Assume that the equation has been put in the homogeneous form . Then we can iterate and substitute repeatedly from the initial condition , which is the initial value of the vector and which must be known in order to find the solution: :\begin \mathbf y_1 &= \mathbf_0 \\ \mathbf y_2 &= \mathbf_1=\mathbf A^2 \mathbf y_0 \\ \mathbf y_3 &= \mathbf_2=\mathbf A^3 \mathbf y_0 \end and so forth, so that by
mathematical induction Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots  all hold. This is done by first proving a ...
the solution in terms of is :\mathbf y_t=\mathbf A^t \mathbf y_0 Further, if is diagonalizable, we can rewrite in terms of its
eigenvalues and eigenvectors In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...
, giving the solution as :\mathbf y_t = \mathbf^\mathbf^ \mathbf y_0, where is an matrix whose columns are the
eigenvector In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by ...
s of (assuming the eigenvalues are all distinct) and is an
diagonal matrix In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero; the term usually refers to square matrices. Elements of the main diagonal can either be zero or nonzero. An example of a 2×2 diagon ...
whose diagonal elements are the eigenvalues of . This solution motivates the above stability result: shrinks to the zero matrix over time if and only if the eigenvalues of are all less than unity in absolute value.


Extracting the dynamics of a single scalar variable from a first-order matrix system

Starting from the -dimensional system , we can extract the dynamics of one of the state variables, say . The above solution equation for shows that the solution for is in terms of the eigenvalues of . Therefore the equation describing the evolution of by itself must have a solution involving those same eigenvalues. This description intuitively motivates the equation of evolution of , which is : y_ = a_1 y_ + a_2 y_ + \dots + a_n y_ where the parameters are from the characteristic equation of the matrix : :\lambda^ - a_1 \lambda^ - a_2 \lambda^ - \dots - a_n \lambda^ = 0. Thus each individual scalar variable of an -dimensional first-order linear system evolves according to a univariate th-degree difference equation, which has the same stability property (stable or unstable) as does the matrix difference equation.


Solution and stability of higher-order cases

Matrix difference equations of higher order—that is, with a time lag longer than one period—can be solved, and their stability analyzed, by converting them into first-order form using a
block matrix In mathematics, a block matrix or a partitioned matrix is a matrix that is interpreted as having been broken into sections called blocks or submatrices. Intuitively, a matrix interpreted as a block matrix can be visualized as the original matrix w ...
(matrix of matrices). For example, suppose we have the second-order equation :\mathbf x_t = \mathbf_ + \mathbf_ with the variable vector being and and being . This can be stacked in the form :\begin\mathbf_t \\ \mathbf_ \\ \end = \begin \mathbf & \mathbf \\ \mathbf & \mathbf \\ \end \begin \mathbf_ \\ \mathbf_ \end where is the
identity matrix In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. It has unique properties, for example when the identity matrix represents a geometric transformation, the obje ...
and is the
zero matrix In mathematics, particularly linear algebra, a zero matrix or null matrix is a matrix all of whose entries are zero. It also serves as the additive identity of the additive group of m \times n matrices, and is denoted by the symbol O or 0 followe ...
. Then denoting the stacked vector of current and once-lagged variables as and the block matrix as , we have as before the solution :\mathbf z_t = \mathbf L^t \mathbf z_0 Also as before, this stacked equation, and thus the original second-order equation, are stable if and only if all eigenvalues of the matrix are smaller than unity in absolute value.


Nonlinear matrix difference equations: Riccati equations

In linear-quadratic-Gaussian control, there arises a nonlinear matrix equation for the reverse evolution of a current-and-future-cost ''matrix'', denoted below as . This equation is called a discrete dynamic
Riccati equation In mathematics, a Riccati equation in the narrowest sense is any first-order ordinary differential equation that is quadratic in the unknown function. In other words, it is an equation of the form y'(x) = q_0(x) + q_1(x) \, y(x) + q_2(x) \, y^2( ...
, and it arises when a variable vector evolving according to a linear matrix difference equation is controlled by manipulating an exogenous vector in order to optimize a quadratic cost function. This Riccati equation assumes the following, or a similar, form: : \mathbf_ = \mathbf +\mathbf'\mathbf_t\mathbf - \mathbf'\mathbf_t\mathbf\left mathbf'\mathbf_t\mathbf+\mathbf\right\mathbf'\mathbf_t\mathbf where , , and are , is , is , is the number of elements in the vector to be controlled, and is the number of elements in the control vector. The parameter matrices and are from the
linear equation In mathematics, a linear equation is an equation that may be put in the form a_1x_1+\ldots+a_nx_n+b=0, where x_1,\ldots,x_n are the variables (or unknowns), and b,a_1,\ldots,a_n are the coefficients, which are often real numbers. The coeffici ...
, and the parameter matrices and are from the quadratic cost function. See here for details. In general this equation cannot be solved analytically for in terms of ; rather, the sequence of values for is found by iterating the Riccati equation. However, it has been shown that this Riccati equation can be solved analytically if and , by reducing it to a scalar rational difference equation; moreover, for any and if the transition matrix is nonsingular then the Riccati equation can be solved analytically in terms of the eigenvalues of a matrix, although these may need to be found numerically. In most contexts the evolution of backwards through time is stable, meaning that converges to a particular fixed matrix which may be irrational even if all the other matrices are rational. See also . A related Riccati equation is :\mathbf_ = -\left mathbf+\mathbf\mathbf_t\rightleft mathbf+\mathbf\mathbf_t\right in which the matrices are all . This equation can be solved explicitly. Suppose \mathbf X_t = \mathbf N_t \mathbf D_t^, which certainly holds for with and with . Then using this in the difference equation yields :\begin \mathbf_&=-\left mathbf+\mathbf_t\mathbf_t^\rightmathbf_t\mathbf_t^\left mathbf+\mathbf_t\mathbf_t^\right\\ &=-\left mathbf_t+\mathbf_t\rightleft left[\mathbf+\mathbf_t \mathbf_t^\rightmathbf_t\right">mathbf+\mathbf_t_\mathbf_t^\right.html" ;"title="left[\mathbf+\mathbf_t \mathbf_t^\right">left[\mathbf+\mathbf_t \mathbf_t^\rightmathbf_t\right\\ &=-\left mathbf_t+\mathbf_t\rightleft[\mathbf_t+\mathbf_t\right]^\\ &=\mathbf_\mathbf_^ \end so by induction the form \mathbf X_t = \mathbf N_t \mathbf D_t^ holds for all . Then the evolution of and can be written as :\begin \mathbf_ \\ \mathbf_ \end = \begin -\mathbf & -\mathbf \\ \mathbf & \mathbf \end \begin \mathbf_t \\ \mathbf_t \end \equiv \mathbf \begin\mathbf_t \\ \mathbf_t \end Thus by induction :\begin \mathbf_t \\ \mathbf_t \end = \mathbf^ \begin \mathbf_0 \\ \mathbf_0 \end


See also

* Matrix differential equation *
Difference equation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
*
Linear difference equation In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear ...
*
Dynamical system In mathematics, a dynamical system is a system in which a Function (mathematics), function describes the time dependence of a Point (geometry), point in an ambient space, such as in a parametric curve. Examples include the mathematical models ...
* Algebraic Riccati equation


References

{{reflist Linear algebra Matrices (mathematics) Recurrence relations Dynamical systems