矩阵多项式的有效计算外文翻译资料

英语原文共 22 页，剩余内容已隐藏，支付完成后下载完整资料

矩阵多项式的有效计算

J. Sastre

瓦伦西亚理工大学电信与多媒体应用研究所, 西班牙 瓦伦西亚 46022

摘要：本文提出了一种新的计算矩阵多项式的方法，比现有的Paterson-Stockmeyer方法更有效。本文还给出了矩阵指数和矩阵余弦等矩阵函数的泰勒多项式近似的应用实例。我们把它们的效率与一般多项式和常规近似等现有最好计算方案的效率进行了比较，也与最近基于混合有理和多项式近似的方法进行了比较。多年来，Paterson-Stockmeyer方法一直被认为是计算矩阵多项式最有效的通用方法。我们将在本文中证明这个说法不再准确。而且，多年来有理近似被认为比多项式近似更有效，尽管最近已经被证实在矩阵指数和矩阵余弦的计算中通常不是这样。在本文中我们证明了，实际上多项式近似提供了比基于矩阵乘法的， 相同成本合理近似的最先进计算方法更高的近似阶数。

关键词：矩阵，多项式，合理的，混合有理和多项式，近似，计算矩阵函数

Efficient evaluation of matrix polynomials

J. Sastre

Instituto de Telecomunicaciones y Aplicaciones Multimedia, Universitat Politegrave;cnica de Valegrave;ncia, Camino de Vera s/n, Valencia, 46022 Spain

abstract：This paper presents a new family of methods for evaluating matrix polynomials more efficiently than the state-of-the-art Paterson–Stockmeyer method. Examples of the application of the methods to the Taylor polynomial approximation of ma- trix functions like the matrix exponential and matrix cosine are given. Their efficiency is compared with that of the best existing evaluation schemes for general polynomial and ra- tional approximations, and also with a recent method based on mixed rational and polynomial approximants. For many years, the Paterson–Stockmeyer method has been considered the most efficient general method for the evaluation of matrix polynomials. In this paper we show that this statement is no longer true. Moreover, for many years rational approximations have been considered more efficient than polynomial approx- imations, although recently it has been shown that often this is not the case in the computation of the matrix exponential and matrix cosine. In this paper we show that in fact polyno- mial approximations provide a higher order of approximation than the state-of-the-art computational methods for rational approximations for the same cost in terms of matrix products.

Keywords: Matrix;
Polynomial;
Rational;
Mixed rational and polynomial; Approximation; Computation; Matrix function

1 介绍：

在本文中，我们提出了一种新的计算矩阵多项式的方法，比采用Horner方法[1], [2, Sec. 4.2]的最先进的Paterson-Stockmeyer方法更有效。我们提出的这个方法可用于高效地计算矩阵函数的泰勒多项式近似。矩阵函数的计算在许多科学区域都有应用，且已有许多算法被提出[2,3]。在所有的矩阵函数中，矩阵指数已引起了特别的关注，具体参见[4-6]及其中的参考文献；还有最近关于矩阵余弦的内容，参见[7,8]及其中的参考文献。计算矩阵函数主要运用如或Chebyshev近似，多项式近似如Taylor近似，相似变换和矩阵迭代[2] 这样基于有理近似的方法。此外，[9]中提出了一种基于混合有理和多项式近似的新近似。

对于矩阵指数和余弦，最近已被证明，使用Horner和Paterson-Stockmeyer方法[1]，[2，Sec. 4.2]多项式近似可能比有理近似更有效[6,8]。在本文中我们表明，以同样的计算成本计算多项式和有理近似，使用本文提出的矩阵多项式计算方法，比使用现有的先进方法得到的多项式近似更精确。此外我们发现，在某些情况下，新方法比最近提出的混合有理和多项式近似方法更有效，且我们给出了矩阵指数和矩阵余弦计算的例子。

在整篇论文中，表示不小于的最小整数，表示不超过的最大整数，表示正整数的集合，和表示复矩阵和实矩阵的集合大小为，分别表示两个集合的单位矩阵，分别表示有理函数的空间，分子和分母最多分别为和。

注意矩阵有理近似中矩阵求逆的乘法被计算为多个右侧线性系统的解。因此，计算多项式和有理近似的成本，将以用表示的矩阵乘积的数量和多个右侧线性系统的解的代价来表示，其中矩阵和是的，用表示。从[10, App. C]看来，参阅[9, p. 11940]：

， (1)

全文规划如下。第2节回顾了有效Taylor、和一般矩阵函数的混合有理及多项式近似的一些结果。第3节介绍新的矩阵多项式计算方法，给出计算矩阵指数和矩阵余弦的例子。第4部分将新技术与最先进的有效计算方案相比较，用于多项式有理以及混合有理和多项式近似。第5节给出的矩阵指数计算的例子甚至比第3节给出的更有效，这显示了计算矩阵多项式的更一般的公式。最后，第6节给出结论。

2 多项式，有理，和混合有理及多项式近似

本节总结了Taylor，，和混合有理及多项式近似的计算成本的一些成果[9]。

2.1 泰勒近似矩阵函数

如果是根据定理4.7由泰勒级数定义的矩阵函数[2, p. 76]，其中是复方阵，那么我们将用表示由的阶的截断泰勒级数定义的矩阵多项式。

对于标量，它遵循关于原点的

, (2)

并且从现在开始，我们将把表示为泰勒近似的阶数。在文献中，计算矩阵多项式

, (3)

的最有效的方法,是由

， (4)

给出的，Horner和Paterson-Stockmeyer方法[1]的组合,其中整数除以和矩阵幂，事先被计算和存储。

表1

表1给出了对于给定数量的中的矩阵乘积，对于使用Paterson-Stockmeyer方法可以获得的最大值，对应于和。对于中的值，由表示的计算成本（4）由下式给出[9, Eq. (6)]：

. (5)

表1以矩阵乘积的形式列出了计算（4）中前11个值的成本。对于阶，我们使用（4）取，并在（4）中为设置系数，计算成本与计算相同。请注意，由于多项式的计算方式，使用（4）的成本低于Paterson-Stockmeyer在[2, Sec. 4.2]中的实施成本（比较（5）和[2, Eq. (4.3)]）。

矩阵指数是目前研究最多的矩阵函数[ 4 ]，[2, Chap. 10]。对于，的矩阵指数可由泰勒级数得出：

. (6)

定义：最近受到关注的另一个矩阵函数是矩阵余弦,它可以通过其泰勒级数

. (7)

来类似地定义。最近已经提出了几种基于泰勒近似的，计算矩阵指数和余弦[6,8]的有效算法。

2.2 矩阵函数的近似

有理标量函数是标量函数的近似，如果，并且

. (8)

从现在起，将表示的泰勒级数关于与原点的最后一项的阶数，即，并且我们将称为近似的阶。

表2

表2 (见[9, 表2])示出了对于给定数量的中的矩阵乘积可以获得的的最大值，由表示，以及相应的计算成本，由表示。式

, (9)

其中取或除以并给出较小的任何值。表2还给出了近似的相应阶，如果其为给定函数的近似，即。

最后，值得注意的是，对于给定和，近似可能不存在。此外，当计算给定方阵的函数的有理近似时，我们必须证明矩阵是非奇异的，并且为了精确计算，它需要是条件良好的。多项式近似不是这样，因为它们不需要矩阵求逆。

2.3 混合有理多项式近似

对于方阵，[ 9 ]中提出的方法是基于使用这种类型的混合有理近似和多项式近似的聚合

， （10）

其中，是至多次的多项式，是至多次的多项式，其中。注意，如果，我们认为没有有理部分。在[9, Sec. 4]中给出了一种由有理近似得到的方法。与有理近似类似，矩阵求逆的每次乘法都是通过得到多右侧线性系统的解求得的。因此在计算时，验证矩阵是非奇异且条件良好的是很重要的。计算总成本( 10 )由表示，见[ 9, Sec. 5 ]

. (11)

注意，对于近似（10），意在再现给定函数的泰勒级数的第一项的情况，它等价于近似。然后标量的只要存在，就满足<!--

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[23885]，资料为PDF文档或Word文档，PDF文档可免费转换为Word