張衡

（福建師范大學(xué)福清分校電子與信息工程學(xué)院，福建 福清 350300）

一維問題m次lagrange形函數(shù)有限元方程的條件數(shù)與預(yù)處理

張衡

（福建師范大學(xué)福清分校電子與信息工程學(xué)院，福建 福清 350300）

求解大型稀疏病態(tài)線性方程組是科學(xué)計(jì)算和工程應(yīng)用中經(jīng)常遇到的重要問題，通過預(yù)處理、降低條件數(shù)來改善病態(tài)是解決該問題的關(guān)鍵。在用有限元方法求解積分形式的一維兩點(diǎn)邊值問題時(shí)，利用m次lagrange形函數(shù)可將該問題的求解化成稀疏病態(tài)有限元方程組的求解。本文研究該方程組的特殊結(jié)構(gòu)，分析了該方程的條件數(shù)，再將系數(shù)矩陣的大范數(shù)部分分解成4個(gè)結(jié)構(gòu)特殊的簡(jiǎn)單矩陣乘積，基于這種特殊分解設(shè)計(jì)出預(yù)條件子，并對(duì)預(yù)條件子的性能進(jìn)行了定量分析，結(jié)果說明該預(yù)條件子幾乎不增加迭代的計(jì)算量，預(yù)處理后的條件數(shù)接近1。

病態(tài)稀疏線性方程組；lagrange形函數(shù)；特別結(jié)構(gòu)；條件數(shù)；預(yù)處理

大規(guī)模稀疏線性方程組的迭代求解是科學(xué)計(jì)算和工程中經(jīng)常遇到的問題[1-3]，其中方程組過高的條件數(shù)經(jīng)常制約求解精度和效率，因此，在迭代求解之前，通過對(duì)方程組使用預(yù)處理技術(shù)來降低條件數(shù)，成為提高求解精度和效率的必要措施。所謂“預(yù)處理技術(shù)”是指在求解方程組時(shí)，如果A的條件數(shù)Cond(A)太大，則構(gòu)造矩陣D≈A，使得D-1比A-1容易計(jì)算，D-1A的條件數(shù) Cond(D-1A)＜＜Cond(A)，從而方程組（1）化成同解的、條件數(shù)更小的方程組

矩陣D稱為預(yù)條件子或者預(yù)處理器[4]。在解決實(shí)際問題中，經(jīng)常遇到高條件數(shù)（病態(tài)）的稀疏線性方程組，而且條件數(shù)隨著問題規(guī)模的增加而增加[5]，成功的迭代求解，往往以適當(dāng)?shù)念A(yù)條件子作為前提，否則，迭代過程可能很慢，甚至不收斂。然而，目前并沒有通用的預(yù)條件子，只能針對(duì)具體問題，根據(jù)預(yù)條件子的基本要求，設(shè)計(jì)具體的預(yù)條件子[6-8]。很多計(jì)算工作者針對(duì)不同的方程組設(shè)計(jì)了不同的預(yù)條件子，但是對(duì)預(yù)條件子的性能（條件數(shù)下降的程度，預(yù)處理后的條件數(shù)，對(duì)計(jì)算量的影響等），多以計(jì)算結(jié)果說明，鮮見有定量的分析結(jié)果[9-15]。

使用有限元方法，求解積分形式的兩點(diǎn)邊值問題時(shí)，基于m次lagrange形函數(shù)形成的有限元方程，屬于稀疏線性方程組，其總剛度矩陣有特別的結(jié)構(gòu)。針對(duì)這種結(jié)構(gòu)，本文討論了該方程的條件數(shù)，并設(shè)計(jì)出預(yù)條件子，定量分析了預(yù)條件子的性能。

1 m次lagrange形函數(shù)有限元方程的形成

根據(jù)問題（1）離散形式的矩陣表達(dá)式（8）得：

從而得到有限元方程

總剛度矩陣為：

將總剛度矩陣寫成分解的形式（10），可以避免剛度矩陣的拼接計(jì)算，而且有利于分析條件數(shù)，有利于設(shè)計(jì)預(yù)處理子和算法。

2 有限元方程的條件數(shù)

顯然在總剛度矩陣A=UPUT+Q中，U有特別的作用，U如同條件數(shù)的放大器，將條件數(shù)從Cond(P)放大到因此U是造成A有高條件數(shù)的重要原因。

3 有限元方程的預(yù)處理

如果使用迭代法求解方程（9），則因方程（9）的條件數(shù)很大，可能不收斂，必須進(jìn)行預(yù)處理降低條件數(shù)。因?yàn)?||UPUT||＞＞||Qi||，所以 1＞＞||(UPUT)-1Q||，Cond[I+(UPUT)-1Q]≈Cond(I)=1，因此選擇UPUT為預(yù)條件子，將有限元方程（9）化成

根據(jù)式（12），取迭代式為

預(yù)條件子UPUT是否合適，不僅要看它是否能夠降低條件數(shù)，更重要的是看它是否會(huì)導(dǎo)致計(jì)算量的增加。求解方程（13），主要的計(jì)算量是（UPUT）-1與向量的乘積。本文通過分析UPUT的結(jié)構(gòu)，研究（UPUT）-1與向量的乘積的計(jì)算量。

4 結(jié)語

稀疏線性方程組的稀疏性，往往隱含著簡(jiǎn)單的結(jié)構(gòu)，這些簡(jiǎn)單的結(jié)構(gòu)并不是顯然的，所以沒有顯然、通用的預(yù)處理方法，通常要針對(duì)具體的問題找到這些特別的簡(jiǎn)單結(jié)構(gòu)，才能發(fā)現(xiàn)影響條件數(shù)的主要原因，并提出合適的預(yù)處理方法。

使用有限元方法求解積分形式的兩點(diǎn)邊值問題時(shí)，基于m次lagrange形函數(shù)形成有限元方程，本文通過研究該方程總剛度矩陣的結(jié)構(gòu)找到了影響條件數(shù)的主要原因，并針對(duì)該方程總剛度矩陣的特別結(jié)構(gòu)，將剛度矩陣的大范數(shù)部分，分解成4個(gè)結(jié)構(gòu)簡(jiǎn)單的矩陣乘積，從而提出預(yù)處理方法，使條件數(shù)接近1，而且與一般的迭代法相比，不需要過多的計(jì)算量。

[1]Jia Z X,The Convergence of Krylov Subspace Methods for Large Nonsymmertric Linear Systems[J].Acta Mathematical Sinica,1988,14(4):507-518.

[2]Van Der Vorst H A,Dekker K.Conjugate Gradient Type Methods and Preconditioning[J].Journal of Computational and Applied Mathematics,1988,24(1):73-87.

[3]Yong D M,Jea K C.Generalized Conjugate-Gradient Acceleration of Nonsymmetrizable Iterative Methods[J].Linear Algebra Appl,1980,34:159-194.

[4]李榮華.偏微分方程數(shù)值解法[M].2版.北京：高等教育出版社，2010：139-140

[5]周志陽，聶存云，舒適.一種二階混合有限體元格式的GAMG預(yù)條件子[J].計(jì)算物理,2011,28(4):493-500.Zhou Zhiyang，Nie Cunyun,Shu Shi1.An Effcient GAMG-based Preconditioner for Second Order Mixed-type Finite Volume Element Method[J].Chinese Journal of Coputational Physics,2011,28(4):493-500.

[6]Bai Z Z,Li G Q.Restrictively Preconditioned Conjugate Gradient Methods for Systems of Linear Equations,IMA Journal of Numerical Analysis 2003(23)：561-580

[7]Wang Z Q.Restrictively Preconditioned Chebyshev Method for Solving Systems of Linear Equations[J].Eng Math，2015 93,61-76

[8]Rafael Bru,Jos?e Mar?in,Jos?e Mas,et al.Preconditioned Iterative Methods for Solving Linear Least Squares Problems[J].SIAM J Sci Comput,2014,36(4)：2002-2022.

[9]于春肖,苑潤(rùn)浩,穆運(yùn)峰.新預(yù)處理ILUCG法求解稀疏病態(tài)線性方程組[J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用,2014,35(1):21-27.Yu C X,Yuan R H,Mu Y F.New Preconditioning ILUCG Method for Solving Sparse Ill Conditioned Linear Equations[J].Journal on Numerical Methods and Computer Applications,2014,35(1):21-27.

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

[11]潘春平,馬成榮,曹文方,等.一類預(yù)條件AOR 迭代法的收斂性分析[J].數(shù)學(xué)雜志,2013,33(3):479-484.Pan Chunping,Ma Chengrong,Cao Cenfang,et al.On Convergence of a Cype of Preconditional AOR Iterative Method[J].Journal of Mathematics,2013,33(3):479-484.

[12]羅芳.L-矩陣的多參數(shù)預(yù)條件AOR迭代法[J]數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(15)：277-282.Luo F.On the Ulti-parameter Precondition AOR Iterative Method for L-matrices[J].Mathematics in Practice and Theory,2013,43(15)：277-282.

[13]吳建平,趙軍,馬懷發(fā),等.一般稀疏線性方程組的因子組合型并行預(yù)條件研究[J].計(jì)算機(jī)應(yīng)用與軟件,2012,29(5):6-9,108.Wu J P,Zhao J,Ma H F,et al.General Sparse Linear Equations System Factor Combined Parallel Precondition Research[J].Computer Applications and Software,2012,29(5):6-9,108.

[14]李繼成,蔣耀林.預(yù)條件IMGS迭代方法的比較定理[J],數(shù)學(xué)物理學(xué)報(bào),2011,31A(4):880-886.Li J C,Jiang Y L.Comparison Theorems of the IMGS Iterative Method wtih Preconditioner[J].Acta Mathematica Scientia,2011,31A(4):880-886.

[15]Pan Chunping.A new Effective Preconditioned Gauss_Seidel Iteration Method[J].Journal on Numerical Methods and Computer Applications,2011,32(4):267-273.

[16]林群.微分方程數(shù)值解法基礎(chǔ)教程[M].2版.北京：科學(xué)出版社,2003：87-111.

Condition number and preprocess of the finite element equation of one dimensional problem with m-degree lagrange shape function

Zhang Heng
(School of electronic and Information Engineering,Fuqing Branch of Fujian Normal University,Fuqing,Fujian 350300,China)

Solving the large sparse ill-conditioned linear equations is very important in scientific computing and engineering applications.Reducing the condition number by preprocessing is the key to it.The finite element equations formed in solving two-point boundary value problems with integral form using finite element method based on m-degree lagrange shape function are discussed.The condition number of the finite element equations is analyzed by studying the special structure of the equation.The part of the coefficient matrix with big norm is decomposed into product of four simple structure matrices.The preconditionerwas obtained based on the decomposition,and performance analysis ofthe preconditionerwas given quantificationally.The results of analysis show that the condition number is close to 1 after pretreatment without causing more computing.

sparse ill-conditioned linear equations;lagrange shape function;special structure;condition number;preprocess method.

O241.6

A

10.13880/j.cnki.65-1174/n.2017.04.021

1007-7383(2017)04-0518-04

2016-03-13

福建省自然科學(xué)基金項(xiàng)目(2014J01006)

張衡，男，（1961-），教授，從事微分方程數(shù)值解以及并行計(jì)算方法與應(yīng)用研究，e-mail:zhheng01@163.com。