EE363 Winter 2008-09Lecture 5Observability and state estimation• state estimation• discrete-time observability• observability – controllability duality• observers for noiseless case• continuous-time observability• least-squares observers• statistical interpretation• example5–1State estimation set upwe consider the discrete-time systemx(t + 1) = Ax(t) + Bu(t) + w(t), y(t) = Cx(t) + Du(t) + v(t)• w is state disturbance or noise• v is sensor noise or error• A, B, C, and D are known• u and y are observed over time interval [0, t − 1]• w and v are not known, but can be described statistically or assumedsmallObservability and state estimation 5–2State estimation problemstate estimation problem: estimate x(s) fromu(0), . . . , u(t − 1), y(0), . . . , y(t − 1)• s = 0: estimate initial state• s = t − 1: estimate current state• s = t: estimate (i.e., predict) next statean algorithm or system that yields an estimate ˆx(s) is called an observer orstate estimatorˆx(s) is denoted ˆx(s|t − 1) to show what information estimate is based on(read, “ˆx(s) given t − 1”)Observability and state estimation 5–3Noiseless caselet’s look at finding x(0), with no state or measurement noise:x(t + 1) = Ax(t) + Bu(t), y(t) = Cx(t) + Du(t)with x(t) ∈ Rn, u(t) ∈ Rm, y(t) ∈ Rpthen we havey(0)...y(t − 1)= Otx(0) + Ttu(0)...u(t − 1)Observability and state estimation 5–4whereOt=CCA...CAt−1, Tt=D 0 · · ·CB D 0 · · ·...CAt−2B CAt−3B · · · CB D• Otmaps initials state into resulting output over [0, t − 1]• Ttmaps input to output over [0, t − 1]hence we haveOtx(0) =y(0)...y(t − 1)− Ttu(0)...u(t − 1)RHS is known, x(0) is to be determinedObservability and state estimation 5–5hence:• can uniquely determine x(0) if and only if N (Ot) = {0}• N (Ot) gives ambiguity in determining x(0)• if x(0) ∈ N (Ot) and u = 0, output is zero ov er interval [0, t − 1]• input u does not affect ability to determine x(0);its effect can be subtracted outObservability and state estimation 5–6Observability matrixby C-H theorem, each Akis linear combination of A0, . . . , An−1hence for t ≥ n, N (Ot) = N (O) whereO = On=CCA...CAn−1is called the observability matrixif x(0) can be deduced from u and y over [0, t − 1] for any t, then x(0)can be deduced from u and y over [0, n − 1]N (O) is called unobservable subspace; describes ambiguity in determiningstate from input and outputsystem is called observable if N (O) = {0}, i.e., Rank(O) = nObservability and state estimation 5–7Observability – controllability dualitylet (˜A,˜B,˜C,˜D) be dual of system (A, B, C, D), i.e.,˜A = AT,˜B = CT,˜C = BT,˜D = DTcontrollability matrix of dual system is˜C = [˜B˜A˜B · · ·˜An−1˜B]= [CTATCT· · · (AT)n−1CT]= OT,transpose of observability matrixsimilarly we have˜O = CTObservability and state estimation 5–8thus, system is observable (controllable) if and only if dual system iscontrollable (observable)in fact,N (O) = range(OT)⊥= range(˜C)⊥i.e., unobservable subspace is orthogonal complement of controllablesubspace of dualObservability and state estimation 5–9Observers for noiseless casesuppose Rank(Ot) = n (i.e., system is observable) and let F be any leftinverse of Ot, i.e., F Ot= Ithen we have the observerx(0) = Fy(0)...y(t − 1)− Ttu(0)...u(t − 1)which deduces x(0) (exactly) from u, y over [0, t − 1]in fact we havex(τ − t + 1) = Fy(τ − t + 1)...y(τ )− Ttu(τ − t + 1)...u(τ)Observability and state estimation 5–10i.e., our observer estimates what state was t − 1 epochs ago, given pastt − 1 inputs & outputsobserver is (multi-input, multi-output) finite impulse response (FIR) filter,with inputs u and y, and output ˆxObservability and state estimation 5–11Invariance of unobservable setfact: the unobservable subspace N (O) is invariant, i.e., if z ∈ N (O),then Az ∈ N (O)proof: suppose z ∈ N (O), i.e., CAkz = 0 for k = 0, . . . , n − 1evidently CAk(Az) = 0 for k = 0, . . . , n − 2;CAn−1(Az) = CAnz = −n−1Xi=0αiCAiz = 0(by C-H) wheredet(sI − A) = sn+ αn−1sn−1+ · · · + α0Observability and state estimation 5–12Continuous-time observabilitycontinuous-time system with no sensor or state noise:˙x = Ax + Bu, y = Cx + Ducan we deduce state x from u and y?let’s look at derivatives of y:y = Cx + Du˙y = C ˙x + D ˙u = CAx + CBu + D ˙u¨y = CA2x + CABu + CB ˙u + D¨uand so onObservability and state estimation 5–13hence we havey˙y...y(n−1)= Ox + Tu˙u...u(n−1)where O is the observability matrix andT =D 0 · · ·CB D 0 · · ·...CAn−2B CAn−3B · · · CB D(same matrices we encountered in discrete-time case!)Observability and state estimation 5–14rewrite asOx =y˙y...y(n−1)− Tu˙u...u(n−1)RHS is known; x is to be determinedhence if N (O) = {0} we can deduce x(t) from derivatives of u(t), y(t) upto order n − 1in this case we say system is observablecan construct an observer using any left inverse F of O:x = Fy˙y...y(n−1)− Tu˙u...u(n−1)Observability and state estimation 5–15• reconstructs x(t) (exactly and instantaneously) fromu(t), . . . , u(n−1)(t), y(t), . . . , y(n−1)(t)• derivative-based state reconstruction is dual of state transfer usingimpulsive inputsObservability and state estimation 5–16A conversesuppose z ∈ N (O) (the unobservable subspace), and u is any input, withx, y the corresponding state and output, i.e.,˙x = Ax + Bu, y = Cx + Duthen state trajectory ˜x = x + eAtz satisfies˙˜x = A˜x + Bu, y = C ˜x + Dui.e., input/output signals u, y consistent with both state trajectories x, ˜xhence if system is unobservable, no signal processing of any kind applied tou and y can deduce xunobservable subspace N (O) gives fundamental ambiguity in deducing xfrom u, yObservability and state estimation 5–17Least-squares observersdiscrete-time system, with sensor noise:x(t + 1) = Ax(t) + Bu(t), y(t) = Cx(t) + Du(t) + v(t)we assume Rank(Ot) = n (hence, system is observable)least-squares observer uses pseudo-inverse:ˆx(0) =