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).

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[17]

D. M. Young, "Iterative Solutions of Large Linear Systmes,", Academic Press, (1971).

[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.

[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.

[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.

[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.

show all references

References:
[1]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[17]

D. M. Young, "Iterative Solutions of Large Linear Systmes,", Academic Press, (1971).

[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.

[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.

[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.

[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.

[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]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial & Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193

[18]

Binjie Li, Xiaoping Xie, Shiquan Zhang. New convergence analysis for assumed stress hybrid quadrilateral finite element method. Discrete & Continuous Dynamical Systems - B, 2017, 22 (7) : 2831-2856. doi: 10.3934/dcdsb.2017153

[19]

Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893

[20]

Zhong-Zhi Bai. On convergence of the inner-outer iteration method for computing PageRank. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 855-862. doi: 10.3934/naco.2012.2.855

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]