Computing the Fréchet Derivative of the Matrix Exponential, with an Application to Condition Number Estimation
Computing the Fréchet Derivative of the Matrix Exponential, with an Application to Condition Number Estimation
复制标题
计算矩阵指数的 Fréchet 导数及其在条件数估计中的应用
DOI：
10.1137/080716426
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
N. Higham
中科院分区：
文献类型：
--
作者：
Awad H. Al;N. Higham
矩阵指数函数是一个被广泛研究的矩阵函数，有着广泛的应用。矩阵指数的Frechet导数描述了$e^A$对$A$扰动的一阶灵敏度，其范数决定了$e^A$的条件数。在计算$e^A$的众多方法中，缩放和平方法是使用最广泛的。我们证明了该方法在[N。J. highham，矩阵指数的标度和平方方法再探讨，[j] .矩阵学报。达成。[j], 26 (2005), pp. 1179-1193]可以扩展到计算$e^A$和$A$在$e $方向上的$A$ Frechet导数，用$L(A, e)$表示，其成本约为单独计算$e^A$的三倍。该算法由缩放和平方法推导而来，通过微分Pade近似和平方递归，重用在Pade近似求值过程中计算的数量，并在平方阶段将递归交织在一起。为了指导算法参数的选择，对现有的缩放和平方方法的后向误差分析进行了扩展，结果表明，对舍入误差取模，得到的近似为$e^{A+\Delta A}$和$L(A+\Delta A, e +\Delta e)$，两者具有相同的$\Delta A$，并且在$\|\Delta A\|$和$\|\Delta e \|$上具有可计算的界。L(A，E)$的算法用于开发计算$ E ^A$及其条件数估计的算法。除了指数函数特有的结果外，我们还开发了一些适用于任意函数的结果和技术。我们展示了f(a)$的矩阵迭代如何产生Frechet导数的迭代，并展示了如何有效地计算幂级数的Frechet导数。我们还证明了一个矩阵多项式及其Frechet导数的计算代价最多是计算多项式本身的三倍，并给出了一个用Pade逼近求矩阵函数及其Frechet导数的一般框架。
The matrix exponential is a much-studied matrix function having many applications. The Frechet derivative of the matrix exponential describes the first-order sensitivity of $e^A$ to perturbations in $A$ and its norm determines a condition number for $e^A$. Among the numerous methods for computing $e^A$ the scaling and squaring method is the most widely used. We show that the implementation of the method in [N. J. Higham, The scaling and squaring method for the matrix exponential revisited, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 1179-1193] can be extended to compute both $e^A$ and the Frechet derivative at $A$ in the direction $E$, denoted by $L(A,E)$, at a cost about three times that for computing $e^A$ alone. The algorithm is derived from the scaling and squaring method by differentiating the Pade approximants and the squaring recurrence, reusing quantities computed during the evaluation of the Pade approximant, and intertwining the recurrences in the squaring phase. To guide the choice of algorithmic parameters, an extension of the existing backward error analysis for the scaling and squaring method is developed which shows that, modulo rounding errors, the approximations obtained are $e^{A+\Delta A}$ and $L(A+\Delta A,E+\Delta E)$, with the same $\Delta A$ in both cases, and with computable bounds on $\|\Delta A\|$ and $\|\Delta E\|$. The algorithm for $L(A,E)$ is used to develop an algorithm that computes $e^A$ together with an estimate of its condition number. In addition to results specific to the exponential, we develop some results and techniques for arbitrary functions. We show how a matrix iteration for $f(A)$ yields an iteration for the Frechet derivative and show how to efficiently compute the Frechet derivative of a power series. We also show that a matrix polynomial and its Frechet derivative can be evaluated at a cost at most three times that of computing the polynomial itself and give a general framework for evaluating a matrix function and its Frechet derivative via Pade approximation.