Stability and sensitivity of tridiagonal LU factorization without pivoting (Q2566632)

The authors present an error analysis of the LU decomposition of tridiagonal matrices. For this purpose the effect of perturbations on the factors of the LU decomposition is investigated. The sensitivity of the LU factorization to two types of perturbations is described by suitably defined condition numbers. Thereby condition numbers that are defined via matrix components are considered as well as condition numbers defined by matrix norms. For the condition numbers under consideration explicit expressions are derived. Furthermore it is shown that the condition numbers, associated to a perturbation type, are of similar magnitude. Explicit expressions for the costs of the computation of condition numbers in terms of floating point operations are given. The results are applied to show the forward stability of the LU algorithm. The stability of the LU factorization in the `mixed forward-backward' sense is also shown.