Show simple item record

dc.contributor.authorHigham, Nicholas J.en_US
dc.description.abstractIf $\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.en_US
dc.format.extent1184166 bytes
dc.format.extent243042 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleBounding the Error in Gaussian Elimination for Tridiagonal Systemsen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record