Discrete-time Linear Systems - IMT School For Advanced Studies Lucca

Lecture: Discrete-time linear systemsAutomatic Control 1Discrete-time linear systemsProf. Alberto BemporadUniversity of TrentoAcademic year 2010-2011Prof. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-20111 / 34

Lecture: Discrete-time linear systemsIntroductionIntroductiony(t), y(kTs)u(kTs)3.543.5332.52.5221.51.501234510time t12345time tSampling of a continuous signalDiscrete-time signalDiscrete-time models describe relationships between sampled variablesx(kTs ), u(kTs ), y(kTs ), k 0, 1, . . .The value x(kTs ) is kept constant during the sampling interval [kTs , (k 1)Ts )A discrete-time signal can either represent the sampling of a continuous-timesignal, or be an intrinsically discrete signalDiscrete-time signals are at the basis of digital controllers (as well as of digitalfilters in signal processing)Prof. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-20112 / 34

Lecture: Discrete-time linear systemsDifference equationsDifference equationConsider the first order difference equation (autonomous system)§x(k 1) ax(k)x(0) x0The solution is x(k) ak x032.5a 1x(k)21.5a 110.50 a 10012345678910kProf. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-20113 / 34

Lecture: Discrete-time linear systemsDifference equationsDifference equationFirst-order difference equation with input (non-autonomous system)§x(k 1)x(0) ax(k) bu(k)x0The solution has the formx(k) ka x0 {z}natural response k 1 i 0 ai bu(k 1 i){z}forced responseThe natural response depends on the initial condition x(0), the forced responseon the input signal u(k)Prof. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-20114 / 34

Lecture: Discrete-time linear systemsDifference equationsExample - Wealth of a bank accountk: year counterρ: interest ratex(k): wealth at the beginning of year ku(k): money saved at the end of year kx0 : initial wealth in bank accountDiscrete-time model:§ (1 ρ)x(k) u(k)x0Stored amount of money (keur)10 k 5 k 10 %5045403530x(k)x0u(k)ρx(k 1)x(0)2520151 (1.1)k5 60(1.1)k 50x(k) (1.1) · 10 1 1.1kProf. Alberto Bemporad (University of Trento)Automatic Control 1105000.511.522.533.544.55k (years)Academic year 2010-20115 / 34

Lecture: Discrete-time linear systemsDifference equationsLinear discrete-time systemConsider the set of n first-order linear difference equations forced by theinput u(k) R x1 (k 1) a11 x1 (k) . . . a1n xn (k) b1 u(k) x a21 x1 (k) . . . a2n xn (k) b2 u(k)2 (k 1) . xn (k 1) an1 x1 (k) . . . ann xn (k) bn u(k) x1 (0) x10 , . . . xn (0) xn0In compact matrix form:§ x1 where x . Rn .x(k 1)x(0) Ax(k) Bu(k)x0xnProf. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-20116 / 34

Lecture: Discrete-time linear systemsDifference equationsLinear discrete-time systemThe solution isx(k) Ak x {z}0 natural responsek 1 Ai Bu(k 1 i)i 0 {z}forced responseIf matrix A is diagonalizable, A TΛT 1 λ0 .0 λ2 .100 λk1 0 .0 λk2. 0 0Λ . . . . . Ak T . . . . T 1. . . . . . . .0 0 . λn0 0 . λknwhere T [v1 . . . vn ] collects n independent eigenvectors.Prof. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-20117 / 34

Lecture: Discrete-time linear systemsModal responseModal responseAssume input u(k) 0, k 0Assume A is diagonalizable, A TΛT 1The state trajectory (natural response) isk 1x(k) A x0 TΛ T x0 kn αi λki vii 1whereλi eigenvalues of Avi eigenvectors of Aαi coefficients that depend on the initial condition x(0) α1 α . T 1 x(0), T [v1 . . . vn ]αnThe system modes depend on the eigenvalues of A, as in continuous-timeProf. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-20118 / 34

Lecture: Discrete-time linear systemsModal responseExampleConsider the linear discrete-time system x (k 1) 1x2 (k 1)x1 (0) x2 (0) x(k 1)112 x1 (k) 2 x2 (k)x2 (k) u(k) 11 12 0u(k)1x(k) 1 1 x(0)1201Eigenvalues of A: λ1 12 , λ2 1Solution: x(k) 0 1212k0 121 k 111 1k211 1 k 12 k 1 0i 0 1 1 k 1 i 0 1 {z}natural response12 12 i 11 1i21 0u(k 1 i)1 x1(k),x2(k)1.510.5u(k 1 i) k 1 1 1i2u(k 1 i)1i 0 {z}forced response0 0.5 1 1.5012345678910step ksimulation for u(k) 0Prof. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-20119 / 34

Lecture: Discrete-time linear systemsLinear difference equationsnth -order difference equationConsider the nth -order difference equation forced by uan y(k n) an 1 y(k n 1) · · · a1 y(k 1) y(k) bn u(k n) · · · b1 u(k 1) b0 u(k)Equivalent linear discrete-time system in canonical state matrix form 0010.0001.0 0 . . . . . .x(k 1) . x(k) . u(k) 0000.11 a a a. ann 1n 2 1y(k) (bn b0 an ) . . . (b1 b0 a1 ) x(k) b0 u(k) There are infinitely many state-space realizationsMATLABtf2ssnth -order difference equations are very useful for digital filters, digitalcontrollers, and to reconstruct models from data (system identification)Prof. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-201110 / 34

Lecture: Discrete-time linear systemsDiscrete-time linear systemsDiscrete-time linear system x(k 1)y(k) x(0) Ax(k) Bu(k)Cx(k) Du(k)x0Given the initial condition x(0) and the input sequence u(k), k N, it ispossible to predict the entire sequence of states x(k) and outputs y(k), k NThe state x(0) summarizes all the past history of the systemThe dimension n of the state x(k) Rn is called the order of the systemThe system is called proper (or strictly causal) if D 0General multivariable case:x(k)u(k)y(k)Prof. Alberto Bemporad (University of Trento) RnRmRpAutomatic Control 1ABCD Rn nRn mRp nRp mAcademic year 2010-201111 / 34

Lecture: Discrete-time linear systemsDiscrete-time linear systemsExample - Student dynamicsProblem Statement:3-years undergraduate coursepercentages of students promoted, repeaters, and dropouts are roughly constantdirect enrollment in 2nd and 3rd academic year is not allowedstudents cannot enrol for more than 3 yearsNotation:kxi (k)u(k)y(k)αiβiγiYearNumber of students enrolled in year i at year k, i 1, 2, 3Number of freshmen at year kNumber of graduates at year kpromotion rate during year i, 0 αi 1failure rate during year i, 0 βi 1dropout rate during year i, γi 1 αi βi 03rd -order linear discrete-time system: x (k 1) 1x2 (k 1)x (k 1) 3y(k) β1 x1 (k) u(k)α1 x1 (k) β2 x2 (k)α2 x2 (k) β3 x3 (k)α3 x3 (k)Prof. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-201112 / 34

Lecture: Discrete-time linear systemsDiscrete-time linear systemsExample - Student dynamicsIn matrix form x(k 1) y(k) β1 0 α1 β 20 α2 0 0 α3 010 x(k) 0 u(k)β0 3x(k)Simulationy(k)40α1 .60α2 .80α3 .90β1 .20β2 .15β3 .082002012201420162018202020182020step ku(k)51u(k) 50, k 2012, . . .5049201220142016step kProf. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-201113 / 34

Lecture: Discrete-time linear systemsDiscrete-time linear systemsExample - Supply )y(k) 3x3(k)Rx2(k)x3(k)Problem Statement:S purchases the quantity u(k) of raw material at each month ka fraction δ1 of raw material is discarded, a fraction α1 is shipped to producer Pa fraction α2 of product is sold by P to retailer R, a fraction δ2 is discardedretailer R returns a fraction β3 of defective products every month, and sells afraction γ3 to customersMathematical model: x (k 1) 1x2 (k 1)x3 (k 1) y(k) (1 α1 δ1 )x1 (k) u(k)α1 x1 (k) (1 α2 δ2 )x2 (k) β3 x3 (k)α2 x2 (k) (1 β3 γ3 )x3 (k)γ3 x3 (k)Prof. Alberto Bemporad (University of Trento)Automatic Control 1kx1 (k)x2 (k)x3 (k)y(k)month counterraw material in Sproducts in Pproducts in Rproducts sold to customersAcademic year 2010-201114 / 34

Lecture: Discrete-time linear systemsStability of discrete-time linear systemsEquilibriumConsider the discrete-time nonlinear system§x(k 1)y(k) f (x(k), u(k))g(x(k), u(k))DefinitionA state xr Rn and an input ur Rm are an equilibrium pair if forinitial condition x(0) xr and constant input u(k) ur , k N,the state remains constant: x(k) xr , k NEquivalent definition: (xr , ur ) is an equilibrium pair if f (xr , ur ) xrxr is called equilibrium state, ur equilibrium inputThe definition generalizes to time-varying discrete-time nonlinear systemsProf. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-201115 / 34

Lecture: Discrete-time linear systemsStability of discrete-time linear systemsStabilityConsider the nonlinear system§x(k 1)y(k) f (x(k), ur )g(x(k), ur )and let xr an equilibrium state, f (xr , ur ) xrDefinitionThe equilibrium state xr is stable if for each initial conditions x(0) “closeenough” to xr , the corresponding trajectory x(k) remains near xr for all k N aaAnalytic definition: ε 0 δ 0 : x(0) xr δ x(k) xr ε, k NThe equilibrium point xr is called asymptotically stable if it is stable andx(k) xr for k Otherwise, the equilibrium point xr is called unstableProf. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-201116 / 34

Lecture: Discrete-time linear systemsStability of discrete-time linear systemsStability of first-order linear systemsConsider the first-order linear systemx(k 1) ax(k) bu(k)xr 0, ur 0 is an equilibrium pairFor u(k) 0, k 0, 1, . . ., the solution isx(k) ak x0The origin xr 0 is3unstable if a 12.5stable if a 12x(k)asymptotically stable if a 1a 11.510.5x0Automatic Control 10 a 1xr00Prof. Alberto Bemporad (University of Trento)a 1a 024k6810Academic year 2010-201117 / 34

Lecture: Discrete-time linear systemsStability of discrete-time linear systemsStability of discrete-time linear systemsSince the natural response of x(k 1) Ax(k) Bu(k) is x(k) Ak x0 , the stabilityproperties depend only on A. We can therefore talk about system stability of adiscrete-time linear system (A, B, C, D)Theorem:Let λ1 , . . ., λm , m n be the eigenvalues of A Rn n . The systemx(k 1) Ax(k) Bu(k) isasymptotically stable iff λi 1, i 1, . . . , m(marginally) stable if λi 1, i 1, . . . , m, and the eigenvalues with unitmodulus have equal algebraic and geometric multiplicity aunstable if i such that λi 1aAlgebraic multiplicity of λi number of coincident roots λi of det(λI A). Geometricmultiplicity of λi number of linearly independent eigenvectors vi , Avi λi viThe stability properties of a discrete-time linear system only depend on the modulus of the eigenvalues of matrix AProf. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-201118 / 34

Lecture: Discrete-time linear systemsStability of discrete-time linear systemsStability of discrete-time linear systemsProof:The natural response is x(k) Ak x0If matrix A is diagonalizable1 , A TΛT 1 , λ1 0 .0 λ2 .00 λk1 0 .0 . 0 0 1Λ . . . . Ak T . . . . . T. . . . . .00 . λnλk200 . λknTake any eigenvalue λ ρejθ : λk ρ k ejkθ ρ kA is always diagonalizable if algebraic multiplicity - geometric multiplicity 1If A is not diagonalizable, it can be transformed to Jordan form. In this case the natural responsex(t) contains modes kj λk , j 0, 1, . . . , alg. multiplicity geom. multiplicityProf. Alberto Bemporad (University of Trento)Automatic Control 1Academic year 2010-201119 / 34

Lecture: Discrete-time linear systemsStability of discrete-time linear systemsExample 1 x(k 1) 01 x 10x(0) x20solution: x1 (k) x2 (k) 10 x(k)12 eigenvalues of A:ª§10,20, k 1, 2, . . . k1 k 1x10 12 x20 , k 1, 2, . . .21.510.5x2(k)x1(k)0.5asymptotically stable00 0.5 0.50246810 1kProf. Alberto Bemporad (University of Trento)0246810kAutomatic Control 1Academic year 2010-201120 / 34

Lecture: Discrete-time linear systemsStability of discrete-time linear systemsExample 2 x(k 1) 01 x x(0) x1020 x1 (k)x2 (k)110.80.60.60.40.40.20.20 0.2 0.4 0.4 0.6 0.6 1marginally stable0 0.2 0.8kπx10 cos kπ2 x20 sin 2 , k 0, 1, . . .kπx10 sin 2 x20 cos kπ2 , k 0, 1, . . . , 0.8x2(k)x1(k)solution: 1x(k)0 eigenvalues of A: { j, j} 0.80246 1kProf. Alberto Bemporad (University of Trento)0246kAutomatic Control 1Academic year 2010-201121 / 34