Matrix difference equation
A matrix difference equation is a difference equation in which the value of a vector (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.[1][2] The order of the equation is the maximum time gap between any two indicated values of the variable vector. For example,
- [math]\displaystyle{ \mathbf x_t = \mathbf{Ax}_{t-1} + \mathbf{Bx}_{t-2} }[/math]
is an example of a second-order matrix difference equation, in which x is an n × 1 vector of variables and A and B are n × n 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
- [math]\displaystyle{ \mathbf x_{t+2} = \mathbf{Ax}_{t+1} + \mathbf{Bx}_{t} }[/math]
or as
- [math]\displaystyle{ \mathbf x_n = \mathbf{Ax}_{n-1} + \mathbf{Bx}_{n-2} }[/math]
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
- [math]\displaystyle{ \mathbf x_t = \mathbf{Ax}_{t-1} + \mathbf{b} }[/math]
with additive constant vector b. The steady state of this system is a value x* of the vector x which, if reached, would not be deviated from subsequently. x* is found by setting xt = xt−1 = x* in the difference equation and solving for x* to obtain
- [math]\displaystyle{ \mathbf{x}^* = [\mathbf{I}-\mathbf{A}]^{-1}\mathbf{b} }[/math]
where I is the n × n identity matrix, and where it is assumed that [I − A] is invertible. Then the nonhomogeneous equation can be rewritten in homogeneous form in terms of deviations from the steady state:
- [math]\displaystyle{ \left[\mathbf{x}_t - \mathbf{x}^*\right] = \mathbf{A}\left[\mathbf{x}_{t-1}-\mathbf{x}^*\right] }[/math]
Stability of the first-order case
The first-order matrix difference equation [xt − x*] = A[xt−1 − x*] is stable—that is, xt converges asymptotically to the steady state x*—if and only if all eigenvalues of the transition matrix A (whether real or complex) have an absolute value which is less than 1.
Solution of the first-order case
Assume that the equation has been put in the homogeneous form yt = Ayt−1. Then we can iterate and substitute repeatedly from the initial condition y0, which is the initial value of the vector y and which must be known in order to find the solution:
- [math]\displaystyle{ \begin{align} \mathbf y_1 &= \mathbf{Ay}_0 \\ \mathbf y_2 &= \mathbf{Ay}_1=\mathbf A^2 \mathbf y_0 \\ \mathbf y_3 &= \mathbf{Ay}_2=\mathbf A^3 \mathbf y_0 \end{align} }[/math]
and so forth, so that by mathematical induction the solution in terms of t is
- [math]\displaystyle{ \mathbf y_t=\mathbf A^t \mathbf y_0 }[/math]
Further, if A is diagonalizable, we can rewrite A in terms of its eigenvalues and eigenvectors, giving the solution as
- [math]\displaystyle{ \mathbf y_t = \mathbf{PD}^{t}\mathbf{P}^{-1} \mathbf y_0, }[/math]
where P is an n × n matrix whose columns are the eigenvectors of A (assuming the eigenvalues are all distinct) and D is an n × n diagonal matrix whose diagonal elements are the eigenvalues of A. This solution motivates the above stability result: At shrinks to the zero matrix over time if and only if the eigenvalues of A 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 n-dimensional system yt = Ayt−1, we can extract the dynamics of one of the state variables, say y1. The above solution equation for yt shows that the solution for y1,t is in terms of the n eigenvalues of A. Therefore the equation describing the evolution of y1 by itself must have a solution involving those same eigenvalues. This description intuitively motivates the equation of evolution of y1, which is
- [math]\displaystyle{ y_{1,t} = a_1 y_{1,t-1} + a_2 y_{1,t-2} + \dots + a_n y_{1,t-n} }[/math]
where the parameters ai are from the characteristic equation of the matrix A:
- [math]\displaystyle{ \lambda^{n} - a_1 \lambda^{n-1} - a_2 \lambda^{n-2} - \dots - a_n \lambda^{0} = 0. }[/math]
Thus each individual scalar variable of an n-dimensional first-order linear system evolves according to a univariate nth-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 (matrix of matrices). For example, suppose we have the second-order equation
- [math]\displaystyle{ \mathbf x_t = \mathbf{Ax}_{t-1} + \mathbf{Bx}_{t-2} }[/math]
with the variable vector x being n × 1 and A and B being n × n. This can be stacked in the form
- [math]\displaystyle{ \begin{bmatrix}\mathbf{x}_t \\ \mathbf{x}_{t-1} \\ \end{bmatrix} = \begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{I} & \mathbf{0} \\ \end{bmatrix} \begin{bmatrix} \mathbf{x}_{t-1} \\ \mathbf{x}_{t-2} \end{bmatrix} }[/math]
where I is the n × n identity matrix and 0 is the n × n zero matrix. Then denoting the 2n × 1 stacked vector of current and once-lagged variables as zt and the 2n × 2n block matrix as L, we have as before the solution
- [math]\displaystyle{ \mathbf z_t = \mathbf L^t \mathbf z_0 }[/math]
Also as before, this stacked equation, and thus the original second-order equation, are stable if and only if all eigenvalues of the matrix L 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 H. This equation is called a discrete dynamic Riccati equation, 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:
- [math]\displaystyle{ \mathbf{H}_{t-1} = \mathbf{K} +\mathbf{A}'\mathbf{H}_t\mathbf{A} - \mathbf{A}'\mathbf{H}_t\mathbf{C}\left[\mathbf{C}'\mathbf{H}_t\mathbf{C}+\mathbf{R}\right]^{-1}\mathbf{C}'\mathbf{H}_t\mathbf{A} }[/math]
where H, K, and A are n × n, C is n × k, R is k × k, n is the number of elements in the vector to be controlled, and k is the number of elements in the control vector. The parameter matrices A and C are from the linear equation, and the parameter matrices K and R are from the quadratic cost function. See here for details.
In general this equation cannot be solved analytically for Ht in terms of t; rather, the sequence of values for Ht is found by iterating the Riccati equation. However, it has been shown[3] that this Riccati equation can be solved analytically if R = 0 and n = k + 1, by reducing it to a scalar rational difference equation; moreover, for any k and n if the transition matrix A 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.[4]
In most contexts the evolution of H backwards through time is stable, meaning that H converges to a particular fixed matrix H* which may be irrational even if all the other matrices are rational. See also Stochastic control § Discrete time.
A related Riccati equation[5] is
- [math]\displaystyle{ \mathbf{X}_{t+1} = -\left[\mathbf{E}+\mathbf{B}\mathbf{X}_t\right]\left[\mathbf{C}+\mathbf{A}\mathbf{X}_t\right]^{-1} }[/math]
in which the matrices X, A, B, C, E are all n × n. This equation can be solved explicitly. Suppose [math]\displaystyle{ \mathbf X_t = \mathbf N_t \mathbf D_t^{-1}, }[/math] which certainly holds for t = 0 with N0 = X0 and with D0 = I. Then using this in the difference equation yields
- [math]\displaystyle{ \begin{align} \mathbf{X}_{t+1}&=-\left[\mathbf{E}+\mathbf{BN}_t\mathbf{D}_t^{-1}\right]\mathbf{D}_t\mathbf{D}_t^{-1}\left[\mathbf{C}+\mathbf{AN}_t\mathbf{D}_t^{-1}\right]^{-1}\\ &=-\left[\mathbf{ED}_t+\mathbf{BN}_t\right]\left[\left[\mathbf{C}+\mathbf{AN}_t \mathbf{D}_t^{-1}\right]\mathbf{D}_t\right]^{-1}\\ &=-\left[\mathbf{ED}_t+\mathbf{BN}_t\right]\left[\mathbf{CD}_t+\mathbf{AN}_t\right]^{-1}\\ &=\mathbf{N}_{t+1}\mathbf{D}_{t+1}^{-1} \end{align} }[/math]
so by induction the form [math]\displaystyle{ \mathbf X_t = \mathbf N_t \mathbf D_t^{-1} }[/math] holds for all t. Then the evolution of N and D can be written as
- [math]\displaystyle{ \begin{bmatrix} \mathbf{N}_{t+1} \\ \mathbf{D}_{t+1} \end{bmatrix} = \begin{bmatrix} -\mathbf{B} & -\mathbf{E} \\ \mathbf{A} & \mathbf{C} \end{bmatrix} \begin{bmatrix} \mathbf{N}_t \\ \mathbf{D}_t \end{bmatrix} \equiv \mathbf{J} \begin{bmatrix}\mathbf{N}_t \\ \mathbf{D}_t \end{bmatrix} }[/math]
Thus by induction
- [math]\displaystyle{ \begin{bmatrix} \mathbf{N}_t \\ \mathbf{D}_t \end{bmatrix} = \mathbf{J}^{t} \begin{bmatrix} \mathbf{N}_0 \\ \mathbf{D}_0 \end{bmatrix} }[/math]
See also
- Matrix differential equation
- Difference equation
- Linear difference equation
- Dynamical system
- Algebraic Riccati equation
References
- ↑ Cull, Paul; Flahive, Mary; Robson, Robbie (2005). Difference Equations: From Rabbits to Chaos. Springer. ch. 7. ISBN 0-387-23234-6.
- ↑ Chiang, Alpha C. (1984). Fundamental Methods of Mathematical Economics (3rd ed.). McGraw-Hill. pp. 608–612. ISBN 9780070107809. https://archive.org/details/fundamentalmetho0000chia_h4v2.
- ↑ Balvers, Ronald J.; Mitchell, Douglas W. (2007). "Reducing the dimensionality of linear quadratic control problems". Journal of Economic Dynamics and Control 31 (1): 141–159. doi:10.1016/j.jedc.2005.09.013. https://papers.tinbergen.nl/01043.pdf.
- ↑ Vaughan, D. R. (1970). "A nonrecursive algebraic solution for the discrete Riccati equation". IEEE Transactions on Automatic Control 15 (5): 597–599. doi:10.1109/TAC.1970.1099549.
- ↑ Martin, C. F.; Ammar, G. (1991). "The geometry of the matrix Riccati equation and associated eigenvalue method". in Bittani; Laub; Willems. The Riccati Equation. Springer-Verlag. doi:10.1007/978-3-642-58223-3_5. ISBN 978-3-642-63508-3.
 |  |
