American Institute of Mathematical Sciences

Advanced
2012, 2(4): 797-809. doi: 10.3934/naco.2012.2.797

On product-type generalized block AOR method for augmented linear systems

Fang Chen 1, , Ning Gao 1, and  Yao- Lin Jiang 1,

1. 

Department of Mathematical Sciences, Xi'an Jiaotong University, Xi'an 710049, China, China, China

Received  December 2011 Revised  August 2012 Published  November 2012

The generalized inexact accelerated overrelaxation ( GIAOR) method was presented by Bai, Parlett and Wang (Numer. Math. 102(2005)1-38) for solving the augmented system of linear equations. In this paper, a product-type generalized block AOR ( PGBAOR ) method is proposed, which is a two-step generalization of the GIAOR method. Both convergence and semi-convergence of the PGBAOR method are proved for the nonsingular and the singular augmented linear systems.
Keywords: Augmented linear system, block AOR method, convergence, semi-convergence..
Mathematics Subject Classification: Primary: 65F10, 65F5.
Citation: Fang Chen, Ning Gao, Yao- Lin Jiang. On product-type generalized block AOR method for augmented linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 797-809. doi: 10.3934/naco.2012.2.797
References:
[1]

K. Arrow, L. Hurwicz and H. Uzawa, "Studies in Nonlinear Programming," Stanford University Press, Stanford, 1958. Google Scholar

[2]

Z. Z. Bai, Structured preconditioners for nonsingular matrices of block two-by-two structures, Math. Comput., 75 (2006), 791-815. doi: 10.1090/S0025-5718-05-01801-6.  Google Scholar

[3]

Z. Z. Bai and G. H. Golub, Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems, IMA J. Numer. Anal., 27 (2007), 1-23. doi: 10.1093/imanum/drl017.  Google Scholar

[4]

Z. Z. Bai, G. H. Golub and M. K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24 (2003), 603-626. doi: 10.1137/S0895479801395458.  Google Scholar

[5]

Z. Z. Bai, G. H. Golub and J. Y. Pan, Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Numer. Math., 98 (2004), 1-32.  Google Scholar

[6]

Z. Z. Bai and G. Q. Li, Restrictively preconditioned conjugate gradient methods for systems of linear equations, IMA J. Numer. Anal., 23 (2003), 561-580. doi: 10.1093/imanum/23.4.561.  Google Scholar

[7]

Z. Z. Bai, B. N. Parlett and Z. Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102 (2005), 1-38. doi: 10.1007/s00211-005-0643-0.  Google Scholar

[8]

Z. Z. Bai and Z. Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl., 428 (2008), 2900-2932. doi: 10.1016/j.laa.2008.01.018.  Google Scholar

[9]

Z. Z. Bai, L. Wang and J. Y. Yuan, Weak-convergence theory of quasi-nonnegative splittings for singular matrices, Linear Algebra Appl., 47 (2003), 75-89.  Google Scholar

[10]

M. Benzi and G. H. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26 (2004), 20-41. doi: 10.1137/S0895479802417106.  Google Scholar

[11]

J. H. Bramble, J. E. Pasciak and A. T. Vassilev, Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal., 34 (1997), 1072-1092. doi: 10.1137/S0036142994273343.  Google Scholar

[12]

H. C. Elman and G. H. Golub, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal., 31 (1994), 1645-1661. doi: 10.1137/0731085.  Google Scholar

[13]

G. H. Golub, X. Wu and J.-Y. Yuan, SOR-like methods for augmented systems, BIT, 41 (2001), 71-85. doi: 10.1023/A:1021965717530.  Google Scholar

[14]

C.-J. Li, Z. Li, D. J. Evans and T. Zhang, A note on an SOR-like method for augmented systems, IMA J. Numer. Anal., 23 (2003), 581-592. doi: 10.1093/imanum/23.4.581.  Google Scholar

[15]

Y.-L. Jiang, R. M. M. Chen and O. Wing, Improving convergence performance of relaxation-based transient analysis by matrix splitting in circuit simulation, IEEE Trans. Circuits Systems: Part I, 48 (2001), 769-780. doi: 10.1109/81.928160.  Google Scholar

[16]

Y.-L. Jiang, Y.-W. Liu, K.-K. Mei and R. M. M. Chen, A new iterative technique for large and dense linear systems from the MEI method in electromagnetics, Appl. Math. Comput., 139 (2003), 157-163. doi: 10.1016/S0096-3003(02)00187-X.  Google Scholar

[17]

D. M. Young, "Iterative Solutions of Large Linear Systmes," Academic Press, New York, 1971. Google Scholar

[18]

J.-F. Yin and Z.-Z. Bai, The restrictively preconditioned conjugate gradient methods on normal residual for block two-by-two linear systems, J. Comput. Math., 26 (2008), 240-249.  Google Scholar

[19]

G.-F. Zhang and Q.-H. Lu, On generalized symmetric SOR method for augmented systems, J. Comput. Appl. Math., 219 (2008), 51-58. doi: 10.1016/j.cam.2007.07.001.  Google Scholar

[20]

B. Zheng, Z.-Z. Bai and X. Yang, On semi-convergence of parameterized Uzawa methods for singular saddle point problems, Linear Algebra Appl., 431 (2009), 808-817. doi: 10.1016/j.laa.2009.03.033.  Google Scholar

[21]

B. Zheng, K. Wang and Y.-J. Wu, SSOR-like methods for saddle point problems, Intern. J. Comput. Math., 86 (2009), 1405-1423. doi: 10.1080/00207160701871835.  Google Scholar

show all references

References:
[1]

K. Arrow, L. Hurwicz and H. Uzawa, "Studies in Nonlinear Programming," Stanford University Press, Stanford, 1958. Google Scholar

[2]

Z. Z. Bai, Structured preconditioners for nonsingular matrices of block two-by-two structures, Math. Comput., 75 (2006), 791-815. doi: 10.1090/S0025-5718-05-01801-6.  Google Scholar

[3]

Z. Z. Bai and G. H. Golub, Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems, IMA J. Numer. Anal., 27 (2007), 1-23. doi: 10.1093/imanum/drl017.  Google Scholar

[4]

Z. Z. Bai, G. H. Golub and M. K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24 (2003), 603-626. doi: 10.1137/S0895479801395458.  Google Scholar

[5]

Z. Z. Bai, G. H. Golub and J. Y. Pan, Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Numer. Math., 98 (2004), 1-32.  Google Scholar

[6]

Z. Z. Bai and G. Q. Li, Restrictively preconditioned conjugate gradient methods for systems of linear equations, IMA J. Numer. Anal., 23 (2003), 561-580. doi: 10.1093/imanum/23.4.561.  Google Scholar

[7]

Z. Z. Bai, B. N. Parlett and Z. Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102 (2005), 1-38. doi: 10.1007/s00211-005-0643-0.  Google Scholar

[8]

Z. Z. Bai and Z. Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl., 428 (2008), 2900-2932. doi: 10.1016/j.laa.2008.01.018.  Google Scholar

[9]

Z. Z. Bai, L. Wang and J. Y. Yuan, Weak-convergence theory of quasi-nonnegative splittings for singular matrices, Linear Algebra Appl., 47 (2003), 75-89.  Google Scholar

[10]

M. Benzi and G. H. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26 (2004), 20-41. doi: 10.1137/S0895479802417106.  Google Scholar

[11]

J. H. Bramble, J. E. Pasciak and A. T. Vassilev, Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal., 34 (1997), 1072-1092. doi: 10.1137/S0036142994273343.  Google Scholar

[12]

H. C. Elman and G. H. Golub, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal., 31 (1994), 1645-1661. doi: 10.1137/0731085.  Google Scholar

[13]

G. H. Golub, X. Wu and J.-Y. Yuan, SOR-like methods for augmented systems, BIT, 41 (2001), 71-85. doi: 10.1023/A:1021965717530.  Google Scholar

[14]

C.-J. Li, Z. Li, D. J. Evans and T. Zhang, A note on an SOR-like method for augmented systems, IMA J. Numer. Anal., 23 (2003), 581-592. doi: 10.1093/imanum/23.4.581.  Google Scholar

[15]

Y.-L. Jiang, R. M. M. Chen and O. Wing, Improving convergence performance of relaxation-based transient analysis by matrix splitting in circuit simulation, IEEE Trans. Circuits Systems: Part I, 48 (2001), 769-780. doi: 10.1109/81.928160.  Google Scholar

[16]

Y.-L. Jiang, Y.-W. Liu, K.-K. Mei and R. M. M. Chen, A new iterative technique for large and dense linear systems from the MEI method in electromagnetics, Appl. Math. Comput., 139 (2003), 157-163. doi: 10.1016/S0096-3003(02)00187-X.  Google Scholar

[17]

D. M. Young, "Iterative Solutions of Large Linear Systmes," Academic Press, New York, 1971. Google Scholar

[18]

J.-F. Yin and Z.-Z. Bai, The restrictively preconditioned conjugate gradient methods on normal residual for block two-by-two linear systems, J. Comput. Math., 26 (2008), 240-249.  Google Scholar

[19]

G.-F. Zhang and Q.-H. Lu, On generalized symmetric SOR method for augmented systems, J. Comput. Appl. Math., 219 (2008), 51-58. doi: 10.1016/j.cam.2007.07.001.  Google Scholar

[20]

B. Zheng, Z.-Z. Bai and X. Yang, On semi-convergence of parameterized Uzawa methods for singular saddle point problems, Linear Algebra Appl., 431 (2009), 808-817. doi: 10.1016/j.laa.2009.03.033.  Google Scholar

[21]

B. Zheng, K. Wang and Y.-J. Wu, SSOR-like methods for saddle point problems, Intern. J. Comput. Math., 86 (2009), 1405-1423. doi: 10.1080/00207160701871835.  Google Scholar

[1]

Jahnabi Chakravarty, Ashiho Athikho, Manideepa Saha. Convergence of interval AOR method for linear interval equations. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021006
[2]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319
[3]

Leyu Hu, Xingju Cai. Convergence of a randomized Douglas-Rachford method for linear system. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 463-474. doi: 10.3934/naco.2020045
[4]

Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic & Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1
[5]

Xi-Hong Yan. A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 45-54. doi: 10.3934/naco.2016.6.45
[6]

Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507
[7]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030
[8]

Hongxiu Zhong, Guoliang Chen, Xueping Guo. Semi-local convergence of the Newton-HSS method under the center Lipschitz condition. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 85-99. doi: 10.3934/naco.2019007
[9]

Liu Liu. Uniform spectral convergence of the stochastic Galerkin method for the linear semiconductor Boltzmann equation with random inputs and diffusive scaling. Kinetic & Related Models, 2018, 11 (5) : 1139-1156. doi: 10.3934/krm.2018044
[10]

Xiaoxue Ji, Pengcheng Niu, Pengyan Wang. Non-existence results for cooperative semi-linear fractional system via direct method of moving spheres. Communications on Pure & Applied Analysis, 2020, 19 (2) : 1111-1128. doi: 10.3934/cpaa.2020051
[11]

Wilhelm Schlag. Regularity and convergence rates for the Lyapunov exponents of linear cocycles. Journal of Modern Dynamics, 2013, 7 (4) : 619-637. doi: 10.3934/jmd.2013.7.619
[12]

Feng-Yu Wang. Exponential convergence of non-linear monotone SPDEs. Discrete & Continuous Dynamical Systems, 2015, 35 (11) : 5239-5253. doi: 10.3934/dcds.2015.35.5239
[13]

G. Gentile, V. Mastropietro. Convergence of Lindstedt series for the non linear wave equation. Communications on Pure & Applied Analysis, 2004, 3 (3) : 509-514. doi: 10.3934/cpaa.2004.3.509
[14]

Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial & Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199
[15]

Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033
[16]

Karl Kunisch, Markus Müller. Uniform convergence of the POD method and applications to optimal control. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4477-4501. doi: 10.3934/dcds.2015.35.4477
[17]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381
[18]

Yong Duan, Jian-Guo Liu. Convergence analysis of the vortex blob method for the $b$-equation. Discrete & Continuous Dynamical Systems, 2014, 34 (5) : 1995-2011. doi: 10.3934/dcds.2014.34.1995
[19]

Jiequn Han, Jihao Long. Convergence of the deep BSDE method for coupled FBSDEs. Probability, Uncertainty and Quantitative Risk, 2020, 5 (0) : 5-. doi: 10.1186/s41546-020-00047-w
[20]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397

 Impact Factor: 

Tools

Metrics

  • PDF downloads (70)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences