论文标题
局部枢纽的高斯消除平均分析
Average-case analysis of the Gaussian Elimination with Partial Pivoting
论文作者
论文摘要
局部枢轴（GEPP）的高斯消除是一种用于求解线性方程系统的经典算法。尽管在特定情况下，由于圆形误差而导致的GEPP中的精度丧失可能非常重要，但经验证据强烈表明，对于{\ IT典型}方形系数矩阵，GEPP在数值上是稳定的。我们通过表明，鉴于随机的$ n \ times n $ n $标准高斯系数矩阵$ a $ a $，我们获得了这种现象的（部分）理论理由，而高斯消除的{\ it增长因子}，部分枢轴的{\ it增长因子}最多是多项函数的$ n $，含有接近$ n $。这意味着，使用GEPP是$ m+o（\ log n）$的概率接近一个精度的概率，足以求解$ ax = b $至$ m $的精度，这可以改善较早的$ m+m+m+o（\ log^2 n）$，我们认为这是最佳的命令。我们进一步提供了可用于支持经验观察的生长因子的尾巴估计值，即GEPP比没有枢轴的高斯消除更稳定。
The Gaussian Elimination with Partial Pivoting (GEPP) is a classical algorithm for solving systems of linear equations. Although in specific cases the loss of precision in GEPP due to roundoff errors can be very significant, empirical evidence strongly suggests that for a {\it typical} square coefficient matrix, GEPP is numerically stable. We obtain a (partial) theoretical justification of this phenomenon by showing that, given the random $n\times n$ standard Gaussian coefficient matrix $A$, the {\it growth factor} of the Gaussian Elimination with Partial Pivoting is at most polynomially large in $n$ with probability close to one. This implies that with probability close to one the number of bits of precision sufficient to solve $Ax = b$ to $m$ bits of accuracy using GEPP is $m+O(\log n)$, which improves an earlier estimate $m+O(\log^2 n)$ of Sankar, and which we conjecture to be optimal by the order of magnitude. We further provide tail estimates of the growth factor which can be used to support the empirical observation that GEPP is more stable than the Gaussian Elimination with no pivoting.
