dc.contributor.author Higham, Nicholas J. en_US dc.date.accessioned 2007-04-23T17:35:32Z dc.date.available 2007-04-23T17:35:32Z dc.date.issued 1988-12 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-953 en_US dc.identifier.uri https://hdl.handle.net/1813/6793 dc.description.abstract 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. en_US dc.format.extent 1184166 bytes dc.format.extent 243042 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title Bounding the Error in Gaussian Elimination for Tridiagonal Systems en_US dc.type technical report en_US
﻿