九對(duì)角線性方程組的追趕法

鄭茂波

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

九對(duì)角線性方程組的追趕法

鄭茂波

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

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

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

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

1 算法的推導(dǎo)

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

(1)

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

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

A=LU[3]

(2)

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

(3)

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

(4)

容易證明矩陣A非奇異當(dāng)且僅當(dāng)αi≠0，i=1,2,…,n。因此，當(dāng)A非奇異時(shí)可以實(shí)現(xiàn)矩陣A的LU分解。從而原方程(1)等價(jià)于下面2個(gè)方程關(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ì)蔬菜專家工作站”的試驗(yàn)基地設(shè)在裕農(nóng)公司沽源生產(chǎn)基地，是北京市農(nóng)林科學(xué)院在京津冀地區(qū)合作共建的首批專家工作站之一。該工作站旨在結(jié)合張家口壩上地區(qū)農(nóng)業(yè)生產(chǎn)現(xiàn)狀，以生菜等葉類蔬菜為重點(diǎn)，以規(guī)?；G色生產(chǎn)為主題，通過產(chǎn)學(xué)研合作新模式，推行水肥高效管理、生態(tài)調(diào)控、生物防治、土壤修復(fù)等方面亟需的相關(guān)科技支撐，提升沽源蔬菜產(chǎn)業(yè)的競爭力，保障環(huán)京地區(qū)集約化種植業(yè)的健康發(fā)展。授牌儀式后，魯西集團(tuán)特種肥北方公司畢景龍總監(jiān)做了關(guān)于液體肥使用及發(fā)展的相關(guān)學(xué)術(shù)報(bào)告，與參會(huì)人員就相關(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 運(yùn)算量和內(nèi)存的估計(jì)

2.1 運(yùn)算量的估計(jì)

表1 用追趕法求解的運(yùn)算量估計(jì)

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

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

如表1所示，用追趕法求解n階九對(duì)角線性方程組大約共需要23n個(gè)乘法和19n個(gè)加法，其運(yùn)算量級(jí)完全是線性的，為O(23n)。而大家熟知的高斯消元法的運(yùn)算量是O(n3/3)?？梢姰?dāng)n較大時(shí)，追趕法的運(yùn)算量比高斯消元法少。

2.2 內(nèi)存的估計(jì)

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

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

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

[7] 李欣.一類順序主子式全為正的三對(duì)角矩陣[J].攀枝花學(xué)院學(xué)報(bào),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è)學(xué)院科研項(xiàng)目“模具壽命預(yù)估研究”(KY1211007B)

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

O241.6

A

2095-5383(2013)02-0026-03