求解對(duì)稱正定線性代數(shù)方程組的一個(gè)代數(shù)預(yù)處理器

劉海峰, 李正光

(1. 中山大學(xué) 數(shù)學(xué)學(xué)院(珠海), 廣東 珠海 519082; 2. 吉林大學(xué) 數(shù)學(xué)學(xué)院, 長(zhǎng)春 130012)

科學(xué)與工程中的許多計(jì)算問(wèn)題最終都涉及對(duì)稱正定線性代數(shù)方程組的求解. 預(yù)處理共軛梯度法是求解這類方程組的最有效迭代法, 其關(guān)鍵是預(yù)處理器的構(gòu)造. 目前人們已構(gòu)造出多種預(yù)處理器, 主要分為兩類： 基于問(wèn)題的預(yù)處理器和代數(shù)預(yù)處理器[1]. 一般情況下, 基于問(wèn)題的預(yù)處理器比代數(shù)預(yù)處理器更有效, 但構(gòu)造基于問(wèn)題的預(yù)處理器需深入了解問(wèn)題的背景, 利用問(wèn)題的特點(diǎn)構(gòu)造預(yù)處理器, 因此, 這類預(yù)處理器的使用范圍較窄, 不具有通用性[2-6]. 代數(shù)預(yù)處理器只根據(jù)方程組的系數(shù)矩陣構(gòu)造預(yù)處理器, 因此具有一定的通用性. 常見(jiàn)的代數(shù)預(yù)處理器有對(duì)角預(yù)處理器、 分塊對(duì)角預(yù)處理器、 逼近逆預(yù)處理器及不完全Cholesky分解預(yù)處理器等[7]. 本文提出一種新的代數(shù)預(yù)處理器, 用Weyl不等式對(duì)該預(yù)處理器和分塊對(duì)角預(yù)處理器進(jìn)行理論分析, 并用數(shù)值算例驗(yàn)證所提出預(yù)處理器的有效性.

1 主要結(jié)果

考慮用預(yù)處理共軛梯度法求解如下對(duì)稱正定線性代數(shù)方程組:

Kx=b,

(1)

其中K∈n×n是對(duì)稱正定矩陣，b∈n是給定向量，x∈n是待求向量. 關(guān)于預(yù)處理共軛梯度法的執(zhí)行過(guò)程參見(jiàn)文獻(xiàn)[8].

1.1 預(yù)處理器的構(gòu)造

將系數(shù)矩陣K進(jìn)行如下分塊:

(2)

其中A∈m×m是方陣. 受文獻(xiàn)[9]中構(gòu)造預(yù)處理器方法的啟發(fā), 本文構(gòu)造如下代數(shù)預(yù)處理器W求解線性代數(shù)方程組(1):

(3)

可證明預(yù)處理器W是對(duì)稱正定的[9].

1.2 本文提出預(yù)處理器的理論分析

(4)

由方程(4), 有

(5)

由方程(5), 若用W作為求解方程組(1)的預(yù)處理器, 則預(yù)處理后的系數(shù)矩陣為

由Weyl不等式[11], 并結(jié)合方程(6), 有

(7)

由式(8)并結(jié)合不等式(7), 有

證畢.

1.3 分塊對(duì)角預(yù)處理器的理論分析

其中

若用M作為求解方程組(1)的預(yù)處理器, 則預(yù)處理后的系數(shù)矩陣為

(9)

即

(10)

由式(9),(10)并結(jié)合引理2知結(jié)論成立, 證畢.

2 數(shù)值算例

考慮如圖1所示的某款轎車(chē)門(mén)結(jié)構(gòu)的有限元模型, 該模型剛度矩陣的維數(shù)為192 732. 用預(yù)處理共軛梯度法對(duì)該車(chē)門(mén)進(jìn)行靜力分析, 迭代終止條件為殘量的2-范數(shù)小于10-6. 表1列出了用本文提出的預(yù)處理器、 分塊對(duì)角預(yù)處理器和不完全Cholesky分解預(yù)處理器IC(0)的迭代步數(shù)和計(jì)算時(shí)間比較結(jié)果. 由表1可見(jiàn), 本文提出預(yù)處理器的迭代步數(shù)和計(jì)算時(shí)間均最少, 用本文提出預(yù)處理器的計(jì)算時(shí)間約是用分塊對(duì)角預(yù)處理器計(jì)算時(shí)間的77%, 是用IC(0)計(jì)算時(shí)間的20%.

圖1 某款轎車(chē)門(mén)結(jié)構(gòu)的有限元模型Fig.1 Finite element model of a car door structure

表1 3種不同預(yù)處理器迭代步數(shù)和計(jì)算時(shí)間的比較Table 1 Comparison of iteration numbers and computational time of three different preconditioners

綜上, 本文提出了一種新的代數(shù)預(yù)處理器, 理論分析表明, 用該預(yù)處理器預(yù)處理后的譜條件數(shù)小于用分塊對(duì)角預(yù)處理器預(yù)處理后的譜條件數(shù). 數(shù)值算例表明, 用該預(yù)處理器的計(jì)算時(shí)間和迭代步數(shù)均少于用分塊對(duì)角預(yù)處理器和不完全Cholesky分解預(yù)處理器IC(0)的計(jì)算時(shí)間和迭代步數(shù).