We present a structured perturbation theory for the LDU factorization of (row) diagonally dominant matrices and we use this theory to prove that a recent algorithm of Ye (Math Comp 77(264):2195-2230, 2008) computes the L, D and U factors of these matrices with relative errors less than 14n~3u, where u is the unit roundoff and n × n is the size of the matrix. The relative errors for D are componentwise and for L and U are normwise with respect the "max norm" {double pipe}A{double pipe}_M = max_(ij){pipe}a_(ij). These error bounds guarantee that for any diagonally dominant matrix A we can compute accurately its singular value decomposition and the solution of the linear system Ax = b for most vectors b, independently of the magnitude of the traditional condition number of A and in O(n~3) flops.
展开▼
