Accurate solutions of diagonally dominant tridiagonal linear systems (Q466809)

Classic perturbation results imply that for ill-conditioned matrices there is no guarantee of full accuracy. Accuracy can increase if a special structure of the matrix is exploit. The authors are concerned with accurate algorithms for the solution of the diagonally dominant tridiagonal system of linear algebraic equations \(Ax=b\). Throughout the paper, they assume that all diagonal entries of a nonsingular row diagonally dominant matrix \(A\) are positive. They also suppose that the matrix \(A=(a_{ij}) \in \mathbb{R}^{n \times n}\) is re-parametrized as \(A=(A_D,v)\), where \(A_D\) is the matrix whose off-diagonal elements are the same as those of \(A\) and whose diagonal entries are zero, and \(v=(v_1,v_2, \dots, v_n) \geq 0\) is defined as \[ v_i= a_{ii}- \sum_{j \neq i} |a_{ij}|, \quad i=1,2,\dots,n. \] The authors present Higham's conjecture for LU factorization of diagonally dominant tridiagonal matrices. They prove this conjecture for a nonsingular row diagonally dominant tridiagonal matrix \(A\in \mathbb{R}^{n \times n}\) under the assumption that \(a_{ii} >0\) for all \(i\). They say that this assumption is not a restriction and Higham's conjecture is true. In particular they proved that in this case the upper bound for \(\text{cond(A,x)}\) does't depend on \(n\). The authors show how to solve accurately a diagonally dominant tridiagonal linear system \(Ax=b\) provided that the parametrization \(A=(A_D,v)\) is given accurately. They give a corresponding algorithm and perform the error analysis. The algorithm is based on recursively repeating the process on the Schur complements. Numerical examples computed in MATLAB are given in the last section of the paper.