Backward Error of Polynomial Eigenproblems Solved by Linearization
Backward Error of Polynomial Eigenproblems Solved by Linearization
复制标题
DOI：
10.1137/060663738
复制
发表时间：
2007-11
期刊：
影响因子：
--
通讯作者：
N. Higham;Ren-Cang Li;F. Tisseur
中科院分区：
文献类型：
--
作者：
N. Higham;Ren-Cang Li;F. Tisseur
解决多项式特征值问题$ p（\ lambda）x =（\ sum_ {i = 0}^m \ l^i a_i）x = 0 $ in $ n \ times n $ n $矩阵$ a_i $是线性化以产生更大的订单铅笔$ l（\ lambda）= \ lambda x + y $，其特征系统是通过任何方法找到广义本本特征问题。对于给定的多项式$ p $，存在无限的许多线性化$ l $，通过线性化计算的$ P $的近似本征可能会有很大变化的向后错误。我们表明，如果可以找到与$ l $与$ p $相关的某个单方面分解，那么一个简单的公式允许从$ l $的$ p $中恢复$ p $的正确特征，以及近似eigenpair的向后错误$ p $可以根据$ l $的相应大约eigenpair的向后错误来限制。类似的分解对左侧特征向量也具有相同的影响。我们使用此技术仅取决于伴侣铅笔的$ a_i $的规范以及向量空间$ \ mathbb {dl}（P）梅尔曼。在所有情况下，都确定了足够的条件，对于$ p $的最佳向后错误。这些结果被证明与Higham，Mackey和Tisseur的结果完全一致，以$ p $的线性化条件。这项工作的其他贡献是伴侣铅笔的块缩放，从而提高了向后误差边界。界限适用于结构化多项式的某些结构性线性化的证明；专门针对二次情况的后退误差界限，包括对Fan，Lin和van Dooren最近提出的缩放缩放的益处的分析。此处的结果对适用于$ l $的方法的稳定性或方法是直接的还是迭代的。
The most widely used approach for solving the polynomial eigenvalue problem $P(\lambda)x = (\sum_{i=0}^m \l^i A_i) x = 0$ in $n\times n$ matrices $A_i$ is to linearize to produce a larger order pencil $L(\lambda) = \lambda X + Y$, whose eigensystem is then found by any method for generalized eigenproblems. For a given polynomial $P$, infinitely many linearizations $L$ exist and approximate eigenpairs of $P$ computed via linearization can have widely varying backward errors. We show that if a certain one-sided factorization relating $L$ to $P$ can be found then a simple formula permits recovery of right eigenvectors of $P$ from those of $L$, and the backward error of an approximate eigenpair of $P$ can be bounded in terms of the backward error for the corresponding approximate eigenpair of $L$. A similar factorization has the same implications for left eigenvectors. We use this technique to derive backward error bounds depending only on the norms of the $A_i$ for the companion pencils and for the vector space $\mathbb{DL}(P)$ of pencils recently identified by Mackey, Mackey, Mehl, and Mehrmann. In all cases, sufficient conditions are identified for an optimal backward error for $P$. These results are shown to be entirely consistent with those of Higham, Mackey, and Tisseur on the conditioning of linearizations of $P$. Other contributions of this work are a block scaling of the companion pencils that yields improved backward error bounds; a demonstration that the bounds are applicable to certain structured linearizations of structured polynomials; and backward error bounds specialized to the quadratic case, including analysis of the benefits of a scaling recently proposed by Fan, Lin, and Van Dooren. The results herein make no assumptions on the stability of the method applied to $L$ or whether the method is direct or iterative.