張衡,鄭漢垣
(1. 福建技術(shù)師范學(xué)院 a.無損檢測技術(shù)福建省高等學(xué)校重點實驗室;b.電子與信息工程學(xué)院,福建福清350300;2.龍巖學(xué)院傳播與設(shè)計學(xué)院,福建龍巖364012)
大規(guī)模病態(tài)(高條件數(shù))稀疏線性方程組常常來自偏微分方程大規(guī)模數(shù)值求解問題[1,2],該方程組的條件數(shù)往往隨著問題規(guī)模的增加而增加[3],成為求解效率和精度的制約因素,因此,在迭代求解之前,使用預(yù)處理方法來減少方程組的病態(tài),成為提高求解效率和精度的必要措施.“預(yù)處理技術(shù)”是指在求解方程組
預(yù)條件子的構(gòu)造一直是難題,對病態(tài)問題缺乏科學(xué)研究是主要原因之一.目前關(guān)于病態(tài)機理和預(yù)處理原理的研究鮮見有成果發(fā)表.
文獻[6]針對二維泊松方程邊值問題的五點差分方程,研究了病態(tài)結(jié)構(gòu)和病態(tài)因子,提出用去病因子消除原發(fā)病態(tài)的方法.文章研究二維泊松方程邊值問題九點差分方程的病態(tài)問題,基于結(jié)構(gòu)分析的策略[6-9],研究病態(tài)結(jié)構(gòu),分離出該方程的病態(tài)因子、給出去病因子.通過與五點差分方程比較,說明去病因子的通用性.
1.1 病態(tài)因子和去病因子
定義1 設(shè)β>α,α,β是整數(shù),Z 是α×β矩陣,如果ZZTT可逆,Cond(Z ZTT)是階數(shù)α的增函數(shù).則Z 稱為α×β病態(tài)因子.
定義2 對于定義1中α×β的病態(tài)因子Z ,如果有可逆矩陣H 滿足:ZZT=HHT,則稱矩陣H 為屬于Z的去病因子[6].
命題1[6]設(shè)Z 是α×β病態(tài)因子,矩陣H 為屬于Z 的去病因子,則對于任意β階正定對稱矩陣P,有
1.2 矩陣的病態(tài)結(jié)構(gòu)
定義3 稱可逆矩陣A的如下結(jié)構(gòu)為病態(tài)結(jié)構(gòu):
在定義3中,ZPZTT為A 的主體,所以Cond(A) ≈ Cond(Z PZT).Q對 病 態(tài)的影響很小.
定義4 在定義3中,由病態(tài)因子表達的病態(tài)稱為原發(fā)性病態(tài),其他因素表達的病態(tài)稱為繼發(fā)性病態(tài).
1.3 基于病態(tài)結(jié)構(gòu)的預(yù)處理
如果A有(3)式的病態(tài)結(jié)構(gòu),則根據(jù)命題1結(jié)論1),可以利用病態(tài)因子的條件數(shù),估計方程組的病態(tài);根據(jù)命題1結(jié)論2),屬于Z的去病因子H可以抑制或者消除的作用,即消除原發(fā)性病態(tài).
事實上,如果A具有(3)式的病態(tài)結(jié)構(gòu),使用去病因子H作為預(yù)條件子,則方程(1)化成
因為Cond(P)關(guān)于A的階數(shù)一致有界,因此,HHTT是最優(yōu)預(yù)條件子[5].
綜上所述,提出如下基于病態(tài)結(jié)構(gòu)的預(yù)處理策略:
1)通過結(jié)構(gòu)分析,分離出病態(tài)因子,確定病態(tài)結(jié)構(gòu);
2)針對病態(tài)因子,確定去病因子;
3)去病因子是最優(yōu)預(yù)條件子.
注1:不同的分析方法,可能得到不同的病態(tài)因子,同一個病態(tài)因子,也可以有不同的去病因子;病態(tài)因子的選擇,應(yīng)有利于計算條件數(shù)和得到去病因子,去病因子的選擇,應(yīng)有利于降低預(yù)處理成本.
基于病態(tài)結(jié)構(gòu)的預(yù)處理策略,是針對病因的,病態(tài)因子就是病因,去病因子可以抑制病因發(fā)作.與此相比,以往的預(yù)處理方法主要是針對病癥而不是病因,所以效果有限,難以通用.
依據(jù)上述預(yù)處理策略,確定病態(tài)因子和去病因子是預(yù)處理的關(guān)鍵,本文將針對二維泊松
使用有限差分方法,求解二維泊松方程邊值問題[4]91-98
2.1 非均勻網(wǎng)格的有限差分格式則
根據(jù)4階精度的泰勒展開式,有
2.2 非均勻網(wǎng)格的有限差分方程
容易驗證,由格式(6)確定的差分方程為
則向量uyx由邊界條件和邊界上的網(wǎng)格點確定,是已知的;格式(7)的矩陣形式如下
因此容易驗證,由格式 (7)確定的差分方程為
3.1 兩個病態(tài)因子及其去病因子
證明:1)驗證即可;
證明:直接驗證.證畢
命題5.
命題 5說明Zt是病態(tài)因子,命題 4說明Ht是Zt的去病因子,t∈{5,9}.
3.2 有限差分方程的病態(tài)結(jié)構(gòu)與去病因子
3) 根據(jù)命題1的結(jié)論2)可得.證畢.
命題 5和 6結(jié)論 1)和 2)說明:式 (12)、(13)表達了At的病態(tài)結(jié)構(gòu),Zt是At的病態(tài)因子;命題 4說明:Ht是Zt的去病因子;命題 6結(jié)論3)說明:Ht是最優(yōu)預(yù)條件子.
上述差分方程(9)、(11)都有(3)式的病態(tài)結(jié)的主要病態(tài)來自微分算子,病態(tài)因子是這些病態(tài)的表達,而去病因子則可以抑制或者消除這些病態(tài).
基于病態(tài)結(jié)構(gòu)的預(yù)處理策略是針對病因的,可以從根本上解決病態(tài)的主要問題.
病態(tài)因子及其去病因子有簡單、確定、獨立的結(jié)構(gòu),病態(tài)因子及其去病因子可以因數(shù)值方法的不同而有不同的形式,但是病態(tài)結(jié)構(gòu)是類似的.
文獻 [6]給出的差分方程與方程 (9)是 2階精度的不同差分格式得到的不同的差分方程,有類似的病態(tài)結(jié)構(gòu),病態(tài)因子完全相同,因此去病因子也通用.
由命題1結(jié)論1),結(jié)論成立.證畢.
命題7 結(jié)論1)、2)分別說明,H9,H5可以作為方程(9)、(11)的預(yù)條件子,仍然是最優(yōu)預(yù)條件子,所以H9,H5是通用的預(yù)條件子.
5.1 二維泊松方程邊值問題有限差分網(wǎng)格方程的原發(fā)性病態(tài),是微分算子造成的,差分方程的結(jié)構(gòu)中包含表達這種病態(tài)的病態(tài)因子.基于病態(tài)結(jié)構(gòu)的預(yù)處理策略,是針對這種病因的所采取的方法,可以從根本上抑制病態(tài),并且使用的預(yù)條件子具有通用性.
5.2 與以往的預(yù)處理方法比較,基于病態(tài)結(jié)構(gòu)的預(yù)處理策略,針對性強(針對病態(tài)因子),目標和效果明確(消除原發(fā)性病態(tài),控制繼發(fā)性病態(tài)),方法具有通用性.
5.3 病態(tài)因子和去病因子有稀疏、獨立的結(jié)構(gòu),因此在預(yù)處理中,無須專門的存儲,易于編程,不顯著增加計算復(fù)雜度.
5.4 去病因子不唯一,而且是通用的,有利于根據(jù)實際問題和計算環(huán)境的具體需要(如并行計算等的需要),靈活設(shè)計.