Geodesic
Stochastic Matrices and Lp Norms : New Algorithms for Solving Ill-conditioned Linear Systems of Equations
Riadh Zorgati1, 2 ; Wim van Ackooij2 ; Marc Lambert1
1Supelec, Plateau de Moulon, 3 rue Joliot-Curie, F-91192 Gif-sur-Yvette Cedex FRANCE
2EDF R&D. 1, avenue du Général de Gaulle, F-92141 Clamart Cedex FRANCE
ESAIM. Proceedings, Tome 18 (2007), pp. 70-86
Cet article a éte moissonné depuis la source EDP Sciences

Voir la notice de l'article

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.
DOI : 10.1051/proc:071807

Riadh Zorgati  1 , 2   ; Wim van Ackooij  2   ; Marc Lambert  1

1 Supelec, Plateau de Moulon, 3 rue Joliot-Curie, F-91192 Gif-sur-Yvette Cedex FRANCE
2 EDF R&D. 1, avenue du Général de Gaulle, F-92141 Clamart Cedex FRANCE 
@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 :