Bounding the Error in Gaussian Eimination for Tridiagonal Systems
Nicholas John Higham · SIAM Journal on Matrix Analysis and Applications · 1990
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 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 matrices the appropriate forward error bound involves Skeel’s condition number cond $(A,x)$, which, it is shown, can be computed exactly in $O(n)$ operations. For diagonally dominant tridiagonal A the same type of backward error result holds, and the author obtains a useful upper bound for cond $(A,x)$ that can be computed in $O(n)$ operations. Error bounds and their computation for general tridiagonal matrices are discussed also.