兩點邊值問題2次Lagrange形函數有限元方程的條件數和預處理

張 衡

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

兩點邊值問題2次Lagrange形函數有限元方程的條件數和預處理

張 衡

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

求解積分形式的兩點邊值問題時， 基于2次Lagrange形函數形成的有限元方程是病態正定對稱五對角方程組. 為了尋找該方程的病態原因， 提出根據系數矩陣的特別結構， 設計出預條件子的方法， 并將產生病態的因子定義為致病因子， 預條件子稱為去病因子. 分析結果表明， 使用去病因子進行預處理， 可以保證系數矩陣的正定對稱性， 迭代求解時， 預條件子幾乎不增加迭代的計算量， 預處理后的條件數接近1.

病態五對角方程組; 特別結構; 條件數; 預條件子； 邊值問題

0 引言

大規模稀疏線性方程組的迭代求解是科學計算和工程中經常遇到的問題[1-3]， 其中方程組過高的條件數(病態)經常制約求解精度和效率， 因此， 在迭代求解之前， 通過對方程組使用預處理技術來降低條件數， 成為提高求解精度和效率的必要措施.

在解決實際問題中， 經常遇到高條件數(病態)的稀疏線性方程組， 而且條件數隨著問題規模的增加而增加[5]. 成功的迭代求解， 往往以適當的預條件子作為前提; 否則， 迭代過程可能很慢， 甚至不收斂.

然而， 目前并沒有通用的預條件子， 只能針對具體問題， 根據預條件子的基本要求， 設計具體的預條件子[6-8]. 很多計算工作者針對不同的方程組設計了不同的預條件子， 但是對預條件子的性能(條件數下降的程度， 預處理后的條件數， 對計算量的影響等)， 鮮見有定量的分析結果[9-15]

使用有限元方法， 求解積分形式的兩點邊值問題時， 基于2次Lagrange形函數形成的有限元方程， 是五對角正定對稱病態方程組， 其總剛度矩陣有特別的結構. 基于結構分析的思想[16]， 針對這種結構， 本研究討論了該方程的條件數， 發現方程產生高條件數的因素， 并稱之為致病因子， 且找到消除致病因素的預條件子， 定義為去病因子. 將系數矩陣的大范數部分分解成幾個簡單矩陣的特殊組合. 基于這種特殊分解， 定量地分析了預條件子的性能(條件數下降的程度， 對計算量的影響)， 說明了在幾乎不增加計算量的情況下， 預處理后的條件數接近1.

1 2次Lagrange形函數有限元方程的形成

使用有限元方法， 求解積分形式的兩點邊值問題[17]

其中:p=p(x)≥pmin>0,q=q(x)≥0,f=f(x),x∈[a,b].

Ni=Ni(ξ)∈P2[ξ],ξ∈[0, 1],i=1, 2, 3， 則N1+N2+N3=1.

構造問題(3)的離散形式[17]：

問題(3)的離散形式可以寫成

(6)

從而問題(3)的離散形式(5)可以表示為

其中:

將問題(1)離散形式(7)， 寫成下面的矩陣表達式

其中:

由問題(1)離散形式的矩陣表達式(8)， 得到vT(UPUT+Q)u=vTd， 從而得到有限元方程

總剛度矩陣為：

注： 將總剛度矩陣寫成分解的形式(10)， 可以避免剛度矩陣的拼接計算， 而且有利于分析條件數， 有利于設計預處理子和算法.

2 有限元方程的條件數

因為，

所以,

所以UPUT條件數為:

(11)

注：U與P無關， 即與兩點邊值問題(3)無關， 只與m有關.

3 有限元方程的預條件子

所以HUPUTHT條件數為:

(13)

注：H與P無關， 即與兩點邊值問題(3)無關， 只與m有關.

選擇H和HT分別為左、 右預條件子， 將方程(9)化成

(14)

其中:u′=H-Tu，d′=Hd

4 有限元方程預條件子的性能分析

根據式(13)，UUT=H-1H-T， 容易驗證：

所以方程(15)中P是系數矩陣的大范數部分， 從而在方程(16)中I是系數矩陣的大范數部分， 即主要部分， 當α-β很小時， Cond[I+W]≈Cond(I)=1.

可以取迭代式為

方程(14)、 (15)的系數矩陣是對稱正定矩陣， 可以使用經典Krylov子空間方法——CG方法求解， 因其主要的計算操作是I+W與向量的乘積， 所以計算量并沒有顯著增加.

5 結論

稀疏線性方程組的稀疏性， 往往隱含著簡單的結構， 而方程組的病態， 也往往是因其結構中有致病因子而產生. 這些簡單的結構和致病因子并不是顯而易見的， 所以沒有簡潔、 通用的預處理方法， 通常要針對具體的問題， 找出這些特殊的簡單結構， 才能發現影響條件數的主要原因， 并提出合適的預處理方法.

使用有限元方法求解積分形式的兩點邊值問題時， 通過研究基于2次Lagrange形函數形成有限元方程的總剛度矩陣的結構， 找到的影響條件數的主要原因， 本研究稱之為致病因子. 針對該方程總剛度矩陣的特別結構， 將剛度矩陣的大范數部分， 分解成幾個結構簡單的矩陣組合. 基于這種特別的組合， 得到預條件子， 稱之為致病因子， 并由此提出預處理方法， 經預處理后矩陣保持正定對稱， 在基本不增加計算操作數的情況下， 使條件數接近1.

[1] JIA Z X. The convergence of krylov subspace methods for large nonsymmertric linear systems[J]. Acta Mathematica Sinica， 1988， 14(4): 507-518.

[2] VORST H A V D， 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(12): 159-194.

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

[5] 周志陽， 聶存云， 舒適. 一種二階混合有限體元格式的GAMG預條件子[J]. 計算物理， 2011， 28(4): 493-500.

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

[7] WANG Z Q. Restrictively preconditioned chebyshev method for solving systems of linear equation[J]. Journal of Engineering Mathematics， 2015， 93(1): 61-76.

[9] 于春肖， 苑潤浩， 穆運峰. 新預處理ILUCG法求解稀疏病態線性方程組[J]. 數值計算與計算機應用， 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] 潘春平， 馬成榮， 曹文方， 等. 一類預條件AOR迭代法的收斂性分析[J]. 數學雜志， 2013， 33(3): 479-484.

[12] 羅芳. L-矩陣的多參數預條件AOR迭代法[J]. 數學的實踐與認識， 2013， 43(15): 277-282.

[13] 吳建平， 趙軍， 馬懷發， 等. 一般稀疏線性方程組的因子組合型并行預條件研究[J]. 計算機應用與軟件， 2012， 29(5): 6-9.

[14] 李繼成， 蔣耀林. 預條件IMGS迭代方法的比較定理[J]. 數學物理學報， 2011， 31(4): 880-886.

[15] PAN C P. A new effective preconditioned Gauss_Seidel iteration method[J]. Journal on Numerical Methods and Computer Applications， 2011， 32(4): 267-273.

[16] 張衡. 一維問題一次形函數有限元方程的條件數與預處理[J]. 福建師大福清分校學報， 2016(2): 1-3.

[17] 林群. 微分方程數值解法基礎教程[M]. 2版. 北京： 科學出版社， 2003： 87-111.

Conditionnumberandpreprocessofthefiniteelementequationoftwopointboundaryvalueproblemswith2-degreeLagrangeshapefunction

ZHANG Heng

(School of Electronic and Information Engineering， Fuqing Branch of Fujian Normal University, Fuqing, Fujian 350300, China)

For the ill conditioned problem of the positive definite symmetric five diagonal finite element systems formed solving two-point boundary value problems of integral form using finite element method based on 2-degree Lagrange shape function. The method for looking up the reason producing ill called pathogenic factor and designing preconditioner called eliminate ill factor to eliminating the ill-condition was obtained based on the special structure of the systems. The results of the analysis shows that pretreatment using the eliminate ill factor, can guarantee positive definite symmetry of the coefficient matrix, and the condition number is close to 1 after pretreatment without causing more computing.

ill conditioned five diagonal equations; special structure; condition number; preconditioner； boundary value problems

10.7631/issn.1000-2243.2017.05.0617

1000-2243(2017)05-0617-06

O241.82； O242.21；O241.6

A

2016-05-06

張衡(1961-)， 教授， 主要從事微分方程數值解、 高性能計算方法與應用方面研究， zhheng01@163.com

福建省自然科學基金資助項目(2014J01006)

(責任編輯： 林曉)