IIT Home Page CNR Home Page

Stability of Levinson algorithm for Toeplitz-like Systems

Numerical stability of the Levinson algorithm, generalized for Toeplitz-like systems, is studied. Arguments based on the analytic results of an error analysis for °oating point arithmetic produce an upper bound on the norm of the residual vector, which grows exponentially with respect to the size of the problem. The base of such an exponential function can be small for diagonally dominant Toeplitz-like matrices. Numerical experiments show that, for these matrices, Gaussian elimination by row and the Levinson algorithm have residuals of the same order of magnitude. As expected, the empirical results poNumerical stability of the Levinson algorithm, generalized for Toeplitz-like systems, is studied. Arguments based on the analytic results of an error analysis for °oating point arithmetic produce an upper bound on the norm of the residual vector, which grows exponentially with respect to the size of the problem. The base of such an exponential function can be small for diagonally dominant Toeplitz-like matrices. Numerical experiments show that, for these matrices, Gaussian elimination by row and the Levinson algorithm have residuals of the same order of magnitude. As expected, the empirical results point out that the theoretical bound is too pessimistic. 


SIAM. J. Matrix Anal. & Appl. , 2010

Autori esterni: Grazia Lotti (Universita' di Parma ), Ornella Menchi (Universita' di Pisa )
Autori IIT:

Tipo: Articoli su riviste ISI
Area di disciplina: Mathematics

File: levinson.pdf
Da pagina 2531 a pagina 2552

Attività: Metodi numerici per problemi di grandi dimensioni