Probabilistic analysis of Gaussian elimination without pivoting

M.-C. Yeung, T.F. Chan

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

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.
Original languageEnglish
Pages (from-to)499-517
Number of pages19
JournalSIAM Journal on Matrix Analysis and Applications
Volume18
Issue number2
DOIs
StatePublished - 1997
Externally publishedYes

Fingerprint

Dive into the research topics of 'Probabilistic analysis of Gaussian elimination without pivoting'. Together they form a unique fingerprint.

Cite this