鄭茂波

(成都工業(yè)學院 信息與計算科學系，成都 610031)

九對角線性方程組的追趕法

鄭茂波

(成都工業(yè)學院 信息與計算科學系，成都 610031)

通過矩陣的分解，利用三對角線性方程組追趕法思想，推導(dǎo)出九對角線性方程組的追趕法。理論推導(dǎo)表明：對于九對角線性方程組的求解，該算法運算量和存儲量均為線性量級。數(shù)值實驗表明: 該算法比高斯消去法和其他一些迭代法有明顯的速度和內(nèi)存優(yōu)勢，極大地提高了線性方程的求解速度。

九對角矩陣;線性方程組;追趕法;對角占優(yōu)

在現(xiàn)代科學與工程計算領(lǐng)域，線性方程組的求解極為重要[1-2]。幾乎有效的數(shù)值方法，最終都歸結(jié)于求解線性方程組。通過矩陣分解引出的追趕法[3-7]是求解線性方程組的有效方法。九對角線性方程組當其階數(shù)較大時，雖然用其他解法(比如常見的高斯消元法，LU分解等)也可實現(xiàn)，但是精度和速度都不夠理想。本文在三對角線性方程組追趕法的研究基礎(chǔ)上，推導(dǎo)出針對九對角線性方程組的快速追趕算法，速度和精度都有較大提高，并用數(shù)值算例進行了驗證。

1 算法的推導(dǎo)

設(shè)有九對角線性方程組

(1)

簡記為Ax=h。其中A為非奇異的九對角帶狀矩陣，系數(shù)滿足丨i-j丨gt;4時，aij=0，特別地，當

時，A為對角占優(yōu)矩陣，利用三角分解，將矩陣A分解為2個三角矩陣的乘積。

A=LU[3]

(2)

其中:L為下三角陣，U為上三角陣，具體如下：

(3)

根據(jù)式(1)～(3)，利用矩陣乘法，比較等式兩邊的對應(yīng)元素有：

(4)

容易證明矩陣A非奇異當且僅當αi≠0，i=1,2,…,n。因此，當A非奇異時可以實現(xiàn)矩陣A的LU分解。從而原方程(1)等價于下面2個方程關(guān)于x求解：

Ly=h

(5)

Ux=y

(6)

首先，用以下的遞推式求出待定系數(shù)：

α1=c1,β1=d1/α1,q1=e1/α1,n1=f1/α1

v1=ki/αi(i=1,2,…,n-4)

(7)

γ2=b2,α2=c2-γ2β1,β2=(d2-γ2q1)/α2,q2=(e2-γ2n1)/α2

ni=(fi-γivi-1)/αi(i=2,3,…,n-3)

(8)

z3=α3,γ3=b3-z3β1,α3=c3-z3q1-γ3β2,β3=(d3-z3n1-γ3q3)/α3

qi=(ei-zivi-2-γini-1)/αi(i=3,4,…,n-2)

(9)

m4=g4,z4=a4-m4β1,γ4=b4-m4q1-z4β2,α4=c4-m4n1-z4q2-γ4β3

βi=(di-mivi-3-zini-2-γiqi-1)/αi(i=4,5…,n-1)

(10)

ui=ji,mi=gi-uiβi-4,zi=αi-uiqi-4-miβi-3,

γi=bi-uini-4-miqi-3-ziβi-2

αi=ci-uivi-4-mini-3-ziqi-2-γiβi-1(i=5,6,…,n)

(11)

1)設(shè)Ly=h，求y。算法如下：

y1=h1/α1,

y2=(h2-γ2y1)/α2,

y3=(h3-z3y1-γ3y2)/α3,

“沽源優(yōu)質(zhì)蔬菜專家工作站”的試驗基地設(shè)在裕農(nóng)公司沽源生產(chǎn)基地，是北京市農(nóng)林科學院在京津冀地區(qū)合作共建的首批專家工作站之一。該工作站旨在結(jié)合張家口壩上地區(qū)農(nóng)業(yè)生產(chǎn)現(xiàn)狀，以生菜等葉類蔬菜為重點，以規(guī)模化綠色生產(chǎn)為主題，通過產(chǎn)學研合作新模式，推行水肥高效管理、生態(tài)調(diào)控、生物防治、土壤修復(fù)等方面亟需的相關(guān)科技支撐，提升沽源蔬菜產(chǎn)業(yè)的競爭力，保障環(huán)京地區(qū)集約化種植業(yè)的健康發(fā)展。授牌儀式后，魯西集團特種肥北方公司畢景龍總監(jiān)做了關(guān)于液體肥使用及發(fā)展的相關(guān)學術(shù)報告，與參會人員就相關(guān)技術(shù)、資源在沽源地區(qū)規(guī)?；~菜綠色生產(chǎn)的應(yīng)用開展了深入地交流和討論。

y4=(h4-m4y1-z4y2-γ4y3)/α4,

yi=(hi-uiyi-4-miyi-3-ziyi-2-γiyi-1)/αi(i=5,6,…,n)

(12)

2)設(shè)Ux=y，求x。算法如下：

xn=yn

xn-1=yn-1-βn-1xn,

xn-2=yn-2-βn-2xn-1-qn-2xn,

xn-3=yn-3-βn-3xn-2-qn-3xn-1-nn-3xn,

(13)

2 運算量和內(nèi)存的估計

2.1 運算量的估計

表1 用追趕法求解的運算量估計

表2 求解n階九對角(對角占優(yōu)但不對稱)線性方程組示例

表3 求解n階九對角(對角不占優(yōu))線性方程組示例

如表1所示，用追趕法求解n階九對角線性方程組大約共需要23n個乘法和19n個加法，其運算量級完全是線性的，為O(23n)。而大家熟知的高斯消元法的運算量是O(n3/3)。可見當n較大時，追趕法的運算量比高斯消元法少。

2.2 內(nèi)存的估計

由式(1)，存儲n階九對角線性方程組的系數(shù)向量和右端向量需要10n個存儲單元，由式(7)～(11)，計算系數(shù)mi,zi,γi,αi,βi,qi,ni,vi需要8n個存儲單元，由式(12)～(13)計算中間變量y和最終結(jié)果x需要n個存儲單元。所以，求解n階九對角線性方程組總共需要19n個存儲單元。從這個結(jié)果來看，用追趕法解對角方程所需的存儲單元也為線性的。

3 數(shù)值試驗及與其他算法比較

本文用Matlab編程實現(xiàn)九對角線性方程組的求解，用2個例子調(diào)用該函數(shù)進行了試驗，并且將本文的追趕法(febs)與LU分解法(LU)，qr分解法(qr)，最小二乘法(lsqr)，穩(wěn)定雙共軛梯度法(bicgstab)，擬最小殘余法(qmr)，雙共軛梯度法(bicg)，共軛梯度法(cgs)等算法進行了比較。

例1：設(shè)n階九對角線性方程組(1)中的系數(shù)為ai=4，bi=6，ci=30，di=3，ei=5，fi=1，gi=2，ji=1，ki=7，hi=1 000。這個對角方程組是對角占優(yōu)的但是不對稱，用追趕法及以上方法對比試驗，迭代條件為：容忍誤差1e-10或者迭代次數(shù)30次，計算結(jié)果見表2。

例2：設(shè)n階九對角線性方程組(1)中的系數(shù)為ai=0，bi=-1，ci=5，di=2，fi=0，gi=1，ji=2，ki=1，hi=1 000。此方程組對角不占優(yōu)，用追趕法及以上各種方法對比試驗，迭代條件都為：容忍誤差1e-10或者迭代次數(shù)30次，計算結(jié)果見表2。

4 結(jié)語

從理論上看，用追趕法求解n階九對角線性方程組的運算量是線性量級，比其他算法的運算量大為減少，精度也比較好。追趕法對內(nèi)存的需求也很少。數(shù)值試驗表明運算的速度與理論估計基本一致。同時，追趕法有較好的適應(yīng)性，當?shù)ㄐЧ^差時追趕法仍然有比較良好的計算性能。此外，算法也比較容易實現(xiàn)。

[1] 蔡大用,白峰杉.高等數(shù)值分析[M].北京:清華大學出版社,1997.

[2] 李慶揚,王能超,易大義.數(shù)值分析[M].北京:施普格林出版社,2001.

[3] 徐樹方,高立,張平文.數(shù)值線性代數(shù)[M].北京:北京大學出版社，2009.

[4] 王禮廣,蔡放,熊岳山.五對角方程組追趕法[J].南華大學學報:自然科學版,2008,22(1):1-4.

[5] 葉新濤,張志.七對角線性方程組的追趕法[J].紹興文理學院學報,2010,30(10):1-5.

[6] 夏愛生,李長國,胡寶安,等.求解五對角方程組追趕法[J].軍事交通學院學報,2008,10(4):87-89.

[7] 李欣.一類順序主子式全為正的三對角矩陣[J].攀枝花學院學報,2004,21(4):101-104.

Catch-upMethodofNineDiagonalLinearEquations

ZHENGMaobo

(Department of Information and Computing Science, Chengdu Technological University, Chengdu 610031, China)

A catch-up algorithm is derived for solutions of linear equation system with nine diagonal matrix using ones with triune diagonal matrix.It is deduced theoretically that the operational amount and the memory amount of the algorithm are linear. It is shown in the numerical experiments that this method has some advantages in computational cost and memory need evidently. It improves the calculational rates.

nine diagonal matrix;linear equation;catch-up method; diagonal domination

2013-04-02

成都工業(yè)學院科研項目“模具壽命預(yù)估研究”(KY1211007B)

鄭茂波(1984- )，男(漢族)，四川營山人，講師，碩士，研究方向：微分方程數(shù)值解。

O241.6

A

2095-5383(2013)02-0026-03