臺灣博碩士論文加值系統

現今科學發展，大型運算成為重要的研究課題。Algebraic Riccati equations 是從二次優化控制問題中而來。在這篇論文中，我們探討大型稀疏 algebraic Riccati equations 低秩逼近解與控制系統的關係，利用控制系統中的可控性及可觀測性，得到可以利用低秩解去逼近大型稀疏 algebriac Riccati equations；在求解 algebriac Riccati equations，我們利用牛頓法(Newton's method)進行迭代，一般而言牛頓法為二次收斂，但在每一次迭代時需要求解 Lyapunov equation，使得收斂速度大幅降低，在大型稀疏矩陣下求解 Lyapunov equation，有 Cholesky Factor Alternating Direction Implicit 迭代法可以保持低秩解結構，進而減少其運算量；更進一步利用兩個策略：Guess initial、Relaxed CFADI，減少內部迭代次數，加速整體牛頓法的迭代速度，最後以數值實驗觀察其迭代速度的變化。

In recent years, large-scale computing has become an important research topic. Algebraic Riccati equations is a control problem comes from the quadratic optimization. In this paper, we study the relationship between the large-scale sparse algebraic Riccati equations low-rank approximate solutions and the control systems, the control system controllability and observability that can be used to obtain low-rank approximate solution of large sparse algebriac Riccati equations; we use Newton's method solving the algebriac Riccati equations, the convergence rate of Newton's method is quadratic, but each iteration requires solving the Lyapunov equation, so that the convergence rate significantly lower, for solving the Lyapunov equations Cholesky Factor Alternating Direction Implicit iterative method can be kept low-rank structure of the solution, thereby reducing its computation; further use of two strategies: Guess initial value, Relaxed CFADI, reducing the total number of inner iteration to accelerate the convergence rate of Newton's method, and finally provide some numerical results.

1 Introduction 1
2 Preliminary 4
2.1 Preliminary 4
2.2 Numerically Low Rank Approximation 8
3 Low Rank Newton ADI Method 15
3.1 ADI and Lyapunov Equations 15
3.1.1 ADI Parameters Selection 16
3.2 CFADI 20
3.3 Newton’s Method for AREs 23
4 Relaxed NM-CFADI Method 25
4.1 Initial Value Guess 25
4.2 Relaxed ADI Method 26
5 Numerical Experiments 30
6 Conclusion and Remarks 35
Reference 37

[1] 王竹溪與郭敦仁. 特殊函數概論. 凡異出版社, 1993.
[2] 徐樹方. 控制論中的矩陣計算. 北京: 高等教育出版社, 2011.
[3] Peter Benner and Heike Faßbender. On the numerical solution of large-scale sparse discrete-time Riccati equations. Advances in Computational Mathematics, 35(2-4):
119–147, 2011.
[4] Peter Benner, Alan J Laub, and Volker Mehrmann. A collection of benchmark examples for the numerical solution of algebraic Riccati equations i: Continuoustime case. In Fak. f. Mathematik, TU Chemnitz–Zwickau. Citeseer, 1995.
[5] Peter Benner, Jing-Rebecca Li, and Thilo Penzl. Numerical solution of largescale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems. Numerical Linear Algebra with Applications, 15(9):755–777, 2008.
[6] Peter Benner and Jens Saak. A Galerkin-Newton-ADI method for solving largescale algebraic Riccati equations. 2010.
[7] Peter Benner and André Schneider. Model order and terminal reduction approaches via matrix decomposition and low rank approximation. In Scientific Computing in Electrical Engineering SCEE 2008, pages 523–530. Springer, 2010.
[8] Russell Carden. Ritz values and Arnoldi convergence for nonsymmetric matrices. ProQuest, 2009.
[9] Yi-Ru Chao. A survey on numerical solutions for algebraic Riccati equations. Master Thesis, NCKU, 2007.
[10] Eric King-Wah Chu, Hung-Yuan Fan, Wen-Wei Lin, and Chern-Shun Wang. Structure-preserving algorithms for periodic discrete-time algebraic Riccati equations. International Journal of Control, 77(8):767–788, 2004.
[11] Biswa Nath Datta. Numerical methods for linear control systems: design and analysis. Access Online via Elsevier, 2004.
[12] Gene H Golub and Charles F Van Loan. Matrix computations, volume 3. JHU Press, 2012.
[13] Ming Gu and Stanley C Eisenstat. Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM Journal on Scientific Computing, 17(4): 848–869, 1996.
[14] Chun-Hua Guo and Peter Lancaster. Analysis and modificaton of Newton’s method for algebraic Riccati equations. Mathematics of Computation of the American Mathematical Society, 67(223):1089–1105, 1998.
[15] Yu-Ling Lai, Kun-Yi Lin, and Wen-Wei Lin. An inexact inverse iteration for large sparse eigenvalue problems. Numerical Linear Algebra with Applications, 4(5):425–437, 1997.
[16] Hsing-Chuan Li. A modified computation strategy for low-rank approximate solution of large-scale algebraic Riccati equation. Ph.D. Thesis, NSYSU, 2014.
[17] Jing-Rebecca Li and Jacob White. Low rank solution of Lyapunov equations. SIAM Journal on Matrix Analysis and Applications, 24(1):260–280, 2002.
[18] Tiexiang Li, Eric King-Wah Chu, Yueh-Cheng Kuo, and Wen-Wei Lin. Solving large-scale nonsymmetric algebraic Riccati equations by doubling. SIAM Journal on Matrix Analysis and Applications, 34(3):1129–1147, 2013.
[19] Tiexiang Li, Eric King-Wah Chu, and Wen-Wei Lin. Solving large-scale discretetime algebraic Riccati equations by doubling. Technical report, NCTS Preprints in Mathematics, National Tsing Hua University, Hsinchu, Taiwan, 2012.
[20] An Lu and Eugene L Wachspress. Solution of Lyapunov equations by alternating direction implicit iteration. Computers ＆ Mathematics with Applications, 21(9): 43–58, 1991.
[21] Hermann Mena and Jens Saak. On the parameter selection problem in the Newton-ADI iteration for large-scale Riccati equations. Electronic Transactions on Numerical Analysis, 29:136–149, 2008.
[22] Chris Paige. Properties of numerical algorithms related to computing controllability. Automatic Control, IEEE Transactions on, 26(1):130–138, 1981.
[23] Donald W Peaceman and Henry H Rachford, Jr. The numerical solution of parabolic and elliptic differential equations. Journal of the Society for Industrial ＆ Applied Mathematics, 3(1):28–41, 1955.
[24] Thilo Penzl. A cyclic low-rank Smith method for large sparse Lyapunov equations. SIAM Journal on Scientific Computing, 21(4):1401–1418, 1999.
[25] Andrew P Sage and Chelsea C White. Optimum systems control, volume 2. Prentice-Hall Englewood Cliffs, NJ, 1977.
[26] Ji-Guang Sun. Perturbation theory for algebraic Riccati equations. SIAM Journal on Matrix Analysis and Applications, 19(1):39–65, 1998.
[27] Paul Van Dooren and Michel Verhaegen. On the use of unitary state-space transformations. Contemporary Mathematics on Linear Algebra and its Role in Systems Theory, 47, 1985.
[28] William T. Vetterling. Numerical Recipes Example Book. Cambridge University Press, 2002.
[29] Eugene L Wachspress. ADI iterative solution of Lyapunov equations. pages 229–231, North-Holland, Amsterdam, 1992.
[30] W Murray Wonham. Linear multivariable control: a geometric approach, volume 3. Springer-Verlag New York, 1979.
[31] Shu-Fang Xu. Sensitivity analysis of the algebraic Riccati equations. Numerische Mathematik, 75(1):121–134, 1996.