American Institute of Mathematical Sciences

Advanced
2012, 2(4): 863-873. doi: 10.3934/naco.2012.2.863

On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems

Yanxing Cui 1, , Chuanlong Wang 2, and  Ruiping Wen 2,

1. 

Department of Mathematics, Changzhi University, Changzhi 046011, Shanxi Province, China
2. 

Department of Mathematics, Taiyuan Normal University, Taiyuan 030012, Shanxi Province, China, China

Received  January 2012 Revised  October 2012 Published  November 2012

In this paper, we present the generalized stationary and nonstationary multisplitting iterative methods for positive semidefinite linear systems. We study the convergence theories of new methods and show that the quotient convergence and convergence of stationary parallel multisplitting method are equivalent under a concise condition. Finally, we prove that the generalized nonstationary parallel multisplitting method is quotient convergence with general weighting matrices.
Keywords: Parallel Multisplitting, seminorm convergence, semidefinite matrix, convergence, quotient convergence..
Mathematics Subject Classification: 58F15, 58F1.
Citation: Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
References:
[1]

Z.-Z. Bai and D.-R. Wang, Generalized matrix multisplitting relaxation methods and their convergence, Numer. Math. J. Chinese Univ. (English Ser.), 2 (1993), 87-100.

[2]

Z.-Z. Bai, On the convergence of the generalized matrix multisplitting relaxed methods, Commun. Numer. Methods Engrg., 11 (1995), 363-371. doi: 10.1002/cnm.1640110410.

[3]

Z.-Z. Bai, J.-C. Sun and D.-R. Wang, A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations, Comput. Math. Appl., 32 (1996), 51-76. doi: 10.1016/S0898-1221(96)00207-6.

[4]

Z.-Z. Bai and C.-L. Wang, On the convergence of nonstationary multisplitting two-stage iteration methods for Hermitian positive definite linear systems, J. Comput. Appl. Math., 138 (2002), 287-296. doi: 10.1016/S0377-0427(01)00376-4.

[5]

Z.-Z. Bai, L. Wang and J.-Y. Yuan, Weak-convergence theory of quasi-nonnegative splittings for singular matrices, Appl. Numer. Math., 47 (2003), 75-89. doi: 10.1016/S0168-9274(03)00057-6.

[6]

A. Ben-Israel and T. N. E. Greville, "Generalized Inverses: Theory and Applications," Wiley, New York, 1974.

[7]

A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Science," Academic Press, New York, 1979.

[8]

Z. Cao and Z. Liu, Symmetric multisplitting of a symmetric positive definite matrix, Linear Algebra Appl., 285 (1998), 309-319. doi: 10.1016/S0024-3795(98)10151-9.

[9]

Z. Cao, On the convergence of nonstationary iterative methods for symmetric positive (semi)defnite systems, Appl. Numer. Math., 37 (2001), 319-330. doi: 10.1016/S0168-9274(00)00047-7.

[10]

Z. Cao, On the convergence of general stationary linear iterative methods for singular linear systems, SIAM J. Matrix Anal. Appl., 29 (2007), 1382-1388. doi: 10.1137/060671243.

[11]

Z. Cao, On the convergence of iterative methods for solving singular linear systems, J. Comput. Appl. Math., 145 (2002), 1-9. doi: 10.1016/S0377-0427(01)00531-3.

[12]

M. J. Castel, V. Migallón and J. Penadés, Convergence of non-stationary parallel multisplitting methods for hermitian positive definite matrices, Math. Comput., 67 (1998), 209-220. doi: 10.1090/S0025-5718-98-00893-X.

[13]

X. Cui, Y. Wei and N. Zhang, Quotient convergence and multisplitting methods for solving singular linear equations, Calcolo, 44 (2007), 21-31. doi: 10.1007/s10092-007-0127-y.

[14]

A. Frommer, R. Nabben and D. B.Szyld, Convergence of stationary iterative methods for hermitian semidefinite linear systems and applications to schwarz methods, SIAM J. Matrix Anal. Appl., 30 (2008), 925-938. doi: 10.1137/080714038.

[15]

H. B. Keller, On the solution of singular and semidefinite linear systems by iteration, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), 281-290.

[16]

Y.-J. Lee, J. Wu, Jinchao Xu and L. Zikatanov, On the convergence of iterative methods for semidefinite linear systems, SIAM J. Matrix Anal. Appl., 28 (2006), 634-641. doi: 10.1137/050644197.

[17]

L. Lin, Y. Wei and N. Zhang, Convergence and quotient convergence of iterative methods for solving singular linear equations with index one, Linear Algebra Appl., 430 (2009), 1665-1674. doi: 10.1016/j.laa.2008.06.019.

[18]

G. I. Marchuk and Y. Kuznetsov, "Iterative Methods and Quadratic Functionals," Science Press, Norvosibirsk, 1972 (in Russian).

[19]

V. Migallón, J. Penadés and D. B. Szyld, Nonstationary multisplittings with general weighting matrices, SIAM J. Matrix Anal. Appl., 22 (2001), 1089-1094. doi: 10.1137/S0895479800367038.

[20]

D. P. O'Leary and R. E. White, Multisplittings of matrices and parallel solution of linear systems, SIAM J. on Alg. and Disc. Meth., 6 (1985), 630-640. doi: 10.1137/0606062.

[21]

D. B. Szyld, Equivalence of conditions for convergence of iterative methods for singular equations, Numer. Linear Algebra Appl., 1 (1994), 151-154. doi: 10.1002/nla.1680010206.

[22]

R. S. Varga, "Matrix Iterative Analysis," 2nd edition, Springer, Berlin, Heidelberg, 2000. doi: 10.1007/978-3-642-05156-2.

[23]

C.-L. Wang, Nonstationary multisplitting with general weighting matrices for non-Hermitian positive definite systems, Appl. Math. Lett., 16 (2003), 919-924. doi: 10.1016/S0893-9659(03)90017-6.

[24]

D.-R. Wang and Z.-Z. Bai, Asynchronous parallel matrix multisplitting multiparameter relaxation methods, (Chinese) Numer. Math. J. Chinese Univ., 16 (1994), 107-115.

[25]

Y. Wei, Index splitting for the Drazin inverse and the singular linear system, Appl. Math. Comput., 95 (1998), 115-124. doi: 10.1016/S0096-3003(97)10098-4.

[26]

Y. Wei, Perturbation analysis of singular linear systems with index one, Int. J. Comput. Math., 74 (2000), 483-491. doi: 10.1080/00207160008804956.

[27]

J. Wu, Y.-J. Lee, J. Xu and Ludmil Zikatanov, Convergence analysis on iterative methods for semidefinite systems, J. Comput. Math., 26 (2008), 797-815.

[28]

D. M. Young, "Iterative Solution of Large Linear Systems," Academic Press, New York, 1971.

show all references

References:
[1]

Z.-Z. Bai and D.-R. Wang, Generalized matrix multisplitting relaxation methods and their convergence, Numer. Math. J. Chinese Univ. (English Ser.), 2 (1993), 87-100.

[2]

Z.-Z. Bai, On the convergence of the generalized matrix multisplitting relaxed methods, Commun. Numer. Methods Engrg., 11 (1995), 363-371. doi: 10.1002/cnm.1640110410.

[3]

Z.-Z. Bai, J.-C. Sun and D.-R. Wang, A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations, Comput. Math. Appl., 32 (1996), 51-76. doi: 10.1016/S0898-1221(96)00207-6.

[4]

Z.-Z. Bai and C.-L. Wang, On the convergence of nonstationary multisplitting two-stage iteration methods for Hermitian positive definite linear systems, J. Comput. Appl. Math., 138 (2002), 287-296. doi: 10.1016/S0377-0427(01)00376-4.

[5]

Z.-Z. Bai, L. Wang and J.-Y. Yuan, Weak-convergence theory of quasi-nonnegative splittings for singular matrices, Appl. Numer. Math., 47 (2003), 75-89. doi: 10.1016/S0168-9274(03)00057-6.

[6]

A. Ben-Israel and T. N. E. Greville, "Generalized Inverses: Theory and Applications," Wiley, New York, 1974.

[7]

A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Science," Academic Press, New York, 1979.

[8]

Z. Cao and Z. Liu, Symmetric multisplitting of a symmetric positive definite matrix, Linear Algebra Appl., 285 (1998), 309-319. doi: 10.1016/S0024-3795(98)10151-9.

[9]

Z. Cao, On the convergence of nonstationary iterative methods for symmetric positive (semi)defnite systems, Appl. Numer. Math., 37 (2001), 319-330. doi: 10.1016/S0168-9274(00)00047-7.

[10]

Z. Cao, On the convergence of general stationary linear iterative methods for singular linear systems, SIAM J. Matrix Anal. Appl., 29 (2007), 1382-1388. doi: 10.1137/060671243.

[11]

Z. Cao, On the convergence of iterative methods for solving singular linear systems, J. Comput. Appl. Math., 145 (2002), 1-9. doi: 10.1016/S0377-0427(01)00531-3.

[12]

M. J. Castel, V. Migallón and J. Penadés, Convergence of non-stationary parallel multisplitting methods for hermitian positive definite matrices, Math. Comput., 67 (1998), 209-220. doi: 10.1090/S0025-5718-98-00893-X.

[13]

X. Cui, Y. Wei and N. Zhang, Quotient convergence and multisplitting methods for solving singular linear equations, Calcolo, 44 (2007), 21-31. doi: 10.1007/s10092-007-0127-y.

[14]

A. Frommer, R. Nabben and D. B.Szyld, Convergence of stationary iterative methods for hermitian semidefinite linear systems and applications to schwarz methods, SIAM J. Matrix Anal. Appl., 30 (2008), 925-938. doi: 10.1137/080714038.

[15]

H. B. Keller, On the solution of singular and semidefinite linear systems by iteration, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), 281-290.

[16]

Y.-J. Lee, J. Wu, Jinchao Xu and L. Zikatanov, On the convergence of iterative methods for semidefinite linear systems, SIAM J. Matrix Anal. Appl., 28 (2006), 634-641. doi: 10.1137/050644197.

[17]

L. Lin, Y. Wei and N. Zhang, Convergence and quotient convergence of iterative methods for solving singular linear equations with index one, Linear Algebra Appl., 430 (2009), 1665-1674. doi: 10.1016/j.laa.2008.06.019.

[18]

G. I. Marchuk and Y. Kuznetsov, "Iterative Methods and Quadratic Functionals," Science Press, Norvosibirsk, 1972 (in Russian).

[19]

V. Migallón, J. Penadés and D. B. Szyld, Nonstationary multisplittings with general weighting matrices, SIAM J. Matrix Anal. Appl., 22 (2001), 1089-1094. doi: 10.1137/S0895479800367038.

[20]

D. P. O'Leary and R. E. White, Multisplittings of matrices and parallel solution of linear systems, SIAM J. on Alg. and Disc. Meth., 6 (1985), 630-640. doi: 10.1137/0606062.

[21]

D. B. Szyld, Equivalence of conditions for convergence of iterative methods for singular equations, Numer. Linear Algebra Appl., 1 (1994), 151-154. doi: 10.1002/nla.1680010206.

[22]

R. S. Varga, "Matrix Iterative Analysis," 2nd edition, Springer, Berlin, Heidelberg, 2000. doi: 10.1007/978-3-642-05156-2.

[23]

C.-L. Wang, Nonstationary multisplitting with general weighting matrices for non-Hermitian positive definite systems, Appl. Math. Lett., 16 (2003), 919-924. doi: 10.1016/S0893-9659(03)90017-6.

[24]

D.-R. Wang and Z.-Z. Bai, Asynchronous parallel matrix multisplitting multiparameter relaxation methods, (Chinese) Numer. Math. J. Chinese Univ., 16 (1994), 107-115.

[25]

Y. Wei, Index splitting for the Drazin inverse and the singular linear system, Appl. Math. Comput., 95 (1998), 115-124. doi: 10.1016/S0096-3003(97)10098-4.

[26]

Y. Wei, Perturbation analysis of singular linear systems with index one, Int. J. Comput. Math., 74 (2000), 483-491. doi: 10.1080/00207160008804956.

[27]

J. Wu, Y.-J. Lee, J. Xu and Ludmil Zikatanov, Convergence analysis on iterative methods for semidefinite systems, J. Comput. Math., 26 (2008), 797-815.

[28]

D. M. Young, "Iterative Solution of Large Linear Systems," Academic Press, New York, 1971.

[1]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023
[2]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[3]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial and Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[4]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[5]

James Broda, Alexander Grigo, Nikola P. Petrov. Convergence rates for semistochastic processes. Discrete and Continuous Dynamical Systems - B, 2019, 24 (1) : 109-125. doi: 10.3934/dcdsb.2019001
[6]

Xiaoxue Gong, Ying Xu, Vinay Mahadeo, Tulin Kaman, Johan Larsson, James Glimm. Mesh convergence for turbulent combustion. Discrete and Continuous Dynamical Systems, 2016, 36 (8) : 4383-4402. doi: 10.3934/dcds.2016.36.4383
[7]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete and Continuous Dynamical Systems, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
[8]

Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61
[9]

Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems and Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030
[10]

Jacek Banasiak, Amartya Goswami. Singularly perturbed population models with reducible migration matrix 1. Sova-Kurtz theorem and the convergence to the aggregated model. Discrete and Continuous Dynamical Systems, 2015, 35 (2) : 617-635. doi: 10.3934/dcds.2015.35.617
[11]

Micol Amar, Andrea Braides. A characterization of variational convergence for segmentation problems. Discrete and Continuous Dynamical Systems, 1995, 1 (3) : 347-369. doi: 10.3934/dcds.1995.1.347
[12]

Michael Boshernitzan, Máté Wierdl. Almost-everywhere convergence and polynomials. Journal of Modern Dynamics, 2008, 2 (3) : 465-470. doi: 10.3934/jmd.2008.2.465
[13]

Antonio Giorgilli, Stefano Marmi. Convergence radius in the Poincaré-Siegel problem. Discrete and Continuous Dynamical Systems - S, 2010, 3 (4) : 601-621. doi: 10.3934/dcdss.2010.3.601
[14]

Giuseppe Maria Coclite, Lorenzo di Ruvo. A note on the convergence of the solution of the Novikov equation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (6) : 2865-2899. doi: 10.3934/dcdsb.2018290
[15]

Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure and Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791
[16]

Chunlei Zhang, Qin Sheng, Raúl Ordóñez. Notes on the convergence and applications of surrogate optimization. Conference Publications, 2005, 2005 (Special) : 947-956. doi: 10.3934/proc.2005.2005.947
[17]

Eric Cancès, Claude Le Bris. Convergence to equilibrium of a multiscale model for suspensions. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 449-470. doi: 10.3934/dcdsb.2006.6.449
[18]

Martin Hutzenthaler, Thomas Kruse, Tuan Anh Nguyen. On the speed of convergence of Picard iterations of BSDEs. Probability, Uncertainty and Quantitative Risk, , () : -. doi: 10.3934/puqr.2022009
[19]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control and Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[20]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems and Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

 Impact Factor: 

Tools

Metrics

  • PDF downloads (69)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy