Bounding the Error in Gaussian Elimination for Tridiagonal Systems

If $\hat{x}$ is the computed solution to a tridiagonal system $Ax = b$ obtained by Gaussian elimination, what is the "best" bound available for the error $x - \hat{x}$ and how can it be computed efficiently? This question is answered using backward error analysis, perturbation theory, and properties of the $LU$ factorization of $A$. For three practically important classes of tridiagonal matrix, those that are symmetric positive definite, totally nonnegative, or are $M$-matrices, it is shown that $(A + E)\hat{x} = b$ where the backward error matrix $E$ is small componentwise relative to $A$. For these classes of matrix the appropriate forward error bound involves Skeel's condition number cond$(A, x)$, which we show can be computed exactly in $O(n)$ operations. For diagonally dominant tridiagonal $A$ the same type of backward error result holds and we obtain a useful upper bound for cond$(A, x)$ which can be computed in $O(n)$ operations. We also discuss error bounds and their computation for general tridiagonal matrices