Notes - Discrete Systems
Rick Hutcheson January 21, 2013
Contents
1 Basic Denitions and Examples 1.1 Discrete Dynamic Systems . . . . . . . . . . . . . . . . . . 1.2 Snapshots and Sequences . . . . . . . . . . . . . . . . . . . 1.3 Systems as Recurrences . . . . . . . . . . . . . . . . . . . . Classifying Systems 2.1 System Orders . 2.2 Homogeneity . 2.3 Linearity . . . . 2.4 Autonomy . . . Equilibrium Values Solving Systems 2 2 2 3 5 5 6 6 6 7 8
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
3 4
1
1.1
Basic Denitions and Examples
Discrete Dynamic Systems
We will dene a discrete dynamic system in stages. Informally, a system is a collection of objects or elements that are each in some state (of being). The combined state of all of these objects is the state of the system. A dynamic system is one whose status may change over time. This is in direct contrast to a static system, whose state will be the same for all time. A discrete dynamic system is a dynamic system whose status we measure at discrete time intervals. For example, given some system, S, we call S discrete if we (somehow) measure its status at each passing of some discrete amount of time, such as 1 second, 1 year, etc. One of the only terms that we have not yet dened is state. We Informally, we will say that the state of the system is some value (usually a numeric value) that represents the important properties of the system.
Example 1.1 (A Simple System)
A situation that lends itself simple system denition is one containing two objects, the sun and a thermometer. Here, a reasonable denition for the systems state would be the reading of the thermometer.
1.2
Snapshots and Sequences
Given that our discrete systems have their state measured at regular and intervals, we will usually normalize the units, so that each measurement takes place 1 unit of time after the next. If a represents our system, then a(0) is the systems initial value, and each measurement afterwards is labelled by
a(1), a(2), a(3), . . . , a(n) . Our goal when working with discrete systems will be to nd a pattern in this sequence.
1.3
Systems as Recurrences
Since discrete systems describe the change in some situation as time passes, they lend themselves naturally to recursive denition. That is, in many situations, it will be most natural to describe the behavior of the system in terms of how it has changed since the last measurement. Combined with some initial conditions, this gives a complete description of the system.
Example 1.2 (Recursive Denition)
Initially, Rosie has a lollipop. Since Rosie is a bully, she manages to wrangle another lollipop from one of her (innite) classmates every minute. We shall let a(n) denote the state of the system after n minutes have passed. We will dene the state of the system to be the number of lollipops Rosie has acquired. Initial Condition: by: Initially, Rosie has a single lollipop, easily modelled
a(0) = 1 Behavior: We are trying to make a general statement about how the system will change at time n + 1, given that it is in some state at time n. The simplest solution to this problem is to use recursion, since it allows us to ignore the number of lollipops Rosie has at the moment, and instead concentrate on how the number of lollipops will change.
Since we know that Rosie acquires another lollipop each minute, we will dene a(n + 1) in terms of a(n). That is: a(n + 1) = a(n) + 1. And so, the entire system is modelled by the system of relations:
a(0) = 1 a(n + 1) = a(n) + 1
Note:
In many cases, systems occur when studying real-world situations, and so we can call that situation the system. However, there are also situations in which we have no real-world analogue to the system, only a recurrence relation. In these situations, we say that the equation itself is the system. That is, do not be surprised when encountering a sentence such as: Consider the system a(n) = ka(n 1) + b.
Classifying Systems
In general, a discrete system takes the form:
a(n) = f1 (a(n 1)) + f2 (a(n 2)) + fn (a(0)) + g(n) + h(a(n), n) (1) where any or all of the terms, fi (a(n i )), can be 0. There are many properties of these relations that can give us clues as to their solutions.
2.1
System Orders
Sometimes, systems will depend on more than just the previous value. Informally, the number of values that our recurrence has to remember is called the order of the system. Formally, the order of the system is the maximum i s.t. a(n i ) appears in the system.
Example 2.1 (System Orders)
Given the 3 systems: a(n) = a(n 1) + 2a(n 2) + 3a(n 5) b(n) = 2b(n 4) c(n) = 4 We have: 1. System a is order 5 (A fth-order system). 2. System b is order 4 (A fourth-order system). 3. System c is order 0.
2.2
Homogeneity
As equation (1) shows, a system can contain functions of both a(n) and n itself. (Designated by equations fi (a(n)) and g(n). Informally, the system is called homogeneous if a system contains only terms containing a(n). If the system contains terms with both a(n) and n, then it is called nonhomogeneous. Formally, the system is nonhomogeneous if g(n) is nonconstant.
2.3
Linearity
We classify the linearity of a system by the linearity of the functions of a(ni ) and n. Informally, a system is linear if all of the functions f1 , f2 , . . . , fn , g is linear. It is nonlinear otherwise. Formally, a system is linear if the degree of f1 , f2 , . . . , fn , g are all less than 2, and nonlinear if any of f1 , f2 , . . . , fn , and g are greater than or equal to 2.
2.4
Autonomy
There is one more generalization we can make to our general system. Weve shown that there can be terms with both a(n i ) and n, as well as constants. However, we have not discussed terms that have both a(n i ) and n. In (1), this is the function h(a(n), n). Informally, if the system does not contains terms like these, we call it autonomous, and if it does then it is called nonautomous. Formally, the system is nonautonomous if the function h is nonconstant.
Equilibrium Values
Solving Systems