Discrete (Difierence) Equations

1 Discrete (Difference) EquationsA Discrete , or difference, equation expresses a relationship between the elements of a sequence,{yn},wheren N0 {0,1,2, ..}. For example, the trivial difference equationyn+1=yn,(1)has the solutionyn=y0, which means that the sequence{yn}may be any constant mathematical models are posed in the form of Discrete Equations . The (in)famous logisticmapyn+1=ryn(1 yn),(2)was introduced as a model for the growth of a population. Here,yn [0,1] represents the (scaled)population in then-th year,y0is the initial population; andr >0 is a combined birth and Equations also arise when solving continuous models using numerical methods, a nec-essary task for all but the most simple models. Computers can only work with Discrete data, socontinuous Equations must be discretised1before they can be solved continuous differential equationdydx= 0;(3)has the simple solutiony=y(0), a constant function. A simple discretisation method is to usefinite differences and approximate the derivative by the expressiondydx(x) y(x+h) y(x)h,wherehis , we define the sequence{yn}, such thaty0=y(0),y1=y(h),y2=y(h+h) =y(2h).

2 Yn=y(nh). Thus,dydx(nh) y(nh+h) y(nh)h=yn+1 Discrete approximation to the differential equation (3) is, therefore,yn+1 ynh= 0 yn+1 yn= 0 yn+1=yn,our original example (1). In this simple example, the solutions to the Discrete equation and contin-uous equation are exactly the same and independent ofh, why?In fact, there is a strong connection between difference Equations and differential a differential equation can always be approximated by a difference equation, can you seehow?1 Discretisation is the general term used to describe the procedure of converting a continuous system into a set ofdiscrete Linear difference Equations with constant coefficientsA generalm-th order difference equation with constant coefficients can be written in the formamyn+m+am 1yn+m 1+ +a1yn+1+a0yn=rn,(4)where{ak},k 0, .. , mare constants, andrn=r(n) is an arbitrary function. Note that the axishas been re-scaled so that the distance between points in the sequence{yn}ish= 1, the standardconvention when working directly with difference solution of equation (4) can be split into two separate procedures: Solution of the homogeneous equation (rn= 0) Calculation of a particular solution(any function that satisfies the entire inhomogeneous equation)The solution of the equation is thesumof the particular solution and the solution of thehomogeneous equation, known as the complementary function.

3 Note that this linear superposition(adding the two solutions together) is only possible because the difference equation is equations1st orderA homogeneous difference equation is one in which the right-hand side is zero,i.. 0, inequation (4). Initially, the simplest case to consider is a first- order , linear, homogeneous differenceequation with constant coefficients,yn+1+pyn= 0,(5)wherepis a find the solution by an inductive procedure; rearranging equation (5) givesyn= pyn 1,(6)and because the equation (6) must be true for anyn(>1), thenyn 1= pyn 2,provided thatn >2.(7)Combining Equations (6) and (7) givesyn= ( p)2yn 2= = ( p)ny0;we have continued the inductive procedure until we reachedy0, which must be given as an initialcondition Thus, the fundamental solution of the equation (5) isy0Cn, whereCis a constant thatis the solution of the characteristic (or auxiliary) equationC+p= orderOur result may be generalised to homogeneous difference Equations of any order :amyn+m+am 1yn+m 1+ +a1yn+1+a0yn= 0.

4 (8)The equation (8) can only be satisfied ifyn+1is equal toynmultiplied by a constant,yn+1=Cyn;in which case, each term in the equation is equal to any other term multiplied by a constant,e. +2=Cyn+1=C2yn, etc. Note that the constant will not necessarily be the same for each pair ofterms. The condition is merely equation(5) in another guise, however, and we have already shownthat the solution has the formyn=Cn. On substitution of this result into equation (8), we obtainamCn+m+am 1Cn+m 1+ +a1Cn+1+a0Cn= though byCn,2we obtain the characteristic equationamCm+am 1Cm 1+ +a1C+a0= characteristic equation is anm-th order polynomial and will havemroots, each of whichrepresents a different solution of the difference equation. The general solution may by found by alinear combination of thesemsolutions:yn=A1Cn1+A2Cn2+ +AmCnm,where{Ak}are constants and{Ck}are the roots of the characteristic equation. Note that calcula-tion of the constants{Ak}requiresmboundary will see in MT1222/MT1232 that the same general philosophy can be used to deduce thegeneral solution of a linear homogeneous differential equation with constant +am 1dm 1ydxm 1+ +a1dydx+a0y= 0.

5 (9)In this case the condition to be satisfied is thatdydx=Cy, which implies thaty= eCx. Substitutionof this form into equation (9) gives the resultamCmeCx+am 1Cm 1eCx+ +a1 CeCx+a0eCx= now divide through by eCxto obtain the same characteristic equation as in the case of thedifference equation:amCm+am 1Cm 1+ +a1C+a0= 0,but the general solution of the differential equation isy(x) =A1eC1x+A2eC2x+ + note that the trivial sequenceyn= 0 is always a solution of a homogeneous equation, and we assume thatC6= 0, in order to find a non-trivial Express the series{5,10,20,40, ..}as a difference equation and solve it to find an explicitexpression difference equation isyn+1= 2yn yn+1 2yn= characteristic equation is, therefore,C 2 = 0, and so the general solution isyn=A12nThe initial conditiony0= 5, can be used to findA1= 5 and soyn= 5 solutionsIn order to calculate a particular solution, we use the method of substitution , which is fancy wayof saying that we determine the solution by working from a general (guessed) Find a particular solution of the difference equationyn+1+ 2yn=n.

6 (10)If the right-hand side is a polynomial inn, then we should try a general polynomial solutionof the same order . In this case, we try a solution of the formyn=An+B. On substitutioninto the equation we obtainA(n+ 1) +B+ 2An+ 2B= find the unknown valuesAandBby equating coefficients of powers ofn:n1: 3A= 1,n0:A+ 3B= 0,Solving these two simultaneous Equations we find the solutionA= 1/3, B= 1/9 yn=3n complementary function of the equation (10) isA1( 2)n, because the characteristic equationisC+ 2 = 0. The general solution of the difference equation (10) is, thereforeyn=3n 19+A1( 2)n,and the constantA1will depend on the initial Non-linear difference equationsIn a linear difference equation, every term of the equation contains at most one of the elementsof the sequence{yn}and the elements occur only as themselves are not raised to anypower (other than one) and are not an argument to a function. In a non-linear difference equation,all these restrictions are +1=yn,yn+1=y2n,yn+2=yn+1+ynyn+2=yn+1yn,y n+2= 4yn+1+ 3ynyn+2= 4eyn,As you might expect, methods of solution for the two different types of equation are very differentand the solutions themselves exhibit very different properties:LinearNon-linearStandard methods for finding analyticsolutions, see 1No standard method for findinganalytic solutions,Non-uniqueness multiple solutionsLinear Superposition sum of solutions is also a behaviour, bifurcations, chaosThere is no standard method for finding analytic solutions to non-linear difference , it is an area, where numerical experiments are as important as theory in understanding thesystem.

7 You may wish to try and write programs that calculate the sequences{yn}for non-lineardifference Fixed points of difference equationsA simple technique that can be used to obtain a great deal of information about non-linear differenceequations is to use a fixed-point analysis. The idea is to find particular points for which the solutionis fixed (does not change), in other words,yn+1=yn, n. The analysis is not restricted to non-lineardifference Equations ; in fact, the second problem on Worksheet 1 included a fixed point Find the fixed points of the difference equationyn+1=y2n.(11)At a fixed pointyn+1=yn, so we are looking for values ofynsuch thatyn=y2n y2n yn= 0, yn(yn 1) = 0,and the equation has two fixed points atyn= 0 and 1. That these solutions are fixed pointsis easy to verify on substitution into equation (11).3 The fixed points of a difference equation are rather special because if any sequence ever visits one of the fixed points, it will always remain there. We might expect, therefore, that any solutionwill eventually reach a fixed point of the system.

8 Unfortunately, things aren t quite that example, if there is more than one fixed point, can we say which one the system will reach first?The answermustdepend on where the sequence starts the initial condition. If the sequencestarts at a fixed point, we know that it will remain there, but what about when it starts nearby?How near is near? What do we mean by near anyway? In order to answer these types of questions,we can perform alinear stability analysisof the fixed Linear stability analysis of fixed pointsDefinition of linear stabilityThe first step is to define what we mean by the term linear stability. The idea is remarkably simpleand is best (always) explained through a simple analogy. Consider a rigid pendulum moving freelyunder the action of gravity. The pendulum is a mechanical system that consists of a rigid bar withone end fixed to a rigid support. The bar is free to rotate about the fixed end (the pivot).uuFigure 1: A rigid pendulum has two fixed points: the free end can be either directly above ordirectly below the pivot (assuming that gravity acts vertically downwards.)

9 There are, in fact, two possible fixed points of the system, corresponding to the states when theend of the pendulum is either directly above or directly below the pivot. If you were to place thependulum (carefully) in either of these positions, it would remain there for all time. The idea of alinear stability analysis is to see what happens if we displace the pendulum slightly from either ofthese positions,i. it a flick with your fixed point is said to belinearly stableif the systemmoves backto the fixed point afterit has been slightly perturbed. In the context of our mechanical analogy, the pendulum hangingbelow the pivot is a linearly stable fixed that we could also regard as a fixed point of the system, although in order to prove this we must usethe substitutionzn= 1/ynand show thatzn= 0 is a fixed point of the resulting difference fixed point is said to belinearly unstableif the systemmoves awayfrom the fixed pointafter it has been slightly perturbed. The free end of the pendulum balanced vertically above thepivot is a linearly unstable fixed point.

10 If the pendulum is displaced, it will swing around the pivot,oscillate about the lower fixed point and eventually settle mathematical terms, we must consider what happens whenyn=Y+ yn,(12)whereYis a fixed point of the system and yn 1 is a small perturbation to the system. The ideaof the analysis is to find an explicit expression for yn. If| yn| 0 whenn , then the systemmoves back to the fixed point atYand we conclude that the fixed point is linearly stable. Thewordlinearin the expression linear stability analysis refers to the following important assumption:In a linear stability analysis we assume that the perturbation ynis so small that wecan neglect all terms of the form ymnwherem 2. That is, we keep only termslinear in Recall that the difference equationyn+1=y2n(11) has two fixed points atyn= 0, 1. Analysethe linear stability of these fixed substitute the ansatz (12) into the equation (11) to obtainY+ yn+1= (Y+ yn)2=Y2+ 2Y yn+ ,Yis a fixed point of equation (11), soY=Y2and we have yn+1= 2Y yn+ y2n 2Y yn,when we neglect all non-linear terms, because yn 1.