报告题目：Highly accurate doubling algorithms for M-matrix algebraic Riccati equations

报告人：薛军工

主持人：徐玮玮副教授

报告时间：2019年1月2日10:20-11:20

报告地点：尚贤楼 706报告厅

报告摘要: The doubling algorithms are very efficient iterative methods for computing the unique minimal nonnegative solution to an $M$-matrix algebraic Riccati equation (MARE).They are globally and quadratically convergent, except for MARE in the critical case at which it converges linearly with the linear rate $1/2$. However, the initialization phase and the doubling iteration kernel of any doubling algorithm involve inverting nonsingular $M$-matrices. In particular for MARE in the critical case, the $M$-matrices in the doubling iteration kernel, although nonsingular, move towards singular $M$-matrices at convergence. A nonsingular $M$-matrix can be inverted by the GTH-like algorithm to almost full entrywise relative accuracy, provided a triplet representation of the matrix is known. Recently, Nguyen and Poloni(Numer. Math.,130(4):763--792,2015) discovered away to construct triplet representations in a cancellation-free manner for all involved $M$-matrices in the doubling iteration kernel, for a special class of MAREs arising from Markov-modulated fluid queues.In this talk, we extend Nguyen's and Poloni's work to all MAREs by also devising a way to construct the triplet representations cancellation-free. Our construction, however, is not a straightforward extensionof theirs. It is made possible by an introduction of novel recursively computable auxiliary nonnegative vectors. As the second contribution, we propose an entrywise relative residual for an approximate solution. The residual has an appealing feature of being able to reveal the entrywise relative accuracies of all entries, large and small, of the approximation. This is in marked contrast to the usual legacy normalized residual which reflects relative accuracies of large entries well but not so much those of very tiny entries. Numerical examples are presented to demonstrate and confirm our claims.

报告人简介：薛军工，复旦大学数学科学学院教授，博士生导师，复旦大学数学科学学院副院长。德国洪堡基金获得者，入选“教育部新世纪优秀人才计划”、上海市浦江计划等，主要从事数值代数、排队论、随机微分方程数值解、计算金融等方向研究。成果主要发表在计算数学顶尖刊物Math. Comp., SIAM J. Matrix Anal. Appl., Numer. Math.以及运筹学重要刊物 INFORMS J. Computing、 Queueing System,、J Appl. Prob.上。

数学与统计学院

2018年12月29日