兩點(diǎn)邊值問題網(wǎng)格方程病態(tài)機(jī)理和預(yù)處理

張 衡，鄭漢垣

(1.福建師范大學(xué)福清分校，無損檢測技術(shù)福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，福建福清 350300;2.福建師范大學(xué)福清分校電子與信息工程學(xué)院，福建福清 350300;3.龍巖學(xué)院傳播與設(shè)計(jì)學(xué)院，福建龍巖 364012)

0 引言

兩點(diǎn)邊值問題大規(guī)模數(shù)值求解問題，是使用不同的離散方法轉(zhuǎn)化為各種網(wǎng)格方程來求解的，這些網(wǎng)格方程的病態(tài)(高條件數(shù))隨著問題規(guī)模的增加而增加［1］，成為制約求解效率和精度的瓶頸因素.因此，在求解之前，使用預(yù)處理方法來減少方程組的病態(tài)，成為提高求解效率和精度的必要措施.

所謂“預(yù)處理方法”是指在求解方程組

并保證不增加大的計(jì)算成本的前提下，用線性變換將方程組(1)轉(zhuǎn)化成等價的方程組

使得Cond(A')＜＜Cond(A)，其中線性變換矩陣稱為預(yù)條件子［2－3］;如果Cond(A')與A的階數(shù)無關(guān)，則稱預(yù)條件子為最優(yōu)預(yù)條件子［4］.

病態(tài)方程組的成功求解，依賴于適當(dāng)?shù)念A(yù)條件子.然而，由于缺乏對病態(tài)機(jī)理和預(yù)處理原理的研究，目前關(guān)于預(yù)處理問題的理論和研究方法都不完善，一是缺乏一般的預(yù)處理方法，以及最優(yōu)且通用的預(yù)條件子，通常是針對具體問題，根據(jù)預(yù)條件子的基本要求，設(shè)計(jì)具體的預(yù)條件子［5－7］.二是對預(yù)處理的效果(條件數(shù)下降的程度、條件數(shù)的估計(jì)、對計(jì)算量的影響等)缺少科學(xué)的定量分析，多用定性分析和實(shí)驗(yàn)結(jié)果說明［8－14］.

本研究討論病態(tài)機(jī)理和預(yù)處理原理.定義方程組的病態(tài)結(jié)構(gòu)、病態(tài)因子、去病因子，并討論其性質(zhì)和作用.目前關(guān)于病態(tài)機(jī)理和預(yù)處理原理的研究鮮見有成果發(fā)表.

求解兩點(diǎn)邊值問題時，使用有限元方法和有限差分方法形成不同的網(wǎng)格方程.基于結(jié)構(gòu)分析的思想［15－18］，本研究對網(wǎng)格方程的病態(tài)機(jī)理和預(yù)處理原理進(jìn)行探討.研究結(jié)果說明，這些不同的網(wǎng)格方程有類似的病態(tài)結(jié)構(gòu)和相同的病態(tài)因子以及對應(yīng)的去病因子;將病態(tài)分為由病態(tài)因子表達(dá)的原發(fā)病態(tài)和由具體問題引起的繼發(fā)病態(tài)，更準(zhǔn)確地說明了不同的因素對病態(tài)的影響;推廣文獻(xiàn)［17－18］的方法，依次針對原發(fā)病態(tài)和繼發(fā)病態(tài)進(jìn)行了二次預(yù)處理，通過定量分析預(yù)處理的效果(條件數(shù)下降的程度，對計(jì)算量的影響)，說明了在幾乎不增加計(jì)算量的情況下，預(yù)處理后的條件數(shù)接近1;通過與文獻(xiàn)［17－18］的比較，說明了去病因子不僅是網(wǎng)格方程的最優(yōu)預(yù)條件子［4］，而且作為預(yù)條件子主要部分，具有通用性.

1 矩陣的病態(tài)結(jié)構(gòu)

1.1 矩陣的病態(tài)結(jié)構(gòu)

定義1矩陣A的如下結(jié)構(gòu)稱為病態(tài)結(jié)構(gòu):

1.2 去病因子

命題11)如果Z∈Rα×β，β≥α，ZZT可逆，則對任意β階正定對稱矩陣P，有

2)如果可逆矩陣H滿足ZZT=HHT，則對任意β階正定對稱矩陣P，有

證明 1)利用Rayleigh－Ritz定理［19］，有

2) 根據(jù)結(jié)論 1)，有 Cond(H－1ZPZTH－T) ≤ Cond(P)Cond(H－1ZZTH－T)，由 ZZT=HHT，有Cond(H－1ZZTH－T)=1，所以結(jié)論成立.證畢.

定義2如果Z∈Rα×β，β≥α，ZZT可逆，則稱滿足ZZT=HHT的可逆矩陣H為屬于Z的去病因子.

若病態(tài)矩陣A病態(tài)結(jié)構(gòu)中，病態(tài)主體ZPZT是正定對稱的， ZPZT＞＞ Q ，Z，ZT是病態(tài)因子，可逆矩陣H為屬于Z的去病因子，則根據(jù)命題1結(jié)論2)，A≈ZPZT，Cond(H－1AH－T)≈Cond(H－1ZPZTH－T)≤Cond(P).上述分析說明去病因子H可以將病態(tài)主體的條件數(shù)降為P條件數(shù)，相當(dāng)于消除了病態(tài)因子的作用.

1.3 特殊的病態(tài)因子和去病因子及其性質(zhì)

為方便起見，記In為n階單位矩陣，0n為n維零向量的第i個列向量則可以直接驗(yàn)證得到下面的命題2～3.

命題2［20］

命題3任意n階對稱矩陣B=(bi，j)n都可以寫成其中:

命題2說明，Un是病態(tài)因子，Ln是Un的去病因子.

2 兩點(diǎn)邊值問題網(wǎng)格方程的病態(tài)結(jié)構(gòu)

2.1 兩點(diǎn)邊值問題Lagrange有限元方程的病態(tài)結(jié)構(gòu)

使用有限元方法，求解積分形式的兩點(diǎn)邊值問題［21］

將［a，b］剖分成m+1個小區(qū)間，每個小區(qū)間內(nèi)k－1個信息點(diǎn)，取k次Lagrange形函數(shù)，則根據(jù)問題(4)的有限元離散格式［21］，得到問題(4)的有限元方程［16］

其中:P是m階塊對角矩陣，第i個塊Pi=(p(s，i)t)k是k階正定對稱矩陣;Q是對角矩陣; P ＞＞ Q ，Z=k=2時為文獻(xiàn)［17］的情形，k=3時為文獻(xiàn)［18］的情形.根據(jù)命題1～2和定義1可知，式(5)表達(dá)了A的病態(tài)結(jié)構(gòu)，ZPZT是A的病態(tài)主體，Z，ZT分別是A的左、右病態(tài)因子，H=Ln為方程(5)中Z的去病因子.

2.2 兩點(diǎn)邊值問題有限差分方程的病態(tài)結(jié)構(gòu)

使用有限差分方法，求解兩點(diǎn)邊值問題［21］

得到差分格式

根據(jù)差分格式(7)，易得到下列命題4

命題4問題(6)有如下的差分方程

3 兩點(diǎn)邊值問題網(wǎng)格方程的病態(tài)機(jī)理與去病因子

在方程(5)、(8)中，病態(tài)結(jié)構(gòu)類似，有相同的病態(tài)因子以及對應(yīng)的去病因子.ZPZT，ZP^ZT是網(wǎng)格方程的病態(tài)主體對網(wǎng)格方程的病態(tài)影響很小.

定義3稱病態(tài)因子Z表達(dá)的病態(tài)為原發(fā)病態(tài)表達(dá)的病態(tài)為繼發(fā)病態(tài).

4 網(wǎng)格方程的預(yù)處理及其效果分析

僅討論方程(5)的預(yù)條件子，k=1時即為方程(8)的預(yù)條件子，方程(8)中相當(dāng)于方程(5)的的不對稱性，不影響預(yù)處理過程與效果.根據(jù)命題3，易驗(yàn)證下列命題5.

命題5對于式(5)，有其中:是m階塊對角矩陣，第i個塊分別記為ˇ

上述預(yù)處理方法是文獻(xiàn)［17－18］方法的推廣.k=1時即為方程(8)的情形，k=2時為文獻(xiàn)［17］的方法，k=3時為文獻(xiàn)［18］的方法.對于方程(10)，可以取迭代式為u″(k+1)=d″－Ru″(k)，在該式的求解中，無需計(jì)算R，每個迭代步，只要一次R與向量的乘積計(jì)算，O(kn)次計(jì)算操作，與一般的迭代法相當(dāng).方程(9)～(10)的系數(shù)矩陣主體仍然是正定對稱矩陣，可以使用經(jīng)典Krylov子空間方法——共軛梯度法求解，即為預(yù)處理共軛梯度法［2］，其中主要的計(jì)算操作仍然是R與向量的乘積，所以計(jì)算量幾乎沒有增加.

5 結(jié)論

基于結(jié)構(gòu)分析的策略，研究兩點(diǎn)邊值問題網(wǎng)格方程的病態(tài)機(jī)理和預(yù)處理原理，結(jié)論如下:

1)對于不同兩點(diǎn)邊值問題，使用不同的離散方法形成不同的網(wǎng)格方程.這些網(wǎng)格方程隱藏著類似的病態(tài)結(jié)構(gòu)和相同的病態(tài)因子，病態(tài)因子表達(dá)了主要的病態(tài)——原發(fā)病態(tài)，而次要的病態(tài)——繼發(fā)病態(tài)則因具體問題、具體方法的不同而不同，針對病態(tài)因子，可以找到去病因子，使用去病因子作為預(yù)條件子的重要部分，可消除病態(tài)因子的作用，即消除原發(fā)病態(tài).

2)文獻(xiàn)［17－18］中的網(wǎng)格方程，與本研究兩種網(wǎng)格方程有相同的病態(tài)因子，因此相應(yīng)的去病因子也相同，這說明作為預(yù)條件子主要部分的去病因子，是預(yù)條件子中可以通用的部分.

3)使用去病因子進(jìn)行預(yù)處理后，網(wǎng)格方程的條件數(shù)，幾乎與網(wǎng)格方程的階數(shù)無關(guān)，因此去病因子是最優(yōu)預(yù)條件子［4］.

4)使用去病因子進(jìn)行預(yù)處理，不明顯增加計(jì)算成本，也不改變網(wǎng)格方程的正定對稱性.

綜上所述，通過結(jié)構(gòu)分析，發(fā)現(xiàn)病態(tài)結(jié)構(gòu)和病態(tài)因子，確定原發(fā)病態(tài)和繼發(fā)病態(tài)，有針對性地設(shè)計(jì)出最優(yōu)的、通用的預(yù)條件子，可以有效地解決病態(tài)問題.