note12

pdf

School

Harvard University *

*We aren’t endorsed by this school

Course

16B

Subject

Electrical Engineering

Date

Oct 30, 2023

Type

pdf

Pages

Uploaded by CorporalKnowledge12458

EECS 16B Designing Information Systems and Devices II UC Berkeley Fall 2023 Note 12: Controllability 1 Overview and Motivation In Note 9, we computed explicit state trajectories for discrete-time and continuous-time LTI models. In Note 11, we used the state trajectories to examine the asymptotics of the discrete-time and continuous-time LTI models, i.e., what happens when t → ª§¦ª . Now, we tackle another relevant question in control. Namely, we ask: is it possible to reach a given target state, and if so, what is the sequence of inputs that makes the state reach the target? To answer this question, we introduce the concepts of reachability and controllability in discrete-time. Key Idea 1 (Reachability and Controllability) A model can reach a target state from an initial state if it is possible to provide inputs that push the model state to the target state, given that it starts at the initial state. A model is controllable if, with the correct set of inputs, the model state can reach any given target state from any given initial state. We give algorithms that check for reachability and controllability. We also show how to reach a target state. We conclude with optional discussions about the connections between controllability and stability (which was covered in Note 11), and continuous-time versions of reachability and controllability. To reiterate, this note will mostly be in discrete-time . 2 Reachability Analysis Recall from Note 7 that the discrete-time model we are using is Model 2 (Discrete-Time LTI Difference Equation Model) The model is of the form ⃗ x [ i + 1 ] = A ⃗ x [ i ] + B ⃗ u [ i ] (1) for ⃗ x : N → R n the state vector as a function of timestep, ⃗ u : N → R m the control inputs as a function of timestep, and A ∈ R n × n , B ∈ R n × m matrices. We also know from Note 7 that the state trajectory for this model is ⃗ x [ i ] = A i ⃗ x [ 0 ] + i − 1 êçæêôæ k = 0 A i − 1 − k B ⃗ u [ k ] . (2) We are interested in when a given state is reachable at a given timestep. This motivates the following definition. 1

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 Definition 3 (Reachability in Discrete-Time LTI Difference Equation Model ) Suppose we are in the Discrete-Time LTI Difference Equation Model . Fix an initial state ⃗ x 0 ∈ R n and a target state ⃗ x ⋆ ∈ R n . • State ⃗ x ⋆ is reachable in i ⋆ timesteps from ⃗ x 0 if there exists a sequence of inputs ⃗ u [ 0 ] , ⃗ u [ 1 ] , . . . , ⃗ u [ i ⋆ − 1 ] such that, if ⃗ x [ 0 ] = ⃗ x 0 then ⃗ x [ i ⋆ ] = ⃗ x ⋆ . • State ⃗ x ⋆ is reachable from ⃗ x 0 if there exists a timestep i ⋆ for which ⃗ x ⋆ is reachable in i ⋆ timesteps from ⃗ x 0 . We can give useful characterizations for reachability by using the linear algebraic tools we have devel- oped. The main insight is that we can write the latter summation as a matrix-vector product in terms of the control inputs ⃗ u : ⃗ x [ i ] = A i ⃗ x [ 0 ] + h A i − 1 B A i − 2 B · · · AB B i          ⃗ u [ 0 ] ⃗ u [ 1 ] . . . ⃗ u [ i − 2 ] ⃗ u [ i − 1 ]          . (3) This matrix is given a special name. Definition 4 (Controllability Matrix in Discrete-Time LTI Difference Equation Model ) Suppose we are in the Discrete-Time LTI Difference Equation Model . The controllability matrix at timestep i ≥ 1 is defined to be the matrix C i : = h A i − 1 B A i − 2 B · · · AB B i ∈ R n × ( i · m ) . (4) We may also call C n the controllability matrix without reference to the timestep, and alternatively denote it C . This allows us to state and prove the main result of reachability analysis. Theorem 5 (Reachability Criteria in Discrete-Time LTI Difference Equation Model ) Suppose we are in Discrete-Time LTI Difference Equation Model . Fix an initial state ⃗ x 0 ∈ R n , target state ⃗ x ⋆ ∈ R n , and a target timestep i ⋆ ∈ N . Then the following are equivalent a : (i) ⃗ x ⋆ is reachable in i ⋆ timesteps from ⃗ x 0 . (ii) ⃗ x ⋆ − A i ⋆ ⃗ x 0 ∈ Col ( C i ⋆ ) . a This is another way to write "(i) if and only if (ii)". The proof of Theorem 5 is on the longer side and may distract from the overall flow of this note, so it is left to Appendix A.1 . © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 2

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 Corollary 6 (Practical Reachability Analysis in Discrete-Time LTI Difference Equation Model ) Suppose we are in Discrete-Time LTI Difference Equation Model . To determine if a target state ⃗ x ⋆ is reachable in exactly i ⋆ timesteps from ⃗ x 0 , it is sufficient to run Gaussian elimination to find ⃗ w in the system C i ⋆ ⃗ w = ⃗ x ⋆ − A i ⋆ ⃗ x 0 . (5) • If there is at least one solution for ⃗ w , then ⃗ x ⋆ is reachable in i ⋆ timesteps from ⃗ x 0 . Furthermore, every solution ⃗ w can be unpackaged as ⃗ w =     ⃗ u [ 0 ] . . . ⃗ u [ i ⋆ − 1 ]     . Thus every solution ⃗ w gives a sequence of control inputs that, if ⃗ x [ 0 ] = ⃗ x 0 , makes ⃗ x [ i ⋆ ] = ⃗ x ⋆ . • If there are no ⃗ w that solve the system, then ⃗ x ⋆ is not reachable in i ⋆ timesteps from ⃗ x 0 . Writing this out in algorithmic form, we have Algorithm 7 Reachability Analysis in Discrete-Time LTI Difference Equation Model 1: function I S R EACHABLE ( ⃗ x 0 , ⃗ x ⋆ , i ⋆ ) 2: Compute C i ⋆ : = h A i ⋆ − 1 B · · · B i 3: if G AUSSIAN E LIMINATION ( C i , ⃗ x ⋆ − A i ⋆ ⃗ x 0 ) yields a solution then 4: Get any solution ⃗ w : = G AUSSIAN E LIMINATION ( C i ⋆ , ⃗ x ⋆ − A i ⋆ ⃗ x 0 ) 5: Unpack     ⃗ u [ 0 ] . . . ⃗ u [ i ⋆ − 1 ]     : = ⃗ w 6: return R EACHABLE , ( ⃗ u [ 0 ] , . . . , ⃗ u [ i ⋆ − 1 ]) 7: else 8: return N OT REACHABLE 9: end if 10: end function 3 Controllability Now that we know how to check that a given target state is reachable by the model, we would like to characterize models that can reach any target state by a given time. This is a desired property in practice because we may not know in advance what state we would like to reach, and only would know during the system runtime. If the model has this property, called controllability, we would be able to adapt the control to reach the desired state. Definition 8 (Controllability in Discrete-Time LTI Difference Equation Model ) Suppose we are in Discrete-Time LTI Difference Equation Model . • A model is controllable in i timesteps if and only if any target state is reachable in i timesteps from any initial state. © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 3

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 • A model is controllable if and only if any target state is reachable from any initial state. This definition essentially means that a model is controllable in i timesteps if and only if it can reach any state in i timesteps from any other state, and is controllable if and only if it can eventually reach any state starting from any other state. The following characterization of controllability is the one that is most useful in practice. Theorem 9 (Controllability Criteria in Discrete-Time LTI Difference Equation Model ) Suppose we are in Discrete-Time LTI Difference Equation Model . Fix i ∈ N . Then the following are equivalent: (i) The model is controllable in i timesteps. (ii) Col ( C i ) = R n . Further, the following are equivalent: (iii) The model is controllable. (iv) The model is controllable in n timesteps. (v) Col ( C n ) = R n . The proof of Theorem 9 is on the longer side and may distract from the overall flow of this note, so it is left to Appendix A.2 . We fully expect you to read the proof and understand it. It is completely in-scope for the course. NOTE : It is not true that all models are controllable. By the above theorem, if rank ( C n ) < n , then adding more blocks of the form A k B will not add anything to Col ( C n ) , and the model is not controllable. NOTE : This fact is why we may call C = C n the controllability matrix without reference to the timestep, since it tells us whether the model is controllable at any timestep. Based on this, there is an easy way to show controllability. Corollary 10 (Practical Controllability Analysis in Discrete-Time LTI Difference Equation Model ) Suppose we are in Discrete-Time LTI Difference Equation Model . • To determine if a model is controllable in i steps, first compute C i , then compute its rank. The model is controllable in i steps if and only if rank ( C i ) = n . • To determine if a model is controllable, check if it is controllable in n steps; this means that we compute C n , then its rank. The model is controllable if and only if rank ( C n ) = n . We can turn this into an algorithm. 4 Controllability, Stability, and Controllable Canonical Form In this section, we cover an interesting connection between controllability (this note) and stability (Note 11). The goal of this section is to build up to a proof of the following theorem. In a nutshell, this result says that under certain conditions, controllable systems may be stabilized by closed-loop feedback. © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 4

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 Algorithm 11 Controllability Analysis for Discrete-Time LTI Difference Equation Model 1: function I S C ONTROLLABLE I N S TEPS ( i ) 2: Compute C i = h A i − 1 B · · · AB B i 3: if rank ( C i ) = n then 4: return Y ES 5: else 6: return N O 7: end if 8: end function 9: function I S C ONTROLLABLE 10: return I S C ONTROLLABLE I N S TEPS ( n ) 11: end function Theorem 12 (Controllable Systems can Be Stabilized in Discrete-Time LTI Difference Equation Model with m = 1 ) Suppose we are in Discrete-Time LTI Difference Equation Model , with m = 1, i.e., ⃗ x [ i + 1 ] = A ⃗ x [ i ] + ⃗ bu [ i ] . (6) Suppose the model is controllable. Then closed-loop feedback of the form u [ i ] = ⃗ f ⊤ ⃗ x [ i ] + u OL [ i ] can set all eigenvalues of the closed-loop feedback matrix A CL : = A + ⃗ b ⃗ f ⊤ . We begin by introducing the controllable canonical form, which allows us to concretely tie together controllability and stability. Definition 13 (Controllable Canonical Form for Discrete-Time LTI Difference Equation Model ) A Discrete-Time LTI Difference Equation Model is in controllable canonical form (CCF) if m = 1, i.e., ⃗ x [ i + 1 ] = A ⃗ x [ i ] + ⃗ bu [ i ] , (7) and the coefficients have the following special structure: A =       ⃗ 0 n − 1 I n − 1 a 1 a 2 · · · a n       ∈ R n × n and ⃗ b = " ⃗ 0 n − 1 1 # ∈ R n . (8) This specific structure for A and B is relevant because its characteristic polynomial has a nice form. Indeed, we have the following result, which we will not prove. Proposition 14 © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 5

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 Suppose A : =       ⃗ 0 n − 1 I n − 1 a 1 a 2 · · · a n       ∈ R n × n . (9) Then its characteristic polynomial p A is given by p A ( λ ) = λ n − n êçæêôæ i = 1 a i λ i − 1 . (10) Using this specific form, we are able to control the eigenvalues of A using state feedback. In particular, we have the following result. Proposition 15 (State Feedback in CCF for Discrete-Time LTI Difference Equation Model ) Suppose we are in Discrete-Time LTI Difference Equation Model where our model is in CCF. Then state feedback of the form u [ i ] = ⃗ f ⊤ ⃗ x [ i ] + u OL [ i ] can assign all eigenvalues of A CL : = A + ⃗ b ⃗ f ⊤ . The proof of Proposition 15 is on the longer side and may distract from the overall flow of this note, so it is left to Appendix A.3 . We fully expect you to read the proof and understand it. It is completely in-scope for the course. Thus we can change the stability of a model in CCF however we like, by the appropriate state feedback. We now discuss where controllability comes into the picture. Theorem 16 (Controllability and CCF in Discrete-Time LTI Difference Equation Model ) For a controllable Discrete-Time LTI Difference Equation Model with m = 1, i.e., ⃗ x [ i + 1 ] = A ⃗ x [ i ] + ⃗ bu [ i ] , (11) there is a change of variables ⃗ x = T ⃗ z such that the system in these variables, i.e., ⃗ z [ i + 1 ] = e A ⃗ z [ i ] + ⃗ e bu [ i ] (12) where e A = T − 1 AT and ⃗ e b = T − 1 ⃗ b , is in CCF. The proof of Theorem 16 is on the longer side and may distract from the overall flow of this note, so it is left to Appendix A.4 . We fully expect you to read the proof and understand it. It is completely in-scope for the course. Now we are able to prove Theorem 12 . The proof of Theorem 12 is on the longer side and may distract from the overall flow of this note, so it is left to Appendix A.5 . We fully expect you to read the proof and understand it. It is completely in-scope for the course. 5 (OPTIONAL) Continuous-Time Controllability In this section, we provide an overview of continuous-time controllability results. Proofs are not provided, and they are out of scope of the course. First, let us recall the model we are using. © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 6

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 Model 17 (Continuous-Time LTI Differential Equation Model) The model is of the form d d t ⃗ x ( t ) = A ⃗ x ( t ) + B ⃗ u ( t ) (13) for ⃗ x : R + → R n the state vector as a function of time, ⃗ u : R + → R m the control inputs as a function of time, and A ∈ R n × n , B ∈ R n × m matrices. Surprisingly, the results and definitions for continuous-time look similar to the results and definitions in discrete-time. More specifically, the reachability and controllability definitions (i.e., Definition 3 and Definition 8 ) go through, except replacing discrete timestep i with continuous timestep t . The surprising part is that the criteria for controllability to check is the same, that is, the model is con- trollable if and only if rank ( C n ) = R n , where C n = h A n − 1 B · · · AB B i . This is roughly because a continuous-time model can be discretized, at which point the analysis we did can go through for the dis- cretization, and then converted back to continuous-time. A rigorous derivation is out of scope for the course. 6 Examples Suppose n = 2 and we have the system ⃗ x [ i + 1 ] = " 3 1 2 2 # | {z } : = A ⃗ x [ i ] + " 1 1 # |{z} : = ⃗ b u [ i ] . (14) Then the controllability matrices are C 1 = " 1 1 # (15) C 2 = " 4 1 4 1 # . (16) Since rank ( C 1 ) = 1 < 2, the model is not controllable in one timestep. Similarly, rank ( C 2 ) = 1 < 2, so the model is not controllable in two timesteps, and is thus not controllable. Some states are reachable from other states; for example, suppose ⃗ x 0 = " 0 0 # and ⃗ x ⋆ = " 2 2 # . Then ⃗ x ⋆ is reachable from ⃗ x 0 in one step, i ⋆ = 1; namely, u [ 0 ] = 2 is a suitable input. However, not all states are reachable from all other states. On the other hand, consider the system ⃗ x [ i + 1 ] = " 3 2 1 2 # | {z } : = A ⃗ x [ i ] + " 1 1 # |{z} : = ⃗ b u [ i ] . (17) Then the controllability matrices are C 1 = " 1 1 # (18) © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 7

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 C 2 = " 5 1 3 1 # . (19) Since rank ( C 1 ) = 1 < 2, the model is not controllable in one timestep. But rank ( C 2 ) = 2, so Col ( C 2 ) = R 2 , and the model is controllable in two timesteps, and thus controllable. In terms of reachability analysis, suppose i ⋆ = 2, ⃗ x 0 = " 1 1 # , and ⃗ x ⋆ = " 10 10 # . Then we compute ⃗ x ⋆ − A i ⋆ ⃗ x 0 = ⃗ x ⋆ − A 2 ⃗ x 0 (20) = " 10 10 # − " 3 2 1 2 # 2 " 1 1 # (21) = " 10 10 # − " 11 10 5 6 # " 1 1 # (22) = " − 11 − 1 # . (23) Now we solve C 2 ⃗ w = ⃗ x ⋆ − A i ⋆ ⃗ x 0 (24) " 5 1 3 1 # ⃗ w = " − 11 − 1 # (25) which implies ⃗ w = " − 5 14 # . (26) Thus ⃗ x ⋆ is reachable in 2 timesteps from ⃗ x 0 with the inputs u [ 0 ] = − 5 and u [ 1 ] = 14. Note that, if we had a different ⃗ x ⋆ and ⃗ x 0 , we would have zero, one, or infinitely many solutions for ⃗ w . If we had zero solutions, then ⃗ x ⋆ would not be reachable from ⃗ x 0 in two timesteps. If we had one solution, then there would be a unique choice of control that reaches ⃗ x ⋆ from ⃗ x 0 in 2 timesteps. If we had infinitely many solutions, then there would be infinitely many choices of control that reaches ⃗ x ⋆ . Picking the "best" control for a particular notion of "best" (minimum energy consumption) is the subject of Note 14 . Since the above model is controllable, and m = 1, we know by Theorem 12 that we can arbitrarily set the eigenvalues of A CL : = A + ⃗ b ⃗ f ⊤ by choosing feedback control of the form ⃗ u [ i ] = ⃗ f ⊤ ⃗ x [ i ] . We verify this here. A CL = A + ⃗ b ⃗ f (27) = " 3 2 1 2 # + " 1 1 # h f 1 f 2 i | {z } : = ⃗ f ⊤ (28) = " 3 + f 1 2 + f 2 1 + f 1 2 + f 2 # (29) p A CL ( λ ) = det ( A CL − λ I 2 ) (30) = det " 3 + f 1 − λ 2 + f 2 1 + f 1 2 + f 2 − λ #! (31) © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 8

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 = ( 3 + f 1 − λ )( 2 + f 2 − λ ) − ( 2 + f 2 )( 1 + f 1 ) (32) = λ 2 − ( f 1 + f 2 + 5 ) λ + ( 2 f 2 + 4 ) . (33) Now if we want A CL to have eigenvalues λ 1 , λ 2 , we have p A CL ( λ ) = ( λ − λ 1 )( λ − λ 2 ) (34) = λ 2 − ( λ 1 + λ 2 ) λ + λ 1 λ 2 . (35) Thus by matching coefficients, we have λ 1 + λ 2 = 5 + f 1 + f 2 (36) λ 1 λ 2 = 2 f 2 + 4 (37) from which the solution is f 1 = − 3 + λ 1 + λ 2 − λ 1 λ 2 2 (38) f 2 = λ 1 λ 2 2 − 2. (39) We can also get it into CCF and work out the control in the CCF basis. The characteristic polynomial of A is p A ( λ ) = det ( A − λ I 2 ) (40) = det " 3 − λ 2 1 2 − λ #! (41) = ( 3 − λ )( 2 − λ ) − 2 · 1 (42) = λ 2 − 5 λ + 4. (43) Thus (from the method of construction in the proof of Theorem 16 ) we can read off the CCF matrix e A , and vector ⃗ e b , as e A : = " 0 1 − 4 5 # ⃗ e b : = " 0 1 # . (44) The closed loop matrix is e A CL : = e A + ⃗ e b ⃗ e f ⊤ , so e A CL = e A + ⃗ e b ⃗ e f ⊤ (45) = " 0 1 − 4 5 # + " 0 1 # h e f 1 e f 2 i (46) = " 0 1 − 4 + e f 1 5 + e f 2 # . (47) The characteristic polynomial of e A CL : = e A + ⃗ e b ⃗ e f ⊤ is p e A CL ( λ ) = det e A CL − λ I 2 (48) = det " − λ 1 − 4 + e f 1 5 + e f 2 − λ #! (49) © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 9

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 = λ ( λ − e f 2 − 5 ) − 1 · ( e f 1 − 4 ) (50) = λ 2 − ( e f 2 + 5 ) λ + ( 4 − e f 1 ) . (51) Then by the same analysis as before, we get the system of equations λ 1 + λ 2 = e f 2 + 5 (52) λ 1 λ 2 = 4 − e f 1 . (53) Inverting to recover the feedback control gives us e f 1 = 4 − λ 1 λ 2 (54) e f 2 = λ 1 + λ 2 − 5. (55) To get the original feedback control ⃗ f , by the proof of Theorem 12 , we have ⃗ e f ⊤ : = ⃗ f ⊤ T , where T is the CCF basis. It remains to compute T . Indeed, T = C 2 e C − 1 2 (56) = h A ⃗ b ⃗ b i h e A ⃗ e b ⃗ e b i − 1 (57) = " 5 1 3 1 # " 1 0 5 1 # − 1 (58) = " 0 1 − 2 1 # . (59) Then ⃗ e f ⊤ = ⃗ f ⊤ T (60) h e f 1 e f 2 i = h f 1 f 2 i " 0 1 − 2 1 # (61) h e f 1 e f 2 i = h − 2 f 2 f 1 + f 2 i (62) which implies e f 1 = − 2 f 2 (63) e f 2 = f 1 + f 2 . (64) Solving this linear system, we get f 1 = e f 1 + 2 e f 2 2 = 4 − λ 1 λ 2 + 2 ( λ 1 + λ 2 − 5 ) 2 = − 3 + λ 1 + λ 2 − λ 1 λ 2 2 (65) f 2 = − e f 1 2 = λ 1 λ 2 2 − 2. (66) This is exactly the same as the original feedback control. 7 Final Comments After this note, we have a better idea of how to do finite-time (i.e., non-asymptotic) control. More specifi- cally, given a Discrete-Time LTI Difference Equation Model , an initial state ⃗ x 0 , and a target state ⃗ x ⋆ , we can see via reachability analysis: © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 10

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 • whether our model can reach this target state from the initial state; • and which inputs can be used to reach the state. More generally we can measure how possible it is for our model to go between states. Via controllability analysis, we can see: • whether our model can reach any target state from any initial state; • and how long it takes for the model to have this property, if it ever does. When there are many choices of inputs that get to a desired target state by the desired time, it is not yet clear which to pick. For a particularly simple choice of "best" input, this question will be resolved in a future note. © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 11

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 A Longer Proofs A.1 Proof of Theorem 5 Proof of Theorem 5 . Using the definition of the controllability matrix, the equation for ⃗ x [ i ] becomes ⃗ x [ i ] = A i ⃗ x [ 0 ] + C i     ⃗ u [ 0 ] . . . ⃗ u [ i − 1 ]     . (67) This can also be written as ⃗ x [ i ] − A i ⃗ x [ 0 ] = C i     ⃗ u [ 0 ] . . . ⃗ u [ i − 1 ]     . (68) Now we can prove the equivalence of (i) and (ii). • (i) = ⇒ (ii). Suppose (i) holds, i.e., we have a sequence of inputs ⃗ u [ 0 ] , . . . , ⃗ u [ i ⋆ − 1 ] which, if ⃗ x [ 0 ] = ⃗ x 0 , sets ⃗ x [ i ⋆ ] = ⃗ x ⋆ . Then ⃗ x ⋆ − A i ⋆ ⃗ x 0 = ⃗ x [ i ⋆ ] − A i ⋆ ⃗ x 0 = C i ⋆     ⃗ u [ 0 ] . . . ⃗ u [ i ⋆ − 1 ]     (69) which writes ⃗ x ⋆ − A i ⋆ ⃗ x 0 as a matrix-vector product C i ⋆     ⃗ u [ 0 ] . . . ⃗ u [ i ⋆ − 1 ]     , i.e., as a linear combination of the columns of C i ⋆ . Thus ⃗ x ⋆ − A i ⋆ ⃗ x 0 ∈ Col ( C i ⋆ ) , so (ii) holds. • (ii) = ⇒ (i). Suppose (ii) holds, i.e., ⃗ x ⋆ − A i ⋆ ⃗ x 0 ∈ Col ( C i ⋆ ) . Then by definition of column space, there exists a vector ⃗ w such that ⃗ x ⋆ − A i ⋆ ⃗ x 0 = C i ⋆ ⃗ w . (70) But if we unpack     ⃗ u [ 0 ] . . . ⃗ u [ i ⋆ − 1 ]     : = ⃗ w , then we have ⃗ x ⋆ − A i ⋆ ⃗ x 0 = C i ⋆     ⃗ u [ 0 ] . . . ⃗ u [ i ⋆ − 1 ]     = ⃗ x [ i ⋆ ] − A i ⋆ ⃗ x [ 0 ] (71) where we get the right-hand side equality from our formula for ⃗ x [ i ] in terms of ⃗ x 0 and the controlla- bility matrix. Looking at the left-most and right-most expressions, we get ⃗ x ⋆ − A i ⋆ ⃗ x 0 = ⃗ x [ i ⋆ ] − A i ⋆ ⃗ x [ 0 ] . (72) From this, if ⃗ x [ 0 ] = ⃗ x 0 , then ⃗ x ⋆ = ⃗ x [ i ⋆ ] . Thus (i) holds by using the given inputs ⃗ u [ 0 ] , . . . , ⃗ u [ i ⋆ − 1 ] . © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 12

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 A.2 Proof of Theorem 9 Proof of Theorem 9 . We show the first pair of equivalencies. • (i) = ⇒ (ii). Suppose (i) holds, i.e., the model is controllable in i timesteps. Then every target state ⃗ x ⋆ is reachable in i timesteps from any initial state ⃗ x 0 . That is, for every ⃗ x 0 , ⃗ x ⋆ ∈ R n , there is a sequence of inputs ⃗ u [ 0 ] , . . . , ⃗ u [ i − 1 ] which, if ⃗ x [ 0 ] = ⃗ x 0 , sets ⃗ x [ i ] = ⃗ x ⋆ . By Theorem 5 , this means that for every ⃗ x 0 , ⃗ x ⋆ ∈ R n , we have ⃗ x ⋆ − A i ⃗ x 0 ∈ Col ( C i ) . Setting ⃗ x 0 = ⃗ 0 n , this means that for every ⃗ x ⋆ ∈ R n , we have ⃗ x ⋆ ∈ Col ( C i ) . This implies that Col ( C i ) = R n , and (ii) holds. • (ii) = ⇒ (i). Suppose (ii) holds, i.e., Col ( C i ) = R n . Fix ⃗ x 0 , ⃗ x ⋆ ∈ R n . We show that ⃗ x ⋆ is reachable from ⃗ x 0 in i timesteps. Indeed, since Col ( C i ) = R n ∋ ⃗ x ⋆ − A i ⃗ x 0 , there exists a vector ⃗ w such that ⃗ x ⋆ − A i ⃗ x 0 = C i ⃗ w . (73) Unpacking     ⃗ u [ 0 ] . . . ⃗ u [ i − 1 ]     : = ⃗ w , we get that ⃗ x ⋆ − A i ⃗ x 0 = C i     ⃗ u [ 0 ] . . . ⃗ u [ i − 1 ]     = ⃗ x [ i ] − A i ⃗ x [ 0 ] (74) where again the right equality is because of our expression for ⃗ x [ i ] in terms of the controllability matrix. The left-most and right-most expressions yield ⃗ x ⋆ − A i ⃗ x 0 = ⃗ x [ i ] − A i ⃗ x [ 0 ] . (75) If ⃗ x [ 0 ] = ⃗ x 0 then this simplifies to ⃗ x [ i ] = ⃗ x ⋆ . (76) Thus by providing the inputs ⃗ u [ 0 ] , . . . , ⃗ u [ i − 1 ] , the state ⃗ x ⋆ is reachable at time i from ⃗ x 0 . This is true for arbitrary ⃗ x 0 , ⃗ x ⋆ , so every state is reachable at time i from every other state. Thus the model is controllable in i timesteps, and (i) holds. The latter equivalence uses a theorem which is very ubiquitous in abstract linear algebra, but which will not be proved in this course. Theorem 18 (Cayley-Hamilton) Suppose A ∈ R n × n is a matrix with characteristic polynomial p A ( λ ) : = n êçæêôæ i = 0 c i λ i . (77) with c n ̸ = 0. Then p A ( A ) : = n êçæêôæ i = 0 c i A i = 0 n × n . (78) This theorem essentially says that A n can be written as a linear combination of A 0 = I n , A 1 , . . . , A n − 1 . In particular, A n = − 1 c n êçæêôæ n − 1 i = 0 c i A i . Using this, we can prove the second set of equivalences. © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 13

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 • (iii) = ⇒ (v). We begin with a lemma. We claim that Col ( C i ) ⊆ Col ( C n ) for all i . Indeed, since the columns of C i are a subset of the columns of C i + 1 , we see that Col ( C 1 ) ⊆ · · · ⊆ Col ( C i ) ⊆ Col ( C i + 1 ) ⊆ · · · (79) Now, we show that for all i ≥ n , we have that Col ( C i ) = Col ( C n ) . It is cleanest to use the following approach. First, we show that A i can be written as a linear combination of I , A , . . . , A n − 1 via recursion 1 . The re- cursive base case is i = n . In this case we want to show that A n can be written as a linear combination of I , A , . . . , A n − 1 . But this is true by the Cayley-Hamilton Theorem, as noted above, so we can write A n = n − 1 êçæêôæ k = 0 γ k A k . (80) So our base case is shown to be true. Now considering general i > n , we immediately do our "recur- sive call" to write A i − 1 as a linear combination of I , A , . . . , A n − 1 : A i − 1 = n − 1 êçæêôæ k = 0 η k A k . (81) Then A i = A · A i − 1 = A n − 1 êçæêôæ k = 0 η k A k (82) = n − 1 êçæêôæ k = 0 η k A k + 1 (83) = η n − 1 A n + n − 2 êçæêôæ k = 0 η k A k + 1 (84) = η n − 1 n − 1 êçæêôæ k = 0 γ k A k + n − 2 êçæêôæ k = 0 η k A k + 1 (85) = γ 0 η n − 1 I n + n − 1 êçæêôæ k = 1 ( γ k η n − 1 + η k − 1 ) A k (86) is a linear combination of I , A , . . . , A n − 1 . Our recursive proof is complete. Now that we have this result, we may now show that Col ( C i ) = Col ( C n ) for i ≥ n . Indeed, from the previous claim, we know that A k is a linear combination of I , A , . . . , A n − 1 , for all k . By multiplying both sides of this linear combination by B , we see that A k B is a linear combination of B , AB , . . . , A n − 1 B for all k . Thus we see that A i − 1 B , A i − 2 B , . . . , A n B are each linear combinations of B , AB , . . . , A n − 1 B . Therefore, the columns of the controllability matrix at time i : C i = h A i − 1 B A i − 2 B · · · A n − 1 B A n − 2 B · · · AB B i (87) are linear combinations of the columns of the controllability matrix at time n : C n = h A n − 1 B A n − 2 B · · · AB B i ; (88) 1 In the language of CS70, this is an inductive proof. But it’s not necessary to know all the formalism of induction to understand the proof strategy. © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 14

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 This directly shows that Col ( C i ) ⊆ Col ( C n ) . Because the columns of C n are a subset of the columns of C i , we have that Col ( C i ) ⊇ Col ( C n ) . Thus Col ( C i ) = Col ( C n ) . This proves the original lemma. Suppose (iii) is true and the model is controllable. Then for every ⃗ x 0 , ⃗ x ⋆ , there exists i ⋆ such that ⃗ x ⋆ is reachable in i ⋆ timesteps from ⃗ x 0 . From Theorem 5 , this is equivalent to the claim that for every ⃗ x 0 , ⃗ x ⋆ there exists i ⋆ such that ⃗ x ⋆ − A i ⋆ ⃗ x 0 ∈ Col ( C i ⋆ ) . Since Col ( C i ⋆ ) ⊆ Col ( C n ) by our lemma, we see that for every ⃗ x 0 , ⃗ x ⋆ , there exists i ⋆ such that ⃗ x ⋆ − A i ⋆ ⃗ x 0 ∈ Col ( C n ) . By picking ⃗ x 0 = ⃗ 0 n , we see that for every ⃗ x ⋆ , we have ⃗ x ⋆ ∈ Col ( C n ) . Thus Col ( C n ) = R n , which shows (v). • (iv) = ⇒ (iii). Suppose the model is controllable in n timesteps. Then all target states ⃗ x ⋆ are reachable in n timesteps from all initial states ⃗ x 0 , so all target states are reachable from all initial states, and so the model is controllable and (iii) holds. • (iv) ⇐⇒ (v). This is just (i) ⇐⇒ (ii) applied to the case i = n . NOTE : The order in which we showed everything is equivalent may be a bit confusing. Here’s a diagram of how we showed the equivalence of our various claims. Here if x points to y then we started with x and proved y . Since we can get to any node in the first component from any other node in the first component, and any node in the second component from any other node in the second component, we have shown that for each component, all statements are logically equivalent. (i) (ii) (iii) (iv) (v) A.3 Proof of Proposition 15 Proof of Proposition 15 . Note that A CL = A + ⃗ b ⃗ f ⊤ (89) =       ⃗ 0 n − 1 I n − 1 a 1 a 2 · · · a n       + " 0 ( n − 1 ) × n ⃗ f ⊤ # (90) =       ⃗ 0 n − 1 I n − 1 a 1 + f 1 a 2 + f 2 · · · a n + f n       . (91) Thus by Proposition 14 the characteristic polynomial is given by p A CL ( λ ) = λ n − n êçæêôæ i = 1 ( a i + f i ) λ i − 1 (92) meaning that we can change the coefficients of λ i , and thus the roots of the polynomial, to whatever we want. © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 15

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 A.4 Proof of Theorem 16 To prove Theorem 16 , we will first need to use this auxiliary result, which will be important later. Theorem 19 (Similarity Preserves Characteristic Polynomial) Let A ∈ R n × n and B ∈ R n × n be square matrices. If there exists an invertible matrix T ∈ R n × n such that B = TAT − 1 , then the characteristic polynomials of A and B are the same: p A ( λ ) = p B ( λ ) . Proof. p B ( λ ) = det ( B − λ I n ) (93) = det TAT − 1 − λ I n (94) = det TAT − 1 − λ TT − 1 (95) = det T ( A − λ I n ) T − 1 (96) = det ( T ) det ( A − λ I n ) det T − 1 (97) = det ( A − λ I n ) (98) = p A ( λ ) . (99) Now we may proceed with the proof of Theorem 16 . Proof of Theorem 16 . First we find a e A of the prescribed format such that it is even possible to find some T such that A = T e AT − 1 . Indeed, if a matrix A and a matrix e A are similar in the sense that there exists an invertible matrix T such that A = T e AT − 1 , then the characteristic polynomials are the same: p A ( λ ) = p e A ( λ ) . Since the characteristic polynomial of e A uniquely determines e A , this gives us a way to find e A by matching the characteristic polynomial of A . The characteristic polynomial of e A is p e A ( λ ) = λ n − n êçæêôæ i = 1 a i λ i − 1 . (100) Now we can expand the characteristic polynomial of p A ( λ ) symbolically to get p A ( λ ) = n êçæêôæ i = 0 c i λ i . (101) Since p A ( λ ) is a characteristic polynomial and thus a product of linear factors of the form λ − λ i , its leading coefficient c n = 1. Thus we can write p A ( λ ) = λ n + n − 1 êçæêôæ i = 0 c i λ i . (102) Matching coefficients of λ i − 1 , we get a i = − c i − 1 . This allows us to construct a candidate e A : e A =       ⃗ 0 n − 1 I n − 1 − c 0 − c 1 · · · − c n − 1       . (103) © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 16

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 Now all we need to do is come up with the transformation T . With this e A and ⃗ e b = " ⃗ 0 n − 1 1 # , let e C n : = h e A n − 1 ⃗ e b · · · ⃗ e b i be the controllability matrix for the model in CCF coordinates. Then e C n = h e A n − 1 ⃗ e b · · · ⃗ e b i (104) = h ( T − 1 AT ) n − 1 T − 1 ⃗ b · · · T − 1 ⃗ b i (105) = h ( T − 1 A n − 1 T ) T − 1 ⃗ b · · · T − 1 ⃗ b i (106) = h T − 1 A n − 1 ⃗ b · · · T − 1 ⃗ b i (107) = T − 1 h A n − 1 ⃗ b · · · ⃗ b i (108) = T − 1 C n . (109) Indeed, since the model is controllable, C n is full rank and thus invertible. Furthermore, because of the special structure of e A and e b , we have that e C n is a lower triangular matrix with 1’s on the diagonal: e C n =       1 0 · · · 0 γ 21 1 · · · 0 . . . . . . . . . . . . γ n 1 γ n 2 · · · 1       (110) and is hence invertible, with the inverse computable via forward-substitution. Thus T : = C n e C − 1 n is the unique change of variables that gets the system into CCF, as desired. A.5 Proof of Theorem 12 Proof of Theorem 12 . Indeed, let T be the CCF change-of-basis, i.e., let ⃗ z be defined by ⃗ x = T ⃗ z and write ⃗ z [ i + 1 ] = e A ⃗ z [ i ] + ⃗ e bu [ i ] (111) where e A = T − 1 AT and ⃗ e b = T − 1 ⃗ b , is in CCF. Then this closed-loop input gives ⃗ z [ i + 1 ] = e A ⃗ z [ i ] + ⃗ e b ( ⃗ f ⊤ ⃗ x [ i ] + u OL [ i ]) (112) = ( e A + ⃗ e b ⃗ e f ⊤ ) ⃗ z [ i ] + ⃗ e bu OL [ i ] (113) = e A CL ⃗ z [ i ] + ⃗ e bu OL [ i ] . (114) where ⃗ e f ⊤ : = ⃗ f ⊤ T and e A CL : = e A + ⃗ e b ⃗ e f ⊤ . By Proposition 15 , for every desired set of eigenvalues of e A CL , there exists a choice of ⃗ e f which places the eigenvalues of e A CL at this set. Now converting back to ⃗ x coordinates, we get ⃗ x [ i + 1 ] = T ⃗ z [ i + 1 ] (115) = T e A CL ⃗ z [ i ] + ⃗ e bu OL [ i ] (116) = T e A CL T − 1 ⃗ x [ i ] + T − 1 ⃗ bu OL [ i ] (117) © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 17

EECS 16B Note 12: Controllability 2023-10-22 13:30:20-07:00 = T e A CL T − 1 ⃗ x [ i ] + ⃗ bu OL [ i ] . (118) Now the eigenvalues of A CL : = T e A CL T − 1 are the same as e A CL , so all eigenvalues of A CL are settable by a suitable choice of feedback ⃗ f , as well. Contributors: • Druv Pai. • Moses Won. • Neelesh Ramachandran. • Rahul Arya. • Murat Arcak. • Anant Sahai. © UCB EECS 16B, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 18

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version