On the uniform distribution of rational inputs with respect to condition numbers of Numerical Analysis
D. Castro, J.L. Montana, L. M. Pardo, J. San Martin
我们表明,边界输入长度的理性数据与数值分析的条件数一致分布。 我们既处理线性代数的条件数,也处理多变量多项式方程系统的条件号。 例如,我们显示对于任何 w>1 和任何 n× n 的位长度为 O(n^4log n) + log w 的 n× n 的均值矩阵 M,条件号 k(M) 满足 k(M) ≤ w n^5/2 的概率至少为 1-2w^-1。 对 M 的条件号 μ_norm 也有类似的估计。 舒布和S。 当应用于多变量均匀多项式方程的有界输入长度的系统时,Smale。 最后,我们应用这些技术来显示精度的概率分布(分母的比特数),以写下多变量多项式方程的近似值系统的近似值,输入长度。
We show that rational data of bounded input length are uniformly distributed with respect to 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 show that for any w>1 and for any n× n rational matrix M of bit length O(n^4log n) + log w, the condition number k(M) satisfies k(M) ≤ w n^5/2 with probability at least 1-2w^-1. Similar estimates are shown for the cond...
