ON CONDITION NUMBERS AND THE DISTANCE TO THE NEAREST ILL-POSED PROBLEM
ON CONDITION NUMBERS AND THE DISTANCE TO THE NEAREST ILL-POSED PROBLEM
复制标题
DOI：
10.1007/bf01400115
复制
发表时间：
1987-01-01
影响因子：
2.1
通讯作者：
DEMMEL, JW
中科院分区：
文献类型：
--
作者：
DEMMEL, JW
问题的条件数衡量了答案对输入的微小变化的敏感性。如果问题的条件数是无限的，我们称该问题为不适定问题。结果表明，对于许多数值分析问题，问题的条件数与该问题到不适定问题的最短距离之间存在一种简单的关系：最短距离与条件数的倒数成正比(或受条件数的倒数的限制)。这适用于线性控制系统中的矩阵求逆、计算特征值和特征向量、寻找多项式的零点和极点配置。在本文中，我们通过证明在所有这些情况下条件数κ满足一个或两个微分不等式·κ2≤∥Dκ∥≤M·κ2来解释这一现象，其中‖Dκ‖是κ的梯度范数。‖Dκ‖上的下界导致距离的上界1/mκ(X)。从X到最近的不适定问题，并且‖Dκ‖上的上界导致距离的下界1/(Mκ(X))。这种方法的吸引力在于它使用局部信息(条件数的梯度)来回答一个全局问题：距离最近的不适定问题有多远？上面的微分不等式也有一个简单的解释：它们意味着计算一个问题的条件数大约和计算问题本身的解一样难。除了得到矩阵求逆、特征分解和多项式求零的许多最好的界外，我们还得到了到多个零点最近的多项式的距离的新界和一个关于极点配置的新的扰动结果。
The condition number of a problem measures the sensitivity of the answer to small changes in the input. We call the problem ill-posed if its condition number is infinite. It turns out that for many problems of numerical analysis, there is a simple relationship between the condition number of a problem and the shortest distance from that problem to an ill-posed one: the shortest distance is proportional to the reciprocal of the condition number (or bounded by the reciprocal of the condition number). This is true for matrix inversion, computing eigenvalues and eigenvectors, finding zeros of polynomials, and pole assignment in linear control systems. In this paper we explain this phenomenon by showing that in all these cases, the condition number κ satisfies one or both of the diffrential inequalitiesm·κ2≤∥Dκ∥≤M·κ2, where ‖Dκ‖ is the norm of the gradient of κ. The lower bound on ‖Dκ‖ leads to an upper bound 1/mκ(x) on the distance. fromxto the nearest ill-posed problem, and the upper bound on ‖Dκ‖ leads to a lower bound 1/(Mκ(X)) on the distance. The attraction of this approach is that it uses local information (the gradient of a condition number) to answer a global question: how far away is the nearest ill-posed problem? The above differential inequalities also have a simple interpretation: they imply that computing the condition number of a problem is approximately as hard as computing the solution of the problem itself. In addition to deriving many of the best known bounds for matrix inversion, eigendecompositions and polynomial zero finding, we derive new bounds on the distance to the nearest polynomial with multiple zeros and a new perturbation result on pole assignment.