Stochastic Matrices and Lp Norms : New Algorithms for Solving Ill-conditioned Linear Systems of Equations
ESAIM. Proceedings, Tome 18 (2007), pp. 70-86
Cet article a éte moissonné depuis la source EDP Sciences
We propose new iterative algorithms for solving a system of linear equations, possibly singular and inconsistent, presenting outstanding performances regarding ill-conditioning and error propagation. The basis of our approach is constructing with the l1 norm, a preconditioning matrix C (an approximation of a generalized inverse of the matrix) such that the preconditioned matrix CA is stochastic. This property allows us to retrieve, in an original way, the Schultz-Hotelling-Bodewig's algorithm of iterative refinement of the approximate inverse of a matrix. The approach, valid for non-negative matrices, is then generalized to any complex, rectangular matrix. We are then able to compute a generalized inverse of any matrix and this inverse is fit for use in classical solving schemes such as : Richardson-Tanabe, Schultz-Hotelling-Bodewig, preconditioned conjugate gradients and also in the Kaczmarz scheme (that we have generalized using lp norms). Regarding the obtained results on pathological well-known test-cases such as Hilbert and Nakasaka matrices, some of the proposed algorithms are empirically shown to be more efficient than the known classical techniques.
Affiliations des auteurs :
Riadh Zorgati 1, 2 ; Wim van Ackooij 2 ; Marc Lambert 1
@article{EP_2007_18_a7,
author = {Riadh Zorgati and Wim van Ackooij and Marc Lambert},
title = {Stochastic {Matrices} and {Lp} {Norms} : {New} {Algorithms} for {Solving} {Ill-conditioned} {Linear} {Systems} of {Equations}},
journal = {ESAIM. Proceedings},
pages = {70--86},
year = {2007},
volume = {18},
doi = {10.1051/proc:071807},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/proc:071807/}
}
TY - JOUR AU - Riadh Zorgati AU - Wim van Ackooij AU - Marc Lambert TI - Stochastic Matrices and Lp Norms : New Algorithms for Solving Ill-conditioned Linear Systems of Equations JO - ESAIM. Proceedings PY - 2007 SP - 70 EP - 86 VL - 18 UR - http://geodesic.mathdoc.fr/articles/10.1051/proc:071807/ DO - 10.1051/proc:071807 LA - en ID - EP_2007_18_a7 ER -
%0 Journal Article %A Riadh Zorgati %A Wim van Ackooij %A Marc Lambert %T Stochastic Matrices and Lp Norms : New Algorithms for Solving Ill-conditioned Linear Systems of Equations %J ESAIM. Proceedings %D 2007 %P 70-86 %V 18 %U http://geodesic.mathdoc.fr/articles/10.1051/proc:071807/ %R 10.1051/proc:071807 %G en %F EP_2007_18_a7
Riadh Zorgati; Wim van Ackooij; Marc Lambert. Stochastic Matrices and Lp Norms : New Algorithms for Solving Ill-conditioned Linear Systems of Equations. ESAIM. Proceedings, Tome 18 (2007), pp. 70-86. doi: 10.1051/proc:071807
Cité par Sources :