Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices |
| |
Authors: | Froilán M Dopico Plamen Koev |
| |
Institution: | 1.Instituto de Ciencias Matemáticas CSIC-UAM-UC3M-UCM and Departamento de Matemáticas,Universidad Carlos III de Madrid,Leganés,Spain;2.Department of Mathematics,San Jose State University,San Jose,USA |
| |
Abstract: | 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
3
u, 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” ||A||M = maxij |aij|{\|A\|_M = \max_{ij} |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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|