 Home Mathematics  # Linear Systems

We are interested in modeling discrete change. Modeling with discrete dynamical systems employs a method to explain certain discrete behaviors or make long-term predictions. A powerful paradigm that we use to model with discrete dynamical systems is: The dynamical systems that we will study with this paradigm will differ markedly in appearance and composition, but we will be able to solve a large class of these “seemingly” different dynamical systems with similar methods. In this chapter, we will use iteration and graphical methods to answer questions about discrete dynamical systems.

We will use flow diagrams to help us see how the dependent variable changes. Flow diagrams help to see the paradigm and to put the problem into mathematical terms. Let’s consider financing a new Ford Mustang. The total cost is \$25,000. We can put down \$2,000, so we need to finance \$23,000. The dealership offers us 2% APR financing over 72 months. Consider the flow diagram for financing the car below in Figure 2.1 that depicts this situation. FIGURE 2.1: Car Financing Flow Diagram

We’ll use the flow diagram to help build the discrete dynamical model. Let A(n) = the amount owed after n months. Notice that the arrow pointing into the Amount Owed is the interest which increases the unpaid balance. The arrow pointing out of the oval is the monthly payment which decreases the debt. then our paradigm future = present + change gives We will model dynamical systems that have constant coefficients. For example, a third-order discrete dynamical system with constant coefficients that is homogeneous may be written in the form where bo, b, and 62 are arbitrary constants. If we added a term not involving a(n)s to the right side, this DDS would be nonhomogeneous.

The “Tower of Hanoi” puzzle, that we will illustrate shortly, involves moving a tower of disks from one pole to another. The number of discrete moves H(n) that it takes to move n disks depends on the number of discrete moves it took to move n — 1 disks. For the drug dosage model of Example 2.1, the model shows the amount of drug in the bloodstream after n hours depends on the amount of drug in the bloodstream after n — 1 hours. For financial matters, such as our Mustang purchase, the amount we still owe after n months depends upon the amount we owed after n — 1 months. We will also find this process based on transitioning states useful when we discuss Markov chains as an example of a discrete dynamical system.

Recall that a first-order DDS is a system where the next iteration a(n), the state of the system after n iterations, is related only to the previous iteration a(n — 1) by the relation i.e., a(n) is a function of only a(n — 1) for n = 2, 3, .... For example, a(n) = 2a(n — 1) is a first-order DDS. If the function / of o(n) is just a constant multiple of a(n), a constant coefficient, we will say that the discrete dynamical system is linear. If the function f involves powers (like a(n)2), or a functional relationship (like a(n)/a(n — 1) or sin(a(n — 1))), we will say that the discrete dynamical system is nonlinear.

Example 2.2. Iteration with the Tower of Hanoi.

The Tower of Hanoi puzzle was invented in 1883 by the French mathematician Edouard Lucas (1842-1891) under the pseudonym "Professor N. Claus (of Siam) from the Mandarin of the College of Li-Sou-Stian.” The puzzle consists of a board with three upright pegs and disks (now usually 6 to 10) with successively smaller outside diameters. The disks begin on the first peg with the largest disk on the bottom, topped by the next largest disk, and so on up to the smallest disk on top forming a tower or pyramid as we see in Figure 2.2.

The object of the game is to transfer the disks, one at a time, using the smallest possible number of moves, to the third peg to form an identical pyramid. During each transfer step, a larger disk may not be placed on top of a smaller disk—this is why a second and third pegs are needed. Lucas’ original rules were the following. FIGURE 2.2: Tower of Hanoi Puzzle4

The game consists of moving this, by threading the disks on another

peg, and by moving only one disk at a time, obeying the following rules:

I. After each move, the disks will all be stacked on one, two, or three pegs, in decreasing order from the base to the top.

II. The top disk may be lifted from one of the three stacks of disks, and placed on a peg that is empty.

III. The top disk may be lifted from one of the three stacks and placed on top of another stack, provided that the top disk on that stack is larger.

Lucas’ original La Tour d’Hanoi game had eight disks. The puzzle was a model to illustrate moving the legendary “Sacred Tower of Brahma,” which actually had “sixty-four levels in fine gold, trimmed with diamonds.” This tower was attended by monks of the Temple of Bernares who moved one disk a minute according to the long-established ritual that no larger disk could be placed on a smaller disk. The monks believed, so Lucas’s story went, that as soon as all sixty-four disks were transferred, the earth would collapse in a cloud of dust.

This legend is somewhat alarming, so let’s use induction to find a formula for the number of moves required to transfer n disks from the first peg to the third peg. Suppose that we have n + 1 disks. Then we can move n smaller disks from the first peg to the second peg in a(n) moves, the number of moves for n disks. Then we move the largest disk from the first peg to the third peg. Finally we move the n smaller disks from the second peg to the third peg in a(n) moves. Therefore, a(n+l) = (a(n) + l)+a(n) = 2a(n) + l. So the recursion relation that gives the number of moves required is a(n + 1) = 2a(n) + 1; the initial value is a(l) = 1, meaning that we start with the case where there is only one disk to move. Figure 2.3 shows a plausible flow diagram for the Tower of Hanoi. FIGURE 2.3: Tower of Hanoi Flow Diagram

There is a formula for the number of moves required to move n disks from the first peg to the third peg. We will consider methods of solving this recursion relation to find this formula. The first method is iteration. Later we will learn a better method by explicitly solving the DDS.

Let’s build Table 2.1 by iterating the recursion relation TABLE 2.1: Tower of Hanoi Recursion

 Number of Disks Recursion Relationship Number of Moves 1 a(l) = 1 1 2 a(2) = 2a(l) + 1 = 2(1) + 1 3 3 a(3) = 2a(2) + 1 = 2(3) + 1 7 4 a(4) = 2a(3) + 1 = 2(7) + 1 15 5 a(5) = 2a(4) + 1 = 2(15) + 1 31 6 a(6) = 2a(5) + 1 = 2(31) + 1 63 7 a(7) = 2a(6) + 1 = 2(63) + 1 127 n o(n) = 2 a(n — 1) + 1 2a(n - 1) + 1

Using iteration, we repeatedly calculate the recursion relation, each time for the next value of n. To find out how many minutes it would take to move sixty-four disks, we would have to iterate the given recursion relation 64 times. We’ll use Maple to help us with the computations for tabulating Table 2.2.

TABLE 2.2: Tower of Hanoi with Sixty-Four Disks

 Disks Moves Required 1 1 5 31 10 1023 15 32767 20 1048575 25 33554431 30 1073741823 35 34359738367 40 1099511627775 45 35184372088831 50 1125899906842623 55 36028797018963967 60 1152921504606846975 64 18446744073709551615

The table above shows that 18446744073709551615 ss 1.84467 x 1019 minutes are needed. Let’s convert to units that are equivalent. There are 1440 minutes in a day and 525,600 minutes in a year. At one move per minute, a(64) is equivalent to 3.5135 x 1013 years. Imagine how long that amount of time really is. (The estimated age of the universe is 1.37 x Ю10 years.)

The power of discrete dynamical systems is that they can always be solved by iteration. Between the table of iteration values and a graph of those values, we are able to analyze difficult modeling problems.

In Maple, to obtain the iteration values, we can either write a procedure with proc or, when the recurrence has a closed-form solution, use the rsolve and seq commands. We illustrate both below to obtain the values seen in Tables 2.1 and 2.2. First, rsolve and seq. We have a closed-form analytical solution H(n) = 2n — 1. If there had not been a formula, rsolve would just have echoed the input. Using rsolve is a quick way to see if a DDS has a closed-form solut ion.

Now we can use seq with the formula from rsolve to generate values. Also, since there is a formula, we don’t have to iterate through all n up to the number we want. When a dynamical system does not have a closed-form analytical solution, the rsolve command echoes its input, so we cannot use a formula in the (seq) command to generate values. We’ll need to use proc to create a program to iterate the discrete dynamical system. Call the program Tower and use inputs nO, fO, and n where nO is the first nonnegative integer in our domain, fO is our first range value (that is, (nO,fO) is the initial condition), and n is the nonnegative integer value from our domain that we need. We use "option remember’ so the program stores and can recall the previously iterated values. Without remembering values, a simple recursion can take huge numbers of calculations to compute a value. For example, the Fibonacci numbers given by F(n) = F{n— 1) +F(n — 2) take on the order of 2” calculations to compute F(n) when previous values aren’t remembered. Now we can use seq with the procedure Tower to generate values. (Tower is in the book’s PSMv2 Maple package.) Also, since there is a formula, we don’t have to iterate through all n up to the number we want. Are the values the same as with the formula?

Let’s plot the recursion. It’s easy to see how quickly this recursion grows.

Example 2.3. A Drug Dosage Problem.

A doctor prescribes an oral dose of 100 mg of a certain drug every hour for a patient . Assume that the drug is immediately absorbed into the bloodstream once taken. Also, assume that every hour the patient’s body eliminates 25% of the drug that is in the bloodstream. Suppose that the patient’s bloodstream had 0 mg of the drug prior to taking the first pill. How much of the drug will be in the patient’s bloodstream after 72 hours?

General Problem Statement.

Determine the relationship between the amount of drug in the bloodstream and time.

Assumptions.

• • The problem can be modeled by a discrete dynamical system.
• • The patient is of normal size and health.
• • There are no other drugs being taken that will affect the prescribed drug.
• • There are no internal or external factors that will affect the drug absorption or elimination rates.
• • The patient always takes the prescribed dosage at the correct time. Variables.

Define o(n) = amount of drug that is in the bloodstream after a period of n = 0, 1, 2, ... hours.

Flow Diagram:

We diagram the flow in Figure 2.4. FIGURE 2.4: Amount of Drug in the Bloodstream Flow Diagram

Model Construction.

Let o(n) represent the amount of drug in the system after time period

n. We calculate the change in the drug’s amount as: change = dose — system’s loss. The the future = present + change paradigm gives Rom the DDS we see that since the body loses 25% of the amount of drug in the bloodstream every hour, there would be 75% of the amount of drug in the bloodstream remaining every hour. After one hour, the body has 75% of the initial amount, 0 mg, plus the dose of 100 mg that is added every hour. The bloodstream has 100 mg of drug after one hour. After two hours the body has 75% of the amount of drug that was in the bloodstream after one hour (100 mg) plus an additional 100 mg of drug added from the new oral dose. There would be 175 mg of drug in the bloodstream after two hours. After three hours the body has 75% of the amount of drug in the bloodstream after two hours plus an additional 100 mg of drug added to the bloodstream. Thus there would be 231.25 mg of drug in the bloodstream after three hours.

The values are tabulated in Table 2.3.

TABLE 2.3: Amount of Drug in the Bloodstream - First Computations

 Hour Amount of Drug (mg) 0 a(0) = 0 1 a(l) = 0.75 -a(0) + 100 = 100 2 a(2) = 0.75 -a(l) + 100 = 175 3 a(3) = 0.75 • a(2) + 100 = 231.25

We can see the change that occurs every hour within this system (amount of drug in the bloodstream), and the state of the system after any hour, is dependent on the state of the system after the previous hour. This is a discrete dynamical system (DSS).

To find the value of a( 72) we can either iterate the recurrence with seq or use rsolve to obtain a formula. Let’s start with iteration. (Remember to either use restart or open a new Worksheet to have a fresh Maple environment.) Since this is a simple recurrence, we’ll use a ‘short-cut’ procedure. Asking Maple for a(72) will perform the iterations and display the result. We could see all the iterates by using se^([A;,a(fc)], к = 0..72).

Let’s attempt to find a formula by using rsolve. (Remember to restart.) Note that, in this case, Maple returned an exact answer even though we entered decimals.

What is the long-term level of drug in the patient’s bloodstream? Checking iterates would show that a patient’s bloodstream would have approximately 400 mg of the drug after 24 hours.

It’s time for a plot.  Interpretation of Results.

The DDS shows that the drug reaches a value where change stops. The concentration of the drug in the bloodstream eventually levels at 400 mg. If 400 mg is both a safe and effective drug level, then this dosage schedule is an acceptable treatment. Note that we’re looking at discrete points, but the drug concentration is a continuous quantity. What is the shape of the continuous curve modeling drug concentration?

We discuss the concept of change stopping—equilibrium—later in this chapter. We used the Maple command limit to quickly determine long-term behavior of the DDS discovering the equilibrium.

Example 2.4. The Time Value of Money.

A bank customer wishes to purchase a \$1000 savings certificate that pays 1.2% interest a year (APR) compounded monthly at 0.1% = 1.2%/12 per month. Why use a discrete model here? At our local financial institution, there is a sign that says that interest is compounded (and paid) at the end of each month based on the average monthly balance. Therefore, we conclude that a discrete model for interest is appropriate.

Remark: Always divide the annual interest rate (APR) by the number of compounding periods per year to compute the actual interest rate being used. Here, the annual rate is 1.2% or 0.012 and interest is calculated and paid monthly (12 times per year). So, use 0.012/12 = 0.001 as the monthly interest rate.

General Problem Statement.

Find a relationship between the amount of money invested and the time over which it is invested.

Assumptions.

The interest rate is constant over the entire time period. No additional money is added or withdrawn other than the interest.

Variables.

Let n = 1,2,3,... be number of months passed.

Let a(n) = the amount of money in the certificate after month n.

Flow Diagram:

We diagram the flow in Figure 2.6. FIGURE 2.5: Flow Diagram for Money in a Certificate

Model Construction.

Since Using our paradigm future = present + change, the worth of the certificate with interest accumulated each month is The initial deposit of \$1000 gives Use the discrete time periods (1,2,3,...) to iterate as follows: Calling 1.001 = r = (1 + г), where i is the monthly interest rate, gives suggesting that Let's check with Maple. Note that Maple converts to rational numbers when using rsolve. Recall that unapply turns an expression into a function.

What is the overall trend? The graph looks like a line even though this function is obviously nonlinear. How many years does it take for the plot to show some curvature?

Let’s look at the sequence of 4 years of values to see how Money grows. Can the account ever reach §10,000? We can determine that it will take about 192 years to reach Si 0.000. Since Money(n) goes to infinity as n grows, the account continues to grow as long as there are no withdrawals.

Example 2.5. A Simple Mortgage.

Five years ago, your parents purchased a home by financing \$150,000 over 20 years with an interest rate of 4% APR. Their monthly payments are \$908.97. They have made 60 payments and wish to know what they actually owe on the house at this time. They can use this information to decide whether or not to refinance their house at a lower interest rate of 3.25% APR for the next 15 years or 3.5% APR for 20 years.

The change in the amount owed each period increases by the amount of the interest and decreases by the amount of the payment.

General Problem.

Build and use a model that relates the time to the amount owed on a mortgage for a home.

Assumptions.

• • Initial interest was 4% APR.
• • The monthly interest rate is 4%/12 = 0.33%.
• • Payments are made on time each month.
• • The current rates for refinancing are 3.25% for 15 years and 3.50% for 20 years.

Variables.

Let b(n) = amount owed on the home after n months. Flow Diagram:

We diagram the flow in Figure 2.6. FIGURE 2.6: Flow Diagram for Amount Owed on Mortgage

Model Construction. Model Solution:

Use rsolve to find a formula for b(n). Since Maple converts to rational numbers for rsolve, we’ll embed an evalf to return to decimals. First, a reasonableness check. The last payment leaves 0.17 / to pay; this is due to round-off error in the computations as 0.04/12 is a repeating decimal value.

Let’s plot the DDS over the entire 20 years (240 months). Note the graph shows that the balance essentially reaches 0 in 240 months. Now let’s make a table of the mortgage balance up to month 60. From the table, we see the balance on the mortgage is b(60) = 122885.7038. After paying for 60 months, your parents still owe \$122,885.70 of the original \$150, 000. They have paid a total of \$54,538.20, but only \$27,114.30 went towards the principal, the rest, \$27,423.90, was interest. If the family continues with this loan, they will make 240 payments of \$908.97 for a total of \$218,152.80. They would pay a total of \$68,152.80 in interest. They’ve already paid \$27,423.90 in interest, so they would pay an additional \$41,038.50 in interest. Should they refinance?

The alternatives for refinancing were 3.25% for 15 years or 3.50% for 20 years. Assuming no additional costs for refinancing, only securing a new mortgage for what they currently owe, \$122,885.70, what is the best choice?

You will be asked to solve this problem in the exercise set.

Exercises

Iterate and graph the following DDSs. Explain their long-term behavior. For each DOS. find a realistic scenario that it might explain/model.

• 1. a(n+ 1) = 0.5a(ra) + 0.1, a(0) = 0.1
• 2. a(n+ 1) = 0.5 a(ra) + 0.1, a(0) = 0.2
• 3. a(n + 1) = 0.5 a(n) + 0.1, o(0) = 0.3
• 4. a{n + 1) = 1.01 a(n) - 1000, a(0) = 90000
• 5. a{n + 1) = 1.01 a(n) - 1000, a(0) = 100000
• 6. a{n + 1) = 1.01 a(n) - 1000, a(0) = 110000
• 7. a(n + 1) =—1.3 a(n) + 20, a(0) = 9
• 8. a(n + 1) = —4a(n) + 50, a(0) = 9
• 9. a(n + 1) = 0.1 a(n) + 1000, a(0) = 9
• 10. a{n + 1) = 0.9987 a(n) + 0.335, a(0) = 72
• 11. Consider the mortgage problem of Example 2.5 (pg. 49). Determine what the cost of each refinancing alternative is compared to the current mortgage. Make a recommendation to your parents.

•  The puzzle is also called the “Tower of Brahma” or the “Tower of Lucas.”There are several intriguing legends about the game. See Paul Stockmeyer’s webpagehttp://www.cs.wm.edu/--pkstoc/toh.html for the original game box and instructions.
•  Photo source: Bjarmason (2005). Creative Commons License.

 Related topics