Balanced Truncation: Difference between revisions

Help

Revision as of 09:53, 23 April 2013

Balanced Truncation is an important projection model reduction method which delivers high quality reduced models by making an extra effort in choosing the projection subspaces.

Derivation

A stable minimal (controllable and observable) system $Σ$ , realized by $(A, B, C, D)$

$\dot{x} = A x + B u$

$y = C x + D u$

is called balanced^[1], if the systems Controllability Gramian and Observability Gramian, the solutions $W_{C}$ and $W_{O}$ of the Lyapunov equations

$A W_{C} + W_{C} A^{T} = - B B^{T}$

$A^{T} W_{O} + W_{O} A = - C^{T} C$

respectively, satisfy $W_{C} = W_{O} = d i a g (σ_{1}, \dots, σ_{n})$ with $σ_{1} \geq σ_{2} \geq \dots \geq σ_{n} > 0$ . Since in general, the spectrum of $W_{C} W_{O}$ are the squared Hankel Singular Values for such a balanced system, they are given by: $\sqrt{λ (W_{C} W_{O})} = {σ_{1}, \dots, σ_{n}}$ .

An arbitrary system $(A, B, C, D)$ can be transformed into a balanced system $(\tilde{A}, \tilde{B}, \tilde{C}, \tilde{D})$ via a state-space transformation:

$(\tilde{A}, \tilde{B}, \tilde{C}, \tilde{D}) = (T A T^{- 1}, T B, C T^{- 1}, D) .$

This transformed system has balanced Gramians $W_{C} = T \tilde{W_{C}} T^{T}$ and $W_{O} = T^{- T} \tilde{W_{O}} T^{- 1}$ which are equal and diagonal. The balanced systems states are ordered (descendingly) by how controllable and observable they are, thus allowing a partion of the form:

$(\tilde{A}, \tilde{B}, \tilde{C}, \tilde{D}) = ([\begin{matrix} {\tilde{A}}_{11} & {\tilde{A}}_{12} \\ {\tilde{A}}_{21} & {\tilde{A}}_{22} \end{matrix}], [\begin{matrix} {\tilde{B}}_{1} \\ {\tilde{B}}_{2} \end{matrix}], [\begin{matrix} {\tilde{C}}_{1} & {\tilde{C}}_{2} \end{matrix}], \tilde{D})$ .

By truncating the discardable states, the truncated reduced system is then given by $\hat{Σ} = ({\tilde{A}}_{11}, {\tilde{B}}_{1}, {\tilde{C}}_{1}, \tilde{D})$ .

Implementation: SR Method

The necessary balancing transformation can be computed by the SR Method^[2]. First, the Cholesky factors of the gramians $W_{C} = S^{T} S, W_{O} = R^{T} R$ are computed. Next, the Singular Value Decomposition of $S R^{T}$ is computed:

$S R^{T} = U Σ V^{T} .$

Now, partitioning $U, V$ , for example based on the Hankel singuar Values, gives

$S R^{T} = [\begin{matrix} U_{1} U_{2} \end{matrix}] [\begin{matrix} Σ_{1} \\ Σ_{2} \end{matrix}] [\begin{matrix} V_{1}^{T} \\ V_{2}^{T} \end{matrix}] .$

The truncation of discardable partitions $U_{2}, V_{2}^{T}, Σ_{2}$ results in the reduced order model $(P^{T} A Q, P^{T} B, C Q, D)$ where

$P = R^{T} V_{1} Σ_{1}^{- \frac{1}{2}},$

$Q = S^{T} U_{1} Σ_{1}^{- \frac{1}{2}} .$

$Q^{T} P = I_{r}$ makes $Q P^{T}$ an oblique projector and hence Balanced Trunctation a Petrov-Galerkin projection method. The reduced model is stable with Hankel Singular Values given by $σ_{1}, \dots, σ_{r}$ , where r is the order of the reduced system. It is possible to choose $r$ via the computable error bound^[3]:

$‖ Σ - \hat{Σ} ‖_{2} \leq 2 ‖ u ‖_{2} \sum_{k = r + 1}^{n} σ_{k} .$

References

↑ B.C. Moore, "Principal component analysis in linear systems: Controllability, observability, and model reduction", IEEE Transactions on Automatic Control , vol.26, no.1, pp.17,32, Feb 1981
↑ A.J. Laub; M.T. Heath; C. Paige; R. Ward, "Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms," IEEE Transactions on Automatic Control, vol.32, no.2, pp.115,122, Feb 1987
↑ D.F. Enns, "Model reduction with balanced realizations: An error bound and a frequency weighted generalization," The 23rd IEEE Conference on Decision and Control, vol.23, pp.127,132, Dec. 1984

[1] B.C. Moore, "Principal component analysis in linear systems: Controllability, observability, and model reduction", IEEE Transactions on Automatic Control , vol.26, no.1, pp.17,32, Feb 1981

[2] A.J. Laub; M.T. Heath; C. Paige; R. Ward, "Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms," IEEE Transactions on Automatic Control, vol.32, no.2, pp.115,122, Feb 1987

[3] D.F. Enns, "Model reduction with balanced realizations: An error bound and a frequency weighted generalization," The 23rd IEEE Conference on Decision and Control, vol.23, pp.127,132, Dec. 1984

[1]

[2]

[3]

@@ Line 4: / Line 4: @@
 [[Category:linear algebra]]
-An important projection model reduction method which delivers high quality reduced models by making an extra effort in choosing the projection subspaces.
+'''Balanced Truncation''' is an important projection model reduction method which delivers high quality reduced models by making an extra effort in choosing the projection subspaces.
-A stable minimal (controllable and observable) system <math>\Sigma</math> , realized by (A,B,C,D) is called balanced, if the Gramians, i.e. the solutions P,Q  of the Lyapunov equations
+==Derivation ==
+A stable minimal (controllable and observable) system <math>\Sigma</math>, realized by <math>(A,B,C,D)</math>
-<math> AP+PA^T+BB^T=0,\quad A^TQ+QA+C^TC=0</math>
+<math> \dot{x} = Ax + Bu</math>
+<math> y = Cx + Du</math>
-satisfy <math> P=Q=diag(\sigma_1,\dots,\sigma_n)</math> with <math> \sigma_1\geq\sigma_2\geq \dots\geq\sigma_n>0</math>
+is called balanced<ref>B.C. Moore, "<span class="plain_links">[http://dx.doi.org/10.1109/TAC.1981.1102568 Principal component analysis in linear systems: Controllability, observability, and model reduction]</span>", IEEE Transactions on Automatic Control , vol.26, no.1, pp.17,32, Feb 1981</ref>, if the systems [[wikipedia:Controllability_Gramian|Controllability Gramian]] and [[wikipedia:Observability_Gramian|Observability Gramian]], the solutions <math>W_C</math> and <math>W_O</math> of the Lyapunov equations
-Since in general the  spectrum of <math> (PQ)^{\frac{1}{2}}</math> are the Hankel singular values for such a balanced system they are given by: <math>\{\sigma_1,\dots,\sigma_n\}</math>
-Given an arbitrary system <math>(\tilde{A},\tilde{B},\tilde{C},\tilde{D})</math> we transform into a balanced one via a state-space transformation
+<math> AW_C+W_CA^T=-BB^T </math>
+<math> A^TW_O+W_OA=-C^TC </math>
-<math> (A,B,C,D)= (T\tilde{A}T^{-1},T\tilde{B},\tilde{C}T^{-1},\tilde{D})=\left (\begin{bmatrix}A_{11} & A_{12}\\ A_{21} & A_{22}\end{bmatrix},\begin{bmatrix}B_1\\B_2\end{bmatrix}\begin{bmatrix} C_1 &C_2 \end{bmatrix},D\right)</math>
+respectively, satisfy <math> W_C=W_O=diag(\sigma_1,\dots,\sigma_n)</math> with <math> \sigma_1\geq\sigma_2\geq \dots\geq\sigma_n>0</math>.
-This transformed system has transformed Gramians <math>P=T\tilde{P}T^T</math> and  <math>Q=T^{-T}\tilde{Q}T^{-1}</math> which are equal and diagonal.
+Since in general, the  spectrum of <math>W_CW_O</math> are the squared Hankel Singular Values for such a balanced system, they are given by: <math>\sqrt{\lambda(W_CW_O)} = \{\sigma_1,\dots,\sigma_n\}</math>.
-The truncated reduced system is then given by
-<math> (\hat{A},\hat{B},\hat{C},\hat{D})=(A_{11},B_1,C_1,D) </math>
+An arbitrary system <math>(A,B,C,D)</math> can be transformed into a balanced system <math>(\tilde{A},\tilde{B},\tilde{C},\tilde{D})</math> via a state-space transformation:
+<math> (\tilde{A},\tilde{B},\tilde{C},\tilde{D})= (TAT^{-1},TB,CT^{-1},D).</math>
+This transformed system has balanced Gramians <math>W_C=T\tilde{W_C}T^T</math> and <math>W_O=T^{-T}\tilde{W_O}T^{-1}</math> which are equal and diagonal.
+The balanced systems states are ordered (descendingly) by how controllable and observable they are, thus allowing a partion of the form:
+<math> (\tilde{A},\tilde{B},\tilde{C},\tilde{D})= \left (\begin{bmatrix}\tilde{A}_{11} & \tilde{A}_{12}\\ \tilde{A}_{21} & \tilde{A}_{22}\end{bmatrix},\begin{bmatrix}\tilde{B}_1\\\tilde{B}_2\end{bmatrix},\begin{bmatrix} \tilde{C}_1 &\tilde{C}_2 \end{bmatrix},\tilde{D}\right)</math>.
+By truncating the discardable states, the truncated reduced system is then given by <math> \hat{\Sigma}=(\tilde{A}_{11},\tilde{B}_1,\tilde{C}_1,\tilde{D}) </math>.
 == Implementation: SR Method==
-One computes it for example by the SR Method.
-First one computes the (Cholesky) factors of the gramians <math>P=S^TS,\; Q=R^TR</math>. Then we compute the singular value decomposition of <math> SR^T\;</math>
+The necessary balancing transformation can be computed by the SR Method<ref>A.J. Laub; M.T. Heath; C. Paige; R. Ward, "<span class="plain_links">[http://dx.doi.org/10.1109/TAC.1987.1104549 Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms]</span>," IEEE Transactions on Automatic Control, vol.32, no.2, pp.115,122, Feb 1987</ref>.
+First, the Cholesky factors of the gramians <math>W_C=S^TS,\; W_O=R^TR</math> are computed.
+Next, the Singular Value Decomposition of <math> SR^T\;</math> is computed:
-<math> SR^T=\begin{bmatrix} U_1 U_2 \end{bmatrix} \begin{bmatrix} \Sigma_1 & \\ & \Sigma_2\end{bmatrix} \begin{bmatrix} V_1^T\\V_2^T\end{bmatrix}</math>
+<math> SR^T= U\Sigma V^T.</math>
-Then the reduced order model is given by <math>(W^TAV,W^TB,CV,D)\;</math> where
+Now, partitioning <math>U,V</math>, for example based on the Hankel singuar Values, gives
-<math> W=R^T V_1\Sigma_1^{-\frac{1}{2}},\quad V= S^T U_1 \Sigma_1^{-\frac{1}{2}}.</math>
+<math>SR^T= \begin{bmatrix} U_1 U_2 \end{bmatrix} \begin{bmatrix} \Sigma_1 & \\ & \Sigma_2\end{bmatrix} \begin{bmatrix} V_1^T\\V_2^T\end{bmatrix}.</math>
+The truncation of discardable partitions <math>U_2,V^T_2,\Sigma_2</math> results in the reduced order model <math>(P^TAQ,P^TB,CQ,D)\;</math> where
-We get then that <math>V^TW=I_r</math> which makes <math> VW^T</math> an oblique projector and hence balanced trunctation a Petrov-Galerkin projection method. The reduced model is stable with Hankel Singular Values given by <math>\sigma_1,\dots,\sigma_r</math>, where r is the order of the reduced system. It is possible to choose r via the computable error bound
+<math> P=R^T V_1\Sigma_1^{-\frac{1}{2}},</math>
-<math> \|y-\hat{y}\|_2\leq (2\sum_{k=r+1}^n\sigma_k)\|u\|_2. </math>
+<math> Q= S^T U_1 \Sigma_1^{-\frac{1}{2}}.</math>
+<math>Q^TP=I_r</math> makes <math> QP^T</math> an oblique projector and hence '''Balanced Trunctation''' a Petrov-Galerkin projection method. The reduced model is stable with Hankel Singular Values given by <math>\sigma_1,\dots,\sigma_r</math>, where r is the order of the reduced system. It is possible to choose <math>r</math> via the computable error bound<ref>D.F. Enns, "<span class="plain_links">[http://dx.doi.org/10.1109/CDC.1984.272286 Model reduction with balanced realizations: An error bound and a frequency weighted generalization]</span>," The 23rd IEEE Conference on Decision and Control, vol.23, pp.127,132, Dec. 1984</ref>:
+<math> \|\Sigma-\hat{\Sigma}\|_2 \leq 2 \|u\|_2 \sum_{k=r+1}^n\sigma_k. </math>
 ==References==
+<references/>