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

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

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.
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, (1958).   Google Scholar

[2]

Z. Z. Bai, Structured preconditioners for nonsingular matrices of block two-by-two structures,, Math. Comput., 75 (2006), 791.  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.  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.  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.   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.  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.  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.  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.   Google Scholar

[10]

M. Benzi and G. H. Golub, A preconditioner for generalized saddle point problems,, SIAM J. Matrix Anal. Appl., 26 (2004), 20.  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.  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.  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.  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.  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.  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.  doi: 10.1016/S0096-3003(02)00187-X.  Google Scholar

[17]

D. M. Young, "Iterative Solutions of Large Linear Systmes,", Academic Press, (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.   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.  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.  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.  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, (1958).   Google Scholar

[2]

Z. Z. Bai, Structured preconditioners for nonsingular matrices of block two-by-two structures,, Math. Comput., 75 (2006), 791.  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.  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.  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.   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.  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.  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.  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.   Google Scholar

[10]

M. Benzi and G. H. Golub, A preconditioner for generalized saddle point problems,, SIAM J. Matrix Anal. Appl., 26 (2004), 20.  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.  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.  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.  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.  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.  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.  doi: 10.1016/S0096-3003(02)00187-X.  Google Scholar

[17]

D. M. Young, "Iterative Solutions of Large Linear Systmes,", Academic Press, (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.   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.  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.  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.  doi: 10.1080/00207160701871835.  Google Scholar

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Yuhua Zhu. A local sensitivity and regularity analysis for the Vlasov-Poisson-Fokker-Planck system with multi-dimensional uncertainty and the spectral convergence of the stochastic Galerkin method. Networks & Heterogeneous Media, 2019, 14 (4) : 677-707. doi: 10.3934/nhm.2019027

[19]

Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863

[20]

Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]