A Fast Newton's Method for a Nonsymmetric Algebraic Riccati Equation
A Fast Newton's Method for a Nonsymmetric Algebraic Riccati Equation
复制标题
DOI：
10.1137/070681478
复制
发表时间：
2008-02
期刊：
影响因子：
--
通讯作者：
Dario Bini;B. Iannazzo;Federico Poloni
中科院分区：
文献类型：
--
作者：
Dario Bini;B. Iannazzo;Federico Poloni
考虑了代数Riccati方程$XCX-XE-AX+B=0$的一个特例，其中$n\乘以n$矩阵系数$A，B，C，E$是秩结构矩阵。基于类柯西矩阵的结构特性，设计了一种算法，用于在$O(n^2)$算术运算（ops）中执行习惯的牛顿迭代。同样的技术被用于降低l - z提出的算法的成本。[数]中的Lu。线性代数应用。从$O(n^3)$到$O(n^2)$ ops，同时在一般情况下仍然保持二次收敛。作为一个副产品，我们通过简单的形式关系证明了后一种算法与习惯的牛顿方法密切相关。在要求解处的雅可比矩阵为奇异且二次收敛变为线性的关键情况下，我们提供了一种移位技术的适应性，以消除奇异性。将原方程转化为等效的Riccati方程，去掉了奇异点，同时矩阵系数保持原方程结构不变。这导致了复杂度$O(n^2)$的二次收敛算法，它提供了完全精确的近似值。数值实验和比较证实了新方法的有效性。
A special instance of the algebraic Riccati equation $XCX-XE-AX+B=0$ where the $n\times n$ matrix coefficients $A,B,C,E$ are rank structured matrices is considered. Relying on the structural properties of Cauchy-like matrices, an algorithm is designed for performing the customary Newton iteration in $O(n^2)$ arithmetic operations (ops). The same technique is used to reduce the cost of the algorithm proposed by L.-Z. Lu in [Numer. Linear Algebra Appl., 12 (2005), pp. 191-200] from $O(n^3)$ to $O(n^2)$ ops while still preserving quadratic convergence in the generic case. As a byproduct we show that the latter algorithm is closely related to the customary Newton method by simple formal relations. In critical cases where the Jacobian at the required solution is singular and quadratic convergence turns to linear, we provide an adaptation of the shift technique in order to get rid of the singularity. The original equation is transformed into an equivalent Riccati equation where the singularity is removed while the matrix coefficients maintain the same structure as in the original equation. This leads to a quadratically convergent algorithm with complexity $O(n^2)$ which provides approximations with full precision. Numerical experiments and comparisons which confirm the effectiveness of the new approach are reported.