两点边值问题3次Lagrange形函数有限元方程的条件数和预处理
|
摘要
大型病态稀疏线性方程组的求解是科学计算和工程应用中的重要问题之一,采用预处理方法,通过降低条件数来减少病态是解决这一问题的关键。基于3次Lagrange形函数,用有限元方法将积分形式两点边值问题的求解转化成病态七对角方程组的求解。通过研究该方程组的特殊结构,分析了该方程的条件数,找到产生病态的因子(致病因子)。将系数矩阵的大范数部分分解成几个简单矩阵的特殊组合,基于这种特殊分解,设计出预条件子(去病因子),并对预条件子的性能进行了定量分析。结果表明,该预条件子的使用几乎不增加迭代的计算量,预处理后的条件数接近1。
Solving large sparse ill-conditioned linear equations is very important in scientific computing and engineering applications.The key to solve the problem is reducing the condition number by preprocessing.The finite element system formed in solving two-point boundary value problems of integral form using the finite element method based on cubic Lagrange shape functions is converted into a system of ill-conditioned seven diagonal equations,and the condition number of the system was analyzed by studying the special structure of the equation,and the factor causing ill-conditioning was found.The big norm part of the coefficient matrix was decomposed into an assemble of several simple matrices.The preconditioner was obtained based on the decomposition,and performance analysis of the preconditioner was given in a quantitative manner.The results of analysis show that the condition number is close to 1after pretreatment without causing more computation.
Solving large sparse ill-conditioned linear equations is very important in scientific computing and engineering applications.The key to solve the problem is reducing the condition number by preprocessing.The finite element system formed in solving two-point boundary value problems of integral form using the finite element method based on cubic Lagrange shape functions is converted into a system of ill-conditioned seven diagonal equations,and the condition number of the system was analyzed by studying the special structure of the equation,and the factor causing ill-conditioning was found.The big norm part of the coefficient matrix was decomposed into an assemble of several simple matrices.The preconditioner was obtained based on the decomposition,and performance analysis of the preconditioner was given in a quantitative manner.The results of analysis show that the condition number is close to 1after pretreatment without causing more computation.
引文
[1]Jia Z X.The convergence of Krylov subspace methods for large unsymmertric linear systems[J].Acta Mathematica Sinica,1988,14(4):507-518.
[2]Van dar Vorst H A,Dekker K.Conjugate gradient type methods and preconditioning[J].Journal of Computational and Applied Mathematics,1988,24(1):73-87.
[3]Young D M,Jea K C.Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods[J].Linear Algebra and Its Applications,1980,34:159-194.
[4]李荣华.偏微分方程数值解法(第二版)[M].北京:高等教育出版社,2010.(LI Rong-hua.Numerical Methods for Partial Differential Equations(Second Edition)[M].Beijing:Higher Education Press,2010.(in Chinese))
[5]Bai Z Z,Li G Q.Restrictively preconditioned conjugate gradient methods for systems of linear equations[J].IMA Journal of Numerical Analysis,2003,23(4):561-580.
[6]Wang Z Q.Restrictively preconditioned Chebyshev method for solving systems of linear equations[J].Journal of Engineering Mathematics,2015,93(1):61-76.
[7]Bru R,Marin J,Mas J,et al.Preconditioned iterative methods for solving linear least squares problems[J].SIAM Journal on Scientific Computing,2014,36(4):A2002-A2022.
[8]于春肖,苑润浩,穆运峰.新预处理ILUCG法求解稀疏病态线性方程组[J].数值计算与计算机应用,2014,35(1):21-27.(YU Chun-xiao,YUAN Runhao,MU Yun-feng.New preconditioning ILUCG method for solving sparse ill-conditioned linear equations[J].Journal on Numerical Methods and Computer Applications,2014,35(1):21-27.(in Chinese))
[9]Xue Q F,Gao X B,Liu X G.Comparison theorems for a class of preconditioned AOR iterative methods[J].Journal of Mathematics,2014,34(3):448-460.
[10]潘春平,马成荣,曹文方,等.一类预条件AOR迭代法的收敛性分析[J].数学杂志,2013,33(3):479-484.(PAN Chun-ping,MA Cheng-rong,CAO Wenfang,et al.On convergence of a cype of preconditional AOR iterative method[J].Journal of Mathematics,2013,33(3):479-484.(in Chinese))
[11]罗芳.L-矩阵的多参数预条件AOR迭代法[J].数学的实践与认识,2013,43(15),277-282.(LUO Fang.On the ulti-parameter precondition AOR iterative method for L-matrices[J].Mathematics in Practice and Theory,2013,43(15),277-282.(in Chinese))
[12]吴建平,赵军,马怀发,等.一般稀疏线性方程组的因子组合型并行预条件研究[J].计算机应用与软件,2012,29(5):6-9,108.(WU Jian-ping,ZHAO Jun,MA Huai-fa,et al.Generalsparse linear equations system factor combined parallel pre-condition research[J].Computer Applications and Software,2012,29(5):6-9,108.(in Chinese))
[13]李继成,蒋耀林.预条件IMGS迭代方法的比较定理[J].数学物理学报,2011,31A(4):880-886.(LI Ji-cheng,JIANG Yao-lin.Comparison theorems for the IMGS iterative method wtih preconditioner[J].Acta Mathematica Scientia,2011,31A(4):880-886.(in Chinese))
[14]Pan C.A new effective pre-conditioned Gauss-Seidel iteration method[J].Journal on Numerical Methods and Computer Applications,2011,32(4):267-273.
[15]林群.微分方程数值解法基础教程(第二版)[M].北京:科学出版社,2003.(LIN Qun.Basic Course of Numerical Methods for Differential Equations(Second Edition)[M].Beijing:Science Press,2003.(in Chinese))
[16]谢冬秀,雷纪刚,陈桂芝.矩阵理论及方法[M].北京:科学出版社,2012.(XIE Dong-xiu,LEI Ji-gang,CHEN Gui-zhi.Matrix Theory and Methodology[M].Beijing:Science Press,2012.(in Chinese))
[2]Van dar Vorst H A,Dekker K.Conjugate gradient type methods and preconditioning[J].Journal of Computational and Applied Mathematics,1988,24(1):73-87.
[3]Young D M,Jea K C.Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods[J].Linear Algebra and Its Applications,1980,34:159-194.
[4]李荣华.偏微分方程数值解法(第二版)[M].北京:高等教育出版社,2010.(LI Rong-hua.Numerical Methods for Partial Differential Equations(Second Edition)[M].Beijing:Higher Education Press,2010.(in Chinese))
[5]Bai Z Z,Li G Q.Restrictively preconditioned conjugate gradient methods for systems of linear equations[J].IMA Journal of Numerical Analysis,2003,23(4):561-580.
[6]Wang Z Q.Restrictively preconditioned Chebyshev method for solving systems of linear equations[J].Journal of Engineering Mathematics,2015,93(1):61-76.
[7]Bru R,Marin J,Mas J,et al.Preconditioned iterative methods for solving linear least squares problems[J].SIAM Journal on Scientific Computing,2014,36(4):A2002-A2022.
[8]于春肖,苑润浩,穆运峰.新预处理ILUCG法求解稀疏病态线性方程组[J].数值计算与计算机应用,2014,35(1):21-27.(YU Chun-xiao,YUAN Runhao,MU Yun-feng.New preconditioning ILUCG method for solving sparse ill-conditioned linear equations[J].Journal on Numerical Methods and Computer Applications,2014,35(1):21-27.(in Chinese))
[9]Xue Q F,Gao X B,Liu X G.Comparison theorems for a class of preconditioned AOR iterative methods[J].Journal of Mathematics,2014,34(3):448-460.
[10]潘春平,马成荣,曹文方,等.一类预条件AOR迭代法的收敛性分析[J].数学杂志,2013,33(3):479-484.(PAN Chun-ping,MA Cheng-rong,CAO Wenfang,et al.On convergence of a cype of preconditional AOR iterative method[J].Journal of Mathematics,2013,33(3):479-484.(in Chinese))
[11]罗芳.L-矩阵的多参数预条件AOR迭代法[J].数学的实践与认识,2013,43(15),277-282.(LUO Fang.On the ulti-parameter precondition AOR iterative method for L-matrices[J].Mathematics in Practice and Theory,2013,43(15),277-282.(in Chinese))
[12]吴建平,赵军,马怀发,等.一般稀疏线性方程组的因子组合型并行预条件研究[J].计算机应用与软件,2012,29(5):6-9,108.(WU Jian-ping,ZHAO Jun,MA Huai-fa,et al.Generalsparse linear equations system factor combined parallel pre-condition research[J].Computer Applications and Software,2012,29(5):6-9,108.(in Chinese))
[13]李继成,蒋耀林.预条件IMGS迭代方法的比较定理[J].数学物理学报,2011,31A(4):880-886.(LI Ji-cheng,JIANG Yao-lin.Comparison theorems for the IMGS iterative method wtih preconditioner[J].Acta Mathematica Scientia,2011,31A(4):880-886.(in Chinese))
[14]Pan C.A new effective pre-conditioned Gauss-Seidel iteration method[J].Journal on Numerical Methods and Computer Applications,2011,32(4):267-273.
[15]林群.微分方程数值解法基础教程(第二版)[M].北京:科学出版社,2003.(LIN Qun.Basic Course of Numerical Methods for Differential Equations(Second Edition)[M].Beijing:Science Press,2003.(in Chinese))
[16]谢冬秀,雷纪刚,陈桂芝.矩阵理论及方法[M].北京:科学出版社,2012.(XIE Dong-xiu,LEI Ji-gang,CHEN Gui-zhi.Matrix Theory and Methodology[M].Beijing:Science Press,2012.(in Chinese))