Reliable solution of bidiagonal systems with applications (Q1307236)

The authors are interested in solution of linear systems \(Ax=f\) by direct methods with little or no pivoting when the matrix \(A\) has large condition number. In this circumstance, roundoff errors can grow as the solution method progresses. \textit{R. D. Skeel} has shown [J. Assoc. Comput. Mach. 26, 494-526 (1979; Zbl 0435.65035)] that solution error can be bounded when \(\theta C(A)<1\), where \(\theta\) represents machine precision, and \(C(A)\) the condition number of A. The authors prove similar bounds without the restriction that the condition number be smaller than the inverse of the machine precision. The authors define a ``componentwise forward stability factor'' that amounts to the \(\sup\) of the componentwise relative error as the matrix \(A\) and vector \(f\) are perturbed in an admissible manner. If a component of the solution is very small, a similar definition using the max norm can be employed. This forward stability factor can be estimated without explicit reference to the condition number, and the authors prove both lower and upper bounds in the case of tridiagnonal and bidiagonal matrices. Moreover, they present an efficient algorithm for estimating the forward stability factor for bidiagonal systems. This algorithm itself is shown to be insensitive to rounding errors. In a companion paper, the authors show that Gaussian elimination without pivoting can be reliably applied to systems so long as the resulting reduced bidiagonal systems have small forward stability factor. A large sample of numerical examples is presented for tridiagonal systems of varying sizes. For each, both the componentwise and norm forward stability factors are computed during a Gaussian elimination process without pivoting. The small forward stability factors confirm that the computed solutions are reliable.