Probabilistic analysis of Gaussian elimination without pivoting

The numerical instability of Gaussian elimination is proportional to the size of the L and U factors that it produces. The worst-case bounds are well known. For the case without pivoting, breakdowns can occur and it is not possible to provide a priori bounds for L and U. For the partial pivoting case, the worst-case bound is O(2m), where m is the size of the system. Yet these worst-case bounds are seldom achieved, and in particular Gaussian elimination with partial pivoting is extremely stable in practice. Surprisingly, there has been relatively little theoretical study of the "average" case behavior. The purpose of our paper is to provide a probabilistic analysis of the case without pivoting. The distribution we use for the entries of A is the normal distribution with mean 0 and unit variance. We first derive the distributions of the entries of L and U. Based on this, we prove that the probability of the occurrence of a pivot less than ∈ in magnitude is O(∈). We also prove that the probabilities Prob(∥U∥∞/∥A∥∞ > m2,5) and Prob(∥L∥∞ > m3) decay algebraically to zero as m tends to infinity. Numerical experiments are presented to support the theoretical results.