The Distribution of Condition Numbers of Rational Data of Bounded Bit Length
The Distribution of Condition Numbers of Rational Data of Bounded Bit Length
复制标题
有界位长有理数据的条件数分布
DOI：
--
复制
发表时间：
2002
影响因子：
3
通讯作者：
Jorge San Martín
中科院分区：
文献类型：
--
作者：
D. Castro;J. L. Montaña;L. M. Pardo;Jorge San Martín
摘要我们证明，相对于数值分析的条件数量的概率分布，有界输入长度的合理数据（在经典的H. Weyl的经典意义上）。例如，具有多元多项式方程的系统的条件号。 ）≤WN5/2至少1-2W-1。我们应用这些技术来估计需要编写有界输入长度的多种多项式方程系统的近似零所需的精度（分母数量）的概率分布。
Abstract We prove that rational data of bounded input length are uniformly distributed (in the classical sense of H. Weyl, in [42]) with respect to the probability distribution of condition numbers of numerical analysis. We deal both with condition numbers of linear algebra and with condition numbers for systems of multivariate polynomial equations. For instance, we prove that for a randomly chosen n imes n rational matrix M of bit length O(n4log n) + log w , the condition number k(M) satisfies k(M) ≤ w n5/2 with probability at least 1-2w-1 . Similar estimates are established for the condition number μ_ norm of M. Shub and S. Smale when applied to systems of multivariate homogeneous polynomial equations of bounded input length. Finally, we apply these techniques to estimate the probability distribution of the precision (number of bits of the denominator) required to write approximate zeros of systems of multivariate polynomial equations of bounded input length.