EECE 574 - Adaptive Control - Recursive …

1 eece 574 - Adaptive ControlRecursive Identification AlgorithmsGuy DumontDepartment of Electrical and Computer EngineeringUniversity of British ColumbiaJanuary 2012 Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 20121 / 21 Recursive IdentificationThere are many situations when it is preferable to perform theidentification on-line, such as inadaptive methods need to be implemented in a Recursive fashion, parameter estimate at timetshould be computed as a function of theestimate at timet 1 and of the incoming information at instrumental extended least-squares and Recursive maximum Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 20122 / 21 Recursive Least-SquaresRecursive Least-Squares (RLS)We have seen that, withtobservations available, the least-squares estimate is (t) = [XT(t)X(t)] 1XT(t)Y(t)withYT(t) = [y(1) y(t)]X(t) = xT(1).

2 XT(t) Assume one additional observation becomes available, the problem is then tofind (t+1)as a function of (t)andy(t+1)andu(t+1).Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 20123 / 21 Recursive Least-SquaresRecursive Least-Squares (RLS)DefiningX(t+1)andY(t+1)asX(t+1) =[X(t)xT(t+1)]Y(t+1) =[Y(t)y(t+1)]and definingP(t)andP(t+1)asP(t) = [XT(t)X(t)] 1P(t+1) = [XT(t+1)X(t+1)] 1one can writeP(t+1) = [XT(t)X(t)+x(t+1)xT(t+1)] 1 (t+1) =P(t+1)[XT(t)Y(t)+x(t+1)y(t+1)]Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 20124 / 21 Recursive Least-SquaresMatrix Inversion LemmaMatrix Inversion LemmaLetA,Dand[D 1+CA 1B]be nonsingular square matrices. ThenA+BDCis invertible and(A+BDC) 1=A 1 A 1B(D 1+CA 1B) 1CA 1 ProofThe simplest way to prove it is by direct multiplication(A+BDC)(A 1 A 1B(D 1+CA 1B) 1CA 1)=I+BDCA 1 B(D 1+CA 1B) 1CA 1 BDCA 1B(D 1+CA 1B) 1CA 1=I+BDCA 1 BD(D 1+CA 1B)(D 1+CA 1B) 1CA 1=IGuy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 20125 / 21 Recursive Least-SquaresMatrix Inversion LemmaMatrix Inversion LemmaAn alternative form, useful for deriving Recursive least-squares is obtainedwhenBandCaren 1 and 1 n( column and row vectors).

3 (A+BC) 1=A 1 A 1 BCA 11+CA 1 BNow, considerP(t+1) = [XT(t)X(t)+x(t+1)xT(t+1)] 1and use the matrix-inversion lemma withA=XT(t)X(t)B=x(t+1)C=xT(t+1)Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 20126 / 21 Recursive Least-SquaresRLS AlgorithmRecursive Least-Squares (RLS)Some simple matrix manipulations then give the Recursive least-squaresalgorithm:RLS (t+1) = (t)+K(t+1)[y(t+1) xT(t+1) (t)]K(t+1) =P(t)x(t+1)1+xT(t+1)P(t)x(t+1)P(t+1) =P(t) P(t)x(t+1)xT(t+1)P(t)1+xT(t+1)P(t)x(t+1) Note thatK(t+1)can also be expressed asK(t+1) =P(t+1)x(t+1)Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 20127 / 21 Recursive Least-SquaresRLS AlgorithmRecursive Least-Squares (RLS)The Recursive least-squares algorithm is theexactmathematicalequivalent of the batch initialized, no matrix inversion is stay the same size all the very proportional to the covariance matrix of the estimate, and is thuscalled the covariance algorithm has to be initialized with (0)andP(0).

4 Generally,P(0)is initialized as IwhereIis the identity matrix and is a large positivenumber. The larger , the less confidence is put in the initial estimate (0).Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 20128 / 21 Recursive Least-SquaresRLS AlgorithmRLS and Kalman FilterThere are some very strong connections between the Recursive least-squaresalgorithm and the Kalman filter. Indeed, the RLS algorithm has the structureof a Kalman filter: (t+1) new= (t) old+K(t+1)[y(t+1) xT(t+1) (t)] correctionwhereK(t+1)is the Kalman Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 20129 / 21 Recursive Least-SquaresRLS AlgorithmMatlab ImplementationThe following Matlab code is a straightforward implementation of the RLSalgorithm:function [thetaest,P]=rls(y,x,thetaest,P)% RLS% y,x: current measurement and regressor% thetaest, P: parameter estimates and covariance matrixK= P*x/(1+x *P*x); % GainP= P- (P*x*x *P)/(1+x *P*x); % Covariance matrix updatethetaest= thetaest +K*(y-x *thetaest).

5 %Estimate updateendGuy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201210 / 21 RELS, AML and RMLRELS and AMLR ecursive Extended Least-Squares and RecursiveMaximum-LikelihoodBecause the prediction error is not linear in the C-parameters, it is not possible toderive an exact Recursive maximum likelihood method as for the ARMAX modelA(q 1)y(t) =B(q 1)u(t)+C(q 1)e(t)can be written asy(t) =xT(t) +e(t)with = [a1,..,an,b1,..,bn,c1,..,cn]TxT(t) = [ y(t 1),.., y(t n),u(t 1),..,u(t n),e(t 1),..,e(t n)]TGuy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201211 / 21 RELS, AML and RMLRELS and AMLR ecursive Extended Least-Squares and ApproximateMaximum-LikelihoodIfe(t)was known, RLS could be used to estimate , however it isunknown and thus has to be can be done in two ways, either using the prediction error or first case corresponds to the RELS method, the second to the Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201212 / 21 RELS, AML and RMLRELS and AMLR ecursive Extended Least-Squares and ApproximateMaximum-LikelihoodThe one-step ahead prediction error is defined as (t) =y(t) y(t|t 1)=y(t) xT(t) (t 1)x(t) = [ y(t 1).]

6 ,u(t 1),.., (t 1),.., (t n)]TThe residual is defined as (t) =y(t) y(t|t)=y(t) xT(t) (t)x(t) = [ y(t 1),..,u(t 1),.., (t 1),.., (t n)]TGuy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201213 / 21 RELS, AML and RMLRELS and AMLR ecursive Extended Least-Squares and ApproximateMaximum-LikelihoodSometimes (t)and (t)are also referred to as a-priori and a-posterioriprediction it uses the latest estimate (t), as opposed to (t 1)for (t), (t)is a better estimate, especially in transient however that if (t)converges ast then (t) (t).Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201214 / 21 RELS, AML and RMLRELS and AMLR ecursive Extended Least-Squares and ApproximateMaximum-LikelihoodThe two schemes are then described by (t+1) = (t)+K(t+1)[y(t+1) xT(t+1) (t)]K(t+1) =P(t+1)x(t+1)/[1+xT(t+1)P(t)x(t+1)]P(t+1 ) =P(t) P(t)x(t+1)xT(t+1)P(t)[1+xT(t+1)P(t)x(t+1 )]but differ by their definition ofx(t)Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201215 / 21 RELS, AML and RMLRELS and AMLR ecursive Extended Least-Squares and ApproximateMaximum-LikelihoodThe RELS algorithm corresponds uses the prediction error.

7 Thisalgorithm is called RELS, Extended Matrix or RML1 in the literature. Ithas generally good convergence properties, and has been provedconsistent for moving-average and first-order auto regressive , counterexamples to general convergence exist, see for exampleLjung (1975).The AML algorithm uses the residual error. The AML has betterconvergence properties than the RML, and indeed convergence can beproven under rather unrestrictive Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201216 / 21 RELS, AML and RMLRMLR ecursive Maximum-LikelihoodThe ML can also be interpreted in terms of data the performance index:V(t) =12t i=1 2(i)with (t) =y(t) xT(t) (t 1)Define the filtered regressorxf(t)asxf(t) =1 C(q 1)x(t)Requires initialization and a stable C(q 1).Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201217 / 21 RELS, AML and RMLRMLR ecursive Maximum-LikelihoodThe resulting scheme is then.

8 (t+1) = (t)+K(t+1)[y(t+1) xT(t+1) (t)]K(t+1) =P(t+1)xf(t+1)[1+xTf(t+1)P(t)xf(t+1)]P(t +1) =P(t) P(t)xf(t+1)xTf(t+1)P(t)[1+xTf(t+1)P(t)xf (t+1)]No global convergence result availableGuy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201218 / 21 RELS, AML and RMLP roperties of AMLP roperties of AMLD efinitionA discrete transfer function is said to be strictly positive real if it is stable andReH(ej )>0 < on the unit condition can be checked by replacingzby1+j 1 j and extracting the realpart of the resulting the convergence of AML, the following theorem is then Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201219 / 21 RELS, AML and RMLP roperties of AMLP roperties of AMLT heorem (Ljung & S derstr m, 1983))Assume both process and model are described by ARMAX with order model orderprocess, then if1{u(t)}is sufficiently rich21C(q 1) 12is strictly positive realthen (t)will converge such thatE[ (t, ) e(t)]2=0If model and process have the same order, this implies (t) ast Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201220 / 21 RPEMA Unified AlgorithmLooking at all the previous algorithms, it is obvious that they all have thesame form, with only different parameters.

9 They can all be represented by arecursive prediction - error method (RPEM).RPEM (t+1) = (t)+K(t+1) (t+1)K(t+1) =P(t)z(t+1)/[1+xT(t+1)P(t)z(t+1)]P(t+1) =P(t) P(t)z(t+1)xT(t+1)P(t)[1+xT(t+1)P(t)x(t+1 )]Guy Dumont (UBC eece ) eece 574 - Adaptive ControlJanuary 201221 / 21