求解病態(tài)線性方程組的自動(dòng)控制步長法

李雪芳，王希云

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024)

關(guān)于病態(tài)線性方程組的求解方法有很多，主要分為直接法和迭代法。近幾年出現(xiàn)的直接法主要有:誤差轉(zhuǎn)移法[1]、增廣方程組法[2]等;常見的迭代法有:有殘差校正迭代法[3]、Wilkinson 迭代法[4]等。

Wilkinson迭代改善是解病態(tài)線性方程組，提高解的精度的一個(gè)重要方法。楊曙光在1989年將Wilkinson迭代改善推廣得到了一種定向擾動(dòng)法[5];吳新元在2002年提出了步長h≡1的Wilkinson迭代法[6]來求解病態(tài)線性方程組，其迭代格式為:

由于上述固定步長的求解方法所產(chǎn)生的解不是很理想，因此吳新元于2007年將一階歐拉公式和二階梯形法則相結(jié)合，提出了一種自動(dòng)控制步長的Wilkinson 迭代法[7]，其迭代形式為:

本文在此基礎(chǔ)上，將一階歐拉公式和二階R-K格式相結(jié)合，構(gòu)造了一種自動(dòng)控制步長的迭代格式，證明了該迭代格式的收斂性，通過數(shù)值實(shí)驗(yàn)結(jié)果，對所得誤差做出了分析。

1 一種嵌入式的新的迭代形式

將一階歐拉公式和二階R-K方法結(jié)合起來，給出一種新的迭代形式。

一階歐拉公式:

二階R-K公式:

(4)式也可以等價(jià)地記為:

也就是說給定一個(gè)初始的步長，可以得到迭代形式為:

由于ˉxn+1比xn+1的階低，因此步長h滿足這樣的條件:

其中ε為精度要求，h為當(dāng)前步長。若s＜0.75，折半步長;若s＞1.5，加倍步長。

2 迭代形式的收斂性

如果hn=h是一個(gè)常量，則迭代形式(5)就是一個(gè)線性平穩(wěn)的迭代形式，可以寫成如下的形式:

其中E為單位矩陣。

此時(shí)迭代形式為:

定理1 如果hn=h＞0是一個(gè)常量，則迭代形式(8)是收斂的。

證明:很明顯。如果hn=h是一個(gè)常量，且h＞0，則迭代形式(5)為迭代形式(8)，形式(8)的迭代矩陣G的譜半徑為:

則 ρ(G) ＜ 1.

則由收斂的條件知:迭代形式(8)為收斂的。

如果hn不是一個(gè)常量，即hn是一個(gè)變量，仍可證得迭代形式(5)是收斂的。

則迭代形式(5)收斂當(dāng)且僅當(dāng)

定理2說明:即使步長hn隨著n的改變在變化，迭代形式(5)仍然是收斂的。

3 數(shù)值實(shí)驗(yàn)及分析

例1典型的病態(tài)線性方程組Ax=b，其中系數(shù)矩陣A=(aij)12×12為m ×m階的Hilbert矩陣，

表1 例1的數(shù)值實(shí)驗(yàn)結(jié)果Tab.1 Numerical results of Example 1

由表1所得:在迭代次數(shù)較小的時(shí)候，已經(jīng)收斂，而且迭代收斂時(shí)的誤差也很小。

表2 例2的數(shù)值實(shí)驗(yàn)結(jié)果Tab.2 Numerical results of example 2

由表2所得:當(dāng)矩陣維數(shù)較大時(shí)，采用該迭代格式求解，仍可得到有效的解，而且所求誤差較小。

表3 數(shù)值實(shí)驗(yàn)結(jié)果比較Tab.3 Comparison of numerical results

由表3可得:本文所構(gòu)造的迭代格式在求解病態(tài)線性方程組時(shí)，所產(chǎn)生的誤差較小。

4 結(jié)論

本文主要在分析了Wilkinson迭代法的基礎(chǔ)上，提出了一種自動(dòng)控制步長的迭代格式，理論上證明了該迭代格式的收斂性，并通過數(shù)值實(shí)驗(yàn)對該迭代格式的收斂性進(jìn)行了驗(yàn)證，而且所得解與精確解的誤差非常小。因此，文中提出的算法是用來求解病態(tài)線性方程組的一個(gè)有效方法。

[1]胡勝榮，羅錫文.病態(tài)線性方程組的新解法:誤差轉(zhuǎn)移法[J].華南農(nóng)業(yè)大學(xué)學(xué)報(bào)，2001，22(4):92-94.

[2]胡勝榮，羅錫文.病態(tài)線性方程組新解法:增廣方程組法[J].華南農(nóng)業(yè)大學(xué)學(xué)報(bào)，2009，30(1):119-121.

[3]顏慶津.數(shù)值分析[M].北京:北京航空航天大學(xué)出版社，1999.

[4]WILKINSON J.數(shù)字計(jì)算機(jī)上用的數(shù)字方法[M].上海:上海人民出版社，1975.

[5]楊曙光.Wilkinson迭代改善的推廣—定向擾動(dòng)法[J].應(yīng)用數(shù)學(xué)，1989(1):37-46.

[6]WU Xinyuan，SHAO Rong，ZHU Yaran.Iterative Improvement of a solution for an Ill-Conditioned System of Linear Equations Based on a Linear Dynamic System [J].Computers and Mathematics with Applications，2002，44:1109-1116.

[7]WU Xinyuan，F(xiàn)ANG Yonglie.Wilkinson’s iterative refinement of solution with automatic step-size control for linear system of equations[J].Applied Mathematics and Computation，2007，193:506-513.

[8]朱華，王希云.一種無約束優(yōu)化問題的譜共軛梯度法[J].太原科技大學(xué)學(xué)報(bào)，2010，31(3):245-248.