Difference Equations Class Notes 2003

Difference Equations M250 Class Notes 2003 1 Introduction In Chapter 1, we experimented a bit with difference equations. We will now present methods of analyzing certain types of difference equations. First some terminology- if you’ve had differential equations before, these will sound very familiar. • A first order homogeneous difference equation is given by: xn+1 = axn or xn+1 − axn = 0 • A first order nonhomogeneous difference equation is given by: xn+1 = axn + b xn+1 = axn + bn In the first case, we’ll be able to transform the equation to a homogeneous version. The second case will take more to analyze. • We say that pn = f (n) is a solution, or closed form solution to a difference equation if it satisfies the difference equation relationship. To show that pn is a solution, substitute it into the difference equation to see if the equality holds. • 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 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 . We create a new sequence, yn , so that: case, we found the fixed point, x∗ = 1−a yn = 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; one that we derived earlier in Chapter 3, when we were working with the rocket launch problem: 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 = −( 74 + 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: b n = c 0 + c 1 n + . . . + c m n m ⇒ p n = A 0 + A1 n + . . . + Am n m 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 = C1 + C2 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 = C1 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 . If (a, b) = (−1, −1), then θ = 5π , and lastly, if (a, b) = (1, −1), then theta = 3π 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π xn = 2 C1 cos + C2 sin 4 4 √ On the other hand, if λ = 1 − i, then r = 2 and θ = − π4 , and n 2 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: n  n   nπ nπ + (x1 − x0 ) sin 4 4   nπ nπ − (x0 − x1 ) sin 4 4  xn = 2 2 x0 cos   And in the second case, x̂n = 2 2 x0 cos   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 7 Nonlinear Difference Equations In general, we will not be able to solve nonlinear difference equations in a closed form, and this will probably not be a surprise to you. After all, in Chapter 1, we saw that we could induce either very simple or very complex output in the logistic model, xn+1 = αxn (1 − xn ) Even in these case, however, we can still do some analysis of the solutions. For example, we can compute the values of the fixed points. To do more analysis requires more tools than we will cover here. For a good reference for these types of equations, see for example, “A First Course in Chaotic Dynamical Systems”, by Robert Devaney. 8 Systems of Difference Equations We’ll follow the textbook for these. 8