Show simple item record

dc.contributor.authorHigham, Nicholas J.en_US
dc.date.accessioned2007-04-23T17:35:32Z
dc.date.available2007-04-23T17:35:32Z
dc.date.issued1988-12en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-953en_US
dc.identifier.urihttps://hdl.handle.net/1813/6793
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.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
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

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics