回歸問題——線性方程組求解的迭代法

1、第六章回歸問題6.1 回歸問題1.1.1 問題的引入在數(shù)理統(tǒng)計中，把研究對象的全體稱為總體，而把組成總體的每個單元稱為個體， 要了解總體的規(guī)律性，必須對其中的個體進行統(tǒng)計觀測。但若對全部個體進行觀測，這樣能對總體有充分的了解，但實際上行不通，而且也不經(jīng)濟。所以對整體進行隨機抽樣觀測，再根據(jù)抽樣觀察的結(jié)果來推斷總體的性質(zhì)成為一種重要的方法。許多數(shù)理統(tǒng)計建模的實際問題中，一個隨機變量與另一個隨機變量的關(guān)系不是線性關(guān)系，而是曲線關(guān)系，那么如何確定回歸方程呢？下表給出了某種產(chǎn)品每件平均單價y（元）與批量x（件）之間的關(guān)系的一組數(shù)據(jù)，試確定y 與 x的函數(shù)關(guān)系。表 6.1.1 已知數(shù)據(jù)x20253035

2、4050606570758090y1.811.701.651.551.481.401.301.261.241.211.201.181.1.2 模型的分析先將表 6.1.1 中的數(shù)據(jù)進行曲線擬合，然后根據(jù)經(jīng)過擬合的曲線形狀確定回歸方程的次數(shù)。用 MATLAB 做出擬合圖如下，由下圖知,可建立二次回歸多項式模型。圖 6.1.1 散點圖1.1.3 模型的假設(shè)假設(shè)上表給出的數(shù)據(jù)是真實的，且以上數(shù)據(jù)是隨機抽取的可以較準確地推斷單位與批量的關(guān)系，假設(shè)單價與批量的函數(shù)關(guān)系是一個多項式函數(shù)，可用多項回歸來建立模型。1.1.4 模型的建立根據(jù)模型的分析，可以建立多項式模型y 01x2x2,N(0, 2)，令 x

3、1 x,x2 x2，則回歸方程可寫成y 01x12x12,N(0, 2)，這是一個二元線性回歸模型。且XTXXTY ，其中：1111111111112025303540506065707580904006259001225160025003600422549005625640081001.181.701.651.551.481.401.301.261.241.211.201.180=126.2 線性方程組迭代法概述迭代法： 即用某種極限過程逐步逼近線性方程組精確解的方法。迭代法具有需要計算機存儲較少、程序設(shè)計簡單、原始系數(shù)矩陣在計算過程中始終不變等優(yōu)點， 但有收斂性或收斂速度的問題。迭代法是解

4、大型稀疏矩陣方程組的重要方法。迭代法能保持矩陣的稀疏性，具有計算簡單、編制程序容易的優(yōu)點，并在許多情況下收斂較快。故能有效地解一些高階方程組。迭代法的基本思想是構(gòu)造一串收斂到解的序列，即建立一種從已有近似解計算新的近似解的規(guī)則。由不同的計算規(guī)則得到不同的迭代法。對線性方程組AX b ， 其中， Aaij n n 非奇異矩陣，b b1 , bn T。構(gòu)造其形如x Mx g 的同解方程組，其中M 為 n階方陣，g Rn。任取初始向量x0 Rn， 代入迭代公式xk 1 Mx k g k 0,1,2, 產(chǎn)生向量序列 x k ，當 k 充分大時，x k 作為方程組AX b 的近似解，這就是求解線性方程組

5、的單步定長線性迭代法。M 稱為迭代矩陣。6.3 迭代法6.3.1 Jacobi 迭代法a11對 Ax b，設(shè) det(A) 0，aii0(i 1 n) (6.3.1) ，將 A改寫成：0 a12a13a1n0a23a2nD L U (6.3.2)an 1,n0a21a22ana31a320an2an,n 1145 / 18又將 A分裂為：A M N ，則 (6.3.1) 等價于 Mx Nx b (6.3.3)其中 M 應(yīng)選擇為一個非奇異陣，并使Mz f 容易求解。對應(yīng) (6.3.3) 可構(gòu)造一個迭代過程：初始向量x(0)，x(k 1) M 1Nx(k) M 1b,(k 0,1, )(6.3.4

6、)特別地，若選取M D ，則 N M A L U ，從而 (6.3.1) 化為：Dx (L U )x b可得： Jacobi 迭代公式：x(0) (初始向量)， x(k 1)Jx(k)f ，其中：J D 1(L U),f D 1b(6.3.5)J 稱為 Jacobi 迭代的迭代矩陣。Jacobi 迭代的分量形式：引進記號：xkx1k , x2k ,xnk T為第 k 次近似，由(6.3.5) 有：x0x10 ,x20 ,xn0 Txik 11aiibinaijxjkj1ji, i 1 n,k 0,1,(6.3.6)Jacobi 迭代公式簡單，由公式(6.3.5), (6.3.6) 可知，每迭代

7、一次只需計算一次矩陣與向量乘法，計算機中只需要兩組工作單元用來保存x(k)及x(k 1)且可用x(k 1) x(k) 來控制迭代終止。由迭代計算公式可知，迭代法一個重要特征是計算過程中原來矩陣A數(shù)據(jù)始終不變。例 6.3.1 用 Jacobi 迭代法求下面線形方程組，其精確解是x* (1,2, 1,1)T：10x1 x2 2x36x1 11x2 x3 x4 252x1 x2 10x3 x4113x2x3 8x4 15解 先將 Ax b 轉(zhuǎn)化為等價方程組：1x110(6 x2 2x3)x2x3x41(25 x1 x3 3x4 )11110( 11 2x1 x2 x4 )1(15 3x2 x3 )8

8、迭代公式：選取初始向量x(0) (0,0,0,0) T ，x1(k 1)x2(k 1)(k 1) x3x4(k 1)1 (6 x2(k) 2x3(k) )101 (25 x1(k)x3(k) 3x4(k) )11,k 0,1,21 ( 11 2x1(k) x(2k)x4(k)1(15 3x2(k) x3(k) )*(10)xx0.0002。經(jīng) 10 次迭代解：x(10) (1.0001,1.9998, 0.9998,0.9998)T ，誤差為：6.3.2 Gauss-Seidel 迭代法在 (6.3.3) 中選取 M D L(下三角陣)，則 N M A U ，從而 (6.3.1)化為等價的：(

9、D L)x Ux b(6.3.7)可得 Gauss-Seidel 迭代公式：初始向量x(0) ， xk 1 Gx k f ，其中1G DLU1(6.3.8)f DLbG 稱 為 Gauss-Seidel 迭 代 矩 陣 。 G-S 迭 代 法 的 分 量 形 式 為 ： 記x kx1k ,x2k ,xnk T ，有迭代公式(6.3.9) ，Tx x1 ,x2 , xn1 i1nxi biaij xjaij xj(6.3.9)aiij 1j i 1i 1n,k 0,1,2,Gauss-Seidel 迭代法每迭代一次只需計算一次矩陣與向量的乘法，但G-S迭代法比Jacobi 迭代法有一個明顯的優(yōu)點

10、，那就是計算機上僅需一組工作單元用來保存x(k)分量(或x(k 1)分量)當計算出x(jk 1)就沖掉舊的分量x(jk)。由G-S迭代公式 (6.3.9) 可看出在x(k)x(k 1)的一步迭代中，計算分量xi(k 1)時利用了已計算出來的新分量x(jk 1)(j 1 i 1)。 因此， G-S迭代法可以看作是Jacobi 迭代法的一個修正。例 6.3.2 用G-S方法解下面方程組，其精確解為：x 1,2, 1,1 T，10x1 x2 2x3 6x1 11x2 x3 3x4 252x1 x2 10x3 x 4113x2 x3 8x415解 由 (6.3.9) 可得本題G-S迭代公式為：x1k

11、11 6 x2k 2x3kx2k 11 25 x1k 1 x3k 3x4k11,k 0,1,2x3k 1111 2x1k 1 x2k 1x4kx4k 11 15 3x2k 1x3k 14823經(jīng) 5 次迭代得：x0(0,0,0,0) T， x51.0001, 2.0000,1.0000, 1.0000 T，x x 50.0001 。從此例可見，G-S 迭代法比Jacobi 迭代法收斂快(初始向量相同，達到同樣精度，所須迭代步數(shù)較少)，但這個結(jié)論對Ax b的矩陣 A滿足某些條件才是對的，甚至有這樣的線性方程組，用Jacobi 方法是收斂的，而用G-S迭代法卻是發(fā)散的。x1 2x2 3x3 1此例

12、用 Jacobi迭代法收斂而G-S迭代法卻發(fā)如線性方程組：x1 x2 x3 12x1 2x2 x31散。 簡要分析如下：1GG D L U(GG) 2 1 ，GJ0 , GJ( J1000D1L U) 。01110000特征方6.3.3 迭代法的收斂性定義 6.3.1 設(shè)有矩陣序列Ak(ai(jk)n n,(k 1,2, )及 A (aij)，如果lkim aijkaij， i, j 1 n 成立，則稱Ak 收斂于 A。記為lkim AkA。1例如，矩陣序列A, A022 02Akkk10kk1 時，k 00Ak00矩陣序列收斂的概念可以用任何矩陣范數(shù)來描述。下面介紹向量、矩陣的范數(shù)定義、常用

13、的范數(shù)形式以及相關(guān)性質(zhì)。定義 6.3.2 (向量范數(shù))如果x Rn的某個實值函數(shù)N(x) |x|， (1) 正定性：|x| 0,|x| 0 x 0 (2) |cx| |c| |x|， c為實數(shù) (3) 三角不等式：|x y| |x| |y| x.y Rn，則稱N(x) |x|為 Rn上的一個向量范數(shù)(或向量。 利用三角不等式容易證明：(4) x y x y在 Rn中，三角不等式即為三角形兩邊長之和大于第三邊長。如下圖：定義633 設(shè)x=(0X2,.xn ) eRn ,定義可上四種常用向量范數(shù)如下:向量的1一范數(shù):向量的8 范數(shù):(3)向量的2范數(shù):1/ f n l|x|2 = (x,x) 2

14、=|E it422XJ向量的p范數(shù):l|x lip = 工 I Xi IIf J1p,P1,+x )易證明：它們均滿足向量范數(shù)定義 6.3.1 ,且前三種向量范數(shù)均為第四種的向量范數(shù)的特例。其中(| xl lim | x|p )P例 6.3.3 設(shè)x=(-123； E 酎計算 HxILIIxILellxlbo|x|=1+2+3=6,|xb= max 1,2,3 =3解1.一|x|b =(f+22 +32 ) 2 =定理631設(shè)非負實值函數(shù)N(x)x|為上任一向量范數(shù)，則N(x)是X分量Xi X2Xn的連續(xù)函數(shù)。定理6.3.2 (范數(shù)等價性)設(shè)|卜|/以|/為川上任意兩種范數(shù)，則存在常數(shù)G 6

15、>0,使得:d|x|s<|x|z<c2|x|s, VxSRn0定理6.3.3 在 山中，lim x)=x* u |x)X* IG 0 ( kT -時)其中為向量 的任一種范數(shù)。定義634 (矩陣的范數(shù))若矩陣AE的某個非負實值函數(shù)N(A)=|A|涉足 條件：正定性：|A廬。且| A|=0J A=0(2)正齊次性:|cA|=|c| |A|, c R1(3) 三角不等式：|A B| |A| |B|(4) |AB | |A| | B |則稱 N A 為上 Rn n的一個矩陣范數(shù)或模。如果將矩陣A看成Rn n向量空間中的元素，則由向量2范數(shù)定義有：n12F A | A |Fai2,

16、j。 這就是矩陣的Frobenius 范數(shù) , 明顯它滿足上面定義。i,j 1在大多數(shù)與估算有關(guān)的問題中，矩陣和向量會同時參與討論，所以希望引進一種矩陣的范數(shù)。它和向量范數(shù)相聯(lián)系且和向量范數(shù)是相容的，即：|Ax| |A| |x|, x Rn, A Rn n定義 6.3.5 (矩陣的算子范數(shù))設(shè)x Rn, A Rn n給出一種向量范數(shù)| x| (如1,2或) ，相應(yīng)地定義一種矩陣的非負函數(shù)：|A| max |Ax| (最大|x| 0 |x|比值) 易驗證： | A| 滿足前一矩陣范數(shù)的定義。因此 | A| 是 Rn n上的一個范數(shù)，稱之為 A的算子范數(shù)。定理 6.3.4 設(shè) |x| 是 Rn上的

17、一個向量范數(shù)，則|A| 是 Rn n上的矩陣范數(shù)，且滿足相容條件：|Ax| |A| |x| 。定理 6.3.5 設(shè) x Rn,A Rn n則：n(1) |A| max |aij | (稱為 A的行范數(shù)) 1in j1 n(2) | A |1 max| aij | (稱為 A的列范數(shù))1jni1(3) |A|2max ATA(稱為 A的2范數(shù))其中 max AT A 表示AT A 的最大特征值。在計算上，(1) ， (2) 比較容易，而(3) 比較困難，但(3) 在理論分析上十分有用。定理 6.3.6lkim AkA充要條件是Ak A 0, k ，我們要考慮迭代法收斂 性 ， 即 要 研 究 B

18、在 什 么 條 件 下 使 誤 差 向 量 趨 于 零 向 量 。 即k x k xBk 00, k定理 6.3.7 設(shè) B (bij )n n， 則 Bk0(零矩陣)， (k )的充要條件是：(B) 1 。定理 6.3.8 (迭代法基本定理)設(shè)有方程組x Bx f ， 對于任意初始向量x(0)及任意 f ， 解此方程組的迭代法(即x(k 1)Bx(k) f ) 收斂的充要條件是：(B) 1 。此定理應(yīng)用時要計算譜半徑，不太方便。將其修改成如下的形式：定理 6.3.9 (迭代法收斂的充分條件)設(shè)有方程組x Bx f ，且 x(k) 為由迭代法產(chǎn)生的序列x(k 1)Bx(k)f ， x(0)為初

19、始任意向量。若迭代矩陣B 的某種范 數(shù)滿足 B q 1 ，則：(1) x(k) 收斂于方程組I B x f 的唯一解x* 。(2) x*x(k) 11xk( 1) xk。()1qk(3) 誤差估計：x x k q x1 x 0 。1q證明 (1) 由于 B q 1 ，即 I B可逆，有唯一解。設(shè)為x ， x Bx f 。引進誤 差 向 量 ek xk x ， 即 得 誤 差 ek 的 遞 推 公 式 ： ek 1 BekBk1e0 ,k 0,1, ， 于是 ek Bke0qke00，k時 e0x0 x。(2) 由迭 代 公 式 有 xk 1 xk B xk xk 1 ， 又 ek1 B ek

20、則xk 1 xk x xk x xk1 x xk x xk 11 q x xk ，即10x1 x2 2x36例 6.3.4 考察用 Jacobi 方法求解線性方程組x1 11x2 x3 x4 25 的收斂2x1 x2 10x3 x4113x2x3 8x4 15性。10121 111解A21100310318101110012800100103102013010則 Jacobi 迭代矩陣為：J D1L U111210011021000111311110011038180J max 3 , 5 , 4 , 41 1. 故解此方程組的Jacobi 方法收斂。10111082k xk xBk 0 ，

21、設(shè) B 有 n 個線性無關(guān)的特征n向量u1, u2un，相應(yīng)的特征值為1，2 n，由 kaiui (線性表示，基)i1nnkBk 0ai Bkuiai ikui 。 可 以 看 出 當 (B) 1 愈 小 時 ，i1i1ik 0 i( 1n 。 (k )愈快，即(k)0愈快，故可用(B)來刻劃迭代法的收斂快慢。現(xiàn)在來確定迭代次數(shù)k ，使 (B) k 10 s，取對數(shù)得：k sln10 。ln (B)定義 6.3.6 稱 R(B) ln ( B)為迭代法的收斂速度。由此可見，(B) 1 愈小，ln (B) 愈大，則所需的迭代次數(shù)就越少。而 n 較大時，矩陣特征值計算比較困難，基本定理的條件比較難

22、驗證，所以最好建立與矩陣元素直接有關(guān)的條件來判斷迭代法的收斂性。由于(B)vB v， 所以可用B v作為(B)v上界的一種估計，這樣的結(jié)果即為迭代法收斂的充分性條件(如上面的定理)。由這個充分性條件的結(jié)果(3) 可見， B q 1 越小，收斂越快。另外，由其結(jié)果(2) 可知：若x(k)x(k 1) 則x* x(k) q 0。因此可以用1qxk xk1 作為控制迭代終止的條件。但要注意當q 1 時， q 較大，盡管x(k) x(k 1) 很小，卻有可能誤差向量模q1(1) x*x(k) 很大，迭代法收斂很慢。而且此充分性條件的結(jié)果(3) 可以用來事先確定需要迭代多少次才能保證(k)。定理 6.3

23、.10 解方程組Ax b的 G-S迭代法收斂的充分必要條件是(G) 1 ， G為 G-S迭代矩陣。定義 6.3.7 (對角占優(yōu)矩陣)設(shè)A (aij)n nn(2) 若aiiaij0(i 1 n) ，即 A的每一行對角元素絕對值嚴格大于同行其j1 ji他元素絕對值之和。則稱A為嚴格對角占優(yōu)矩陣。n(3) 若aiiaij 0(i 1 n) ，且至少有一個不等式嚴格成立，則稱A為弱對j1 ji角占優(yōu)矩陣。定義 6.3.8 (可約與不可約矩陣)設(shè)A (aij)n n，當 n 2時，如果存在n階排列AA矩陣 p使pTAp1112 成立。其中A11 為r 階子矩陣，A22為n r 階子矩陣0A22( 1

24、r n) ， 則稱矩陣A為可約的。若不存在排列矩陣p 使上式成立，則稱 A為不可約矩陣。當 A為可約矩陣，則 Ax b可經(jīng)過若干行列重排化為兩個低階方程yd組求解。 事實上， 由 Ax b化為：PTAP(PTx) PTb， 設(shè) y PTxy1 ,PTbd1 ，y2d2其中y1,d1為 r 維向量。于是，求解Ax b化為求解：A11y1 A12y2 d1 ，另外 A為可約矩陣的充要A22y2 d2條件：存在指標集J 1,2, ,n ,J 使akj 0， k J， j J.定理 6.3.11 (對角占優(yōu)定理)：若 A (aij )n n為嚴格對角占優(yōu)陣或為不可約弱對角占優(yōu)陣，則A 是非奇異陣。證明

25、 (1) A為嚴格對角占優(yōu)陣，采用反證法。若 detA 0， 則 Ax 0有非零的解，設(shè) 為 x (x1x2xn )T0 。設(shè)xkm axxi1in ixi 0齊 次 方 程 中 的 第 k個 方 程 得 ：nakix0，則可得：ki ji1akk xknakjxjj1jknakjj1jkxjnxkj1 jk(6.3.10)n即有：akkakj 這與嚴格對角占優(yōu)陣矛盾，故det A 0。j1 jk(2) A為不可約弱對角占優(yōu)陣，采用反證法。n設(shè) x 0, x (x1xn)T 使Ax 0。并令 m 使ammamj .(6.3.11) (由弱對角占j1 jm優(yōu)定義)成立。再定義下標集合：J k x

26、kxi , i 1 n, xkxj .對某個j在 (6.3.10) 中取 k m，將導(dǎo)致與(6.3.11) 得矛盾。故J (空集合)。對任意nk J ， 有akjka j xk/ x (由 (6.3.10) ) ， 由此可見，當xkxj 時有 akj 0。j1jk否則，上式就與A為弱對角占優(yōu)陣矛盾。但對任意k J 和 j J ，必有 xk xj ，因而akj0,k J,j J 從而 A為可約矩陣，這與A 為不可約矩陣假設(shè)矛盾。定理 6.3.12 若 A Rn n為嚴格對角占優(yōu)矩陣或為不可約對角占優(yōu)矩陣，則對任意的初始向量x(0) ，方程組Ax b的Jacobi 迭代法和G-S迭代法均收斂。且G

27、-S迭代法比Jacobi 迭代法收斂速度快。證明 設(shè) A為不可約對角占優(yōu)矩陣，先證明G-S迭代法收斂。由弱對角占優(yōu)陣假設(shè)知aii 0,(i 1 n)，而 G-S 迭代矩陣為G (D L) 1U ，又 det(D L) 1 0， det( I G) det( I (D L) 1U) det(D L) 1， det( (D L) U) 0即 det( (d l) U ) 0.，記 C (D L) U 。則：a11a12a13a1nca21a22a23a2nan1an2an3ann下面來證明當1 時， detC 0， 這是因為A為不可約陣，則 C也不可約，由 A為弱對角矩陣，可得：i1n(當1)ci

28、iaiiaijaijcijj1ji1ji且至少有一個不可約等式嚴格成立，這表明當1 時， C 為不可約弱對角占優(yōu)矩陣，于是由前一個定理可知當1 時， detC 0，這一結(jié)論表明detC0的根 滿足：1 ，即 (G) 1 ，故G-S法收斂。在同一條件下，對于Jacobi 方法( J D 1(L U )完全類似于上可證。當A為嚴格對角占優(yōu)陣時，證明方法完全類似。6.3.4 超松弛代法逐次超松弛迭代法(Successive Over Relaxation Method. 簡稱為SOR法)是 Gauss-Seidel 法的一種加速方法。這是解大型矩陣方程組的有效方法之一，具有計算公式簡單、程序設(shè)計容易

29、、占用計算機內(nèi)存較少等優(yōu)點，但需要選擇好的加速因子，即最佳的加速因子。對 Ax b(6.3.12) 其中 A Rn n為奇異矩陣，且設(shè)aii0.(i 1 n)，分解：A D L U(6.3.13)設(shè) 已知第 k 次 迭 代 向 量 x(k) ， 及 第 k 1 次 迭 代 向 量 xi(k1 的)分 量x(jk1() j1 , 2 ,i ，現(xiàn)在來計算分量： 1 )先用 G-S迭代法求出輔助量xi(k 1)(預(yù)測)i1nxi(k 1)(biaijx(jk 1)aijx(jk),i 1 n (6.3.14)aiij 1j i 1再取xi(k 1)為 xi(k)與 xi(k 1)的某種平均值(即加權(quán)

30、平均)，即xi(k 1)(1)xi(k)xi(k1)xi(k)(xi(k1)xi(k)(6.3.15) (校正)將 (6.3.14) 代入 (6.3.15) 即得解 Ax b的逐次超松弛迭代公式：162 / 18(k1)(k)i1 (k1) n (k)xixi(biaij xjaijxj )aiij 1j ix(k)(x1(k),x2(k),xn(k),(k 0.1, , i 1 n)其中稱 為松弛因子，或?qū)憺椋簒i(k 1)xi(k)xii1n(k 1)(k)xi(biaij xjaij xj )aiij 1j i(k 0,1, , i 1,2,n)(6.3.16)(6.3.17)顯然 1

31、時，解 (6.3.12) 的 SOR法即為Gauss-Seidel 迭代法。SOR 法中每迭代一次，主要計算量是計算一次矩陣與向量乘法。由(6.3.16)可見在計算機上用SOR法解方程組只需一組工作單位元，以便存放近似解。迭代計算時，可用p max ximax xi(k 1) xi(k)來控制迭代終止。當 1 時，稱 (6.3.16) 為低松弛法；當1 時，稱 (6.3.16) 為超松弛法。例 6.3.5 用 SOR法解：14111141其精確解為x*( 1, 1, 1, 1)T解 取 x(0)0 ，則SOR迭代公式為：x1(k 1)x1(k)(14x1(k)x2(k)x3(k)x4(k)/4

32、x2(k1)x2(k)(1x1(k1)4x2(k)x3(k)x4(k)/4x3(k1)x3(k)(1x1(k1)x2(k1)4x3(k)x4(k)/4x4(k1)x4(k)(1x1(k1)x2(k1)x3(k1)4x4(k)/4取 1.3 ，第 11 次迭代結(jié)果為：x(11) ( 0.99999646, 1.00000310, 0.99999953, 0.99999912)T(11)x(11)x*0.46 10 5松弛因子滿足誤差x k x* 10 5 的迭代次數(shù)1.0221.117對 取其它值，迭代次數(shù)如下表，由此例可見，松弛因子選擇得好，會使SOR迭代的收斂大大加速。本例中，1.3是最佳松

33、弛因子。表 6.3.1 結(jié)果表1.2121.3*11* 最少迭代次數(shù)1.4141.5171.6231.7331.8531.9109下面考察SOR迭代公式的矩陣形式，由(6.3.16) 可改寫為：i1n(k 1)(k)(k 1)(k)aii xi(1)aii xi(biaij xjaij xj ), i 1 n (6.3.17)j1ji1由 A D L U ，則：Dx( k 1) (b Lx(k 1) Ux(k) (1 )Dx(k)即D L)x(k1) (1)DU )x(k)b，由于對任意，(D L)均為奇異陣(設(shè)aii0.i 1 n, 而 L 為下三角陣，且對角線元素為0)則：x(k 1)(D

34、L) 1 (1)DU x(k) (DL)1b.因此，若aii0,i 1 n ，則SOR迭代公式為：x(k 1)L x(k)f(6.3.18)其中 L (D L) 1 (1 )D U , f (D L) 1b， 稱 L 為SOR方法的迭代矩陣，應(yīng)用關(guān)于迭代法的收斂性定理于(6.3.18) 可得：定理 6.3.13 對 Ax b，且aii 0(i 1 n) 則解方程組的充要條件是：(L ) 1。引進超松弛法的想法是希望能選擇松弛因子使迭代過程(6.3.16) 收斂較快，也就是應(yīng)選擇因子使 ( L *)min ( L *) 。下面考慮對于方程組(6.3.12) ( aii 0,i 1 n) ，超松弛因子在什么范圍內(nèi)取值才可能收斂。定理 6.3.14 (必要條件)對Ax b， ( aii,0 i1 n)的SOR方法若收斂，則：02。證明 由 SOR法收斂及上定理，知( L )1 ，設(shè) L 的特征值為1，2， ， n則：1det(L )1 2 n ( (L )n，即 det(L )n (L ) 1，而det( L ) det( D L) 1)det(1 )D U) (1)n ， 因 此 11 ， 即 ：02。此結(jié)果表明要使SOR法收斂，松弛因子必須在 0,2 中。那么，反過來，若選取 在 0,2 中，SOR法是否一定收斂呢？定理 6.3.15 (