第八章 線性方程組迭代法

1、引言引言n直接法是通過有限步運(yùn)算后得到線性方程組的解直接法是通過有限步運(yùn)算后得到線性方程組的解, ,對(duì)于階數(shù)不高的方程組，直接法非常有效，對(duì)于對(duì)于階數(shù)不高的方程組，直接法非常有效，對(duì)于階數(shù)高，而系數(shù)矩陣稀疏的線性方程組卻存在著階數(shù)高，而系數(shù)矩陣稀疏的線性方程組卻存在著困難，在這類矩陣中，非零元素較少，若用直接困難，在這類矩陣中，非零元素較少，若用直接法求解，就要存貯大量零元素。為減少運(yùn)算量、法求解，就要存貯大量零元素。為減少運(yùn)算量、節(jié)約內(nèi)存，使用節(jié)約內(nèi)存，使用迭代法迭代法更有利。更有利。n線性方程組的迭代法主要有線性方程組的迭代法主要有JacobiJacobi迭代法、迭代法、SeidelSei

2、del迭代法和超松弛迭代法和超松弛( (SOR)SOR)迭代法迭代法. .迭代法的基本思想迭代法的基本思想gBxxbAx ( (矩陣矩陣B B不唯一不唯一) )對(duì)應(yīng)寫出對(duì)應(yīng)寫出 )0()()1( ), 2 , 1 , 0( xkgBxxkk取定初始向量產(chǎn)生向量序列產(chǎn)生向量序列,)1()()2()1( kkxxxx若收斂若收斂, ,記記xxkk )1(lim兩端取極限有：兩端取極限有：, gxBx 注意注意: : 迭代陣迭代陣B B不唯一不唯一, ,影響收斂性。影響收斂性。B B叫迭代矩陣。叫迭代矩陣。 x上式說明：上式說明： 是解向量是解向量 , ,從而當(dāng)從而當(dāng)k k充分大時(shí)充分大時(shí) )1(k

3、x 解向量解向量xx 例：若給出解例：若給出解 的迭代公式為的迭代公式為bAx 1 , 0),()()()1(kbxAxxkkk則其迭代矩陣為（則其迭代矩陣為（ ）AI例：用迭代法解線性方程組例：用迭代法解線性方程組352322121xxxx解：構(gòu)造方程組的等價(jià)方程組解：構(gòu)造方程組的等價(jià)方程組3423212211xxxxxx據(jù)此建立迭代公式據(jù)此建立迭代公式3423)(2)(1)1(2)(2)(1)1(1kkkkkkxxxxxx取取 ，計(jì)算得，計(jì)算得0)0(2)0(1 xx33)1(2)1(1xx33)2(2)2(1xx99)3(2)3(1xx1515)4(2)4(1xx3333)5(2)5(1

4、xx可見該迭代不收斂可見該迭代不收斂因此，迭代法的關(guān)鍵包括以下因此，迭代法的關(guān)鍵包括以下兩方面：兩方面：（1 1）如何構(gòu)造迭代格式）如何構(gòu)造迭代格式（2 2）由迭代格式產(chǎn)生的向量）由迭代格式產(chǎn)生的向量序列的收斂性如何序列的收斂性如何nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111雅克比（雅克比（Jacobi）迭代法）迭代法設(shè)有設(shè)有n階方程組階方程組若系數(shù)矩陣非奇異，且若系數(shù)矩陣非奇異，且 (i = 1, 2, n)，將方程組改寫成將方程組改寫成0iia11,22112323121222213132121111111nnnnnnnnnnnnn

5、xaxaxabaxxaxaxabaxxaxaxabax然后寫成迭代格式然后寫成迭代格式)(11,)(22)(11)1()(2)(323)(121222)1(2)(1)(313)(212111)1(1111knnnknknnnnknknnkkkknnkkkxaxaxabaxxaxaxabaxxaxaxabax上式也可以簡(jiǎn)單地寫為上式也可以簡(jiǎn)單地寫為), 2, 1(1)(1)1(nixabaxkjnijjijiiiki寫成寫成矩陣形式矩陣形式：A =LUDBgJacobi 迭代陣迭代陣bDxULDxkk1)(1)1()( bxULxDbxULDbxA )()(bDxULDx11)( )(11)(1

6、)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 只存一組向量即可。只存一組向量即可。寫成寫成矩陣形式矩陣形式：bDxUxLDxkkk1)()1(1)1()( bxUxLDkk )()1()(bLDxULDxkk1)(1)1()()( BgGauss-Seidel 迭代

7、陣迭代陣高斯高斯賽得爾賽得爾(Gauss-Seidel)迭代法迭代法解：解： jacobijacobi迭代法的迭代公式為迭代法的迭代公式為1 , 04/ )122(11/ )334(8/ )2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kxxxxxxxxxkkkkkkkkk前前3 3個(gè)迭代值為個(gè)迭代值為例：分別用例：分別用jacobijacobi迭代法和迭代法和G-SG-S迭代法解線性方程組迭代法解線性方程組12423311420238321321321xxxxxxxxx以以 為初始向量，計(jì)算前為初始向量，計(jì)算前3 3個(gè)迭代值，并與精確解個(gè)迭代值，并與精確解 作比較。作

8、比較。Tx)0 , 0 , 0()0(T) 1 , 2 , 3(Tx)0000. 3 ,0000. 3 ,5000. 2()1(Tx)0000. 1 ,3636. 2 ,8750. 2()2(Tx)97159. 0 ,0455. 2 ,1364. 3()3(G-SG-S迭代法的迭代公式為迭代法的迭代公式為1 , 04/ )122(11/ )334(8/ )2023()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kxxxxxxxxxkkkkkkkkk前前3 3個(gè)迭代值為個(gè)迭代值為Tx)2273. 1 ,0909. 2 ,5000. 2()1(Tx)0043. 1 ,0289.

9、 2 ,9772. 2()2(Tx)9959. 0 ,9968. 1 ,0098. 3()3(方法優(yōu)缺點(diǎn)討論方法優(yōu)缺點(diǎn)討論由以上例題的求解過程可明顯看出由以上例題的求解過程可明顯看出GSGS迭代法迭代法的收斂速度比簡(jiǎn)單迭代法快，但對(duì)于任意給定的收斂速度比簡(jiǎn)單迭代法快，但對(duì)于任意給定的一個(gè)方程組分別用簡(jiǎn)單迭代法和的一個(gè)方程組分別用簡(jiǎn)單迭代法和GSGS迭代法求迭代法求解時(shí)，兩種迭代法可能都收斂，也可能都不收解時(shí)，兩種迭代法可能都收斂，也可能都不收斂也有可能是斂也有可能是GSGS迭代法收斂而迭代法收斂而J J迭代法不收斂迭代法不收斂但亦有相反情況，即簡(jiǎn)單迭代法收斂而但亦有相反情況，即簡(jiǎn)單迭代法收斂而

10、GSGS迭迭代法不收斂而且交換方程組中的方程和未知代法不收斂而且交換方程組中的方程和未知數(shù)的次序都會(huì)影響數(shù)的次序都會(huì)影響GSGS迭代法的計(jì)算結(jié)果，但這迭代法的計(jì)算結(jié)果，但這種交換對(duì)簡(jiǎn)單迭代法是沒有影響的。種交換對(duì)簡(jiǎn)單迭代法是沒有影響的。 例：設(shè)方程組為例：設(shè)方程組為3103220241225321321321xxxxxxxxx試分別寫出其試分別寫出其JacobiJacobi迭代格式和迭代格式和SeidelSeidel迭代格式以及相應(yīng)的迭代矩陣。迭代格式以及相應(yīng)的迭代矩陣。 解：解：JacobiJacobi迭代格式為迭代格式為103)(2103)(151)(2)(1101)1(3)(321)(1

11、41)(3)(141)1(2512)(351)(252)(3)(251)1(1)323(5220()212(kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx故故JacobiJacobi迭代矩陣為迭代矩陣為 0001035121415152SeidelSeidel迭代格式為迭代格式為103)1(2103)1(151)1(3)(321)1(141)1(2512)(351)(252)1(15kkkkkkkkkxxxxxxxxx即即1021)(381)(2201)1(3522)(32011)(2101)1(2512)(351)(252)1(1.kkkkkkkkkxxxxxxxxx故可得故可

12、得SeidelSeidel迭代矩陣為迭代矩陣為 8120120111015152000 從例中可以看出從例中可以看出JacobiJacobi迭代矩陣迭代矩陣BjBj的主對(duì)角線為零，而的主對(duì)角線為零，而SeidelSeidel迭代矩迭代矩陣陣BsBs的第的第1 1列都是零，這對(duì)一般情況也是成立的。列都是零，這對(duì)一般情況也是成立的。超松馳法超松馳法)(1)1(11)1(1kjnijijkjijijiiikixaxabax), 2, 1()1 (1)()1(nixxxkikiki)(1)1(11)()1()1 (kjnijijkjijijiiikikixaxabaxx迭代迭代加速加速是松馳因子是松馳

13、因子 20迭代法的收斂條件迭代法的收斂條件定理定理1：對(duì)任意初始向量對(duì)任意初始向量X(0)及常向量及常向量F，迭代格式迭代格式FBXXkk )1(定理定理2：若迭代矩陣若迭代矩陣的的某種范數(shù)某種范數(shù) 則上式則上式1B收斂的充分必要條件是迭代矩陣收斂的充分必要條件是迭代矩陣B B的譜半徑的譜半徑 (B) 1。確定的迭代法對(duì)任意初值確定的迭代法對(duì)任意初值X(0)均收斂于方程組均收斂于方程組X = BX + F的唯一解的唯一解x*。 定義定義：如果矩陣的每一行中如果矩陣的每一行中，不在主對(duì)角線上的所有不在主對(duì)角線上的所有 元素絕對(duì)值之和小于主對(duì)角線上元素的絕對(duì)值元素絕對(duì)值之和小于主對(duì)角線上元素的絕對(duì)

14、值， 即即niaaiinijjij, 2, 11則稱矩陣則稱矩陣A按行嚴(yán)格對(duì)角占優(yōu)按行嚴(yán)格對(duì)角占優(yōu)，類似地類似地，也有按列也有按列嚴(yán)格對(duì)角占優(yōu)。嚴(yán)格對(duì)角占優(yōu)。定理定理3：若線性方程組若線性方程組AX = b的系數(shù)矩陣的系數(shù)矩陣A按行嚴(yán)格對(duì)角按行嚴(yán)格對(duì)角 占優(yōu)占優(yōu)，則雅克比迭代法和高斯則雅克比迭代法和高斯賽得爾迭代法賽得爾迭代法 對(duì)任意給定初值均收斂對(duì)任意給定初值均收斂。 例：設(shè)方程組為例：設(shè)方程組為23 . 0122121xxxx試討論用試討論用JacobiJacobi迭代法和迭代法和SeidelSeidel迭代法求解此方程組的收斂性。迭代法求解此方程組的收斂性。 解：解：JacobiJacobi迭代格式為迭代格式為23 . 012)(1)1(2)(2)1(1kkkkxxxx故故JacobiJacobi迭代矩陣為迭代矩陣為 03 . 020其特征值為其特征值為 6 . 0故其譜半徑為故其譜半徑為 16 . 0故故JacobiJacobi迭代法收斂迭代法收斂SeidelSeidel迭代格式為迭代格式為2) 12(3 . 012)(2)1(2)(2)1(1kkkkxxxx故故G-S