求解對稱正定線性代數方程組的一個代數預處理器

劉海峰, 李正光

(1. 中山大學 數學學院(珠海), 廣東 珠海 519082; 2. 吉林大學 數學學院, 長春 130012)

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

1 主要結果

考慮用預處理共軛梯度法求解如下對稱正定線性代數方程組:

Kx=b,

(1)

其中K∈n×n是對稱正定矩陣，b∈n是給定向量，x∈n是待求向量. 關于預處理共軛梯度法的執行過程參見文獻[8].

1.1 預處理器的構造

將系數矩陣K進行如下分塊:

(2)

其中A∈m×m是方陣. 受文獻[9]中構造預處理器方法的啟發, 本文構造如下代數預處理器W求解線性代數方程組(1):

(3)

可證明預處理器W是對稱正定的[9].

1.2 本文提出預處理器的理論分析

(4)

由方程(4), 有

(5)

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

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

(7)

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

證畢.

1.3 分塊對角預處理器的理論分析

其中

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

(9)

即

(10)

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

2 數值算例

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

圖1 某款轎車門結構的有限元模型Fig.1 Finite element model of a car door structure

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

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