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, (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: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences