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]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[2]

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

[3]

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

[4]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[5]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[6]

Philipp Harms. Strong convergence rates for markovian representations of fractional processes. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020367

[7]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29

[8]

Qianqian Hou, Tai-Chia Lin, Zhi-An Wang. On a singularly perturbed semi-linear problem with Robin boundary conditions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 401-414. doi: 10.3934/dcdsb.2020083

[9]

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

[10]

Toshiko Ogiwara, Danielle Hilhorst, Hiroshi Matano. Convergence and structure theorems for order-preserving dynamical systems with mass conservation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3883-3907. doi: 10.3934/dcds.2020129

[11]

Xiuli Xu, Xueke Pu. Optimal convergence rates of the magnetohydrodynamic model for quantum plasmas with potential force. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 987-1010. doi: 10.3934/dcdsb.2020150

[12]

Takiko Sasaki. Convergence of a blow-up curve for a semilinear wave equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1133-1143. doi: 10.3934/dcdss.2020388

[13]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226

[14]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[15]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345

[16]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105

[17]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304

[18]

Gheorghe Craciun, Jiaxin Jin, Casian Pantea, Adrian Tudorascu. Convergence to the complex balanced equilibrium for some chemical reaction-diffusion systems with boundary equilibria. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1305-1335. doi: 10.3934/dcdsb.2020164

[19]

Jan Březina, Eduard Feireisl, Antonín Novotný. On convergence to equilibria of flows of compressible viscous fluids under in/out–flux boundary conditions. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021009

[20]

Mario Bukal. Well-posedness and convergence of a numerical scheme for the corrected Derrida-Lebowitz-Speer-Spohn equation using the Hellinger distance. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021001

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]