University of Cambridge Home [Dept of Engineering] Control Group

Validated Numerical Methods for Systems and Control*

Masaaki Kanno and Malcolm C. Smith

* This project was supported by EPSRC Grant GR/S56184/01.

The Purpose of the Research

The aim of this research is to investigate the development of numerical methods for systems and control which have a guarantee on accuracy. An end-product of such research is an algorithm which could be described as "infallible" in the following sense: the user would specify a priori a tolerance as small as desired, and the computer would provide an answer which is guaranteed to be accurate to the specified tolerance. This is an established research topic in computer science and a few application areas in science and engineering, but is less familiar in the control systems area. A characteristic feature of such work is the application of computer algebra tools and the avoidance of floating-point arithmetic.

A formal definition of the meaning of guaranteed accuracy in the context of this research is given as follows [4]:

Definition 1   Let $ f : \mathbb{R}^n \rightarrow \mathbb{R}$ be well-defined (not necessarily continuous). Let $ A $ be some given algorithm taking the form of an executable procedure, which generates a well-defined function $ A : ( \mathbb{F}^n, \mathbb{F}_{> 0} ) \rightarrow \mathbb{F}^2 $ where $ \mathbb{F}\subset \mathbb{R}$ is a set of computer representable numbers, $ \mathbb{F}_{> 0} $ is a set of strictly positive elements in $ \mathbb{F}$ and $ A({\bf P}, \epsilon) = (f_\ell, f_r) $ where $ f_\ell \leq f_r $. Then, $ A $ is said to be a guaranteed accuracy algorithm for $ f $ over $ \mathbb{F}$ if, for any $ {\bf P} \in \mathbb{F}^n $ and any $ \epsilon \in \mathbb{F}_{> 0} $, (the true) $ f({\bf P}) $ is contained in the closed interval $ [f_\ell, f_r] $ and $ f_r - f_\ell \leq \epsilon $.

Guaranteed Accuracy Programs

A Maple Program Library developed in this research project is made available online (it can be downloaded from below). It includes:

Firstly, the Maple library is to be downloaded and saved into a library directory. After starting Maple, the library module should be loaded and, then, the programs can be invoked. 


   > restart:
   > libname := "/users/mk303/Research/Maple_Library/", libname;
        libname := "/users/mk303/Research/Maple_Library", "/tools/maple9.5/lib"

   > with(linalg); with(control);
        Warning, the protected names norm and trace have been redefined and unprotected
        [BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp, Wronskian,
           addcol, addrow, adj, adjoint, angle, augment, backsub, band, basis,
                   ........
           trace, transpose, vandermonde, vecpotent, vectdim, vector, wronskian]

        [Hurwitz, Kharitonov, Lmatrix, McMillan, check_spec_fact, find_inter_matrix,
                   ........
           nugap, nugap_TM, r_convert, root_fact, spec_fact, sqrt_range]

   > G := matrix([[1/(s+1), 1/(s+2)], [3/(s+5), (2*s+3)/(s^2+3*s+5)]]);
                        \bgroup\color{blue}$ G := \left[ \begin{array}{cc}
\frac1{s+1} & \frac1{s+2} \\
\frac3{s+5} & \frac{2s+3}{s^2+3s+5}
\end{array} \right] $\egroup

   > out := linfnorm_TM(G, s, 10^(-8)); evalf(out);
                       \bgroup\color{blue}$ out := \left[ {\frac {46533151}{33554432}}, {\frac {186132605}{134217728}},
{\scriptstyle 0} \right] $\egroup
                       [1.386795968, 1.386795975, 0.]

   > out := h2norm_TM(G, s); evalf(out);
                             \bgroup\color{blue}$ out := \frac{1}{30} \sqrt{\scriptstyle 2355} $\egroup
                                1.617611408

   > G2 := matrix([[1/2/(s+1), 1/(s+2)], [3/(s+5), (2*s+3)/(s^2+3*s+5)]]);
                       \bgroup\color{blue}$ G2 := \left[ \begin{array}{cc}
\frac1{2 (s+1)} & \frac1{s+2} \\
\frac3{s+5} & \frac{2s+3}{s^2+3s+5}
\end{array} \right] $\egroup

   > out := nugap_TM(G, G2, s); evalf(out);
                             checking arguments
                       checking dimensions of matrices
                      checking winding number condition
                          constructing realisation
                         calculation of infinity norm
                           calculating lower bound
                               calculating Phi
                       calculating determinant of Phi
         \bgroup\color{blue}$ out := \left[\frac{1}{11322}\sqrt{\scriptstyle 13063701},
\...
...{1}{5146466564151}\sqrt{\scriptstyle 2699695473781141498350801} \right] $\egroup
                        [0.3192346070, 0.3192627379]

  >
Calling Sequencese Some explanations on the algorithms are found in [1, 2, 4, 5].

How to Use

  1. Download the Library --- index file, library. (You need to download both the index file and the library itself.)
  2. Store them to your library directory. (In the above example, it was /users/mk303/Research/Maple_Library .)
  3. Invoke Maple.
  4. Add the library directory to the libname variable; 
      > libname := "/users/mk303/Research/Maple_Library/", libname;
  5. Load both the linalg and control packages; 
      > with(linalg); with(control);
  6. Now the programs are ready to use.

References

[1] M. Kanno and M. C. Smith. Guaranteed accuracy computations in systems and control. In Proceedings of the European Control Conference ECC 2003, Cambridge, U.K., September 2003.
[2] M. Kanno and M. C. Smith. Validated numerical methods for systems and control engineering. ACM SIGSAM (Association for Computing Machinery --- Special Interest Group on Symbolic and Algebraic Manipulation) Bulletin, 37(3):72--73, September 2003.
[3] M. Kanno and M. C. Smith. Validated numerical methods for systems and control engineering. Poster presented at the International Symposium on Symbolic and Algebraic Computation ISSAC 2003, Philadelphia, Pennsylvania, USA, August 2003.
[4] M. Kanno and M. C. Smith. Validated numerical computation of the $ L_\infty $-norm for linear dynamical systems. Submitted to the Journal of Symbolic Computation, Volume 41, Number 6, Pages 697-707, June 2006.
[5] M. Kanno. Guaranteed Accuracy Computations in Systems and Control. PhD thesis, University of Cambridge, 2003.
Created by Masaaki Kanno <14-May-2005>.