Difference Equations - Class Notes 2016

Difference Equations Class Notes 2016 1 Introduction • The simplest difference equation: xn+1 = axn or xn+1 − axn = 0 • We might add some complexity by adding a constant or a term that depends on n: xn+1 = axn + b xn+1 = axn + bn • We say that {x0 , x1 , x2 , · · ·} is a SOLUTION to the difference equation if the sequence satisfies the given difference equation. Typically, we do not write solutions this wayWe typically define a solution in terms of some formula depending on n: xn = f (n) • A second order, linear, homogeneous difference equation is of the form: xn+2 + axn+1 + bxn = 0 It is second order because of the xn+2 , and it is linear since xn+2 , xn+1 , xn all appear as linear terms. The reason it is homogeneous is because we do not have b or bn on the right hand side. • The value x∗ is said to be a fixed point (or equilibrium) to a difference equation given by: xn+1 = f (xn ) if x∗ = f (x∗ ). 1 2 First Order Homogeneous DE Given a first order homogeneous difference equation, xn+1 = axn we can say that f (n) = an x0 is the solution. The fixed point to this equation is where: x = ax so x = 0 is the only fixed point (unless a = 1, in which case every point is fixed). If |a| > 1, all solutions will tend (in size) to infinity. If |a| < 1, all solutions will tend to zero as n becomes large. 3 First Order, Nonhomogeneous DE, Part I Given a first order nonhomogeneous difference equation of the form: xn+1 = axn + b we can transform it into a first order homogeneous DE. To do this, note that the only fixed point to a first order homogeneous DE is zero. But our difference equation has a different fixed point: b x = ax + b ⇒ (1 − a)x = b ⇒ x = , a 6= 1 1−a If a = 1, then the difference equation has the form: ⇒ xn+1 = xn + b xn = x0 + nb, b 6= 0 In this case, |xn | → ∞ as n gets large, so we’ll focus on the other case, where a 6= 1. In this b case, we found the fixed point, x∗ = 1−a . We create a new sequence, yn , so that: y n = xn − x∗ Now the difference equation associated to yn will have a fixed point at y ∗ = 0, and: yn+1 = xn+1 − x∗ = axn + b − x∗ = a(yn + x∗ ) + b − x∗ = ayn − (1 − a)x∗ + b = ayn So the closed form solution is: yn = an y0 , or: xn − x∗ = an (x0 − x∗ ) ⇒ xn = an (x0 − x∗ ) + x∗ Which gives the closed form solution to the first order, nonhomogeneous difference equation. It could be written in a different way: x n = an x 0 + b 1 − an 1−a The last term is the sum of a partial geometric series in a. 2 4 Summary so far In the first two types of difference equations, we can classify the long term behavior of xn rather simply: The long term behavior will converge to a fixed point if |a| < 1. The long term behavior will diverge if |a| > 1. If a = 1, the long term behavior could be fixed for all x0 (if b = 0) or diverge (if b 6= 0). If a = −1, the behavior will oscillate between ±x0 (if b = 0), or oscillate between x0 and −x0 + b (if b 6= 0)- the second case you’ll consider in the exercises. 5 First Order, Nonhomogeneous DE, Part II In this case, we consider difference equations of the form: xn+1 = axn + bn where bn now depends on n. For example, we might have something like: xn+1 = 3xn − 2n + 1 Before going into the details of the solution, let’s consider a general situation. Suppose I’ve got a difference equation of the form we are considering, and suppose I know a particular solution, pn . We show that, in this case, anything of the form: qn = can + pn is also a solution: We need to show that qn is a solution to the difference equation. This means that we need to show that: qn+1 = aqn + bn On the left hand side of the equation, we have: qn+1 = can+1 + pn+1 and since pn is a solution to the difference equation, qn+1 = can+1 + apn + bn = a(can + pn ) + bn Now on the right hand side of the equation, aqn + bn = a(can + pn ) + bn Therefore, we have shown that can + pn is also a solution. Now we have two things to do to solve a first order nonhomogeneous difference equation: Find pn , and determine the value 3 of c- the value of c will depend on the initial condition, x0 . Before we do this, consider the following difference equations together with their particular solutions: xn+1 = 3xn + (3n − 1)2n xn+1 = 3xn + (3n − 1)3n xn+1 = 3xn + (1 + n + 2n2 ) n pn = (−3n  − 5)2  pn = n 21 n − 56 3n pn = −( 47 + 32 n + n2 ) You might be seeing a pattern- If bn is of a particular form, then we can make an ansatz1 about the form of the particular solution. For example, if bn has the form: bn = c0 + c1 n + . . . + cm nm ⇒ pn = A0 + A1 n + . . . + Am nm or, bn = (c0 + c1 n + . . . + cm nm ) rn ⇒ pn = (A0 + A1 n + . . . + Am nm )rn , r 6= a at which point we would need to solve for the A0 , A1 , . . . , Am . Let’s do this with the first example, since we know what the answer should be. Given xn+1 = 3xn + (3n − 1)2n , my ansatz will be: pn = (A + Bn)2n . Inserting this into the left hand side of the equation, pn+1 = (A + B(n + 1))2n+1 and into the right hand side of the equation, 3pn + (3n − 1)2n = 3(A + Bn)2n + (3n − 1)2n Now equate both sides: (A + B(n + 1))2n+1 = 3(A + Bn)2n + (3n − 1)2n ⇒ 2(A + Bn + B) = 3A + 3Bn + 3n − 1 To solve this, we make an observation: If two polynomials are equal for all input values, then the coefficients must be equal. In this case, we will equate the coefficients of n and the (separately) the constants. This will give two equations in our two unknowns: Coeffs of n 2B = 3B + 3 Constants 2A + 2B = 3A − 1 From which we get: pn = −(5 + 3n)2n . We can check our answer by checking that it does indeed satisfy the difference equation: pn+1 = −(5 + 3(n + 1))2n+1 = (−5 − 3n − 3)2n+1 = (−8 − 3n)2n+1 and 3pn + (3n − 1)2n = 3(−(5 + 3n)2n ) + (3n − 1)2n = (−8 − 3n)2n+1 Similarly, we can solve more complex difference equations, but the algebra gets a little messy. In these cases, Maple can also give solutions using rsolve (for recurrence solver). Here’s an example in Maple: 1 Ansatz is a German word that has many translations- “basic approach” or “point of departure”, for example. In mathematics, we see it used in differential equations to mean a model form for a solution; an “educated guess”, if you will. 4 > eqn:=x(n+1)=3*x(n)+(3*n-1)*2^n; n eqn := x(n + 1) = 3 x(n) + (3 n - 1) 2 > rsolve({eqn},x(n)); n n n n x(0) 3 + 5 3 + (-3 n - 3) 2 - 2 2 To solve a difference equation with an initial condition, there’s a slight change. To solve xn+1 = −xn + e−2n with an initial condition x(0) = 1: > eqn:=x(n+1)=-x(n)+exp(-2*n); eqn := x(n + 1) = -x(n) + exp(-2 n) > rsolve({eqn,x(0)=1},x(n)); n n (-1) - 1/2 exp(-2 n) (-1) + 1/2 exp(-2 n) 5.1 Summary of First Order, Nonhomogeneous DE Given: xn+1 = axn + bn , and a particular solution pn , then the closed form general solution is: xn = can + pn where c can be solved, given an initial condition. The particular solution, pn , can be solved using an ansatz as long as bn is of a particular form. We can also use Maple to solve the difference equation. In these cases, the long term behavior might be simple (convergence to a point), or might be more complicated. If you’ve had differential equations, you might compare this section with first order nonhomogeneous differential equations of the form: y 0 + ay = f (t) where we solve for the nonhomogeneous part of the solution by again using an ansatz based on the form of f . 6 Second Order, Homogeneous DE Here we consider second order, linear, homogeneous difference equations. These are of the form: xn+2 + αxn+1 + βxn = 0 Use an ansatz of xn = λn to back-substitute and solve for λ. λn+2 + αλn+1 + βλn = 0   λn λ2 + αλ + β = 0 5 Therefore, either λ = 0 or from the quadratic formula, √ −α ± α2 − 4β λ= 2 From this, there are three cases, depending on the discriminant α2 − 4β, which is positive, zero, or negative. • If the discriminant is positive, we have two distinct real values of λ. The general solution is given by: xn = C1 λn1 + C2 λn2 The values of C1 , C2 are generally found by defining x0 and x1 . We could write these constants out, and solve: x0 = C 1 + C 2 x1 = C1 λ1 + C2 λ2 so we get two equations in the two unknowns. • If the discriminant is zero, we have only 1 real λ, and the general solution is: xn = C1 λn + nC2 λn = λn (C1 + nC2 ) Again, the values of C1 , C2 can be found by defining x0 , x1 : x0 = C 1 x1 = λ(C1 + C2 ) • Finally, if the discriminant is negative, we have two complex conjugate solutions, √ α 4β − α2 λ=− ± i = a ± bi 2 2 We will define r as the size (or modulus) of the complex number, √ r = a2 + b 2 and θ as the argument of the complex number, −1 θ = tan b a ! You can visualize a complex number in the plane, where the real part is along the x− axis, and the imaginary part is along the y−axis. The point a + bi is associated with the ordered pair (a, b), and from this we have a triangle with side lengths a, b and hypotenuse r. The value of θ is always measured from the positive real axis. To remove any ambiguities introduced by the inverse tangent, we could take this to be the fourquadrant inverse tangent. For example, if (a, b) = (1, 1) then θ = π4 . If (a, b) = (−1, 1), 6 theta = 3π . If (a, b) = (−1, −1), then θ = 5π , and lastly, if (a, b) = (1, −1), then 4 4 7π θ = 4 . Furthermore, it won’t matter if you consider a + bi or a − bi, as the values of the arbitrary constants (see below) will change to make the solutions match up. In these cases, the general solution can be written as: xn = rn (C1 cos(nθ) + C2 sin(nθ)) Example: xn+2 − 2xn+1 + 2xn = 0 In this case, the characteristic equation is: λ2 − 2λ + 2 = 0 λ = 1 ± i √ Considering λ = 1 + i, r = 2 and θ = π4 . This gives: nπ nπ + C2 sin 4 4 √ On the other hand, if λ = 1 − i, then r = 2 and θ = − π4 , and n      xn = 2 2 C1 cos n   x̂n = 2 2 C1 cos − nπ nπ + C2 sin − 4 4    n   = 2 2 C1 cos nπ nπ − C2 sin 4 4    Solving for C1 , C2 in the first case, we get: xn = 2 nπ nπ + (x1 − x0 ) sin x0 cos 4 4  nπ nπ x0 cos − (x0 − x1 ) sin 4 4  n 2  n 2     And in the second case, x̂n = 2    so that it did not matter if we took λ = a + bi or λ = a − bi as the “primary” complex number for our calculations. In this last case, if r < 1, the solution will “spiral” towards the origin. If r > 1, the solution will “spiral” out. In all cases, if we take a simple nonhomogeneous case, xn+2 + αxn+1 + βxn = γ then we can do a similar transformation as before. Find the fixed point, x∗ = x + αx + βx = γ γ 1+α+β Now, let yn = xn − x∗ . We can show that this transformation leads to a homogeneous equation in yn : yn+2 + αyn+1 + βyn = 0 7 Systems of Difference Equations We create systems of difference equations just as we did systems of differential equations. In the case of two variables, we might have: an+1 = f (an , bn ) bn+1 = g(an , bn ) Where we again define the equilibrium solution as a point (a, b) such that a = f (a, b) b = g(a, b) We can also linearize about the equilibrium the usual way. We can also solve the linear system in the usual way- by looking at eigenvalues and eigenvectors: " xn+1 yn+1 # " = a b c d #" xn yn # We can convert second order difference equations into a linear system (as we did with differential equations). Here’s an example: Convert the second order difference equation into a system of first order. xn+2 + 3xn+1 + xn = 0 SOLUTION: Let an = xn and bn = xn+1 . Then: an+1 = bn bn+1 = −an − 3bn Convert the following system into an equivalent second order difference equation: an+1 = −an + bn bn+1 = an − 3bn SOLUTION: From the first equation, we have: bn = an+1 +an . Substitute this expression into the second equation to get: an+2 + an+1 = an − 3(an+1 + an ) ⇒ an+2 + 4an+1 + 2an = 0 We could go ahead an solve this: The roots to the characteristic equation are −2 ± the general solution is: √ √ an = C1 (−2 + 2)n + C2 (−2 − 2)n √ 2, so From this we get bn : bn = an+1 + an = C1 (−2 + √ 2)n+1 + C2 (−2 − 8 √ 2)n+1 + C1 (−2 + √ 2)n + C2 (−2 − √ n 2) Final notes Finally, just as we had competing species and predator prey models as differential equations, we can also do almost exactly the same as difference equations. We’ll write them down and let you observe the similarities to the continuous cases: an+1 − an = an (1 − σ1 an ) − γ1 an bn bn+1 − bn = bn (2 − σ2 bn ) − γ2 an bn an+1 − an = an (1 − σ1 an ) − γ1 an bn bn+1 − bn = −2 bn + γ2 an bn Homework: Discrete Dynamical Systems 1. Solve: (a) xn+1 = xn + 1 (b) xn+1 = 5xn + n2 (c) xn+1 = 21 xn + 3n 2. Assume the temperature of a roast in the oven increases at a rate proportional to the difference between the oven temperature (set to 400) and the roast temperature. If the roast enters the oven at 50 degrees, and is measured one hour later to be 90, when will the roast reach the FDA safe temperature of 160? (Hint: Write down, then solve the difference equation). 3. Convert the following system of difference equations to a second order difference equation, and solve it if x0 = y0 = 1. xn+1 = 2yn yn+1 = 3xn 4. Solve the second order difference equation with x0 = 1, x1 = −1. (a) xn+2 − xn = 0 (b) xn+2 + xn = 0 (c) xn+2 + 3xn+1 + xn = 0 (d) xn+2 = xn+1 + xn (Do you recognize this famous difference equation? Typically we set x0 = 1, x1 = 1 in this example, so you can solve it that way.) 5. Consider the difference equation: xn+2 + αxn+1 + βxn = 0 where we assume α2 = 4β = 0. Show that xn = n(−α/2)n is a solution. 9 6. Convert the following equations to equivalent systems of first order: (a) xn+2 + xn+1 − xn = 0 (b) xn+2 + 3xn+1 + xn = 0 7. Convert the following systems of first order into an equivalent difference equation of second order. (a) an+1 = an + bn bn+1 = 3an + bn (b) an+1 = 2an + bn bn+1 = an + 2bn 8. Is it always possible to convert a system of two linear equations (as in the last problem) to a single second order difference equation? Explain. 10