国立成功大学应用数学研究所硕士论文.pdf

國 立 成 功 大 學 應 用 數 學 研 究 所 碩 士 論 文 關於二次大型動態系統模型化簡的近來發展 On Some Recent Developments in Model Reduction of Large Scale Quadratic Dynamical System 研 究 生 賴 家 朗 指 導 教 授 王 辰 樹 中 華 民 國 九 十 一 年 六 月 誌 謝 本論文得以順利付梓 實承蒙諸位師友的協助與鼓勵 首先感謝 王辰樹老師的悉心指導 謝謝你帶我進入數學的殿堂中 讓我知道數 學的世界是如此的宏偉壯觀 更讓我體會到數學家的偉大和辛勞 也 由衷的佩服你們和你們所作的研究 另外要謝謝的是清華大學林文偉 教授 和北京大學王奕倩博士給我的指導和鼓勵 還有清華大學的范 洪源學長 張書銘學長及郭岳承學長 還有我的夥伴連婉君同學 王 春萬同學 謝謝你們 我會永遠記得你們對我的照顧和關懷 此情難 忘 謹致由衷最大的敬意與謝忱 相信有你們的參與 讓我的生活更 充實 也讓我學習到人跟人之間友情的可貴 而論文口試期間承蒙口試委員林文偉教授 賴玉玲教授 王振男 教授以及王辰樹教授不吝指正本論文之缺失 並惠賜寶貴意見使本論 文更加充實 於此致最誠摯的感謝 在研究所的求學生涯中 我感謝所有授課老師 特別是林琦焜老 師 方永富老師 許瑞麟老師 侯世章老師 沈士育老師以及林正洪 老師 於學習過程中給予的關心與寶貴的建議 讓我得以在學業上更 上層樓 除此之外 由衷感謝與我相處兩年的所有同學 與我相互鼓勵 關懷與幫忙 特別是吳文瑞學長在 TeX 方面的幫忙 林仁彥學長在 Matlab 程式的幫助及陳昆助學長的鼓勵 還有來這裡認識的所有朋友 及同學們 給予我生活及學業上的幫忙 若沒有您們 我這兩年的生 活將黯然失色 謹將這份碩士學位的榮耀與喜悅獻給我最親愛的父母與家人 感 謝你們對我的支持 是我最重要的支柱與動力 我所有榮耀成就 全 屬於你們 在此表達我最真摯的感恩與感謝之心 賴家朗 謹誌於 成大應數所 西元 2002 年 6 月 On Some Recent Developments in Model Reduction of Large Scale Quadratic Dynamical System Jia Lang Lai Institute of Applied Mathematics National Cheng Kung University Tainan 701 Taiwan R O C Abstract The purpose of this paper is to acquire model reductions of large scale quadratic dynamical systems The idea for solving the problem is based on the relation between a quadratic system and its related enlarged linear sys tem That is we transfer the second order system to an enlarged fi rst order systems and obtain the second order model reduction by converting the fi rst order model reduction to a second order one Next we give a brief introduction for numerical methods of the fi rst order model reduction Particularly these methods can be categorized to two groups a SVD based methods b Krylov based methods Finally some numerical experiments are performed The re sults of numerical implementation show that some serious round off errors may occur when the fi rst order model reduction converts to the second order one So we conclude that the propose methods in this paper are eventually not good enough for the second order reduction However a reliable and effi cient method for the model reduction of a quadratic dynamical system is still under investigation Keywords Lyapunov equation Hankel norm Transfer function Low Rank Gramian Schur decomposition Balanced trancation ADI Lanczos Arnoldi Contents 1Introduction2 1 1Problem statement 2 1 1 1 Reduction via fi rst order balance and truncation 3 1 1 2 Transfer fi rst order system to second order system 4 1 2First order linear dynamical system 5 1 3Measures of the accuracy of the approximation 6 2SVD based methods7 2 1Proper orthogonal decomposition POP method 9 2 2Balanced truncation method 9 2 2 1The minimal control and largest observation energies 9 2 2 2Hankel operator Gramians and Lyapunov equations 10 2 2 3Balance and truncate 11 2 3Optimal Hankel norm approximation method 13 3Krylov based methods14 3 1Approximation by moment matching 14 3 1 1Lanczos procedure 16 3 1 2Arnoldi procedure 18 3 1 3Implicitly restarted Arnoldi and Lanczos methods 18 3 1 4Rational Krylov method 19 3 2Krylov subspace method 21 3 2 1Alternating direction implicity iteration ADI and LR ADI 21 3 2 2Smith method 22 3 2 3Low rank square root method LRSRM 22 3 2 4Low rank Schur method LRSM 23 4Some properties of the second order system25 4 1Second order transfer function 25 4 2Second order Gramian 26 4 3Second order singular values and balancing 28 4 4Direct second order reduction method 29 5Numerical experiments30 6Conclusions and future work36 References37 1 1Introduction In the real world there is a very large variety of physical phenomena in which we are much interested In order to observe this variety of physical phenomena one of the methods is to model it So we model the variety of physical phenomena with time invariant dynamical system before we observe However diff erential equations are one of the most successful means of modeling dynamical systems Such models can frequently be acquired through discretizations of partial or ordinary diff erential equations which describe the physical system But in the procedure of modeling the original system we must keep important properties of original system Otherwise the model we want to observe will lose the physical phenomena and be no meanings for us Roughly the resulting reduction model might be used to replace the original system as a component in a larger simulation And it might be used to develop a low dimensional controller which is suitable for real time applications For some dynamical models of fl exible space structures and rotor systems they are often given as a system of linear diff erential equations in second order form M q G q Kq Du Of course there are many modeling methods like Euler Lagrange 20 and fi nite element computer codes like NASTRAN 20 which naturally provide some equa tions in second order form In this diff erential equation the matrices M G K and D have structure which come from the original system and the coordinates q have direct physical meaning For large or distributed fl exible systems second order form dynamical models may have thousands of coordinates and designing controllers Be sides from them there may be a formidable task which require almost impractical amounts of computation So it is often necessary for us to obtain a reduced order model which must keep the most characters of the original system in controller design Then we can observe the phenomena related to real system by observing the reduced model 1 1Problem statement In this paper we will study several classical problems for the time invariant description of a stable system in standard second order state space form M q G q Kq Du y Pq Q q 1 1 with initial condition q t0 q0 q t0 w0 where u Rmis the input function y Rpis the output function and q Rnis the state function usually physical coordinates In particular we focus on realizations 2 with large state space dimension say n 1000 and small input space and output space dimensions say m p 0 K KT 0 G G1 G2withG1 GT 1 0 GT 2 G2 Throughout this paper we assumed to be M is invertible i e det M 6 0 Instead of studying the model reduction of a quadratic system we investigate the reduction of an enlarged linear system which arises from the target quadratic system Then we deal with the fi rst order enlarged system by the familiar model reduction methods which have been proposed Among these methods Moore s balance and truncation have been extensively studied 21 15 26 10 and enjoys many benefi cial properties Roughly Moore s method requires diff erential equations in fi rst order form Therefore to a second order system one must fi rst transfer the original second order system to enlarged linear system and then apply Moore s method to obtain the fi rst order model reduction We explore second order reduction by converting to fi rst order system and the natural issue of collapsing fi rst order systems into a second order system arises 1 1 1 Reduction via fi rst order balance and truncation As our previous discussion our purpose is to reduce 1 1 into the following second order system M qk G qk Kqk Du y Pqk Q qk 1 2 where qk Rk k n For second order model reduction the matrices still must satisfy structural conditions After the reduced procedure we compare 1 1 with 1 2 by putting the same input into 1 1 and 1 2 such that the behavior of output of 1 2 is close to the behavior of output of 1 1 Next we reduce model via fi rst order balance and truncation So we transfer the second order system to an enlarged fi rst order system by involving a new variable vT qT qT and have the following enlarged fi rst order system v Av Bu y Cv 3 where A 0I M 1K M 1G B 0 M 1D C PQ 1 3 with initial condition v t0 v0 q0 w0 Now we had put 1 1 in the enlarged fi rst order system and the size of the matrices in the enlarged system had become double i e 2n After we balanced and truncated to obtain reduced model matrices they had lost the structured conditions Therefore if a fi rst order method is used to reduce the realization A B C then since we want a second order model reduction system a question arises When can a fi rst order system be transferred to a second order system realization in 1 3 That is when does a transfer matrix have a reduced realization with A B in the following form A 0I A12A22 B 0 B21 1 4 From those structural matrices G K D P and Q are extracted after setting M I or any other invertible matrix 20 In the sequel we will try to fi nd a transfer matrix to convert a reduced realization with A B to the second order system in 1 3 1 1 2 Transfer fi rst order system to second order system In this section we acquire a transfer matrix to transfer reduced order model to the second order system 1 3 Through balance and truncation for enlarged fi rst order system the reduction model denoted by A B C does not satisfy second order system 1 3 In order to slove this problem fi nd a transformation TBto transfer B B1 B2 to BTB TB B in 1 3 form For this goal fi rst let B QbRbbe a Q R decomposition of B with Qb QT b I and Rb R1 0 is a triangular matrix Then multiple a permutation matrix Trsuch that Tr Rb 0 R1 Therefore TB T T r QT b and get BTB TB B 0 R1 and ATB TB A T 1 B A1A2 A3A4 4 Next fi nd a transformation TAto transfer ATBto A TA ATB T 1 A in 1 3 form and still keep B TA BTBin 1 3 form Then by Gauss elimination let TA1 I0 A 1 2 A1I andTA2 I0 0A2 Therefore TA TA2 TA1 Finally there exists a transformation matrix T TA TB such that A B C T A T 1 T B C T 1 where A B in the 1 3 form 1 2First order linear dynamical system From above discussion the fi rst thing is to transfer the second order system to the enlarged fi rst order system Then we reduce the enlarged fi rst order dynamical system to the reduced order model and transfer the result to the second order system 20 in 1 3 form We assumed that the fi rst order dynamical system is described by the generalized state space form E x t Ax t Bu t y t Cx t 1 5 Among the realizations of continuous time time invariant dynamical systems E Rn n A Rn n B Rn m C Rq n t R and n is the order or dimension of the realization dim n Here it is assumed that the system is single input single output SISO so that the input u t and output y t are scalar functions of time with B and C column vectors of length n Extensions to multiple input multiple output MIMO systems exist but will not be treated here For details on these issues we refer to 13 For nearly all large scale problems it is assumed that the system matrix A and matrix E are large and sparse or structured Moreover we assume that the system is stable i e the eigenvalues of A are in the open left half plane and minimal that is the system is controllable and observable Besides for simplicity E will be assumed to be an identity matrix Together with an initial condition zero state x 0 x0 realizations 1 5 are uniquely described by the matrices A B C Here we will also use the equivalent notation AB C R n p n m which is more common in control theory The vector valued functions x y and u are referred to as state output and input of the system respectively 5 A reduction order approximation to 1 5 takes the corresponding system x t A x t Bu t y t C x t i e A B C R k p k m 1 6 where k n In the reduced order model reduction the following properties 5 6 must be satisfi ed 1 The approximation error small existence of global error bound 2 System properties like stability passivity are preserved 3 The procedure is computationally stable and effi cient The fi rst property above is to be understood as follows In order to compare with original system and reduced order system feed the same input function u into both systems and and let the corresponding responses be y and y respectively Small approximation error means that y is nearly close to y in an approximate sense and for a same given set of inputs In the sequel we will use the following criterion in reduced order approximations the worse error y y should be minimized for all u this gives rise to the so called H error criterion which is defi ned the largest singular values of the transfer function in the imaginary 5 The dimension of the reduced order model is designated as k which is supposed to be much smaller than n Ideally the reduced order model would produce an output y t which approximate well to the true output y t for all the same inputs u t However in general no simple relation exists between x t and the true vector x t For instance the tenth element of x t does not need to be directly related to the tenth element of x t 1 3Measures of the accuracy of the approximation Given a second order linear system in state space form 1 1 we can transfer it to enlarged fi rst order linear system with coeffi cients as 1 3 Apply the Laplace trans form 24 to the fi rst order system and zero state x 0 0 then obtain its output function of the system yL s H s uL s where H s C sIn A 1B is the transfer function yLand uLare in the Laplace transform domain From above description it can be also to represent the linear dynamical systems via the transfer function H s of the system The model reduction problem therefore reduces to an approximation of the frequency response H s by another rational matrix of lower degree H s C sIk A B Some approximate measures of the accuracy of the reduced order model are pos sible Formally there tends to be an interest in the diff erence between the actual and 6 low order output y t y t given some set of inputs u t and this can be charac terized by a system norm The popular H norm 2 for example measure in the time domain the worst ratio of output error energy to input energy Equivalently in the frequency domain it represents the largest magnitude of the frequency response error A second measure of the accuracy of the approximation is to assess which proper ties of the original model are kept in the reduced order one Those properties which we feel great a interest in are said to be invariant 13 that is they are independent with respect to a similarity transform By retaining certain original properties of the system in the reduced order model we hope the resulting approximation error is small However this error depends on the selection of the retained invariant properties A common choice for these invariant properties is the so called modal approximation of the system 1 8 31 The modal approximation preserves the dominant system s poles eigenvalues nand corresponding residues which both arise in the partial frac tion expansion of the frequency response Hence a reduced order model that matches or approximates specifi c modal components of the original model is expected to ap proximate well its response Potentially iterative eigenvalue techniques can be used to fi nd these specifi c components so that this modal retention approach is feasible for large scale problems Unfortunately it can be diffi cult to identify a priori whose models are the truly dominant modal components of the original system 10 Alternative invariant properties that may be retained in model reduction are the Hankel singular values Hankel singular values are relative to the controllability and observability properties of the system 19 Constructing a reduced order model to retain the largest Hankel singular values is known as balanced truncation A vari ant of this is known as optimal Hankel norm approximation 15 These last two approximations are nearly optimal in terms of the H norm of the error and are constructed from balanced realizations The other invariant properties of interest in this survey are the coeffi cients of some power series expansion of H s The solution techniques proposed determine a reduced order model that accurately matches the leading coeffi cients jarising in a chosen power series The paper is organized as follows We continue in section 2 and section 3 with review the theory of approximation methods of fi rst order dynamical systems based on SVD based methods and Projection based methods respectively In section 4 we discuss some properties of second order dynamical system In section 5 some numer ical experiments are introduced Finally conclusions and future work are provided in section 6 2SVD based methods In this section we introduce the reduction methods for the fi rst order system First we analyze SVD based methods 5 The SVD based methods have their roots in 7 the singular value decomposition and the resulting solution of the approximation of matrices by means of matrices of lower rank which are optimal in the 2 norm The quantities which are important in deciding to what extent a given fi nite dimensional operator can be approximated by one of lower rank are the so called singular values these are the square roots of the eigenvalues of the product of the operator and its adjoint Important is that the ensuing error satisfi es an computable upper bound There are diff erent ways of applying the SVD to the approximation of dynamical systems One way of those application to non linear systems is known as Proper Orthogonal Decomposition POP 6 Choose an input function and compute the resulting trajectory collect samples of this trajectory at diff erent times and compute the SVD of the resulting collection of samples Then apply the SVD to the resulting matrix POP is widely used in computation involving PDEs The problem how ever in this case is that the resulting simplifi cation heavily depends on the initial excitation function chosen the time instances at which the measurements are taken consequently the singular values obtained are not system invariants The advantage of POP is that it can be applied to high complexity linear as well as nonlinear systems 5 For the linear time invariant dynamical system it can be represented by means of an integral convolution operator if in addition the system is fi nite dimensional this operator has fi nite rank and is hence compact Consequently it has a set of fi nitely many non zero singular values Thus in principle the SVD approximation method can be used to simplify such dynamic